算法

LSM 和 sstable

# 核心要点

lsm 是 bigtable、leveldb、rocksdb 等数据库采用的算法。

硬盘,尤其是机械硬盘,顺序写入性能远大于随机写入性能,所以 lsm 把大量的随机写入抓换成了顺序写入,从而极大地又花了写入能力。同时查找效率收到了损伤。

适用于顺序写入多,随机读取少的场景。

之所以要使用 Immutable Memtable,就是为了避免将 MemTable 中的内容序列化到磁盘中时会阻塞写操作。

## 操作

1. 插入

写入 WAL,然后操作 memtable。WAL 是顺序读写,而memtable 是跳表,操作都很迅速

2. 更新

和插入其实是一样的操作

3. 删除

插入一条特殊的删除日志,在 memtable 中标记删除

4. compaction(压缩)

当 memtable 达到设定的阈值的时候,会写入到 immutable memtable,然后写入到硬盘上的 sstable。当 sstable 的数量达到某个阈值的时候,就合并到下一级的 memtable。需要注意的是只有第一级的memtable可能有重复的键值,其他层都不会有重复的,所以可以多线程 compact。

5. 读取

最原始的算法:首先从memtable读,然后从sstable中往高层读取。

可以采取的优化方法:

1. 把 sstable 的一些原始信息放到 manifest 中,放在内存中,快速查找
2. 使用 bloom filter 先过滤一遍,看 key 是否在 LSM 中,然后再查找。

一图胜千言:

