这里的内容来自对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属性"
链接的地址可以使用相对路径,链接名的定义可以任意位置。
图像的语法和链接的类似,只是在比链接多一!
放在链接文本[]
的前面:
![图像替代文字](图像地址 "可选的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 的语法糖