英语读音规则

英语词法

比较级 形容词/副词比较级 常规单音节词 -er fast -> faster small -> smaller nice -> nicer large -> larger(删除词尾不发音的 e) -y -> -ier busy -> busier pretty -> prettier 短元音 + 辅音:重写辅音 -er big -> bigger hot -> hotter 多音节: more + diffcult -> more difficult interesting -> more interesting careful /kɛəful/ -> more careful -y 二音节词(-ly副词除外):常不加 more busy -> busier pretty -> prettier quickly -> more quickly 特殊 much/many -> more little -> less good/well -> better bad -> worse 代词比较级 more less 比较级修饰 a little/ a bit + 比较级 更…一点 much / a lot / far + 比较级 更…得多 英语常见词用法 open/close 静态和动态 open When do you open(v.

流利英语

连读 变音 /d/ + /j/ = /dʒj/ Woul~d y~ou like to try int on? /t/ + /j/ = /tʃj/ What abou~t you~? 词尾辅音 + 词首元音 I~t i~s A glas~s o~f water 还原 r RP he~r i~deas Whe~re is i~t? 语块切割 Chunking 语块(Chunk) 能表达实际含义且语义不割裂的词串。 语块切割(Chunking) 根据说话节奏将句子自然切割为若干语块。 语块语连读 同一语块内能连则连。 吞音 基本原则 同一语块内,音同则吞。 示例 Excuse me, Coul~d you~ tell me how I can get to Pret A Monger?

英语习语

Give me a hand come in 有 come in all/different colors/size come on 「随意」鼓动、鼓励、催促 come to 总计 Excuse me 抱歉/引起注意 by the way/BTW 顺便说一下 shame on sb.! sb. 可耻 make it 成功达成 do/try one’s best (to do sth.) 尽最大努力做某事 sure thing no problem. 礼貌请求 礼貌程度 please > please 疑问句 > 肯定句 could > would > can 示例: Show me (please) Can you show me? Can you show me please?

英语语法结构

双宾语 例句:I want to buy a birthday gift for my sister. 结构:buy sth. for sb. 双宾语:by sb. sth. buy my sister a birthday gift. Can I buy a drink for you? Can I buy you a drink? 双宾语限制 第二个宾语必须为名词,不能是人称代词(pron.)。 下面语句不能使用双宾语 I want to buy you it.(X) 双宾语动词 bring/give/tell/sell/ask/show Bring it to me Bring me a present. Give it to me Give me the pen. tell the story to me tell me the story email the photo to me email me the photo sell the handbag to her sell her the handbag ask sb.

英语常用词

英语短语

shape ʃeip be in great/good shape stay/keep in (good) shape 英语表示次数范围 five times a month once two weeks 英语表示尺码 loose /luːs/ 松的 tight /tait/ 紧的 what/how about 提议 What/How about some coffee? What/How about you? 穿衣:try on/take off/put on n.: try on sth I’d like to try on the shoes. pron.: try sth. on I’d like to try them on. think of 认为 sth.

英语词性

副词 adv/adverb 是指在句子中表示行为或状态特征的词,用以修饰动词、形容词、其他副词或全句,表示时间、地点、程度、方式等概念。 副词可分为:时间副词、频率副词、地点副词、方式副词、程度副词、疑问副词、连接副词、关系副词、表顺序的副词以及表完成的副词。 频率副词 always usually often sometimes about 表示大约大约修饰数量。 形容词 adj 形容词后缀 -ful helpful useful thankful 形容词后缀 -ed interested excited 形容词后缀 -ing interesting exciting -ed adj vs -ing adj. 动词 verb 情态动词 modal verb. can(could)/may(might)/must/need/to/shall(should)/will(would). 动名词 形式 v.-ing 动词的名词化。 语法:名词 语意:动词 形变规则 特殊 1 -e:去 e 加 ing live -> living give -> giving 特殊 2 短元音 + 一辅音:重复最后一个字母加 ing jog -> jogging swim -> swimming 常规:直接加 ing do -> doing study -> studying 词性 I usually go swimming.

英语时态

通过动词变化来区分时间 通过动词变化来区分时间。 I am walking in the rain. 正在 I will walk in the rain. 将要 I walk in the rain sometings. 一般状态、重复、常态 一般现在时 表示: 当前的一般状态 重复或习惯动作 am/is/are(be 动词):是,处于某状态 do/does(实意动词):具体动作 (X): am/is/are + do/des 一般现在时不能 am/is/are 跟动词实意动词 一般现在时第三人称单音形规则 一般现在时第三人称单数动词需要变形,需要注意变形后的读音 清对清 /s/ works helps 非清则浊 /z/ lives sees goes does /dʌz/ 组合 /dz/ /ts/ meets needs 近似音 -es /iz/ introduces fishes 现在进行时 当前正在发生的事情或动作,表示当前正在发生或者近将来。

Linux kernel

Linux I/O Linux I/O 演进 阻塞式:read()/write() 非阻塞式:select()/poll()/epoll(),不支持文件 I/O Thread Pool Direct I/O(数据软件):绕过 page cache 异步 IO(Linux AIO):早起进支持文件 I/O,近期支持了 epoll 支持非文件 I/O Linux io_uring [译] Linux 异步 I/O 框架 io_uring:基本原理、程序示例与性能压测 对比 Linux AIO: 重新设计实现真正的是不。 支持任何类型的 I/O:cached files、direct-access files 甚至 blocking sockets。 灵活、可扩展:基于 io_uring 能够重写 Linux 的每个系统调用。 原理及核心数据结构:SQ/CQ/SQE/CQE 每个 io_uring 实例都有两个环形队列,在内核和应用程序之间共享: 提交队列:submission queue(SQ) 完成队列:completion queue(CQ) 这两个队列: 都是单生产者、单消费者,size 是 2 的幂次; 提供无锁接口(lock-less access interface),内部使用内存屏障做同步(coordinated with memory barrers)。 使用方式:

Scala lsp-metals

领域模式

Airflow

案例 Airflow powers AI。 Airflow SSO 接入 公司 SSO 系统不是基于开源标准,而是一套自定义的方式,目前网上没有成熟的解决方案,通过查看 Flask-AppBuilder 和 Airflow 的代码发现可以扩展 flask_appbuilder.security.views.AuthRemoteUserView 并通过自定义的 SecurityManager 指定 authremoteuserview 来实现,去掉具体 SSO 逻辑后的代码如下: from urllib.parse import urlencode from urllib.parse import urljoin import requests from flask import flash from flask import redirect from flask import request from flask_appbuilder.baseviews import expose from flask_appbuilder.security.views import AuthRemoteUserView try: from airflow.www.security import AirflowSecurityManager except ImportError: AirflowSecurityManager = None __version__ = "0.1.0" AUTHORIZE_URL = "https://example.com/sso/login" ACCESS_TOKEN_URL = "https://example.

Java

Spark

Spark 编程语言选择 毋庸置疑,Python 应该是最简单也是大部分的选择,但是如果有依赖那么将要付出额外的心智负担(Spark 管理 Python 依赖)。 JVM 语言的依赖组织方式则具有天然的优势,可以将依赖(排除 Spark 生态之后)都 bundle 进 Jar 包里。 其中 Scala 兼具简单和 JVM 的优势,但是它「不流行」。 Spark Driver & Executor Driver 执行 spark-commit 客户端,创建 SparkContext 执行 main 函数。 Executor Spark Worker 上的线程 See also: Understanding the working of Spark Driver and Executor Cluster Mode Overview Spark 代码执行 我在配置 Spark 的时候就在好奇,从观察上看部分代码应该是执行在 Driver 上部分代码会执行在 Executer,这让我很好奇。 但是我通过学习 Spark RDD 学习到了一些知识。 以下代码是在 Executor 上执行的: Transformations 和 Actions 是执行在 Spark 集群的。 传递给 Transformations 和 Actions 的闭包函数也是执行在 Spark 集群上的。 其他额外的代码都是执行在 Driver 上的,所以想要在 Driver 打印日志需要上使用 collect:

Scala

Scala 学习资源 Scala Book Scala 这么好的语言为什么不流行 HN:Scala 为什么不流行 Reddit:Scala 为什么不流行 结论:Java 人才更多且成本更低。 Scala 工具 sbt sbt new 无法处理替换过的 SSH 会导致 Auth fail,一个 workaround 就是手动 clone 项目然后: sbt new file:///path/to/template.g8 sbt 国内加速 ~/.sbt/repositories: [repositories] local nexus-aliyun:https://maven.aliyun.com/nexus/content/groups/public nexus-aliyun-ivy:https://maven.aliyun.com/nexus/content/groups/public/, [organization]/[module]/(scala_[scalaVersion]/)(sbt_[sbtVersion]/)[revision]/[type]s/[artifact](-[classifier]).[ext] typesafe: https://repo.typesafe.com/typesafe/ivy-releases/, [organization]/[module]/(scala_[scalaVersion]/)(sbt_[sbtVersion]/)[revision]/[type]s/[artifact](-[classifier]).[ext], bootOnly Unique Scala Rust from Scala Rust 和 Scala 有很多想通的地方,Rust 应该从 Scala 借鉴了很多: 可变量和不可变量 模式匹配 Trait 内置类型 val b: Byte = 1 val x: Int = 1 val l: Long = 1 val s: Short = 1 val d: Double = 2.

SVG 绘制工具

设计

Graphviz

《禅与摩托车维修艺术》

LeetCode: 98. Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree/ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isValidBST(TreeNode* root) { if (root == nullptr || (root->left == nullptr && root->right == nullptr)) { return true; } if (root->left !

LeetCode: 113. Path Sum II

https://leetcode.com/problems/path-sum-ii/ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int targetSum) { vector<vector<int>> r; if (root == nullptr) { return r; } if (root->left !

LeetCode: 112. Path Sum

https://leetcode.com/problems/path-sum/ 递归版 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (root == nullptr) { return false; } return pathSum(root, 0, targetSum); } bool pathSum(TreeNode* node, int sum, int targetSum) { sum += node->val; if (node->left == nullptr && node->right == nullptr) { if (sum == targetSum) { return true; } } if (node->left !

LeetCode: 79. Word Search

79. Word Search class Solution { public: bool exist(vector<vector<char>>& board, string word) { backtracking(board, word, 0, 0); return res; } private: string track; bool res = false; enum Direction { right, down, up, left, }; /** * @param dir: 0: right, 1: down, 2: up, 3: left */ void backtracking(vector<vector<char>>& board, string word, int row, int col) { if (track == word || res) { res = true; return; } for (int i = row; i < board.

Event Store

领域驱动设计

High Performance Browser Networking

预写日志

RabbitMQ

Twitter DistributedLog

Amazon Kinesis Streams

Apache Kafka

消息队列

Networking 101: Building Blocks of TCP

TCP

背压

流处理系统

发送事件流 消息系统 生产者速度比消费者快:丢弃消息、将消息缓存在队列、激活背压。 节点崩溃或者暂时历险,是否会有消息丢失? 生产者与消息系统之间的直接消息传递 UDP 组播:广泛应用于金融股票 无代理消息库:ZerroMQ 和 nanomsg StatsD 和 Brubeck 使用 UDP 传递消息 HTTP、RPC 接口 消息代理 参见:AMQP/JMS 风格的消息代理。 也称消息队列。 消息对比与数据库对比 多个消费者 确认和重传机制 分区日志 参见: 基于日志的消息代理。 数据库与流 保持系统同步 变更数据捕获 变更数据捕获(Change Data Capture,CDC)记录了写入数据库的所有更改,并以可复制到其他系统的形式来提取数据。 如果在写入时立即将更改作为一种流来发布,那么 CDC 就更有趣来。 实现变更数据捕获 解析复制日志,并将解析的内容发送到事件流中进行 replay。 初始快照 replay 日志占用空间过大,需要进行截断,截断之前的进行初始快照保存。 日志压缩 参考哈希索引。 对变更流的 API 支持 数据库开始支持将变更流作为标准接口。 事件溯源 一种在领域驱动设计社区中开发的技术,与 CDC 最大的区别在于事件溯源在不同抽象层次上应用了将所有对应用程序状态的更改保存为更改事件日志: CDC 中:应用程序以数据可变方式来操纵数据库,从数据库中提取较低级的变更日志,从而确保从数据库提取写入顺序与实际写入顺序相匹配。写入数据库的程序不需要知道 CDC 正在发生。 事件溯源中:应用程序的写入逻辑是基于写入事件日志的不可变事件构建的。事件存储仅支持追加,不鼓励甚至禁止更新或删除操作。事件旨在反映在应用程序级别所发生的事情,而不是低级别的状态改变。 专门的数据库 Event Store 来支持使用事件溯源的应用程序。

Why MapReduce is making a comeback

When Zero Cost Abstractions Aren’t Zero Cost

弹性分布式数据集

HBase

大规模并行处理

Clock Synchronization with Chris Perl

Hive

Hadoop

Hadoop Distributed File System MapReduce MapReduce shuffle 按照 reducer 分区,排序和将数据分区从 mapper 复制到 reducer。(令人困惑的术语,并不完全与洗牌一样,在 MapReduce 中其实没有随机性)。 MapReduce 的分布式执行 Hadoop MapReduce 并行化基于数据分区实现: 输入:通常是 HDFS 中的一个目录。 分区:每个文件或文件块都被视为一个单独的分区。 处理:每个分区由单独的 map 任务来处理。 每个 mapper 都会尽量实现计算靠近数据。 代码复制:JAR 文件。 Reduce 任务的计算也被分隔成块,可以不必与 mapper 任务数量相同,MapReduce 框架使用关键字的哈希值来确保具有相同关键字的键值对都在相同的 reduce 任务中处理。 键值对必须进行排序,排序是分阶段进行的: 每个 map 任务都基于关键字哈希值,按照 reducer 对输出进行分块。 每个分区都被写入 mapper 程序所在的本地磁盘上的已排序文件,参见 SSTables 和 LSM-Tree。 reducer 与每个 mapper 相连接:MapReduce 调度器会在 mapper 写入经过排序的输出文件后,通知 reducer 开始从 mapper 中获取输出文件,框架进行 MapReduce shuffle。 reducer 任务从 mapper 中获取文件并将它们合并在一起,同时保持数据的排序。不同 mapper 使用相同的关键字生成记录,会在合并后的 reducer 输入中位于相邻的位置。 reducer 可以使用任意逻辑来处理这些记录,并且生成任意数量的输出记录。记录被写入分布式文件系统中的文件。 MapReduce 工作流调度器 Oozie Azkaban Luigi Airflow Pinball 对比分布式数据库 MapReduce 中的并行处理和并行 join 算法已经在十多年前所谓的大规模并行处理(MPP)数据库中实现了。

Tokio

分布式文件系统

网络连接存储

Hadoop Distributed File System

Emacs Easter egg

数据库

批处理系统

MapReduce MapReduce 与分布式文件系统 MapReduce 就像分布在上千台机器上的 Unix 工具。 MapReduce 作业通常不会修改输入,除了输出外没有任何副作用。 MapReduce 作业在分布式文件系统上读写。(Unix 工具 stdin、stdout),如 HDFS(Hadoop Distributed File System)等(GlusterFS、QFS、Amazon S3、Azure Blob 和 OpenStack Swift)。 MapReduce 作业执行 MapReduce 是一个编程框架,可以使用它编写代码处理 HDFS 等分布式文件系统中的大型数据集。 要创建 MapReduce 作业需要实现两个回调函数: mapper 和 reducer (另请参阅 MapReduce 查询): Mapper: 每个输入记录都会调用一次,从输入记录提取任意数量的关键字和值(可以为空),不保留任何状态,可以独立处理。 Reducer: MapReduce 框架使用 Mapper 生成的键值对,收集同一个关键字的所有值,并使用迭代器调用 reducer 以使用该值的集合。 Reducer 可以生成输出记录。 MapReduce 分布式执行 参见 Hadoop 的 MapReduce 的分布式执行。 MapReduce 工作流 将 MapReduce 作业链接到工作流是非常普遍的,作业的输出作为下一个作业的输入。通过目录名隐式的完成: 第一个作业必须配置将其输出写入 HDFS 中指定目录; 第二个作业必须配置读取相同的目录名作为输入。 目前已经开发了处理依赖管理的 MapReduce 工作流调度器。

LeetCode: 37. Sudoku Solver

LeetCode: 36. Valid Sudoku

https://leetcode.com/problems/valid-sudoku/ <- high -- low -> +------------------- wow(row(i):0,col(j):0) 0 -> [ 0010, 0010 ] | 1 -> [ 0000, 0000 ] | 2 -> [ 0000, 0000 ] | | +--------------- wow(row(i):0,col(j):1) 0 -> [ 0010 | 1 = 0011, 0010 ] | | 1 -> [ 0000, 0000 | 1 = 0001 ] | | 2 -> [ 0000, 0000 ] | | | | +----------- wow(row(i):0,col(j):2) 0 -> [ 0011 | 3 = 0100, 0010 ] | | | 1 -> [ 0000, 0001 ] | | | 2 -> [ 0000, 0000 | 3 = 0100 ] +---+---+---+ | 2 | 1 | 3 | +---+---+---+ ----| 3 | 2 | 1 | | +---+---+---+ | | 1 | 3 | 2 | | +---+---+---+ |- wow(row(i):1,col(j):0) 0 -> [0010 | 3 = 0110, 0010] +---------------------+ 1 -> [0000, 0001 | 3 = 0101] 2 -> [0000, 0100] class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { vector<int> wow(9,0); int mux1; int mux2; int mux3; int box_index; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(board[i][j] == '.

分布式共识

区块链

LeetCode: 40. Combination Sum II

https://leetcode.com/problems/combination-sum-ii/ LeetCode: 39. Combination Sum 的进阶。元素不在唯一且每一个元素只能出现一次。对结果进行排序然后通过 set 对结果进行去重: class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); backtracking(candidates, 0, 0, target); vector<vector<int>> r; for (auto t : res) { r.push_back(t); } return r; } private: set<vector<int>> res; vector<int> track; map<int, bool> visited; void backtracking(vector<int>& condidates, int start, int n, int target) { if (n == target) { res.insert(track); return; } if (n > target) { return; } int c = 0; int sz = condidates.

LeetCode: 39. Combination Sum

https://leetcode.com/problems/combination-sum/ class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { backtracking(candidates, 0, target); return res; } private: vector<vector<int>> res; vector<int> track; void backtracking(vector<int> & candidates, int n, int target) { if (n == target) { res.push_back(track); return; } // this is new if (n > target) { return; } for (auto c : candidates) { track.push_back(c); backtracking(candidates, n + c, target); track.pop_back(); } } }; 问题:会有不同顺序但是元素相同的数组,如何快速高效的进行过滤? - [[2,2,3],[2,3,2],[3,2,2],[7]] + [[2,2,3],[7]] 一个比较 tricky 的技巧,就是判断最终结果是不是升序的,不是就放弃,居然可以通过:

LeetCode: 52. N-Queens II

回溯算法

工业云

云原生

云计算

技术概念

概念

边缘计算

LeetCode: 51. N-Queens

https://leetcode.com/problems/n-queens/ 一旦一个 Queue 被放置,那么横轴、纵轴、对角线。我们按行进行便利,所以我们需要跟踪以下位置是否已经放置 Queue: 纵轴(Column):cols 主对角线(Positive Diagonal):posDiag 次对角线(Negative Diagonal):negDiag 纵轴很好记录,但是对角线比较困难,我们先来看一下对角线的特征,假设横轴为 r 纵轴为 c , r - c 在正对角线是一致的: 斜对角线 r + c 是一致的: class Solution { public: vector<vector<string>> solveNQueens(int n) { for (int r = 0; r < n; r++) { string col = string(n, '.'); track.push_back(col); } backtracking(0, n); return res; } private: set<int> cols; // c set<int> posDiag; // r - c set<int> negDiag; // r + c vector<vector<string>> res; vector<string> track; void backtracking(int r, int n) { if (r == n) { res.

Multi-Paxios

Zab

Paxos

Raft

VSR

To Complete

链式复制

比较-设置

全序

macOS 签名 GDB

偏序

CAP 理论

一致性与共识

一致性保证 分布式一致性主要针对延迟和故障等问题来协调副本之间的状态。 线性化:最强一致性模型 顺序保证:保证时间顺序,特别是因果关系和全局顺序 最终一致性:一种非常弱的保证,参见最终一致性效应 可线性化 分布式语义下对寄存器(单个对象)顺序的读写。应区别与可串行化。 可串行化针对不同事务的隔离,用来确保事务执行的结果与串形执行的结果相同 可线性化是读写寄存器(单个对象)的最新值的保证。 线性化依赖的条件 加锁与主节点选举 每个启动节点都试图获得锁,其中只有一个可以成功成为主节点。通过加锁来保证主节点选举「线性化」。 约束与唯一性保证 同一个用户名、电子邮件或系统中文件名需要唯一性的保证,也应该进行「线性化」。 跨通道的时间依赖 系统中存在其他通信渠道也需要「线性化」。 实现线性化系统 主从复制(部分支持可线性化) 共识算法(可线性化) 多主复制(不可线性化) 无主复制(可能不可线性化) 线性化与Quorum 一致性 Dynamo 风格的复制模型,读写遵从严格的 quorum 是无法支持可线性化的。 线性化的代价 多主复制和主从复制,网络中断都会导致同步暂停,从而无法保证客户端要求的线性化读写。 CAP 理论 可线性化与网络延迟 很少有系统真正满足线性化,现代多个 CPU 对同一个内存地址的读写都不能满足(参见硬件内存模型),如果需要强一致则需要内存屏障(栅栏)指令。 之所以放弃线性化的原因就是性能,而不是为了容错。由于网络延迟的不确定性,无论是否发生网络故障,线性化对性能的影响都是巨大的。 顺序保证 顺序与因果关系 顺序有助于保持因果关系。 因果顺序并非全序:因果关系是小范围集合的偏序,可线性化是一个全序操作。 可线性化强于因果一致性 捕获因果依赖关系:检测并发写 序列号排序 非因果序列发生器 适用于系统不存在唯一主节点。 每个节点都独立产生自己的一组序列号:一个奇数一个偶数,或者切入节点唯一标识符。 用足够高的分辨率的墙上时间戳附加到每个操作上。 预先分配区间范围,并及时扩容。 Lamport 时间戳 可以产生因果关系一致的序列号。Lamport 时间戳是一个值对 (计数器,节点 ID) : 节点 ID:每个节点都有一个唯一标志符。 计数器:每个节点都有一个计数器记录各自处理的请求总数。 优点:

拜占庭故障

Fencing 令牌

单调时钟与墙上时钟

LeetCode: 47. Permutations II

视频解析:https://www.youtube.com/watch?v=s7AvT7cGdSo 在 LeetCode: 46. Permutations 的基础上增加重复的元素。感觉不能依赖于 track + map 的去重逻辑回溯。 class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> res; } }; 数据特征: Value: 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, Index: 2, 1, 0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 1, 0, class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { set<vector<int>> res; vector<vector<int>> ret; int n, i; vector<vector<int>> perms; if (nums.

分布式系统挑战

故障与部分失效 单节点一般是要么工作要么失效,但是分布式系统多节点面临部分失效,大大提高了分布式系统的复杂性。 单节点软件特性: 硬件正常工作时,相同的操作通常总会产生相同的结果,即确定性。 如果发生了某种内部错误,我们宁愿使计算机全部崩溃,而不是返回一个错误的结果。 云计算和超算 超算:垂直扩展的极端,设置检查点,一点节点故障则全部失效从上一个检查点重新开始(离线批处理),类似单机上内核崩溃。 云计算:水平扩展的极端 传统企业位于两个极端的中间 分布式可靠必然面临部分失效,需要依赖软件系统来提供容错机制。我们需要在不可靠的组件上构建可靠的系统。 不可靠网络 分布式无共享系统:成本低廉。 互联网以及大多数 IDC 内部网络都是异步网络:不保证发送一定到达(排队),等待响应时可能出现任何错误。 现实中的网络故障非常普遍 故障检测:HA、主从切换、保活机制(ICMP,SYN) 超时与无限期的延迟 网络拥塞与排队 网络负载过高会出现拥塞。 数据在发送的过程中分别会在发送端和接收端进行排队:等待发送和等待处理。 TCP 的拥塞控制机制。 虚拟化 CPU 核切换虚拟机 同步与异步网络 同步网络:固定电话网络,一路电话分配固定的电路、有带宽保证,规定延迟内保证完成数据包发送,不会丢弃数据包,成本高,利用率低 异步网络:数据中心网络,共享带宽,无法保证延迟和数据包发送,成本低廉,利用率高 不可靠时钟 单调时钟与墙上时钟 时间同步与准确性 计算机中的石英钟不够精确 NTP 服务器不稳定(网络、防火墙或服务本身) 虚拟机中时钟是虚拟化的。 终端设备不可控:休眠、故意设置 依赖同步的时钟 时钟陷阱: 一天可能不总是 86400 秒 回拨 多个节点上的时间完全不相同 需要精确同步的时钟: 自己监控所有节点上的时钟偏差 某个节点时钟漂移超出上限则将其宣告失效 时间戳与时间顺序 最后写入者获胜 时钟的置信区间 通过直接安装 GPS 接收器或原子(铯)时钟,它的误差范围通常可以查询制造商手册。

LeetCode: 46. Permutations

Keywords backtrack 回溯算法 图解 举例: [1, 2, 3] ,顺着叶子节点和删除的节点就可以还原成全排列。 从上面图可以看出来,叶子节点加上回溯路径上被移除的节点就是结果的一项,从左到右依次是: [3,R:2,R:1] -> [3,2,1] [2,R:3,R:1] -> [2,3,1] … class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; vector<int> track; backtrack(res, track, nums); return res; } void backtrack(vector<vector<int>> & res, vector<int> & track, vector<int>& nums) { if (track.size() == nums.size()) { res.push_back(track); return; } for (int i = 0; i < nums.size(); i++) { if (visited.find(nums[i]) != visited.end() && visited[nums[i]]) { continue; } track.

JavaScript 内存模型 (2017)

C、Rust 和 Swift 的内存模型

C++ 弱同步原子(acquire/release atomic)

C++ 还添加了较弱的原子,可以使用 atomic_store_explicit 和 atomic_load_explicit 以及附加的n内存排序参数来访问这些原子。使用 memory_order_seq_cst 使显式调用等效于C++ 同步原子(atomic)较短的调用。 较弱的原子称为 acquire/release 原子,一个 release 如果被后来的 acquire 观察到,那么就创建了一个 happen-before 的关系(从 release 到 acquire)。这个术语意在唤起 mutex:release 就像 unlock mutex , acquire 就像锁定同一个 mutex 。=release= 之前执行的写入必须对后续 acquire 之后执行的读取可见,就像解锁 mutex 之前执行的写入必须对后解锁 mutex 之后执行的读取可见一样。 atomic<int> done; // Thread 1 // Thread 2 atomic_store(&done, 1, memory_order_release); while(atomic_load(&done, memory_order_acquire) == 0) { /* loop */ } acquire/release 原子只对单个内存位置的操作进行顺序一致的交替执行,所以属于内存一致性(coherence)而非顺序一致性。 来看下面 litmus test: Litmus Test: Store Buffering Can this program see r1 = 0, r2 = 0?

C++ 非同步原子(Relaxed atomic)

C++ 同步原子(atomic)

DRF-SC 还是着火(Catch Fire)

C++11 内存模型

Java 同步原子(volatile)

线程的创建前置于(happens bofere)线程的第一个动作。 互斥体 m 的解锁前置于(happens before)任何 后续(subsequent) 对互斥体 m 的锁定。 volatile 变量 v 的写入前置于(happens bofere)任何 后续(subsequent) 对变量 v 的读取。 “后续(subsequent)” 意味着什么?Java 定义了所有锁定、解锁和 volatile 变量访问的行为,给出了整个程序中所有这些操作的总顺序,就像它们发生在某个顺序一致的交错中一样。“后续(subsequent)”指在总顺序中较晚执行。也就是说:锁定、解锁和 volatile 变量的访问的“总顺序”定义了“后续”的含义,“后续”定义了由特定执行创建的“前置于(happens before)”关系,最终“前置于(happens before)”关系定义了该特定执行是否存在数据竞争。如果没有数据竞争,那么执行就会以顺序一致的方式进行。 事实上, volatile 访问必须表现得像在某种总排序一样,意味这在下面 litmus test 中,不能出现 r1=0 和 r2=0 的结果: Litmus Test: Store Buffering Can this program see r1 = 0, r2 = 0? // Thread 1 // Thread 2 x = 1 y = 1 r1 = y r2 = x On sequentially consistent hardware: no.

Java 决定竞争读写的具体规则

内存顺序一致性(sequential consistency)

内存一致性(coherence)

Memory coherence vs consistency

Coherence deals with maintaining a global order in which writes to a single location or single variable are seen by all processors. Consistency deals with the ordering of operations to multiple locations with respect to all processors. Memory coherence: a memory system is coherent if any read of a data item returns the most recently written value of that data item (what values can be returned by a read).

悲观与乐观并发控制

可串形化的快照隔离

两阶段加锁

串行化

写倾斜

写倾斜与幻读

防止更新丢失

更新 Go 内存模型

LeetCode: 25. Reverse Nodes in k-Group

https://leetcode.com/problems/reverse-nodes-in-k-group/ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { deque<ListNode*> dq; ListNode* cur = head; ListNode* top = nullptr; ListNode* tail = nullptr; bool first_k = true; while (cur !

事务隔离级别

ACID

事务

LeetCode: 92. Reverse Linked List II

https://leetcode.com/problems/reverse-linked-list-ii/ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { stack<int> st; ListNode* cur = head; ListNode* prev_start = nullptr; if (left == 1) { prev_start = new ListNode(0, head); // dummy prev_start point to head } int i = 1; while(cur !

Emacs Projectile 优化

Java 内存模型

新的 Java 内存模型(2004)

Java 编译器公共子表达式消除(common subexpression elimination)

原始 Java 内存模型(1996)

DRF-SC 系统同步指令

同步原子(synchronizing atomic)

原子变量(atomic variable)或原子操作(tomic operation)

现代语言以原子变量(atomic variable)或原子操作(atomic operation)的形式提供特殊能力,允许程序同步其线程(参见硬件内存一致性模型)。 代码示例 // Thread 1 // Thread 2 x = 1; while(done == 0) { /* loop */ } done = 1; print(x); 如果使用原子变量实现 done 会产生很多效果: Thread 1 的编译代码必须确保对 x 的写入完成,并且对 done 的写入可见之前对 x 的写入对其他线程可见。 Thread 2 的编译代码必须在循环的每次迭代中(重新)读取 done 。 Thread 2 的编译代码必须在读取 done 之后才读取 x 。 编译后的代码必须做任何必要的事情来禁用可能会重新引入这些问题的硬件优化。 使 done 原子化的最终结果是程序按照我们想要的方式运行,成功地将 x 的值从 Thread 1 传递到 Thread 2 。 上面代码如果不使用原子变量会出现 Thread 1 和 Thread 2 读取 x 的同时写 x ,从而导致数据竞争(data race)。 done 使用原子变量实现后,用于同步对 x 的访问: Thread 1 现在不可能在 Thread 2 读取 x 的同时写 =x=,从而避免数据竞争。 这是硬件内存模型弱有序和无数据竞争(DRF)在编程语言环境的应用。

弱有序和无数据竞争(DRF)

ARM/POWER Relaxed Memory Model

ARM和POWER系统的概念模型是,每个处理器从其自己的完整内存副本中读取和向其写入,每个写入独立地传播到其他处理器,随着写入的传播,允许重新排序。 在这个宽松的(relaxed)模型中,我们迄今为止所看到的每一个litmus test的答案都是“yes,这真的可能发生。” Litmus Test: Message Passing Can this program see r1 = 1, r2 = 0? // Thread 1 // Thread 2 x = 1 r1 = y y = 1 r2 = x On sequentially consistent hardware: no. On x86 (or other TSO): no. On ARM/POWER: yes! Litmus Test: Store Buffering Can this program see r1 = 0, r2 = 0? // Thread 1 // Thread 2 x = 1 y = 1 r1 = y r2 = x On sequentially consistent hardware: no.

内存屏障

x86 总存储有序(x86-TSO)

x86 总存储有序(x86 Total Store Order, x86-TSO):所有处理器仍然连接到一个共享内存,但是每个处理器都将对该内存的写入(write)放入到本地写入队列中。处理器继续执行新指令,同时写操作(write)会更新到这个共享内存。一个处理器上的内存读取在查询主内存之前会查询本地写队列,但它看不到其他处理器上的写队列。其效果就是当前处理器比其他处理器会先看到自己的写操作。 重要的是: 所有处理器都保证写入(存储 store)到共享内存的(总)顺序,所以给这个模型起了个名字:总存储有序(Total Store Order,TSO)。 写队列是一个标准的先进先出队列:内存写操作总是以与处理器执行相同顺序的应用于共享内存。 基于以上下面 litmus test 的答案依然是 no ,这种情况与顺序一致性模型结果一致: Litmus Test: Message Passing Can this program see r1 = 1, r2 = 0? // Thread 1 // Thread 2 x = 1 r1 = y y = 1 r2 = x On sequentially consistent hardware: no. On x86 (or other TSO): no. 但其他测试则并不一致区分与顺序一致性的常用例子: Litmus Test: Write Queue (also called Store Buffer) Can this program see r1 = 0, r2 = 0?

litmus test

顺序一致性

Leslie Lamport 1979 年的论文 How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs 定义: The customary approach to designing and proving the correctness of multiprocess algorithms for such a computer assumes that the following condition is satisfied: the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

内存一致性模型

编程语言内存模型

硬件内存模型

Emacs 优化启动速度

动态再平衡策略

基于词条的二级索引分区

基于文档分区的二级索引

基于关键字哈希值分区

基于关键字区间分区

系统热点

负载倾斜

数据分区

syn

quote

Rust 属性宏解析

准备 解析宏通过两个 crate 进行: quote = “1.0” syn = “1.0” Derive 属性宏 探讨 Rust 宏系统中带属性(Attributes)的 Derive 宏的几种变体,以及如何进行解析。 属性宏的变体 函数调用 #[derive(Custom)] struct Demo { #[attr(arg)] a: i8, } 关键字参数调用 #[derive(Custom)] struct Demo { #[args(name = "val")] b: i8, } 直接赋值 #[derive(Custom)] struct Demo { #[meta = "val"] c: i8, } 函数调用 关键字参数调用 可以从 Struct 解析出各个字段,通过解析各个字段的 attrs 属性,并对 attrs 进行遍历,使用 attr.parse_args()? 即可解析出对应的关键字参数,咱们以前面的代码为例:

Happens-before 关系和并发

检测并发写

sloppy quorum

Quorum 一致性

无主节点复制

全部-至-全部型拓扑

星型拓扑

环形拓扑

最后写入者获胜

收敛于一致的状态

避免冲突

前缀一致读

单调读一致性

强一致性

读写一致性

最终一致性效应

复制滞后问题

复制日志实现

主从复制

数据复制

认同的话

当一个不可能出错的事物出错了,通常也就意味着不可修复 – Douglas Adams,《基本无害》(1992) 关于写文档 There is a secret that needs to be understood in order to write good software documentation: there isn’t one thing called documentation, there are four. They are: tutorials, how-to guides, technical reference and explanation. They represent four different purposes or functions, and require four different approaches to their creation. Understanding the implications of this will help improve most documentation - often immensely.

Actor

Avro

Thrift 与 Protocol Buffers

数据编码与演化

OLAP

OLTP

B-trees

哈希索引

排序字符串表:SSTables

LSM-Tree

数据存储与检索

存储引擎 哈希索引 日志结构存储引擎:LSM-Tree 面向页的存储引擎:B-trees 对比 LSM-Tree 和 B-trees 项目 LSM-Tree B-trees 备注 性能 写入更快,吞吐更高 读取更快 具体场景上需要进行基准测试 存储 可变大小的段,通常 nMB 固定大小的页,传统 4KB 写入 追加,写入更多不利于 SSD 新的数据覆盖磁盘上旧的页 并发控制 后台合并进行原子替换 锁存器 其他索引结构 在索引中存储值 多列索引 全文索引和模糊索引 在内存中保存所有内容 优点:可以支持更复杂的数据结构,而无需考虑数据存储结构。 事务处理与分析处理 事务处理:OLTP 分析处理:OLAP 对比 属性 OLTP OLAP 主要读属性 基于键,每次查询返回少量记录 对于大量记录进行汇总 主要写属性 随机访问,低延迟写入用户的输入 批量导入(ETL)或事件流 典型使用场景 终端用户,通过网络应用程序 内部分析师,为决策提供支持 数据表征 最新的数据状态(当前时间点) 随着事件而变化的所有事件历史 数据规模 GB 到 TB TB 到 PB 数据仓库 星型与雪花型分析模式 星型模型也称为维度建模。

数据模型与查询语言

可靠、可扩展与可维护的应用系统

《数据密集型应用系统设计》读书笔记

项目代号

macOS 问题解决三板斧

macOS TimeMachine 日志

English IPA

一些通用的规则: 音标后面的 ː 提示拖长音。 元音 大而圆 音标 中文 发音技巧 常见单词 拼读规则 /​æ​/ 爱 张大嘴发中文的「爱」,发音短促有力。 bag map dad sad a /​e​/ 爱 音同 /​æ​/ 但是嘴形要小一些。 get let pen yes e /​ɔː​/ 哦 嘴巴轮圆了发音,并拖长音 floor door store sport oor,ore,or /​ɔ​/ 哦 /​ɔː​/ 的短音 lot dog hot shop o 扁扁扁 音标 中文 发音技巧 常见单词 拼读规则 /iː​/ 一 相比一嘴要扁一些,稍稍更用力一些 see meet he she ee, e /​i​/ 一 /iː​/ 短音 happy daddy honey 词尾的 y 或 ey /​I​/ 一 用 /​e​/ 的嘴形发 /​i​/ this give it city i /əː​/ 呃 相比中文嘴要扁一些,稍稍更用力一些 work girl dirt sir or, ir /​ə​/ 呃 /əː​/ 的短音 again a father weather 单独的 a 及词尾的 er 需要额外注意的:

Learning English

二叉树的遍历

分为三种:前序、后序和中序,其中最容易用栈改写的是后序。 前序(Preorder):Root -> Left -> Right class Solution { public: void processPreorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processPreorderTraversal(root->left, collector); collector.push_back(root->val); processPreorderTraversal(root->right, collector); } vector<int> inorderTraversal(TreeNode* root) { vector<int> ret; if (root == nullptr) { return ret; } processPreorderTraversal(root, ret); return ret; } }; 中序(Inorder): Left -> Root -> Right class Solution { public: void processInorderTraversal(TreeNode* root, vector<int> & collector) { if (root == nullptr) { return; } processInorderTraversal(root->left, collector); collector.

OX-HUGO 批量导出 Markdown

中间件

技术随想

C/C++ thread-local storage

macOS max open files

GDB 打出所有线程的 Backtrace

GDB

C++ LSP

Python behind the scenes #2: how the CPython compiler works

Python 幕后 #2: CPython 编译器如何工作 今天的主题(Today’s subject) 在本系列的第一篇文章中我们研究了 Python 虚拟机。我们学了解到它通过执行一系列叫做字节码(bytecode)的指令。 我们也看到 Python 字节码没有完全描述代码片段的行为。这也是为什么存在一个代码对象(code object)的概念。 执行诸如函数或模块的代码块也就是执行对应的代码对象。代码对象包含了代码块的字节码,包含代码中使用的常量和变量名, 还有代码块的一些属性。 通常,一个 Python 程序员不用编写字节码,并且也不用创建代码对象,而是编写正常的 Python 代码。所有 CPython 必须 能够将源代码转换成代码对象。CPython 编译器就负责这部分工作。我们将通过这部分内容探索它是如何工作的。 Note: 本文参考 CPython 3.9。一些实现细节将必然会随着 CPython 的演进而改变。 我将会尝试关注一些重要的改变并添加更新备注。 什么是 CPython 编译器(What CPython compiler is) 我们已经了解了 CPython 编译器的职责,但是在我们进入到它是如何实现的之前,让我们首先来搞清楚为什么我们称之为编译器? 在通常情况加,编译器是一个将一个程序语言翻译到另一个与之等价的程序语言的程序。编译器有许多种类,但是通常情况下我们 讨论的都是静态编译:将一个高级语言的程序翻译成机器码。CPython 编译器也是这样吗?要回答这个问题,我们先看一下静态编 译器的传统三阶段设计(three-stage design)。 编译器前端(frontend)将源代码转换成一种中间语言(IR,intermediate representation)。然后优化器(optimzer)拿到中间语言 对其进行优化并把优化过的中间语言传递给编译器后端生成机器码。如果我们选择一种源语言和目标机器无关的中间语言,我们就 得到了三阶段设计的关键益处:对于一个编译器来说,支持一种新的源语言仅仅需要新增一个对应的编译器前端,支持一种新的目标机器 仅仅需要新增一个对应的编译器后端。 LLVM 工具集(toolchain)就是这个模型的一个很好的成功的例子。有很多编译器前端如 C、Rust、Swift 等其他很多编程语言基于 LLVM 提供给编译器更加复杂的部分。LLVM 的创建者 Chris Latter 提供了一个很好的 LLVM 架构概览。 CPython 尽管不需要支持多个源语言和目标机器,尔仅仅需要支持 Python 代码和 CPython 虚拟机。不过,CPython 同样实现了三阶段设计。 如果想知道为什么,我们需要更加详细的解释编译器的三阶段的每个阶段。

straight.el 命令

straight.el 更新所有已安装的包

Emacs Buffer 名字去重

范数(norm)

MAE(平均绝对误差)

RMSE(均方根误差)

机器学习涉及数学概念

Python behind the scenes #1: how the CPython VM works

原文链接:Python behind the scenes #1: how the CPython VM works。 Python 幕后 #1: CPython 虚拟机如何工作 介绍(Introduction) 你是否曾经好奇过当你运行 Python 代码时 python 做了些什么? $ python script.py 这篇文章将开启一个系列来尝试解答这个问题。我们将深入 Python 最流行的实现 CPython 的内部。 通过深入 CPython 的内部我们将更深一层的去理解这门编程语言本身。这也是我们这个系列的最主要的目标。 如果你熟悉 Python 并且可以阅读 C 代码,但是对 CPython 源码本身没有太多的经验, 那么你可能非常适合本系列,并且对本系列感兴趣。 什么是 CPython 并且为什么有人想学习它(What CPython is and why anyone would want to study it) 我们首先来说明一些众所周知的事情。CPython 是用 C 编写的 Python 解析器。他是 Python 语言的众多实现 的一种,其他还有诸如 PyPy、Jython、IronPython 等。CPython 的独特之处在于它是 Python 的起源、维护时间最长也是最受欢迎的。 CPython 实现了 Python,但是 Python 是什么?最简单的一个答案可能是:Python 是一门编程语言。 当正确问相同的问题,那么答案将会更加明确:什么定义了 Python?Python 不像 C 语言有正式的规范, 但是与之相近的是 Python 语言参考(Python Language Reference),它以如下内容开始:

机器学习测试与验证

机器学习的主要挑战

机器学习系统的种类

监督式/无监督式学习 监督式学习 定义 训练数据经过标注包含素所需解决方案(标签或标记) 相关算法 K-邻近算法 线性回归 逻辑回归:广泛用于分类,输出“属于某个给定类别的概率”的值 支持向量机 决策树和随机森林 神经网络 适应场景 分类任务 预测变量 无监督式学习 定义 训练数据未经标注 相关算法 聚类算法 K-平均算法 分层聚类分析 最大期望算法 可视化和降维 主成分分析 核主成分分析 局部线性嵌入 t-分布随机临近嵌入 关联规则学习 Apriori Eclat 适应场景 通过聚类算法检测相似(层次聚类算法精度更高,可以再次细分) 可视化算法 降维:不丢失太多信息的前提下简化数据,方法之一是合并特征,过程叫做特征提取 异常检测:判断新的输入是正常还是异常,数据初筛、防作弊等 关联规则学习:发现属性之间有趣的联系 半监督式学习 大量未标记数据和少量标记数据进行学习。 强化学习 观察环境、作出选择、执行操作、并获得回报(负值则为惩罚)。 批量学习和在线学习 在数据流中进行增量学习。 批量学习 在线学习 在线学习也称为增量学习,同时支持恢复到上一状态,便于检测到性能下降及时中断和回滚。 核外学习 超大数据集超出一台计算机的主存储器,每次加载部分数据并不断重复直至完成训练。 学习率 学习率高系统迅速适应新数据,同时快速忘记老数据,学习率低则反之。 基于实例和基于模型的学习 基于实例的学习 系统完全记住学习示例,然后通过某种相似度度量方式将其泛化到新的实例。 基于模型的学习 模型选择 观察数据得出模型的过程。

《机器学习实战》读书笔记

Machine Learning

Rust Obscure Words for non-native English speakers

Rust Asynchronous Programming

Future async fn 将一个代码块转换为一个 Future 对象, Future 对象维护一个状态机 Future 对象必须运行在一个 Executor 上 Executor futures::executor::block_on 阻塞当前线程直到 future 完成 // `block_on` blocks the current thread until the provided future has run to // completion. Other executors provide more complex behavior, like scheduling // multiple futures onto the same thread. use futures::executor::block_on; async fn hello_world() { println!("hello, world!"); } fn main() { let future = hello_world(); // Nothing is printed block_on(future); // `future` is run and "hello, world!

Go Swagger 实现代码即文档

目标 当跟随这篇文章完成后将产出如下内容: 代码 http://gitlab.17zuoye.net/vgo/go-swagger-example 文档 http://swagger.17zuoye.net/?url=http%3A%2F%2F10.200.242.61%3A9090%2Fswagger.json 准备 Go1.14 及以上版本 安装 go-swagger :参见 官方文档。 接下来使用 gin 框架作为示例,如果之前没接触过可以先了解下该框架 创建一个项目 $ mkdir go-swagger-example $ cd go-swagger-example/ $ go mod init gitlab.17zuoye.net/vgo/go-swagger-example 开始使用 首先在你的 `main.go` 定义 go generate 像下面这样: //go:generate swagger generate spec -o ./swagger.yml package main func main() { println("Hello world!"); } 此时如果运行 go generate 在项目目录下就会生成一个 swagger.yml 文件: paths: {} swagger: "2.0" 使用单独的包托管 swagger 相关定义 在之前实践的过程中发现,如果在多个包中定义了相同名称的结构体会到只一个结构体覆盖另外一个结构体的定义。 所以为了解决这个问题,我把所有 swagger 相关的定义都放在同一个包下来避免相同名字的结构体。

MySQL forget password

MVCC

MySQL grant subnet

Network

逻辑右移

算数右移

汇编

程序编码 $ gcc -Og -S mstore.c # outputs mstore.s $ gcc -Og -c mstore.c # outptus mstore.o $ objdump -d mstore.o 所有以 ‘.’ 开头额行都是指导汇编器和链接器工作额伪指令。 数据格式 C 声明 Intel 数据类型 汇编代码后缀 大小(字节) char 字节 b 1 short 字 w 2 int 双字 l 4 long 四字 q 8 char* 四字 q 8 float 单精度 l 4 double 双精度 q 8 访问信息 寄存器 一个 x86-64 的中央处理单元(CPU)包含一组 16 个存储 64 位值的 通用目的寄存器 。

IEEE 浮点数

浮点数小数表示形式 .0111 = \(0x2^{-1}+2^{-2}+2^{-3}+2^{-4}\) IEEE 浮点数表示形式 \[ V=(-1)^s X M X 2^E \] s = 0 表示负数, s = 1 表示正数 M 是二进制表示的小数 E 是阶码 浮点数二进制组成 一个单独符号位 s 表吗符合 k 位阶码字段 exp 编码阶码 E n 位小数字段 frac 编码尾数 M 两种常见的格式 float s = 1 k = 8 n = 23 double s = 1 k = 11 n = 52 三种计算方式 前置的一些值

Computer Systems

Web

SSH

Fearless Concurrency with Rust

Rust Means Never Having to Close a Socket

原文链接:Rust Means Never Having to Close a Socket Rust 最酷的特性之一就是它可以自动地帮助你管理资源,同时在仍能保持安全(没有段错误)和高性能。 这是因为 Rust 是一门与众不同地编程语言,要理解我说的可能有点困难,让我来更近一步说明: Rust 就像带垃圾回收的编程语言,你无需手动释放内存 Rust 不同于其他带垃圾回收的编程语言,你无需1手动关闭或者释放像文件、套接字和锁这样的资源 Rust 达到以上这些特性不附带任何运行时开销(垃圾回收或者引用计数),并且不牺牲安全性。 如果你曾经造成过一个套接字或者文件泄漏,或者使用过一些抽象方法造成了这些资源的泄漏,那么你就会知道这有多重要。 你可能已经期望通过“使用后释放”来避免内存问题,而与此同时你并没有考虑到没有明确地关闭套接字可能出现类似的错误。我在这里告诉你,还有更好地办法。 如果你使用的是带垃圾回收的编程语言,则应密切关注本文提到的资源管理方面的内容。如果你使用的是像 C/C++ 这样底层编程语言,你可能会对安全方面更加感兴趣。 Rust 的许多特性都是从其他语言借鉴而来。Rust 之所以变得有趣是因为它把所有的这些特性放在了一起,并且在编程语言层面实现了更严格地保证。 实际上,这种编程语言层面的保证让这些特性更加实用。 所有权系统(The Ownership System) 让这种保证工作的方式是通过 Rust 的「所有权(ownership)」系统。不管任何时候你创建一个新的对象,都被创建它的「作用域(scope)」所拥有。 让我们通过一个例子来进一步说明:我们定义一个函数,函数拷贝输入文件到临时文件去处理它,然后拷贝输入文件到输出文件。 fn process(from: &Path, to: &Path) -> IoResult<()> { // creates a new tempdir with the specified suffix let tempdir = try!(TempDir::new("skylight")); // open the input file let mut from_file = try!

Rust 并发

Rust 宏

智能指针

智能指针 表现的像一个指针,拥有数据并允许在对数据进行维护。 通常通过 struct 实现并实现两个特性 Deref 和 Drop Deref 允许智能指针实例行为像一个引用,让代码可以同时处理引用和智能指针 Drop 允许自定义智能指针超出作用域的行为。 标准库常见的智能指针 Box<T> 用于在堆分配值 Rc<T> 引用计数类型,允许多个拥有者 Ref<T> 和 RefMut<T> 和通过 RefCell<T> 访问,运行时取代编译期强制检查借用规则 Box 场景: 编译期未知大小的类型(递归类型(自己包含自己类型的类型,如链表)编译期无法确定大小) // 递归类型 enum List { Cons(i32, Box<List>), Nil, } fn main() { let b = Box::new(5); println!("b = {}", b); let list = Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil)))))); } 避免大量数据转移所有权时发生拷贝

迭代器

生命周期

生命周期 Rust 中的每一个引用都有其生命周期:引用有效的作用域。 大部分情况下生命周期都是隐式和自举的,在无法完成的情况下就需要我们通过生命周期泛型参数帮助编译器进行注解。 生命周期的主要目标是避免悬空指针。 生命周期泛型参数定义各个引用之间(参数和参数、参数和返回值)的关系,并不改变(延长)变量原本的生命周期 &i32 // a reference &'a i32 // a reference with an explicit lifetime &'a mut i32 // a mutable reference with an explicit lifetime 参考以下代码 fn longest<'a>(x: &'a str, y: &'a str) -> &'a str { if x.len() > y.len() { x } else { y } } 以上代码 标注生命周期 'a 函数有两个引用参数,都使用生命周期 'a 表示两个参数的生命周期必须一致(存活的周期一样长) 函数返回一个引用,并且存活的时间和生命周期 'a 一致 以上指定不改变任何传入的引用的生命周期,我们只是要求借用检查器(borrow checker)检查这些约束。 也就是说借用检查器要检查传入的两个引用的生命周期必须一致,返回的引用的存活周期不能超过传入的引用的存活周期 思考 当函数返回一个引用时,返回值的生命周期注解要和参数的其中之一相匹配,否则那么引用就是指向里函数内创建的值(不能返回)。 也就是说返回引用时,引用的声明周期必须和参数(其一)相关。如果想要返回函数内创建的值最好返回一个有所有权的值类型。

闭包

let add_one = | num | { num + 1 }; 由于闭包和当前上下文相关联,所以 Rust 可以进行类型推导,类型注解也就不是必要的,但是依然可以自己添加: let add_one = | num: i32 | { num + 1 }; fn add_one_v1 (x: u32) -> u32 { x + 1 } let add_one_v2 = |x: u32| -> u32 { x + 1 }; let add_one_v3 = |x| { x + 1 }; let add_one_v4 = |x| x + 1 ; 使用 Fn 存储闭包类型 struct Cacher<T> where T: Fn(u32) -> u32 { calculation: T, value: Option<u32>, } impl Cacher<T> where T: Fn(u32) -> u32 { fn new(calculation: T) -> Cacher<T> { Cacher { calculation, value: None, } } fn value(&mut self, arg: u32) -> u32 { if let Some(value) = self.

Traits

Traits 定义行为在多个类型中共享。 可以定义默认行为在实现者中间共享。 可以用于定义参数的行为,同样可以定义返回值行为,当用 trait 限定返回值类型时,不能同时(if/else)返回多种实现了该 trait 的类型。 pub trait Summary { fn summarize(&self) -> String; } pub struct Article{ pub title: String, } impl Summary for Article { fn summarize(&self) -> String { format!("{}", self.title) } } pub fn notify(item: impl Summary) { println!("{}", item.summarize()); } // trait bound 语法糖版本 pub fn notify<T: Summary>(item: T) { println!("{}", item.summarize()); } 定义参数行为 通过 impl : fn notify(item: impl TraitName) ,用于简单明了的场景,比如一个参数 通过 trait bound : fn notify<T: TraitName> (item: T) ,用于更复杂的场景,比如多个参数用于减少代码 可以通过 + 连接: fn notify(T: TraitName + Display) (item: T)

错误处理

enum Result<T, E> { Ok(T), Err(E), } ? 操作符 对比 use std::io; use std::io::Read; use std::fs::File; fn read_username_from_file() -> Result<String, io::Error> { let f = File::open("hello.txt"); let mut f = match f { Ok(file) => file, Err(e) => return Err(e), }; let mut s = String::new(); match f.read_to_string(&mut s) { Ok(_) => Ok(s), Err(e) => Err(e), } } 和 use std::io; use std::io::Read; use std::fs::File; fn read_username_from_file() -> Result<String, io::Error> { let mut f = File::open("hello.

if let

模块化

包、crate 和模块 Cargo.toml 表示一个包 包含 0 个或 1 个库 crate( src/lib.rs ) 包含 0 个或多个可执行 crate ( src/main.rs src/bin/*.rs ) 可以同时包含以上两种 模块化系统 模块,一种组织代码和控制路径隐私的方法 所有的项(函数,方法,结构体,枚举,模块和常量)默认私有 不允许使用私有的子模块的代码 可以使用父模块和同级模块的代码 路径,一种命名项的方法 use , 一个将路径带到当前作用域的关键字 pub ,一个将项公开的关键字 as ,一个将带到当前作用域项重命名的关键字 super , 一个相当于文件系统里 .. 作用的关键字 * ,通配符用于使用制定路径下的所有项 pub use 用于重新暴露可以访问的模块 模块可以放在一个文件,也可以按照一定规则拆分到不同文件下

模式匹配

枚举

多种类型的集合体,一个类型的变量可以存储多种类型的值,枚举的每一项都是该枚举类型的变体: enum IpAddrKind { V4, V6, } fn main() { route(IpAddrKind::V4); route(IpAddrkind::V6); } fn route(kind: IpAddrKind) { // ... } 枚举的每一个变体都可以直接包含数据,并且每一个变体可以包含不同的数据类型和不同的数量,甚至可以直接放结构体(也可以是匿名的)。 struct Ipv4Addr { // --snip-- } enum IpAddr { V4(Ipv4Addr), V6(String), } let home = IpAddr::V4(127, 0, 0, 1); let loopback = IpAddr::V6(String::from("::1")); struct Message { Quit, Move{ x: i32, y: i32 }, // anonymous struct Write(String), ChangeColor(i32, i32, i32), // three i32 values } 枚举也可以通过 impl 实现方法

结构体

结构体 元组结构体(tuple struct) 用于命名元组并和其他元组进行区分: struct Color(i32, i32, i32); struct Point(i32, i32, i32); let black = Color(0, 0, 0); let origin = Point(0, 0, 0); 由于定义了元组结构体所有 black 和 origin 是两个不同的类型。 没有字段的结构体:类单元(Unit-Like)结构体 没有任何字段的结构体和单元类型 () 类似,用于实现一些特性(trait)但是没有任何数据。 方法语法 self 占有所有权 &self 不可变借用 &mut self 可变借用 自动引用和解引用 在 Rust 中进行方法调用,如 object.something ,Rust 会自动添加 & &mut 或者 * , 用以自动匹配方法签名。以下是等价的: p1.distance(&p2); (&p1).distance(&p2); 方法如果不声明 self 行参则是一个关联方法(静态方法),通过 :: 调用

引用和借用

类型前置 & 表示引用,引用允许变量指向一个值但是不发生所有权转移。 引用不占有所有权,所以变量超出作用域之后不会触发 drop 调用。 引用作为函数形参被成为借用(borrowing) 可变引用 针对特定作用域下的特定数据只能创建一个可变引用。如果要创建多个可变引用可以通过大括号创建新的作用域 let mut s = String::from("hello"); { let s1 = mut &s; } let s2 = mut &s; 当已经存在不可变引用时,则无法再创建可变引用,下面代码无法编译通过 let mut s = String::from("hello"); let s1 = &s; // OK let s2 = &s; // OK let s3 = mut &s; // BIG PROBLEM 悬空引用 以下代码是不允许的,无法编译通过 fn main() { let s = dangling_string(); } fn dangling_string() -> &String { let s = String::from("hello"); &s } 上面代码 s 在函数内部分配,那么在函数执行完成后 s 将被释放,所以返回 s 的引用会造成悬空引用。

所有权

规则 每个值都有一个变量叫做所有者(owner) 同一时间只能有一个所有者 当所有者超出作用域则值被销毁 变量作用域 作用域是一个变量有效的范围 当变量超出作用域范围自动调用对象的 drop 方法进行内存归还操作 变量相互作用:所有权转移(Move) 对于所有在栈上分配的值(固定大小),在进行赋值操作时都对值进行拷贝: let x = 5; ley y = x; // copy 5 to y 但是对于在堆上分配的,变量保存的是指向内存的指针,所以在赋值时拷贝的也是指向该内存的指针: let s1 = String::from("hello"); let s2 = s1; 为了保证内存安全,防止 s1 和 s2 超出作用域范围调用两次 drop 造成重复的内存回收,Rust 会让 s1 不再有效,来避免对 s1 进行回收。继续使用 s1 会导致编译错误。这种情况叫做所有权转移(move)。 变量相互作用:克隆(Clone) 克隆用于深度拷贝变量: let s1 = String::from("hello"); let s2 = s1.clone(); println!(s1); 变量项目作用:拷贝(Copy) 如果数据类型的大小在编译期能够确定都将存储在栈上,这种情况下能够进行快速的拷贝。 Copy 特性(trait)注解用于将值存贮在栈栈上 Copy 特性注解不能和 Drop 特性注解混用 Copy 特性注解使用规则如下 所有的数字类型 所有的布尔型 所有的浮点型 字符类型 所有元素都实现了 Copy 特性注解的元祖 所有权和函数 函数传递实参的规则和变量类似,传递变量到一个函数将为发生所有权转移或者拷贝。

语句和表达式

Member initialize

Iterator class

SSE/AVX/AVX2/AVX512

优化

Surgical Reading: How to Read 12 Books at Once

原文链接:https://superorganizers.substack.com/p/surgical-reading-how-to-read-12-books 手术阅读法:如何同时阅读 12 本书 译者注:这篇文章让我想起了《如何阅读一本书》这本书,文章中的大部分技巧都能在这本书中找出来,阅读是一门需要学习的技能。 当有人问我如何阅读时我总是会有点尴尬,因为我一般都是同时阅读十几本书。 但是我这样阅读并不是为了炫耀 – 我这么做是因为我觉得这种阅读方式更好,最起码对我来说。 这是一个我开发一个叫做 手术阅读法(surgical reading) 的过程,它意味着当我读一本非小说的书籍时,我会专注于尽可能快的从书中找到最有价值的部分并将之剔除。 这样允许我在一个主题上同时阅读许多不同的书籍,并从多个角度来观察这一主题。我的目标是快速地找到有价值的知识,并使用现实中获得的信息去解决问题。 这种方法有很多隐藏的好处。首先,我可以快速了解自己对一本书是否有兴趣,并因此去花更多的时间读我真正感兴趣书籍。当我对一本书不感兴趣时我就可以将其放下并转到其他事情上,因为我知道我将它放回去是有原因的。 阅读不应该是将书籍在 ToDo 事项完成,而是应该解释什么吸引了你。 其次,我可以从多个角度观察一个主题,并真正理解问题。我可以看到有多少不同的人讨论同一个时间和想法,而不是依靠一位作者的陈述。 这使我对当前感兴趣的的任何主题都有更细微的了解。 最后,它将书籍转变为更主动和更积极的事物。我的书架(library)已经不再是死板的存储空间,而是一个与我不断互动的鲜活的事物。 当然,当我找到一本我真正喜欢的书(现在也越来越频繁),我也可以充分的利用它。 我是谁(Who I Am) 我的名字是 Brian Tobal,我耗费了我的大部分时间来思考如何学习。在过去 15 年,我在教育界获得了很多头衔(hats)。 我曾是一名小学科学老师、一家教育公司的研究员、六家教育科技初创公司的产品负责人,本人也是一些初创公司的创始人, 包括我于 2018 年出售的一家名为 Hickory 的公司。 我喜欢初创公司。从学习角度来看,它们使你可以完全沉浸于新的领域,并根据其性质迫使你解决实际问题。 这为我自己的学习方法和阅读方法提供了动力。我不是为了仅仅积累知识来建立知识库,通常我建立它是为了尽快使用它。 手术阅读法就是设计用来帮助我这么做的。 所以你准备好试一试了吗?请从书架上拿出一些已经搁置了一段时间的书,希望您还没有读过。跟着我,亲眼看看手术阅读法的感觉。 让我们开始吧! 把书当作其自身的地图(Use the Book Itself as a Map) 以下是一份我如何阅读一本书的步骤分解: 了解一本书 通过封面评判这本书 索引(index)包含了一切 把目录(TOC)当作骨架 通过前言(preface)进行预览 此过程的重点是获得在大约 15 分钟内对任何书籍进行“地图绘制”的能力。你希望对有价值的知识位于何处、什么地方打动你以及要花费多少时间来阅读它有基本的了解。 下面,我们将逐步完成从一本书中提取要点(或者说知识块)的过程,如何增加阅读一本书的价值,以及如何结合所有内容以便您可以轻松的一次提取多本书。 了解一本书(Approaching a Book ) 当我开始阅读一本非小说的书籍之前,我会话费 5-10 分钟的时间尝试去了解他对我具有什么价值以及它的结构。当我们决定要阅读此书时我们可以通过很多方式做到这一点。 也许通过亚马逊阅读一些评论和反馈或者随机浏览其中一部分。我更喜欢使用这本书本身。

Python

Python vendor package 之前一直在找 Python 类似 go mod vendor 部署的解决方案,今天在看 PySpark 的时候找到了,主要现存两种解决方案: Conda 生态可以使用 conda-pack 原生 CPython 生态可以依托 venv-pack pex 对比 时间 项目 活跃开发 贡献人数 提交数量 2021-08-28 venv-pack 否 2 30 conda-pack 是 15 246 pex 是 87 940 IPython EIN import numpy, math, matplotlib.pyplot as plt %matplotlib inline x = numpy.linspace(0, 2 * math.

CMake

Build System

Tmux 256 colors

Rust Trait Object

Rust Wrapper Types

SOLID

SRP: Single Responsibility Principle 浅显的解释是软件模块只提供单一功能 更进一步任何一个软件模块都应该有且只有一个被修改的原因 再更进一步这个原则是关于人(Actor)的 任何一个软件模块都应该只对一个用户或系统利益相关者负责。 最终就是任何一个软件模块都应该只对某一类行为负责 OCP:Open/Closed Principle 设计良好的软件应该易于扩展,同时抗拒修改。也就是说一个软件模块应该允许在不修改源码的情况下扩展它的行为。 可以通过组合 SRP(代码分组)和调整依赖关系实现(DIP)。如果 A 组件不想被 B 组件上发生的修改所影响,那么就应该让 B 组件依赖于 A 组件。 LSP:Liskov Substitution Principle 里氏替换原则:多态。 每个类型是 S 的对象 o1 都存在一个类型为 T 的对象 o2,能使操作 T 类型的程序 P 在用 o2 替换 o1 时行为保持不变,我们就可以将 S 称为 T 的子类型。 public class LiskovSub { public static main(String[] args) { T o1 = new S(); T o2 = new T(); P(o1); // ok P(o2); // ok } public static P(T o) { o.

《架构整洁之道》读书笔记

技术

系统架构

C/C++

Flink

Kafka

概念组成 Producer 消息产生者,往指定 Topic 的指定 Partition 发送消息 Consumer Group 消费指定 Topic 的消息 Consumer 消费指定 Topic 下某一分区的消息 Topic 区分不同消息主题 Partition 保证同一分区的有序性 Connector 消息可被不同的 Consumer Group 重复消费(广播或订阅)。同一 Consumer Group 下的不同 Consumer 分别消费不同的 Partition,Consumer 数量不能超过 Partition 数量。 数据被持久化并分片成功后发送 ACK 保证里数据不被丢失。 设计 持久化 基于文件系统 基于队列是顺序的和磁盘的顺序访问要比内存的随机访问要快(参见 The Pathologies of Big Data), Kafka 采用在磁盘文件系统上尾部写头部读的方式。 Kafka 没有采用 BTree 存储数据因为 BTree 的操作是 O(log N) ,而且对磁盘的 seek 操作要慢,且同时只能进行一次限制了并行,所以实际操作比 O(log N) 要慢 基于磁盘的顺序访问进行在尾部写和头部读,可以实现读写都是 O(1) 的时间复杂度,并且读写互不干扰 基于以上实现,Kafka 可以不必在消息一经消费就删除,而是可以保留消息一段相对较长的时间(比如一周) 高效 并且采用统一的日志格式,可以方便的使用 sendfile 避免字节拷贝以在各个组件之间高效的交换日志文件

LeetCode

LeetCode: Trapping Tain Water LeetCode: 153.Find Minimum in Rotated Sorted Array LeetCode: 154.Find Minimum in Rotated Sorted Array II LeetCode: 316.Remove Duplicate Letters LeetCode: 3.Longest Substring Without Repeating Characters LeetCode: 4.Median of Two Sorted Arrays LeetCode: 5.Longest Palindromic Substring LeetCode: 6.ZigZag Conversion LeetCode: 92. Reverse Linked List II LeetCode: 25. Reverse Nodes in k-Group LeetCode: 46. Permutations LeetCode: 47. Permutations II LeetCode: 51. N-Queens LeetCode: 52. N-Queens II LeetCode: 39.

LeetCode: Trapping Tain Water

Linux Virtual Memory Management

原文连接:Linux Virtual Memory Management Chapter 2 Describing Physical Memory:描述物理内存 独立于平台架构的方式描述内存 — 更好的支持多平台 本章包含描述存储器、内存页的结构体(structures)和一些影响 VM 行为的标识位(flags) VM 中普遍(prevlent)认为第一重要(principal)的概念是 NUMA。 大型机器中内存访问速度取决于 CPU 到内存的距离。比如一组(bank)内存分配给每一个处理器或者一组内存非常适合靠近的 DMA 设备卡。 这里的每组(bank)内存被称为节点(node)并且这个概念在 Linux 中通过 struct pglist_data(typedef pg_data_t) 表示,即使在 UMA 架构下也是如此。每一个节点是一个由 NULL 结尾的链表,通过 pg_data_t->next_node 指向下一个节点。 每一个节点都被分割成多个块(block)称为分区(zone)用于表示内存中的范围。分区使用 struct zone_struct(typedef zone_t) 结构体描述,每一个分区都是以下三种类型的一种 ZONE_DMA 开始 16MB 内存,供 ISA 设备使用 ZONE_NORMAL 16MB - 896MB,由内核直接映射到线性地址空间的上部区域(将在第四章讨论) ZONE_HIGHMEM 896MB - END,剩余不由内核直接映射的系统可用内存, 大部分内核操作都只能使用这种类型的分区,所以这里也是这里也是最关键的性能区域(most performance critical zone) 每一个物理页帧(physical page frame)都使用结构体 struct page 表示,所有的结构体都保存在全局数组 mem_map 中,mem_map 通常存储在 ZONE_NORMAL 的开始处;

Programming Language

《百箭穿杨》读书笔记

需要熟悉股市相关概念进行扫盲。 粗读要点 树立安全边际,跟随格雷厄姆 寻找好的困难股,降低触底难度,加大触底区间,预测底部区间,分 5 档抄底,最好在 1-3 档就能完成抄底 每次只买总资产的 1% 盈利后可以将本金提出,只留底仓等待顶峰信号后抛出赚取高额利润的前提下保障本金 总是留 25%-40% 的现金 做长线 分析财报看毛利、营收增长率、负债率可以确定一个好股,然后就等一些情况下这只股遇到困难触底 看行业处于哪个周期:萌发、成长啥的 不做重仓 复读要点完善 安全边际 跟随格雷厄姆 偏离:更保守或更激进 大赚小赔不如小赚不赔:不亏钱 困境好企 做有把握的事,不啃硬骨头,广撒网,多捞鱼,选取一批困境好企来实现从小盘大稳定增长股 行业中的好企业标准 行业很关键 需求无限,供给有限 关注行业周期 大周期:新生->成长->成熟->衰落->消亡 小周期:大周期各个过程中的景气与萧条(一两年、三五年甚至一二十年) 消亡之前会有死灰复燃,大周期中成长阶段会有萧条,注意区分。 门槛高,竞争少 只有少数寡头,估值会高 唯一或第一 成熟行业比较简单,成长行业比较困难。 通过企业原则、经营原则、财务原则和市场原则衡量。- P28 生活经验活常识也很重要。 落难好企 行业顺境,某些原因导致的猜疑导致股价下跌 行业遭遇整体困境:偶然事件,反转时间比好把握 个股困境,主打产品破灭:有无法度过的风险 财务数据衡量困境好企能否度过难关 - P32

分布式

动态规划

状态转移方程 无后效性 如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。 一旦 \(f(n)\) 确定,“我们如何凑出 \(f(n)\) ”就再也用不着了: 要求出 \(f(15)\),只需要知道 \(f(14)\),\(f(10)\),\(f(4)\) 的值, 而 \(f(14)\),\(f(10)\),\(f(4)\) 是如何算出来的,对之后的问题没有影响。 “未来与过去无关”,这就是无后效性。 最优子结构 大问题的最优解可以由小问题的最优解推出,这个性质叫做“最优子结构性质”: \(f(n)\) 的定义需要蕴含“最优”,利用 \(f(14)\),\(f(10)\),\(f(4)\) 的最优解,我们即可算出 \(f(15)\) 的最优解。 能将大问题拆成几个小问题,且满足无后效性、最优子结构性质。 练习 0x00 硬币找零 描述 假设有几种硬币,如1、3、5,并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。 状态转移公式 公式 \(f(n)=min\{f(n-1),f(n-3),f(n-5)\} + 1\) 检查是否满足上面提到的两个特性: 无后效性:对于 \(n\),一旦 \(f(n)\) 确定,以后只关心 \(f(n)\) 的值,不关心怎么计算的; 最优子结构:对于 \(n\),只要 \(n - 1\) \(n - 3\) \(n - 5\) 能是最优解,那么就能计算出 n; 推导过程 假设找零 15: 若优先使用 5 元硬币 \(cost = f(10) + 1 = 2 + 1 = 3\)

大数据

归并排序

算法

Let’s Encrypt

这里以新增 vd.linuxzen.com 为例。 新增 DNS 解析 通过 DNSPOD 新增 DNS 解析 A 记录 调整 Nginx 新增 HTTP 站点 Nginx 参考配置 server { listen 80; server_name vd.linuxzen.com; include /etc/nginx/snippets/letsencrypt-acme-challenge.conf; } 新增签发证书 $ acme.sh --force --issue -d linuxzen.com -d www.linuxzen.com -d cwiki.linuxzen.com -d monitor.linuxzen.com -d v.linuxzen.com -d vd.linuxzen.com -d d.linuxzen.com -d piwik.linuxzen.com -d t.linuxzen.com -d wiki.linuxzen.com -d note.linuxzen.com -w /var/www/letsencrypt/ 安装证书 $ acme.sh --install-cert -d linuxzen.com --cert-file /etc/nginx/certs/linuxzen.com/cert.pem --key-file /etc/nginx/certs/linuxzen.com/privkey.pem --fullchain-file /etc/nginx/certs/linuxzen.

V2Ray

翻墙 架构 Client -> DIDIYun(HAProxy) -> HK 滴滴云 HAPorxy 配置 117.51.146.119 frontend v_linuxzen_com bind *:6697 option tcplog mode tcp default_backend v_linuxzen_com_nodes backend v_linuxzen_com_nodes mode tcp balance roundrobin option ssl-hello-chk server webserver1 45.115.36.35:443 check 客户端改动 需要调整 hosts $ echo '117.51.146.119 v.linuxzen.com' | sudo tee -a /etc/hosts HK V2Ray Docker 启动 $ docker run -d -p 127.0.0.1:25001:25001 --name v2ray --restart always -v /etc/v2ray:/etc/v2ray v2ray/official HK Let’s Encrypt 证书 $ acme.sh --issue -d linuxzen.

xinetd

xinetd 代理 SMTP 和 IMAP 通过 xinetd 代理 SMTP 和 IMAP 实现 gmail 翻墙。 配置服务端 service imap { type = UNLISTED port = 993 bind = 0.0.0.0 socket_type = stream wait = no user = nobody redirect = imap.gmail.com 993 per_source = UNLIMITED cps = 100 2 } service smtp-465 { type = UNLISTED port = 465 bind = 0.0.0.0 socket_type = stream wait = no user = nobody redirect = smtp.

翻墙

股市相关概念

基金定投

适合人群:穷人、笨人、忙人、好人 为什么 通胀太高,股票战胜通胀的重要工具 绝大多数人不具备择时能力 避免高点买入 核心逻辑:放弃择时,持续小额买入,降低成本 缺点:在市场上涨、高位震荡过程中,虽然盈利大幅提高,但持仓成本也在快速提高。一旦市场转向熊市,整体会迅速亏本。 单边上涨:定投盈利少于一次性投资 先震荡后上涨:定投盈利少于一次性投资 先上涨后下跌:定投亏损多于一次性投资 单边下跌:定投亏损少于一次性投资 震荡:定投与一次性投资持平 先下跌再震荡:定投亏损少于一次性投资 除了坚持,还在于止盈策略,牛市中成本不断提高,需要及时止盈,防止下跌时候的亏损 错误理念 定投不是万能,需要防止“倒微笑曲线周期” 巴菲特说指数基金难以超越仅限于美股,A 股与之相反 定投组合包含债券基金:定投适合波动较大的权益类资产(股票、商品),债卷等固定收益类产品本身波动小,一次性买入和定投基本没区别 月定投不够还要周定投:基本没差别 定投是懒人投资,坚持即可:还需要主动管理,如定投的标的不再适合定投,该换要换。 一次性投资止损不止赢,定投止赢不止损。 定投只买开放式基金:还可以宽基指数基金、主题指数基金、行业指数基金、风格指数基金、策略指数基金、QDII 指数基金、商品指数基金。此外,还有折价的封闭式基金、定增基金,适当的配置会非常好玩。 策略 定投买入,止盈不止损: 需要在可能出现的“倒微笑曲线周期”及时止盈。 制订量化估值标准 技术分析 通过MA、MACD、RSI等各种技术指标,判断目前市场从长期看,是相对低位还是高位 趋势上涨原则:MA(30)>MA(60)>MA(120); 趋势下跌原则:MA(30)<MA(60)<MA(120)。 均线偏离法:根据指数价格对均线偏离的程度决定投资额度的多少。 P>MA(120):正偏离,减少投资额度; P<MA(120):负偏离,增加投资额度。 基本面分析 根据指数相关基本面指标,判断股市处于高估或者低估。如市盈率、市净率、整体ROI等地。在股市高估时,降低投资额度,在股市低估时,增加投资额度。 定期不定额策略 在上述策略的基础上,如目前市场明显在历史地点,原来每个月投1000的,这时不妨投2000。如市场明显高估,每个月投1000的可以投500。如果涨的都害怕了,可以不投甚至卖出一部分。 产品池管理

Deep Learning

AI

CPI

ELisp

Emacs

Financial Management

Go

Go Channel

Helm

Makefile

Org Mode

Rust

Taking Smart Notes With Org-mode

Unix

《巴比伦富翁新解》读书笔记

基准差

基金

基金

复利

夏普比率

标准差(Standard Deviation)

正在读的书

CPI

《领域驱动设计》读书笔记

前言和目录 好的软件需要控制复杂性,好的领域模型可以帮助控制复杂性。 什么样的项目需要 DDD?尝试型的小型项目应该不需要 DDD,但是一旦上了规模考虑后续迭代则需要 DDD。 本书组织方式: 领域建模 领域建模的过程就是消化知识的过程,这个过程应该贯穿整个开发过程,需要持续学习。 模型用来描绘人们所关注的实现或想法的某个方面,比如地图就是模型。 模型是一种简化,是对实现的解释:把与解决问题密切相关的方面抽象出来,而忽略无关的细节。 软件问题建模的区域就是软件的领域 物质世界的领域:机票预订程序涉及的飞机乘客。 无形的领域:会计程序的金融领域。 领域涉及知识信息超载的问题,模型这种知识对知识进行了选择性的简化和有意的结构化。 领域模型将领域专家头脑中的支持严格的组织且有选择的抽象,并不是尽可能建立一个符合“现实”的模型。 模型表示 关联 规定一个遍历方向:存在双向联结时(地址 -> 人 或 人 -> 地址)尽量只用一种,并避免互相关联 添加一个限定符,以便有效减少多重关联 消除不必要的关联 表示方式 ENTITY 用于跟踪对象的状态,有唯一标识符,在系统中是可变的,两个对象是否一个通过唯一标识来判断,不是靠它们的属性定义。 VALUE OBJECT 区别与 ENTITY ,没有唯一标识,仅记录状态,一般设计为不可变用于共享 VALUE OBJECT,两个对象是否一个通过对象属性的值来判断。 SERVICE 没有状态,但又需要建模的对象,只包含动作。用于一些不适合建模为对象的领域概念。 与领域概念相关的操作不是 ENTITY 或 VALUE OBJECT 的一个自然组成部署 接口是根据领域模型的其他元素定义的。 操作是无状态的 MODULE(或 PACKAGE):划分领域模型,低耦合高内聚

LeetCode: 316.Remove Duplicate Letters

移除小写字母中重复的字母,让所有字母都只出现一次,并且结果是所有结果中按照字典序排序最小的那个。 Example 1 Input: “bcabc” Output: “abc” Example 2 Input: “cbacdcbc” Output: “acdb” 解法之一: 通过一个数组对每一个出现的字母进行计数 遍历每一个字母放入栈,并将该字母的计数减 1 查看栈底的字母有没有比当前字母大且该字母的计数不为 0 的(有比当前更小的字典序),从栈底弹出该字母 func removeDuplicateLetters(s string) string { var countOfEachLetter [26]int var visited [26]bool stack := make([]byte, 0) stackBottom := 0 bytesArr := []byte(s) for _, c := range bytesArr { countOfEachLetter[getIndex(c)]++ } for _, c := range bytesArr { index := getIndex(c) countOfEachLetter[index]-- if visited[index] { continue } // countOfEachLetter[getIndex(stack[stackBottom])] > 0 后面还有该字符 for len(stack[stackBottom:]) > 0 && stack[stackBottom] > c && countOfEachLetter[getIndex(stack[stackBottom])] > 0 { // 标记为未访问用于后面的字符加入结果 visited[getIndex(stack[stackBottom])] = false // 移动栈底 stackBottom++ } // 加入到结果栈 stack = append(stack, c) visited[index] = true } return string(stack[stackBottom:]) } func getIndex(b byte) int { return int(b - 'a') } 通过上面解法遇到如下错误:

LeetCode: 153.Find Minimum in Rotated Sorted Array

解法 1 找到中间节点依次往左右扩散: 向左边扩散,如果左边的大于当前元素,那么当前元素即为最小值 向右边扩散,如果右边的小于当前元素,那么右边元素即为最小值 如果以上不成立则第一个元素为最小元素(未旋转),以下是代码 func findMin(nums []int) int { length := len(nums) if length == 1 { return nums[0] } // 从中间开始确定方向 mid := length / 2 - 1 left, right := mid, mid for left - 1 >= 0 || right + 1 < length { if left - 1 >= 0 { if nums[left - 1] > nums[left] { return nums[left]; } left-- } if right + 1 < length { if nums[right] > nums[right + 1] { return nums[right + 1] } right++ } } return nums[0] } 优化 参考答案后可通过二分查找做如下优化,首先判断是否被旋转:

LeetCode: 154.Find Minimum in Rotated Sorted Array II

LeetCode: 3.Longest Substring Without Repeating Characters

准备 动态规划 实践 字符串 “abcabcbb” 根据索引有如下关系 a b c a b c b b 0 1 2 3 4 5 6 7 \(f(0,1)=f(0,0) + 1\) \(f(0,2)=f(0,1) + 2\) 在所有字符都不重复的情况下有如下公式 \(f(s,e)=f(s,e-1) + e\) 若遇到重复的情况则,3 索引于当前字串 的 0 重复则表明当前字串已经到头,需要记录并偏移 s,s=1: \(f(1,3)=f(1,2)+3\) 假设: s - 开始字符索引 e - 结束字符索引 若遇到当前字符于前面 r 字符重复则: \[ f(r,e)=f(s,e - 1) + e; s=r \]

LeetCode: 4.Median of Two Sorted Arrays

思路 归并排序 代码 func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { nums := mergeSort(nums1, nums2) length := len(nums) if length % 2 != 0 { return float64(nums[(length - 1) / 2]) } i := length / 2 return (float64(nums[i]) + float64(nums[i - 1])) / 2 } func mergeSort(nums1 []int, nums2 []int) []int { l1 := len(nums1) l2 := len(nums2) result := make([]int, 0, l1 + l2) i, j := 0, 0 for i < l1 && j < l2 { if nums1[i] < nums2[j] { result = append(result, nums1[i]) i++ } else { result = append(result, nums2[j]) j++ } } result = append(result, nums1[i:].

LeetCode: 5.Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/description/ 思路 直接暴力往两边搜索 func longestPalindrome(s string) string { buf := []byte(s) length := len(buf) if length == 0 { return s } start, end := 0, 0 for ci, _ := range buf { i, j := ci, ci // 无法处理 "aaaa" 和 "noon" 这种情况 for i > 0 && j < length - 1 && buf[i - 1] == buf[j + 1] { i-- j++ } // 考虑 "bba" 这种情况 if i == j && ci > 0 && buf[ci] == buf[ci - 1] { i, j = ci-1, ci } // 考虑 "abb" 这种情况 if i == j && ci < length - 1 && buf[ci] == buf[ci + 1] { i, j = ci, ci + 1 } if i !

LeetCode: 6.ZigZag Conversion

MySQL

《The Rust Programming Language》读书笔记