![](https://ws3.sinaimg.cn/large/801b780aly1ftt76pvzotj21kw13eh8u.jpg)

参考:

1. http://blog.fatedier.com/2016/06/15/learn-lsm-tree/

红黑树

红黑树的要求:

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色(叶子是NIL节点)。
4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

![](https://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/900px-Red-black_tree_example.svg.png)

两篇不错的教程:

1. [漫画:什么是红黑树](https://juejin.im/post/5a27c6946fb9a04509096248)
2. [维基上的红黑树](https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91)

动态规划(LeetCode 413. Arithmetic Slices)

# LeetCode 413. Arithmetic Slice

是一道可以用动态规划解的问题

## 题目

给定一个数组,找出其中等差数列的个数。等差数列的定义:3各元素以上,每个元素之间差相等。

比如:

“`
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
“`
下面的就不是:

“`
1, 1, 2, 5, 7
“`

例子:

“`
A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
“`

## 解法

观察发现,当我们遍历数组的时候,如果能和前一个元素构成等差数列,那么在这个位置可以构成的等差数列的个数就是上一个位置加一,所以的到递推公式:

“`
dp[i] = dp[i-1] + 1
“`

借用官方答案里的图片:

![](https://ws4.sinaimg.cn/large/006tNc79ly1ftjiweuvyaj317m0homzj.jpg)

所以我们就得到了答案:

“`
class Solution:
def numberOfArithmeticSlices(self, A):
“””
:type A: List[int]
:rtype: int
“””
dp = [0] * len(A)
for i in range(2, len(A)):
if A[i] – A[i-1] == A[i-1] – A[i-2]:
dp[i] = dp[i-1] + 1

return sum(dp)
“`

大规模字符串的匹配

问题:假设我们有一组比较长的文本,每一个文本都有几十k左右,还有一些敏感关键词需要删除,大概有几千,然后需要在这些文本中把关键词找出来。

# 方法1:暴力搜索

“`
import re

compiled_words = [re.compile(r’\b’ + word + r’\b’) for word in my20000words]

for sentence in sentences:
for word in compiled_words:
print(re.sub(word, “***”, sentence))

“`

# 改进1:把正则组合起来

“`
pattern = “\b(word1|word2|word3)\b”

for sentence in sentences:
print(re.sub(pattern, “***”, sentence))
“`

# 改进2:使用 Trie 优化正则

对于数组:[‘foobar’, ‘foobah’, ‘fooxar’, ‘foozap’, ‘fooza’],使用上面的方法,我们可能会写出正则:

“`
“\b(foobar|foobah|fooxar|foozap|fooza)\b”
“`

但是这并不是最优的正则,应该使用前缀树的思想来合并单词,形成下面的正则:

“`
r”\bfoo(?:ba[hr]|xar|zap?)\b”
“`

具体的方法可以看这里:https://stackoverflow.com/a/42789508/1061155

# 改进3:基于集合的搜索

“`
import re

def delete_banned_words(matchobj):
word = matchobj.group(0)
if word.lower() in banned_words:
return “”
else:
return word

word_pattern = re.compile(‘\w+’)

for sentence in sentences:
sentence = word_pattern.sub(delete_banned_words, sentence)
“`

参考:

https://stackoverflow.com/questions/42742810/speed-up-millions-of-regex-replacements-in-python-3/42789508

https://medium.freecodecamp.org/regex-was-taking-5-days-flashtext-does-it-in-15-minutes-55f04411025f

跳表(skiplist)

平衡二叉树可以实现 O(logn) 的查找复杂度。跳表可以实现相当于平衡二叉树的复杂度查询数据,而代码实现比较简单。在 Redis 中,zset 就用到了 skiplist。

跳表是用**并连的链表**来实现的查询结构

![](https://ws3.sinaimg.cn/large/006tNc79gy1fq102txkvvj30hs07haaf.jpg)

* 每个节点包含的指针的层数是由一个随机数决定的。
* 跳表的时间复杂度和平衡二叉树相同,但是在实现上要简单很多。
* 跳表是有序的,跳跃表的特点就是有序的,所以对于一些有序类型的数据,比如整数,日期这种,用跳跃表可以进行范围查找。
* 在构建跳跃表和查询跳跃的复杂度一致,所以也比较适合于在线的实时索引查询,可以来一个文档,一边查找就一边知道要如何进行插入操作了。
* 保存到磁盘和从磁盘载入也比较简单,因为本质上是几个链表,所以保存的时候可以按照数组的方式分别保存几个数组就可以了。

# 一些优化

空间优化,把底层的表放到硬盘里,影响增加删除节点的效率

![](https://ws4.sinaimg.cn/large/006tNc79gy1fq1043qhraj30hs06i3zn.jpg)

时间优化,用数组代替链表,可以使用二分查找而非遍历

![](https://ws4.sinaimg.cn/large/006tNc79gy1fq104leytgj30hs06j0tf.jpg)

对于类似时间这种数据,比如24小时对应1440分钟对应86400秒钟

甚至可以固定直接用索引随机访问

![](https://ws3.sinaimg.cn/large/006tNc79gy1fq106sqt91j30hs06j758.jpg)

# 实现

https://github.com/begeekmyfriend/skiplist/blob/master/skiplist.h

simhash

# shingling

n-shingling 就是把一个句子或者文章分成 n 个连续单词的组合,然后去重。

比如: the cat sat on the cat

第一步,分组: the cat, cat sat, sat on, on the, the cat
第二步,去重: the cat, cat sat, sat on, on the

simhash 计算过程

生成 shingle

# Reference

[1] http://matpalm.com/resemblance/jaccard_coeff/

[2] http://blog.csdn.net/c289054531/article/details/8082952 中文解释

Jaccard coefficient(杰拉德距离)

the jaccard index is a simple measure of how similiar two sets are.
it’s simply the ratio of the size of the intersection of the sets and the size of the union of the sets.

eg.
“`
if J(A,B) is jaccard index between sets A and B
and A = {1,2,3}, B = {2,3,4}, C = {4,5,6},
then J(A,B) = 2/4 = 0.5,
and J(A,C) = 0/6 = 0,
and J(B,C) = 1/5 = 0.2
so the most “similiar” sets are A and B and the least similiar are A and C
(note also J(A,A) = J(B,B) = J(C,C) = 1)
“`

we have to consider what the values(jaccard coefficient) would be in real world. how are the distributed.

Jeccard coeffi is not transtive, so, for a set of n sentences, we have to calculate O(n2) times. There is a way to do it in O(n) time

map N-grams to a set of numbers, then use bit to express whether the N-gram exists in one word/sententce.

“`
A = mat -> {ma, at} \ / 101 \
–> {ma(2), ca(1), at(0)} -> –> &(001), |(111)
B = cat -> {ca, at} / \ 011 /

“`

J(A, B) = and(A, B)/or(A, B)

let X = card(A ^ B), let U = card(A U B)
let J(A, B) = X / (X + U)

动态规划

贪心算法在每一步都会做出局部最优解, 这样通常会很高效

如果每个阶段的决策都和状态无关,那么就是贪心算法

如果需要把整个解空间都遍历一遍,那么就是穷举

如果可一个根据上一步的结果的出下一步的结果,可以使用动态规划

以下转载自:https://www.zhihu.com/question/39948290/answer/155958549

# 1.动态规划是什么?

答:动态规划是一种通过“大而化小”的思路解决问题的算法。区别于一些固定形式的算法,如二分法,宽度优
先搜索法,动态规划没有实际的步骤来规定第一步做什么第二步做什么。所以更加确切的说,动态规划是一种
解决问题的思想。这种思想的本质是,一个规模比较大的问题(假如用2‑3个参数可以表示),是通过规模比
较小的若干问题的结果来得到的(通过取最大,取最小,或者加起来之类的运算)所以我们经常看到的动态规
划的核心——状态转移方程都长成这样:

* f[i][j] = f[i ‑ 1][j] + f[i][j ‑ 1]
* f[i] = max{f[j] if j < i and …} + 1 * f[i][j] = f[0][j ‑ 1] && judge(1,i) || f[1][j ‑ 1] && judge(2,i) || … # 2.动态规划面试考得多么? 答:多。并且越来越多。随着CS从业与求职者的增加,并伴随大家都是“有备而来”的情况下,一般简单的反转 链表之类的题目已经无法再在面试中坚挺了。因此在求职者人数与招聘名额的比例较大的情况下,公司会倾向 于出更难的面试问题。而动态规划就是一种比较具有难度,又比较“好出”的面试问题。相比其他的算法与数据 结构知识来说,贪心法分治法太难出题了,搜索算法往往需要耗费求职者过长的程序编写时间一般也不倾向于 出,二叉树链表等问题题目并没有那么多,而且求职者也都会着重准备这一块。因此动态规划这一类的问题, 便越来越多的出现在了面试中。 # 3.动态规划快在哪儿? 答:动态规划一般来说是“高效”的代名词,因为其解决的问题一般退而求其次的算法只有搜索了。以“数字三 角形”一题为例子(lintcode.com/problem/tr) ,在“三角矩阵”中找一条从上到下的路径,使得权值之和最 小。如果使用暴力搜索的算法,那么需求穷举出2^(n‑1)条路径(n为三角形高度),而使用动态规划的话,则 时间复杂度降低到了n^2,完成了质的飞跃。那么究竟为什么这么快呢?原因在于动态规划算法去掉了“无用和 重复的运算”。在搜索算法中,假如从A‑>B有2条路径,一条代价为10,另外一条代价为100,B‑>终点有1024
条路径。当我们选择了代价为10的那条路径走到B时,可以继续往下走完1024条路径到终点,但是在此之后,
我们再从代价为100的路径从A走到B时,我们可以发现此时无论如何走,都不可能有刚才从10的路径走过来更
好,所以这些计算是“无用”的计算,也可以说是“重复”的计算。这就是动态规划之所以“快”的重要原因。

# 4.学习动态规划有什么捷径?

答:我们将动态规划的常见类型分为如下几种:
* 矩阵型
* 序列型
* 双序列型
* 划分型
* 区间型
* 背包型
* 状态压缩型
* 树型
其中,在技术面试中经常出现的是矩阵型,序列型和双序列型。划分型,区间型和背包型偶尔出现。状态压缩
和树型基本不会出现(一般在算法竞赛中才会出现)。
每种类型都有着自己的题目特点和状态的表示方法。以矩阵型动态规划为例,一般题目会给你一个矩阵,告诉
你有一个小人在上面走动,每次只能向右和向下走,然后问你比如有多少种方案从左上走到右下
(lintcode.com/problem/un)。这种类型状态表示的特点一般是使用坐标作为状态,如f[i][j]表示走到(i,j)这个位
置的时候,一共有多少种方案。状态的转移则是考虑是从哪儿走到(i,j)这个坐标的。而序列型的动态规划,一
般是告诉你一个序列;双序列的动态规划一般是告诉你两个字符串或者两个序列。
将所做过的动态规划问题按照这些类别进行归类,分析状态的表示方法和状态转移方程的构造方法在每种类型
中的近似之处,会让你更快的学会动态规划。

# 5.什么样的问题适合使用动态规划?
答:可以使用动态规划的问题一般都有一些特点可以遵循。如题目的问法一般是三种方式:

1. 求最大值/最小值
2. 求可不可行
3. 求方案总数

如果你碰到一个问题,是问你这三个问题之一的,那么有90%的概率是使用动态规划来求解。
要重点说明的是,如果一个问题让你求出“所有的”方案和结果,则肯定不是使用动态规划。

# 6.解决一个动态规划问题的步骤是什么?
答:首先根据“问5”判断是否是动态规划的问题,如果是,则尝试将其按照“问4”进行分类,找到对应的类别和
相似的问题。接着从下面的4个要素去逐步剖析解决这道题:

1. 状态是什么
2. 状态转移方程是什么
3. 状态的初始值是什么
4. 问题要求的最后答案是什么

每个步骤分析完成之后,就基本上解决了整道动态规划的问题。

# 7.怎么优化动态规划的时间?
答:一般来说,使用动态规划求解的问题,时间上已经比暴力搜索要优化很多了。但是仍然存在着一些可以优
化的空间。通常来说,动态规划的时间优化,有如下两种常见的方式:

1. 通过变换状态优化
2. 通过决策单调优化

对于通过变换状态来优化的问题比较难,需要一些经验和灵感。而对于决策单调的优化,则比较简单,但适用
范围不广,一般只适用于划分型动态规划当中,通常这个方法可以将复杂度降低一个数量级。

# 8.怎样优化动态规划的空间?

答:动态规划的空间优化往往采用滚动数组优化。以一个二维的动态规划为例子。假如状态转移方程如下:
“`
f[i][j] = f[i ‑ 1][j] + f[i][j ‑ 1]。
“`
我们可以发现,第i层的状态,已经和第i‑2层的状态没有关系了,那么这种情况下,用于存储第i‑2层的空间就可以被重复利用。方法非常简单,把数组的第一维对2取模就可以了:

“`
f[i % 2][j] = f[(i ‑ 1) % 2][j] + f[i % 2][j‑1]。
“`

这种方法通常可以将空间复杂度降低一个数量级。

# 9.有什么书籍和参考资料可以推荐么?

著名的背包九讲:
vdisk.weibo.com/s/tanGy (也可以直接在网上搜索背包九讲)

# 10.有哪些动态规划题目必须要练习的?

在LintCode上包含了30余道动态规划的练习题,都是从实际的面试问题中汇总的精选练习:
lintcode.com/tag/dynami

所以,动态规划自学并不难,关键是你要掌握学习的方法。
如果你觉得我说的很有用,欢迎关注我的微信公众号:ninechapter,里面有海量的算法题等你领取~

## 基础介绍

http://www.hawstein.com/posts/dp-novice-to-advanced.html

## 数组分割问题

http://www.cnblogs.com/liyukuneed/archive/2013/05/27/3090454.html