博客
HiGrid is one of the best jQuery grid plugin!
博客
HiGrid is one of the best jQuery grid plugin!
这里的内容来自对MarkDown Base和MarkDown Syntax的翻译。所有 MarkDown 不包含的语法，都可以直接使用HTML自己的标记。唯一的限制就是HTML中的块元素，如：<div>，<table>，<pre>，<p>等，必须和周围的内容用空行分开，并且这些块的开始和结束不能缩进。注意：不能在HTML块中使用MarkDown风格的标记。对于MarkDown有的语法也可以直接用HTML标签来代替。MarkDown不会处理代码(code)和HTML块中的MarkDown语法。
段(paragraph)就是一行或多行连续的文字，这些文字由一个或多个空行将它们与其它内容分开。MarkDown 支持硬换行(hard wrap)，若要在一段内加入一<br />标签，只需在一行的结尾加入两个或多个空格，再按下回车键。
MarkDown提供两种方法来标记标题(header)：Setext和atx。Setex风格是以=或-做下划线来分别得到一级、二级标题：
这是一级标题
===
这是二级标题
------
=或-的数目无关紧要。atx风格则由#做一行的开头引出标题，#的数目对应标题的等级(1~6个#分别对应1~6级标题)：
# 一级标题 #
## 二级标题 ##
.
.
.
###### 六级标题 ###
标题后面可以跟上任意数目的#号(为了好看，可以跟上与标题等级对应数目的#)。
块引用(blockquote)由>来指示，块引用中可以包含块引用、标题、列表以及代码块。
>引用
>下面是一些代码
>
> 代码
>
>下面是一些块引用
>>引用中的引用
>
MarkDown用一对*或_以及一对**或__来表示强调：
*<em>强调*
_<em>强调_
**<strong>强调**
__<strong>强调__
*或_与要强调的内容间不要有空格。
无序列表(unordered list)由单个*或+或-引导：
* 无序表
+ 无序表
- 无序表
有序列表(ordered list)由数字加.来引导。该数字并不影响列表最后的排序：
3. 有序表
1. 有序表
列表的引导符号前最多有3个空格，引导符号后至少要有一个空格或tab。一个表项(list item)中可能会有多个段落，每一个后续的段落的开始要缩进4个空格或1个tab。要在表项中引入块引用，>必须缩进。我这里测试中文表项好像有问题将markdown引擎设为kramdown后就可以了，只是可在标题的下一行用atx风格的标记标题时，若要手动指定header ID就不能在标题后面加上#的样子{: #id}来设置标题的id。
MarkDown支持两种风格创建链接：行间(inline)风格和引用(reference)风格。
行间风格由[]将链接文本括起，后面跟着()，()中放着链接的地址或地址加title属性：
[链接文本](地址)
[链接文本](地址 "title属性")
引用风格可通过名字引用链接，链接的名字在别处定义。链接名可以包含字母、数字、空格，并不区分字母的大小写：
[链接文本][链接名字]
链接名字定义为[]括起链接名后紧跟一:，然后是空格加链接地址：
[链接文本]: 地址 "title属性"
[链接文本]: 地址 (title属性)
[链接文本]: <地址> "title属性"
链接的地址可以使用相对路径，链接名的定义可以任意位置。
图像的语法和链接的类似，只是在比链接多一!放在链接文本[]的前面：
![图像替代文字][图像id]
图像id的定义和链接名的定义是一样的：
[图像id]: 图像地址 "可选的title属性"
MarkDown中不能指定图像的宽、高，要想指定就要用HTML的<img>标签。
代码可放在一对`之间，在代码中&和尖括号<或>都被解释为HTML实体。若代码中包含`，可将代码放在一对 ` ` 中：
`` 含有 ` 的代码 ``
要使用代码块，只需将代码的每一行缩进至少4个空格或1个tab就可以了。 注意：代码块其实会转成两个HTML标签:<pre>和<code>，所以代码块要用空行和周围内容分开。
水平线可由三个或多个*或-放在一行来形成。*或-间可有空格。
MarkDown中可由\引出转义字符，可被转义的字符有：
\ ` * _ {} [] () # + - . !
面试中被问到如何实现读写锁，个人也比较感兴趣锁是如何实现的，最近也在看《深入理解计算机系统》看到相关内容，做了一个调研，在此 mark down。
以下代码是伪代码
在使用 C 语言时，我们可以采用 Mutex 来进行线程同步，那么 Mutex 是如何实现的呢？
每次调用 lock / unlock 都会触发一个系统调用，让内核来协调多个线程的同步，具体同步方式采用 FIFO 队列，避免饥饿。根据 Linux Man Page 中提到系统调用需要上百条指令，而且如果 lock 失败了，会导致进程（线程）上下文的切换，进程上下文切换涉及到，保存、恢复寄存器值，替换进程虚拟地址映射表，消耗较大。
如果竞争不是很激烈，可以采用 CAS（Compare And Swap）实现用户空间锁（user-space lock），从而避免系统调用和上下文切换。CAS 是原子操作，通过 CPU 指令实现，一直尝试直到获取到锁，这种实现方式称为自旋锁。
类似地 CPU 提供 Test-and-Set 原子指令也可以用作用户空间锁。
同是原子操作，Compare-and-Swap 和 Test-and-Set 区别（伪代码形式呈现，事实上只是一条指令）：
Compare-and-Swap：
if (*ptr == oldVal) { *ptr = newVal; return true; }
else return false;
Test-and-Set：
oldVal = *ptr; *ptr = newVal; return oldVal;
需要内核协调同步的方式是引入了内核这 单点，像 100 号人想进入由门卫把控的只允许若干个人（可能不止一个，如 Semaphore）同时进入的房间一样，线程就像人，内核就像门卫。
使用 CAS 原子操作实现的锁，像 100 号人想要进入没门卫把控的只允许若干个人同时进入的房间，没有门卫单点，但是所有人必须打死打残才能获取进入的机会。
C / C++ / Java 都有关键字 volatile，这关键字的作用是使编译器每次从内存中读取值 v，而不使用寄存器中的缓存。根据计算机系统中的存储结构，值 v 会被缓存在 CPU 中的高速缓存中，高速缓存一般是有多层的，有核独占的和共享的，所以是每次从共享高速缓存中读取值 v。
设有以下代码：
int v = 0;
++v;
++v;
翻译成汇编的执行顺序：
如果在多线程下，每个线程都引用寄存器中的值而不是从内存取，那么值 v 将会有多个不同版本的拷贝。
如果加上 volatile 关键字：
volatile int v = 0;
++v;
++v;
翻译成汇编的执行顺序：
仅仅通过 volatile 无法保证更新一个变量线程安全，因为 加载 ==> 更新 ==> 写回 被分开了多步骤实现，也就是读取的值有可能是脏值，写回有可能覆盖另一个线程的写入内容。
使用 kernel 提供的 mutex 实现读写锁的伪代码：
volatile int read_cnt = 0;
mutex_t m; // 保护 read_cnt 变量
mutex_t w; // 写锁
void r_lock()
{
lock(m);
++read_cnt;
if (read_cnt == 1) {
// first reader access write lock
lock(w);
}
unlock(m);
}
void r_unlock()
{
lock(m);
--read_cnt;
if (read_cnt == 0) {
// last reader release write lock
unlock(w);
}
unlock(m);
}
void w_lock()
{
lock(w);
}
void w_unlock()
{
unlock(w);
}
上述代码不是很有必要使用 volatile 保护 read_cnt 变量，因为 read_cnt 只在 r_lock / r_unlock 中访问，而且两个函数边界都是用了 lock(m) / unlock(m) 做保护，在函数执行时都会重新将值从内存加载到寄存器中。
设 cas 的几个接口：
bool cas_set(void *ptr, int oldval, int newval) // return success or not
int cas_inc(void *ptr) // return old value
int cas_dec(void *ptr) // return old value
使用 CAS 实现读写锁的伪代码：
int read_cnt = 0;
int write_cnt = 0;
int mutex = 1; // protector
void r_lock()
{
while (cas_set(&mutex, 1, 0))
;
++read_cnt;
// first reader access write lock
if (read_cnt == 1) {
while (cas_set(&write_cnt, 0, 1))
;
}
while (cas_set(&mutex, 0, 1))
;
}
void r_unlock()
{
while (cas_set(&mutex, 1, 0))
;
--read_cnt;
// last reader release write lock
if (read_cnt == 0) {
while (cas_set(&write_cnt, 1, 0))
;
}
while (cas_set(&mutex, 0, 1))
;
}
void w_lock()
{
while (cas_set(&write_cnt, 0, 1))
;
}
void w_unlock()
{
while (cas_set(&write_cnt, 1, 0))
;
}
以上方案会导致写饥饿，个人感觉写的优先级应该比读要高，应该优先处理写请求，改版为：
int read_cnt = 0;
int write_cnt = 0;
int mutex = 1; // protector
volatile int write_request = 0;
void r_lock()
{
// if write request exist, just wait.
while (write_request == 1)
;
while (cas_set(&mutex, 1, 0))
;
++read_cnt;
// first reader access write lock
if (read_cnt == 1) {
while (cas_set(&write_cnt, 0, 1))
;
}
while (cas_set(&mutex, 0, 1))
;
}
void r_unlock()
{
while (cas_set(&mutex, 1, 0))
;
--read_cnt;
// last reader release write lock
if (read_cnt == 0) {
while (cas_set(&write_cnt, 1, 0))
;
}
while (cas_set(&mutex, 0, 1))
;
}
void w_lock()
{
while (cas_set(&write_request, 0, 1))
;
while (cas_set(&write_cnt, 0, 1))
;
}
void w_unlock()
{
while (cas_set(&write_request, 1, 0))
;
while (cas(&write_cnt, 1, 0))
;
}
对于 Java / Golang 这种由虚拟机或运行时库调度用户级线程的编程语言，实现锁并不需要操作系统介入。
对于不同的需求，如每次随机选出一个线程执行，先申请先获得锁等，具体实现方式也不太一样，在解决业务需求如此复杂的场景 Java JDK 内置非常丰富的实现。
常见的背包问题：
笔试题常遇到背包问题，做了一个简单的调研，mark down here，方便未来查阅。
其他的背包问题都是 0-1 背包的延伸，解题思路也是借鉴 0-1 背包，所以重点是弄清楚最简单的 0-1 背包解题思路。
以下的所有问题都通过动态规划解决，动态规划适用于以下问题：
例如通过动态规划求 Fibonacci 数列：
def fibonacci():
mark = {1: 1, 2: 1}
n = 1
while True:
if n in mark:
ret = mark[n]
else:
ret = mark[n - 1] + mark[n - 2]
mark[n] = ret
yield ret
n += 1
声明：下述代码采用 Go 编程语言，默认会将数据初始化为零值，比如整形数组会初始化为 0；创建动态数组没 Java 灵活，需 make 创建 slice，但不影响理解代码逻辑。
题目描述：有 N 件物品，第 i 件物品的重量为 w[i]，价值为 p[i]，承重为 W 的背包，每件物品有且仅有一件，要求最大化背包中物品的价值。
对于每件物品都有两种选择（放进背包 or not），那么时间复杂度就是 O(2 ^ N)，问题复杂度成指数级别增长，但在 O(2 ^ N) 中有很多重复的子结构，有优化空间。
定义函数：f(i, v) 为在背包承重为 v 的情况下，在 1 ~ i 物品中选择若干件，最大化背包中物品的价值。显然 f(N, W) 是本题的最终答案。
初始条件下，f(0, 0...W) = 0 且 f(0...N, 0) = 0，显然，没有物品和背包容量为 0 的情况下，价值最大化是 0。
状态转移函数：
f(i, v) = max{
f(i - 1, v),
f(i - 1, v - w[i]) + p[i] if v >= w[i] else 0
}
为什么状态转移方程是这样？
如果 w[i] <= v，物品都有两种选择，放入背包 or not。那怎么判断是否应该放入背包呢？答案是两种方案都尝试一下，比较两种方案价值，选择价值更大者，在状态转移函数中是通过查表而不是重复计算子结构。
func zeroOneKnapsack(w, p []int, N, W int) int {
f := make([][]int, N+1)
for i := 0; i <= N; i++ {
f[i] = make([]int, W+1)
}
for i := 1; i <= N; i++ {
for v := 1; v <= W; v++ {
if w[i] > v {
f[i][v] = f[i-1][v]
} else {
f[i][v] = max(f[i-1][v], f[i-1][v-w[i-1]]+p[i-1])
}
}
}
return f[N][W]
}
例子：4 件物品，大小分别为 2, 3, 1, 2，价值分别为 4, 3, 5, 2，背包容量为 7。
按照上述代码，需要构造一个表格，然后按照规律填写表格：
初始状态下表格是这样的：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | |||||||
| 2 | 0 | |||||||
| 3 | 0 | |||||||
| 4 | 0 |
填写后：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 4 | 4 | 4 | 4 | 4 | 4 |
| 2 | 0 | 0 | 4 | 4 | 4 | 7 | 7 | 7 |
| 3 | 0 | 5 | 5 | 9 | 9 | 9 | 12 | 12 |
| 4 | 0 | 5 | 5 | 9 | 9 | 9 | 12 | 12 |
最终返回 12。
使用动态规划复杂度是 O(N * W)，通过存储解记录，下次需要时查表，减少冗余计算。在没有存储解记录的情况下，不难发现上述算法遍历 O(2 ^ N) 的解空间，把所有可能都已经纳入考虑了，得到的自然是最优解。动态规划聪明的地方不是将解空间有效缩小，而是存储解记录减少冗余计算。有兴趣的读者可以一步一步试着推导。
根据状态转移函数：
f(i, v) = max{
f(i - 1, v),
f(i - 1, v - w[i]) + p[i] if v >= w[i] else 0
}
f(i, v) 只依赖于 f(i - 1, v) 和 f(i - 1, v - w[i]) 两个解，也就是求解 f(i, 0...W) 只需要依赖于 f(i - 1, 0...W)，可把存储空间降到 O(N)。
func zeroOneKnapsackSpaceAdvance(w, p []int, N, W int) int {
f := make([]int, W+1)
for i := 1; i <= N; i++ {
for v := W; v > 0 && w[i] <= v; v-- {
// f(i, v) = max{ f(i - 1, v), f(i - 1, v - w[i]) + p[i]}
f[v] = max(f[v-w[i]]+p[i], f[v])
}
}
return f[W]
}
计算 f(i, v) 是从 W ==> 0 计算的，而不能是 0 ==> W。因为 f(i, v) 需要依赖 f(i - 1, v - w[i])，如果是从 0 ==> W 计算，有可能覆盖了 f(i - 1, v - w[i]) 从而丢失解记录。
题目描述：有 N 件物品，第 i 件物品的重量为 w[i]，价值为 p[i]，数量为 n[i]，背包承重为 W，要求最大化背包中物品的价值。
与 0-1 背包的区别：
在 0-1 背包，第 i 件物品只有两个选择，放入 or not。而多重背包，第 i 件物品可选择放入 0 ~ n[i] 件。
多重背包可以转化为 0-1 背包解决，将第 i 件物品，看成是 n[i] 件独立的，重量和价值等价的商品，可以直接复用 0-1 背包。
不把多重背包问题直接转化为 0-1 背包问题，拟定一个多重背包的状态转移函数：
f(i, v) = max(f(i - 1, v - k * w[i]) for k := 0...n[i] if v >= k * w[i])
func multiKnapsack(w, p, n []int, N, W int) int {
f := make([][]int, N+1)
for i := 0; i <= N; i++ {
f[i] = make([]int, W+1)
}
for i := 1; i <= N; i++ {
for v := 1; v <= W; v++ {
for k := 0; k <= n[i]; k++ {
if v >= k*w[i] {
f[i][v] = max(f[i-1][v], f[i-1][v-k*w[i]]+k*p[i])
} else {
f[i][v] = f[i - 1][v]
}
}
}
}
return f[N][W]
}
同样可以将空间复杂度降到 O(W)。
func multiKnapsackSpaceAdvance(w, p, n []int, N, W int) int {
f := make([]int, W + 1)
for i := 0; i <= N; i++ {
for v := W; v > 0; v-- {
for k := 1; k <= n[i] && v >= k * w[i]; k++ {
f[v] = max(f[v], f[v - k * w[i]] + k * p[i])
}
}
}
return f[W]
}
问题描述：有 N 件物品，每件物品数量有无数多个，第 i 件物品的重量为 w[i]，价值为 p[i]，背包承重为 W，要求最大化背包中物品的价值。
与多重背包有什么关联？
虽然物品的数量无上限，但是因为背包承重上限为 W，那么第 i 件商品最多只能够携带 W / w[i] 件，也就是完全背包可以转化为多重背包求解。只需要计算出每件物品的上限数量 n[i] = W / w[i] 就可以复用多重背包求解。
另一种方法是将有限资源（背包承重）的循环条件往外移动，确保背包的承重从小到大变化过程中保持局部最优解。
func comleteKnapsack(w, p []int, N, W int) int {
f := make([]int, W+1)
for v := 1; v <= W; v++ {
for i := range w {
if v >= w[i] {
f[v] = max(f[v], f[v-w[i]]+p[i])
}
}
}
return f[W]
}
Leetcode 377. Combination Sum IV
问题描述：有 N 件物品，每件物品数量为 1，第 i 件物品的重量为 w[i]，大小为 s[i]，价值为 p[i]，背包承重为 W，容量为 S，要求最大化背包中物品的价值。
与 0-1 背包有什么关联？
物品属性的维度不再是单一的，除了重量还有大小，但动态规划的思路是一样的：探索整个解空间，并且存储解记录。
定义函数：f(i, v, y) 为在背包承重为 v，容量为 y 的情况下，在 1 ~ i 物品中选择若干件，最大化背包中物品价值。
状态转移函数：
f(i, v, y) = max {
f(i - 1, v, y),
f(i - 1, v - w[i], y - s[i]) if v >= w[i] and y >= s[i] else 0
}
因为状态转移函数有三个变量，所以解空间大小为三维，需要一个三维数组存储解记录。
func multiDimensionKnapsack(w, p, s []int, N, W, S int) int {
f := make([][][]int, N+1)
for i := 0; i <= N; i++ {
f[i] = make([][]int, W+1)
for j := 0; j <= S; j++ {
f[i][j] = make([]int, S+1)
}
}
for i := 1; i <= N; i++ {
for v := 0; v <= W; v++ {
for y := 0; y <= S; y++ {
if v >= w[i] && y >= s[i] {
f[i][v][y] = max(f[i-1][v][y], f[i-1][v-w[i]][y-s[i]])
} else {
f[i][v][y] = f[i-1][v][y]
}
}
}
}
return f[N][W][S]
}
同样的，存储空间可做降维。
func multiDimensionKnapsackSpaceAdvance(w, p, s []int, N, W, S int) int {
f := make([][]int, W+1)
for i := 0; i <= W; i++ {
f[i] = make([]int, S+1)
}
for i := 1; i <= N; i++ {
for v := W; v > 0 && v >= w[i]; v-- {
for y := S; y > 0 && y >= s[i]; y-- {
f[v][y] = max(f[v][y], f[v-w[i]][y-s[i]]+p[i])
}
}
}
return f[W][S]
}
题目描述：有 N 件物品，第 i 件物品大小为 w[i]，背包容量为 W，问是否存在一种方案刚好塞满背包。
相似的问题：给出一个只有正数的数组 nums 和一个特定值 target，问 nums 的子序列是否存在数字之和为 target。
解决方案：对数组 nums 进行排序，创建一个数组记录某个值是否可达，经过所有遍历后，判断是否能够达到某个值。
如果原来该顶点已经可达，那么 f(i) = true；如果新发现能够到达 i 的路径，那么 f(i) = f(i - v)。
状态转移函数：
f(i) = f(i) || f(i - v)
func fullKnapsack(w []int, N, W int) bool {
// f mark every value is reachable or not.
f := make([]bool, W+1)
// 0 can be reach always
f[0] = true
// make sure every number will be used just once.
for _, v := range w {
// loop from W to 0
// if loop from 0 to W, every f[k * v] will be set true.
for t := W; t > 0 && t >= v; t-- {
f[t] = f[t] || f[t-v]
}
}
// judge
return f[W]
}
因为加法符合交换律，所以不需要对数组进行排序。
dp 的值除了可以记录是否可达（true / false）外，还能够记录到达该顶点的路径数。
到达该值的方法 = 新发现路径数量 + 旧路径数量
状态转移函数：
f(i) = f(i) + f(i - v)
func knapsackWaysCnt(w []int, N, W int) int {
f := make([]int, W+1)
f[0] = 1
for _, v := range w {
for t := W; t >= v; t-- {
f[t] += f[t-v]
}
}
return f[W]
}
Leetcode 416. Partition Equal Subset Sum
上述四种背包问题都采用动态规划解决，所有方案都没有效地缩小解空间，而是通过存储解记录，减少冗余计算。如果分析上述方案，会发现动态规划遍历整个解空间。
不足：如果物品的重量为浮点数，无法采用本博文方法解决。可复用动态规划思路，将浮点数转化为整数处理，但存储空间会被放大。
以下是我在字节跳动面试中遇到的一道算法题：
有 50GB 的 URL 文件，从中寻找出现次数前 10 的 URL，其中 URL 长度最大为 1024B，需要在一台内存为 2GB 的机器中完成。
PS: 面试官后面允许统计中可有一定的误差。
面试过程中回答的并不好。
解决思路：通过外部排序将 50GB 的 URL 进行一次排序，排序后相同的 URL 会相邻，然后扫描 50GB 的文件，统计每一个 URL 出现的次数，使用小根堆维护 Top 10 的 URL。
面试官显然不满意这个答案，问以上解决方案的空间复杂度和时间复杂度。
时间复杂度和空间复杂度的瓶颈都在外部排序上，假设使用归并排序实现外部排序，那么时间复杂度为 O(1024nlogn)，空间复杂度为 O(n)，也就是需要额外的 50GB 的磁盘空间。O(50GBlog(50GB)）≈ 1913614957980.12，即使 CPU 一秒能够执行 10亿 条指令，完成整个过程也至少需要 2000秒，如果加上磁盘频繁的读写，整个程序肯定会运行得很慢，这显然不是一个理想的解决方案。
如果有多台 2GB 内存的机器，可以借助 MapReduce 并行计算的威力。
如果 URL 大部分是重复的，那么 50GB 放入 2GB 内存中统计也是一个可以解决的方案，但是如果重复可能性不大，那么该方案也就无法在 2GB 内存中完成。
解决思路：每次从文件中读取一个 URL，对 URL 进行哈希，然后自增对应的哈希值，扫描一遍文件后，得出出现次数 Top 10 的哈希值，然后再对 50GB 文件做一次扫描，找出哈希值与 Top 10 哈希值一致的 URL，并对这些 URL 进行统计计数，由于哈希可能存在冲突，所以最后取出的 URL 不只有 10 个，再从这些 URL 中筛选出现次数 Top 10 的 URL。
假设每个 URL 都不同，且每个 URL 长度为 1024B，那么 50GB 里大概有 52428800 个 URL，大概需要 26 字节才能够标识每一个 URL（2^25 < 52428800 < 2^26），(2^30 * 8) - 52428800 * 26 = 7226785792，7226785792 / 8 / 52428800 ≈ 17，平均一个 URL 有 17字节做计数统计，足以做统计计数了。
哈希函数选择 MD5 足矣，MD5 有 128位，能够标识 340282366920938463463374607431768211456 个 URL，远超当前场景需求。
这个方案会在一个问题，可能不准确。
这是虎牙面试官给的思路，没错虎牙面试问了同一个问题。
如果能够将所有 URL 放进内存统计计数，那么这个这个问题也就迎刃而解。
内存不够一般做法：
这个方案主要是借助磁盘空间，需要 O(n) 的磁盘空间，在这一题中是 50GB，将 50GB 的大文件，切分为每一个大小大约为 1GB 的小文件，足以放进内存进行统计计数。
步骤：
Hash % 50 文件中。得到名为 0 ~ 49 大小约为 1GB 的文件解释：
m = Hash(x)，如果 x 一样，那么产生的 m 一定一样，也就是想同的 URL 一定被写入到同一个文件，方便统计计数缺点：如果 50GB 文件中 URL 比较凌乱，随机写 50GB 数据到磁盘性能是很差的。
优化：扫描 50GB URL 50次，每次写入 Hash(URL) % 50 == time 的文件，批量读写，每次读写的大小近可能以磁盘页为单位进行，将磁盘的随机读写转化顺序读写。
Trie 前缀树，树中的每一个节点都存储键的一部分信息，因为一个节点存储的信息可以被多个键复用，大大地降低了数据的冗余，提升存储效率。在判断英文单词前缀是否正确，匹配最长前缀等有应用。
面试时候想到这个方案，但是没有说出这种方案，因为假设 URL 平均长度为 20 个字符且仅包含 ASCII 编码的字符，那么 Trie 树的高度为 20，每一个节点有 255 个子节点，也就是 Trie 树子节点的数量大概为 255^20 == 1351461283755592687189686338827705478668212890625，不可能存储在 2GB 的内存中。
布隆过滤器的优点：不存储具体的键数据，借助多个稀疏哈希函数来对数据进行快速地检索，能够保证布隆过滤器判断键不存在的情况下，该键一定不存在；如果布隆过滤器判断键存在的情况下，该键以一个可以推算的概率判断它存在。
后面被问将 50GB 的数据映射到 2GB 内存中，布隆过滤器的错误率是多少。之前简单看过布隆过滤器的错误率计算公式，但是没理解清楚，没答上。知其然不知其所以然。我预估冲突概率的思路：
假设布隆过滤器占用内存为 1GB，有 10 个数组，每个数组长度约为 100MB 有 838860800位，能够标示 2^838860800 个元素，50GB URL 中大概有 52428800 个链接，每个 URL 通过稀疏哈希生成的 1 个数都 10 个，52428800 * 10 / (2^838860800) 错误率小到可以忽略。
解决思路：在内存中建立一个接近 2GB 大小的布隆过滤器，每取出一个 URL 都判断这个 URL 是否已经加入到布隆过滤器中，如果已经加入到就自增 URL 计数，否则将 URL 添加到布隆过滤器中。
上述方案最大的问题是如何以及在哪里进行统计计数。对于这个问题实在没有想到好的解决方案，能够想到的就是在磁盘上进行统计计数，说实话这个方案并不理想。
Count-Min Sketch 是布隆过滤器的变种，除了能够判断一个键是否存在外，还能够记录该键出现的次数，与本题目的要求非常符合。
Count-Min Sketch 适用于 Top K 都是出现次数非常多的，也就是与其他相差悬殊，但是如果每个 URL 出现次数相差不大，那么使用 Count-Mean-Min Sketch 会更好。
如果对于数据准确性要求更高，可通过 Count-Min Sketch 统计计数，将出现次数大于某个阈值的 URL 加入到堆中进行排序。
Lossy Count 有损计数，有可能产生误报，但是可以将误报控制在一定的概率下，建议点开博客链接查看具体算法实现。
大概步骤：
核心思想：通过不断地筛选，最后剩下的都是高频元素。
如果应用在本例 URL TopK 的筛选，将 50GB 平均分为 100 个窗口处理，每个窗口大小约为 0.5GB，先加载第一个窗口进内存，并对 URL 进行统计计数，依次加载 2 ～ 100 号窗口进内存，统计计数，所有 URL 统计数量 -1，如果 -1 后变为 0 就舍弃该元素（该元素很有可能不是高频的元素），统计合并完所有窗口后，剩下的元素中，通过排序或堆得出 TopK URL。
Redis 有一个基于概率的统计计数解决方案 HyperLogLog，该算法能够控制在 10^9 个元素下，只消耗 1.5KB 内存，且将错误率控制在 2% 以下。
上述很多方案都需要用到哈希运算，要注意的是不是所有哈希函数否符合条件的，对于布隆过滤器等应用应该选择 murmurhash 稀疏哈希（期待 0 远多于 1），而不是像 sha1、md5 这种每一位是 0 还是 1 的概率都是相等。
布隆过滤器、Count-Min Sketch以及 Lossy Count 都是基于概率的解决方案，能将保证误报率控制在某个阀值下，且相对其他绝对准确的解决方案，能够节省大量的内存以及处理时间。
Count-Min Sketch、Lossy Count 和 Redis HyperLogLog 在平常阅读博客中已经接触过，但是只是简单地知道它的存在，对两者没有很好的理解，关键时候没有联想到。还是书读的少，很多东西知其然不知其所以然（You don’t know what you can’t build.）。平时应该多关注其他公司比较先进的架构设计理念，成知识体系地看书。
在处理数据量大的情况下，应该借助位图、MapReduce和统计学方面的知识去解决问题。
对大数据下的统计计数感兴趣的可以参考：
Java 只允许单继承，创建类很少出现某些奇怪现象，但是 Python 支持多继承 不熟悉 MRO 有可能导致类无法被创建？不相信请尝试以下代码：
O = object
class X(O): pass
class Y(O): pass
class A(X, Y): pass
class B(Y, X): pass
class C(A, B): pass
具体原因设计到 MRO 所使用的 C3 算法，笔者有在下面展开分析。
以下代码在 2 和 3 都能够正常运行
class Child(Base):
def __init__(self):
super(Child, self).__init__()
以下代码只能在 3 运行
class Child(Base):
def __init__(self):
super().__init__()
super().__init__() 与 Base.__init__(self) 的区别思考以下以下两个代码片段可能产生的效果有什么区别：
# 1
class Child(Base):
def __init__(self):
super(Child, self).__init__()
# 2
class Child(Base):
def __init(self):
Base.__init__(self)
一定要使用代码片段 1，而不应该使用代码片段 2
super(Child, self) 可以减少硬编码为 Base如果 Python 的解析器能够帮助我们做的事情，我们为什么一定要硬编码？如果未来 Child 的父类改变了，忘了改 Base.__init__(self) 那就可能产生灾难。Python 是脚本语言并没有经过完整的编译，上述错误只有在运行时才能够被发现。
super() 可以实现多继承，造成可能像 C++ 一样出现基类重复的情况，C++ 的解决方案是虚基类，那么 Python 呢？Python 支持多继承，假设 class Child(Base1, Base2)，那么是不是手动一个一个地调用父类的 __init__ 方法，如以下丑陋且易错的代码：
class Child(Base1, Base2):
def __init__(self):
Base1.__init__(self)
Base2.__init__(self)
继承中一定要使用
super
如果你在生产环境采用了类似的代码，那么 code review 的时候很可能被公开批评，特别是在多继承的结构变得复杂以后，尤其容易出错。具体分析看下面的 MRO 介绍。
super() 是根据 MRO(Method Resolution Order) 计算的，而 Python 的 MRO 采用了 C3 算法。
有以下的类结构：
O = object
class F(O): pass
class E(O): pass
class D(O): pass
class C(D,F): pass
class B(D,E): pass
class A(B,C): pass
merge(abc, ac, co)
= a + merge(bc, c, co)
= ab + merge(c, c, co)
= abc + merge(o)
= abco
L[O] = O
L[F] = FO
L[E] = EO
L[D] = DO
上述三个我想读者都不会有异议。下面着重分析 C/B/A：
L[C] = C + merge(L[D], L[F], DF)
= C + merge(DO, FO, DF)
= CD + merge(O, FO, F)
= CDF + merge(O)
= CDFO
L[B] = B + merge(L[D], L[E], DE)
= B + merge(DO, EO, DE)
= BD + merge(O, EO, E)
= BDEO
L[A] = A + merge(L[B], L[C], BC)
= A + merge(BDEO, CDFO, BC)
= AB + merge(DEO, CDFO, C)
= ABC + merge(DEO, DFO)
= ABCD + merge(EO, FO)
= ABCDEFO
所以创建 A 类的 __init__ 和 __new__ 方法调用顺序为：A-->B-->C-->D-->E-->F-->O。
读者可以通过上述代码，通过 A.mro() 或 A.__mro__ 检验是否正确。
回到之前的问题，为什么 class C 是无法被创建的。
O = object
class X(O): pass
class Y(O): pass
class A(X, Y): pass
class B(Y, X): pass
class C(A, B): pass
继承树的结构如下：
O
/ \
/ \
X Y
/ \ / \
/____\/____\
A B
\ /
\ /
\ /
C
很容易产生错误的认识，如果创建类 C 不会产生问题，类似 C++ 中的虚基类初始化顺序为：O-->X-->Y-->X-->A-->B-->C，但事实上确实无法创建 class C。
按照上述 C3 算法计算 L[C]：
L[O] = O
L[X] = XO
L[Y] = YO
L[A] = AXYO
L[B] = BYX0
L[C] = C + merge(L[A], L[B], AB)
= C + merge(AXYO, BYXO, AB)
= CA + merge(XYO, BYXO, B)
= CAB + merge(XYO, YXO) # 无法继续计算
merge(XYO, YXO) 误解，因为 X/Y/O 三个元素都不满足以下两个条件：
所以 Python 无法确定其初始化的顺序，也就无法创建类 C。
__init__ 与 __new__ 的区别class A:
def __init__(self, *args, **kwargs):
super(A, self).__init__(*args, **kwargs)
def __new__(cls, *args, **kwargs):
return super(A, cls).__new__(cls, *args, **kwargs)
__init__ |
__new__ |
|---|---|
| 初始化实例的属性 | 创建实例 |
| 没返回值 | 有返回值 |
| 不需要传递 self | 需要传递 cls |
后于 __new__ 调用 |
先于 __init__ 调用 |
| 实例方法，第一个参数是 self | 类方法，第一个参数是 cls |
大多数情况下，我们是不需要重写父类的 __new__ 方法的，除非需要实现单例模式、不可变量等属性。元编程可以借助 __new__ 实现，后面有机会写一篇关于 Python 元编程的文章。
super().__init__() 并没有携带 self 参数，说明 super() 调用返回的是一个实例。
而为什么 super().__new__(cls) 需要附带 cls 参数呢？
那首先得知道 super() 到底返回的是什么，在不同情况下调用有什么不同的表现？
我写了这个小 demo：
from typing import Any
class A:
def __new__(cls) -> Any:
print('A.__new__')
s = super()
return s.__new__(cls)
def __init__(self):
print('A.__init__')
s = super()
s.__init__()
class B(A):
def __new__(cls) -> Any:
print('B.__new__')
s = super()
return s.__new__(cls)
def __init__(self):
print('B.__init__')
s = super()
s.__init__()
class C(B):
def __new__(cls) -> Any:
print('C.__new__')
s = super()
return s.__new__(cls)
def __init__(self):
print('C.__init__')
s = super()
s.__init__()
c = C()
通过打断点，逐个检查 super() 的返回值，以及每一个 __new__ 方法中的 cls 参数 和 __init__ 方法中的参数 self 的变化，我得出以下结论：
__new__ 方法先于 __init__ 方法执行super() 似乎每次都返回相同的值__new__ 返回不是本类的实例，__init__ 方法也就无法被调用__new__ 中方法的 cls 一直都是同一个 cls，也就是 cls 一直往下传递。我通过 id(cls) 来判断的，在 CPython 中，id 方法返回的是内存地址值，我发现 id(cls) 每次都返回同样的内容__init__ 中方法的 self 一直都是同一个 self，验证方法与 __new__ 一样也就是说 super() 是找到 MRO 中下一个父类的 __new__ 和 __init__ 进行调用。
发现了没，Python 类中如果重写了某个父类方法 fun(self)，但是在某个时刻我们需要调用父类的方法 fun，该如何处理呢？
假设父类为 Base，子类为 Child。除了可以使用 Base.fun(self) 调用外。还可以 super().fun()，当然这种方案只能够调用在 MRO 中紧跟 Child 的类的方法，但是如果我们想多跳几级呢？设 Base 的唯一父类为 SuperBase，我们需要在 Child 中调用 SuperBase 的实例方法，我们可以 super(Base, self).fun()。当然在代码中应该避免这样的调用，因为下次阅读代码需要再次计算 MRO，为了代码的可读性，应该这样调用：SuperBase.fun(self)。
在 stackoverflow 看到这样一个问题： old-style class 与 new-style class 区别
class A: x = 'a'
class B(A): pass
class C(A): x = 'c'
class D(B, C): pass
D.x # 'a'
class A(object): x = 'a'
class B(A): pass
class C(A): x = 'c'
class D(B, C): pass
D.x # 'c'
上述的结果我在 Python3.6 中都无法复现，但是我在 Python2.7 中复现了。因为 “old-style class” 只存在于 Python2，Python3 中只有 new-style class。new-style class 是在 Python2.1 后引入的，以下声明方法决定其是 new or old style：
# new
class A(object): pass
# old
class A: pass
没有 super，怎么调用多级的父类 __init__ 方法呢？
还记得我们有 mro() 方法，而且 super() 的初始化顺序就是按照 MRO 进行的。
如果没有 super()，可能需要写类似以下的代码：
class Child(Base):
def __init__(self):
mro = type(self).mro()
for next_class in mro[mro.index(Child)+1:]:
if hasattr(next_class, '__init__'):
# 调用实例方法
next_class.__init__(self)
break
在多继承中以下代码还能够正常运行吗？
可以。
最后举个错误例子：
class A:
def __init__(self):
print('A.__init__')
super(self.__class__, self).__init__() # 1
class B(A):
def __init__(self):
print('B.__init__')
super(self.__class__, self).__init__() # 2
在 2 处调用 super(self.__class__, self).__init__() 时候传递的参数 self 是 B 的实例，所以传递到 A.__init__ 1 处 self 依然是 B 的实例，super(self.__class__, self).__init__() 这条语句和 2 产生一样的效果，继续执行 A.__init__ 最后导致栈溢出。
刷算法题的时候很多时候遇到字符串操作问题，我比较喜欢使用 Python 或者 Golang 进行算法的实现，但是比较坑的一点就是 Golang 的字符串操作比较麻烦。
怎么麻烦？我举几个例子：
for _, x := range "hello" {
// x 的类型是 rune，其实就是对应字符的 utf8 编码
}
s = "刘曦光"
s[0] == uint8(229)
上面我标明是 uint8 的原因是 Go 是强类型语言，甚至没有像 C 一样的隐式转化。不同类型之间是不能够直接进行互操作的。比如 int 与 uint8 就无法比较大小。
len("刘曦光") == 9
返回的是底层字符串字节所占用的长度，而不是字符串中对应 utf8 字符的个数。
如果我想取字符串中的第 k 个字符该咋搞呢？
如果字符串只包含 ASCII 符号（ASCII 所有字符编码长度为 1Byte），那么我们完全可以使用下标解决：
s = "hello"
s[0] == byte('h')
s[1] == byte('e')
s[2] == byte('l')
s[3] == byte('l')
s[5] == byte('o')
但是如果遇到中文等 utf8 编码长度不止 1Byte 的呢？怎么办？
比较简单的解决方案：
func find(s string, index int) (rune, error) {
for i, v := range s {
if i == index {
return v, nil
}
}
return rune(0), errors.New("Out of range.")
}
求助 unicode/utf8 官方库的帮助，遗憾的是该库中也没有特别丰富的函数支持，但是总比我们自己写轮子好。
以下例子隐含：
import (
"unicode/utf8"
"fmt"
)
func main() {
s := "今天愚人节"
for i := 0; i < len(s); {
r, size := utf8.DecodeRuneInString(s[i:])
fmt.Print(string(r))
i += size
}
}
每次取字符串的一个切片，对字符串取切片的一个开销很小的操作，新的切片会引用原字符串。
func main() {
s := "今天愚人节"
for i := len(s); i > 0; {
r, size := utf8.DecodeLastRuneInString(s[:i])
fmt.Print(string(r))
i -= size
}
}
func main() {
s := "今天愚人节"
fmt.Println(utf8.RuneCountInString(s))
}
int main() {
s := "今天愚人节"
fmt.Printf("%q", string([]rune(s)[3])) // "人"
}
这里我们先把字符串 s 转化为 []rune 类型，也就是相当于把字符串中的每一个 utf8 字符解码出来。如果字符串长度不是非常大的话，建议先将 string 转化为 []rune，但如果字符串很大的场景下，这个方法并不适用
改良版
func stringIndex(s string, index int) (rune, error) {
c := 0
for i := 0; i < len(s); c++ {
r, size := utf8.DecodeLastRuneInString(s[i:])
if c == index {
return r, nil
}
i += size
}
return 0, errors.New(fmt.Sprintf("index=%d len(s)=%d index out of range", index, c))
}
unicode/utf8 下的方法并不是很丰富，在刷算法题中可能用到的就是上面几个，上面对应的 string 方法都有一个面相 []byte 的版本。
每个语言都会有非常丰富的对应字符串的操作方法集和，Go 的字符串操作在 strings 包。
以下简单介绍以下 strings 的基本操作
最简单的方法是使用 < > == >= <= 等操作符实现，非常灵活。
也可以使用 strings.Compare(a, b string) 方法实现，直接使用操作符返回的是 bool 值，而 strings.Compare 返回 -1 0 1 三者之一。想到什么没有？可以使用 switch 语句，减少大量的 if-else 语句。
func main() {
a, b := "hello", "world"
switch strings.Compare(a, b) {
case 0:
fmt.Printf("%q==%q", a, b)
case -1:
fmt.Printf("%q<%q", a, b)
case 1:
fmt.Printf("%q>%q", a, b)
}
}
这个问题是不是与搜索字串及其下标很相似？
strings.Contains(s, substr string) bool
判断字符串是否包含某个字符集和
strings.ContainsAny(s, chars string) bool
没错，判断是否包含子串就是搜索子串下标，然后判断搜索下标是否为 -1。
fmt.Println(strings.EqualFold("hello你好", "HELLO你好")) // true
fmt.Println(strings.EqualFold("hello", "world")) // false
通过 unicode.IsSpace 判断是否是空白字符，然后通过空白字符进行切割
fmt.Println(strings.Fields("hello\tworld 你好\n世界"))
// [hello world 你好 世界]
如果需要进行切割的不是空白字符，需要自定义方法怎么办？
fmt.Println(strings.FieldsFunc("hello world", func(r rune) bool {
return r == ' '
}))
// [hello world]
判断是否包含前缀
fmt.Println(strings.HasPrefix("hello world", "hello")) // true
判断是否包含后缀
fmt.Println(strings.HasSuffix("hello world", "world")) // true
fmt.Println(strings.Index("hello world", "world")) // 6
上面例子是第一个出现的位置，下面这个例子我们求最后一次出现的位置
fmt.Println(strings.LastIndex("hello world", "l")) // 9
如果我们要求符合某个特别条件的字符的位置呢？
fmt.Println(strings.IndexFunc("hello world", func(r rune) bool {
return r + 1 == 'e'
}))
对应的也有 strings.LastIndexFunc(s string, f func(r rune) bool)
如果我们有一个字符串slice []string，将他们拼装起来，并且指定分隔符
fmt.Println(strings.Join([]string{"hello", "world"}, "/")) // hello/world
fmt.Sprintf() 为我们提供了非常强大的拼装字符串的能力，而且能够指定输出的格式，与 fmt.Printf 类似，不同的是前者返回格式化后的字符串，后者将该字符串写入到标准输出流。比如将十进制数转化为对应的二进制字符串：
s := fmt.Sprintf("%b\n", 100)
fmt.Println(s) // 1100100
如果使用过 Python 的 map filter reduce 函数的会觉得这样用起来写代码非常舒服，不用写很多循环，数据像是管道一样流动。
Go 对字符串也有对应的支持，下面演示一个对简单的凯撒密码实现：
func Caesar(s string) string {
return strings.Map(func(r rune) rune {
if 'a' <= r && r <= 'z' {
r -= 3
if r < 'a' {
r += 26
}
}
return r
}, s)
}
fmt.Println(strings.Split("hello world", "l")) // [he o wor d]
上面例子会把所有含有子串的都切割开，但是如果我们只是想切割指定数量的字符串呢？
fmt.Println(strings.SplitN("hello world", "l", 2)) // [he lo world]
要求高一点想要保留子串怎么办？
fmt.Println(strings.SplitAfter("hello world", "l")) // [hel l o worl d]
类似的，指定相应切割数量对应的方法：
fmt.Println(strings.SplitAfterN("hello world", "l", 2)) // [hel lo world]
增长字符串除了 + 运算符，strings.Join 方法还可以使用以下方法：
fmt.Println(strings.Repeat("i", 10)) // iiiiiiiiii
这个功能手写也很简单，但是有轮子就别重复造了
func ToLower(s string) string
func ToUpper(s string) string
Go 官方文档给出了一个例子，还可以自定义大小写转化的映射，有特殊需求的同学可以实现 unicode.SpecialCase。
func ToLowerSpecial(c unicode.SpecialCase, s string) string
func ToUpperSpecial(c unicode.SpecialCase, s string) string
对应的还有 strings.ToTitle
fmt.Println(strings.Count("hello world", "l")) // 3
func Trim(s string, cutset string) string
Trim 还有很多变种，比如 TrimPrefix、TrimSuffix 等。
fmt.Println(strings.Replace("hello world", "l", "L", 2)) // heLLo world
strconv 下是一些字符串与其他基本类型的转换，如整数、浮点数与字符串之间的转换。
Atoi / Itoa 与 C 语言中的字符串与整形之间的转换非常像：
s := strconv.Itoa(-100) // "-100"
i, _ := strconv.Atoi("-100") // -100
因为字符串转化为整形有可能输入值不合法，所以 Atoi 方法会返回一个错误值。
strconv.ParseXxx 将字符串转化为相应类型的数据：
b, _ := strconv.ParseBool("true")
f, _ := strconv.ParseFloat("3.1415926", 64) // 最后一个参数指明 float 的 bitSize
i64, _ := strconv.ParseInt("-100", 10, 32)
在字符串转化为整数可以指定进制，比如十进制、二进制、十六进制等等….虽然可以 bitSize 参数，但是返回的值还是 int64 类型。
二进制：
bin, _ := strconv.ParseInt("1001", 2, 64) // 9
十六进制：
hex, _ := strconv.ParseInt("1a", 16, 64) // 26
注意这里不能改写为 0x1a，如果加上 0x 或者 0X 前缀则无法解析。但可以加 0 前缀，比如改写为 01a。
八进制：
oct, _ := strconv.ParseInt("-017", 8, 64) // -15
类似十六进制、二进制，八进制也可以加 0 前缀，负数只需要再追前面加上 - 即可。
字符串转化为整数不能够出现小数点，也就是不能够输入一个浮点数格式的字符串。
无符号数的转换：
u64, _ := strconv.ParseUint("100", 10, 64) // 100
u64, err := strconv.ParseUint("-100", 10, 64) // 0
如果无符号数转化中，字符串中形式是有符号的，则返回错误值，并且返回无符号数的零值也就是 0。
strconv.FormatXxx 与 strconv.ParseXxx 相反。其功能也可以通过 fmt.Sprintf 实现，strconv.FormatXxx 的相对优点是指定参数更加灵活，不需要写死到字符串中。
b := strconv.FormatBool(true) // "true"
f := strconv.FormatFloat(3.1415926, 'f', 10, 32) // "3.1415925026"
字符串的转化函数的参数比较多，具体可以参考文档
i := strconv.FormatInt(100, 2) // "1100100"
i = strconv.FormatInt(-100, 16) // "-64"
u := strconv.FormatUint(10, 2) // "1010"
工欲善其事，必先利其器
学习中、工作中需要掌握某些有利于提升我们效率的工具，比如对 IDE 快捷键、语言的标准库、第三方库等，要好好利用前人载的树来乘凉。Python 为什么在数据科学等领域如此火热呢？我想除了其自身特性外，更中要的是丰富的第三方库支持。很多不是 Python 开发的工具都有 Python 的接口实现，比如著名了 Tensorflow。
学习不仅需要花大量时间，更重要的是提升效率。
使用 Golang 做算法题让我不禁怀念 Python 的语法糖