关于算法，那些你不知道的事

时间：2021-11-27 19:36:40

关于算法，那些你不知道的事

1.算法，不止于刷题

提到算法，不管是科班出身还是半路出家的程序员可能都会说上几句，算法谁没学过谁不知道啊？对于走工业界路线而非学术路线的同学来说，算法学习的最大作用也许是找工作…… 毕竟工作后，绝大多数时候都用各种成熟的类库，少有自己实现高级数据结构和算法的时候。但刚结束一学期修的算法课，上得我还真跟没学过算法似的，让我大开眼界，虽然每次课上我都听的不是很懂，但每节都期盼着老师又能带来什么新奇的东西。一点点发现，原来竟然还有这么多很有用却从来没学习过甚至没听过的算法和数据结构啊！

这些可以算作比较前沿的研究成果了，而且又不是离我们的日常工作非常遥远的纯理论，所以个人觉得这些知识非常值得学习，哪怕只是了解一下开拓思路。参考资料的话，除了下面每节提到的具体论文外，系统介绍这些高级算法和数据结构的书还真是凤毛麟角，不过还真发现了一本：Peter Brass的《Advanced Data Structures》。此外的话，就是老老实实地看原作者或分析得比较好的论文，这也是这学期练成的一项能力。当然，有的论文挺难的，我们可以节选着看，大多数时候还是看的挺享受的！

2.随机化算法（Randomized Algorithms）

随机化（Randomization）是这门课的重点，也是以前一直忽略了的，现在却发现非常重要的算法设计策略。在《Introduction to Algorithm》（这门课的教材）中有一些系统的讲解和举例，但这本经典教材毕竟不是专门讲随机化算法的。专攻于这一方面的经典书籍是Motwani Raghvan的《Randomized Algorithms》，以及稍微现代化一些的《Probability and Computing: Randomized Algorithms and Probabilistic Analysis》，但对于我来说，这两本真的都太难了！如果像我一样只是有些感兴趣，想稍微系统了解一下的话，推荐认真学习一下《Algorithm Design》中第13章随机化算法就可以了，这一章内容从基本定义、w.h.p.、到常见随机化算法和数据结构的分析，已经足够详细了～

2.1 Randomized Quicksort

就像归并排序的关键在Merge函数一样，快速排序性能的关键就在Partition函数。但因为我们无法控制输入数据的样子，所以这时一般求助于随机化思想。随机化快速排序采取的策略有两种：1）随机选取Pivot；2）随机采样三个数取中位数。两种方式都能达到O(nlogn)。第一种方式的证明在CLRS中有详细解释，第二种方式在书中是以Problem习题形式出现的。当时在课上老师直接将这个看似挺难的问题分析，轻描淡写地转化到了掷硬币模型中，四两拨千金，给人感觉很震撼！

推荐阅读：这两种方式在《Introduction to Algorithm》中有详细的性能分析，也可以通过《Algorithm Design》补充学习，里面的证明方法能稍微容易理解一些。

2.2 Skip List

因为之前工作中重点研究过Redis的缘故，所以对Skip List有些了解，Redis中Dictionary数据结构就是用Skip List而没采取红黑树的方式实现的。当时了解是因为Skip List实现简单、缓存locality好等，但不清楚原来跳表是一种随机化数据结构。每个新插入的Key是通过反复投掷硬币（Flip a fair coin）来决定是否将其Promote到向上一级。怎么样，挺有意思的吧！但奇怪的是，很多算法书里都对Skip List只字未提，包括后面要讲到的在大型分布式系统中非常重要的Bloom Filter。

关于算法，那些你不知道的事

推荐阅读：

  1. 作者论文：《Skip Lists: A Probabilistic Alternative to Balanced Trees》
  2. 实现：Sedgewick的《Algorithm in C, 3rd edition》中13.5节。
  3. 基于CLRS的MIT课件对Skip List进行了补充，讲解的也非常棒（强烈推荐！）！

2.3 Universal Hashing

通常来说，一个精心选取的哈希函数是可以良好工作的，但在一些极端情况下，例如有人知道你的哈希机制，并故意制造大量哈希冲突时就行不通了。这并不是天方夜谭，2012年时就真的发生过，包括PHP、Java、Python等几乎所有主流平台都中招了，详细请看《Hash Collision DoS问题》。所以一种防御方法就是，不只使用一个哈希函数，而是一族函数，每次需要使用时都这一族函数中随机选取一个。

推荐阅读：

  1. 《Introduction to Algorithm》中Universal Hashing和Perfect Hashing两节。
  2. 基于CLRS的MIT课件讲解的也非常棒！

2.4 Bloom Filter & Cuckoo Filter

以前在《大数据：互联网大规模数据挖掘与分布式处理》一书中曾听说过Bloom Filter，但一直以为是一个很高级很难理解的算法。经过老师详细分析讲解后发现，原来这么简单，而且真的太有用了！它就像我们日常使用的无处不在的哈希表一样，可以与许多数据结构组合起来使用。其核心就是：在判断数据是否存在于集合的问题中，如果否定答案占绝大多数，那么它将使用很少的空间帮你实现目的。偶尔碰到肯定答复时，BF给出的只是不确定（False positive），这时就要去查BF背后的真正数据了。

而Cuckoo Filter是CMU的一位中国同学实现的，它巧妙地运用Fingerprint、Multi-choice哈希等技术，主要解决BF的痛点：无法删除或扩展（resize），只能推倒重建，以及数据locality不好，会大量产生随机I/O。

推荐阅读：

  1. 论文（强烈推荐！）：《Theory and Practice of Bloom Filters for Distributed Systems》
  2. 论文：《Cuckoo Filter: Practically Better Than Bloom》

2.5 Robin-Karp String Matching

关于字符串匹配，老师没有讲更有名的KMP算法，也是看中了Robin-Karp算法中的随机化思想：充分利用已经遇见过的“字符”形成Rolling哈希，减少浪费（这也是很多高效算法的常用策略，例如Trie树也是如此）。而且对于匹配的判断与前面介绍过的Bloom Filter有些类似，也会产生False positive。CLRS中给出了详细的讲解和证明。

推荐阅读：《Introduction to Algorithm》中对应章节。

2.6 Treaps

就像我们用两种版本的随机化保证Quicksort的性能一样，Treaps是对二叉搜索树的“保护”。它通过给每个Key额外随机分配一个Priority数，插入新数据时会让树根据Key保证BST的性质，同时根据随机分配的Priority保证堆特性，达到树的平衡。所以从名字就能看出，Treap=Tree+Heap。

推荐阅读：《Introduction to Algorithm》中是作为Problem习题出现的。

2.7 Matrix Product Equlity Testing

这是当时老师留的作业里的一道题，很神奇的一道题，推荐大家看一下，真的可以从中看出随机化的魅力！证明方式与Universal Hashing一样，采用了所谓的Deferred Principle。具体我也不太懂，大意是固定住其他所有变量的值只保留一个“*”变量，得出这种特殊情况的结果后再看这种特殊情况有多少种（即刚才固定住的那些变量有多少组合方式），从而简化了证明。感觉有些难，等有时间要系统学习一下概率问题的证明方法。

推荐阅读：

  1. 《Matrix-Product Verification》
  2. 《Verifying matrix multiplication》
  3. Deferred Principle：《Events and Probability (verifying matrix multiplication, randomized min-cut)》

3.并行算法（Parallel Algorithms）

并行计算也是当前的一个热点，作为初学者，我们最好的资料就是《Introduction to Algorithm》。它首先介绍了Work、Span、Parallelism三个基本概念和相关定理，简单来说Work就是单核运行时程序的性能，而Span就是在有无限核心的平台上运行程序时的性能，最后两者的比例就是Parallelism，即程序的最大并行度。要实现并行化主要有三个原语：Parallel-loop、Spwan、Sync。书中重点分析了矩阵相乘和归并排序，这两个很常见算法的并行化版本。

4.外存算法（External Memory Algorithms）

尽管RAM模型是我们最熟悉的模型，但它并不是万能的，例如在分析外部存储相关算法时就有些无能为力。因为与外部存储的I/O延迟相比，RAM分析的内存操作渐近复杂度可以忽略不计了。正出于这个原因，在考虑外部存储时，我们会采用另一种分析模型——DAM。重点分析与磁盘的数据交换次数，即I/O数。

我们可以把最常见算法的数据结构放到DAM模型中去分析，例如线性搜索、二分查找，还有最重要的K-Way合并算法（在如数据库的JOIN等有广泛应用）。找到些感觉后，再分析复杂一些的矩阵相乘、B-Tree、LSM-Tree、B^epsilon-Tree等。

因为之前只了解B-Tree与外存有关，当系统学习到许多外存算法时还以为这是个比较新的话题。实际却是，像Hash表的Linear Probing早在上世纪70年代，Knuth就在《The Art of Computer Programming》（TAOCP）中有详细的研究，还真是孤陋寡闻了！

推荐阅读：

  1. Pagh整理的手册（强烈推荐！）：《Basic External Memory Data Structures》
  2. Stony*课件：《Analyzing I/O and Cache Performance》

5.写优化数据结构（Write-Optimized Dictionaries, WODs）

写优化可以看做是一种很重要的设计策略，即Buffer缓冲区的思想。问题背景就是B-Tree家族的普遍问题，每次插入都会将新加入Key放置到最终位置，从而导致插入性能瓶颈。而WODs家族的数据结构使用缓冲思想，将树内部结点中的一部分划出来当作缓冲区，当插入数据时先暂存到缓冲区，之后再一点点Flush到Key应去的位置。WODs家族的成员有Buffer Tree（这应该是应用这种策略比较早也比较原始的一种树了）、谷歌的应用了缓冲和级联两种思想的Log-Structured Merge Tree (LSM-Tree，广泛应用于HBase、Cassandra、LevelDB等流行软件)、Stony*老师研究出的B^epsilon-Tree和Cache-Oblivious Streaming B-trees（COLA）等变种。

关于算法，那些你不知道的事

重点说一下B^epsilon树。它将Key抽象成异步消息，整个树仿佛成了一个MQ。根据对epsilon参数的选择，决定每个树结点中要留出多少空间作为Buffer。不仅对B-Tree的写性能有大幅提升，而且能够充分利用磁盘带宽。值得一提的是，几个老师合伙将B^epsilon-Tree应用到数据库、Linux文件系统等各种存储软件中，于是就商业化成了一个公司。简单说就是，一种数据结构撑起来了一家创业公司，完全由技术驱动来发起，真是令人钦佩！

推荐阅读：

  1. 论文：《The Buffer Tree: A Technique for Designing
    Batched External Data Structures》
  2. 论文：《The Log-Structured Merge-Tree (LSM-Tree)》
  3. 论文（强烈推荐！）：《An Introduction to Bepsilon-trees and Write-Optimization》
  4. 论文：《Cache-Oblivious Streaming B-trees》
  5. 从MIT过来的大牛Bender教授（强烈推荐！），其中几乎涉及了大数据和WODs的方方面面，并有一些对他商业化公司的介绍，Slide内容非常棒！：《Data Structures and Algorithms for Big Databases》

5.CO算法（Cache-Oblivious Algorithm）

这是一类神奇的算法，在任何Block大小的机器架构上都能以最优的性能运行！这在前面介绍的DAM模型中是不可想象的，因为分析外存算法时都要假设一个Block大小B，然后在此基础上进行分析。对于任意大小的B或者说忽略B，真是难以想象！但这样的算法真的存在，而且不只是一个两个，已经发现了好多。

CO算法的模型叫做理想缓存模型（Ideal Cache Model），在DAM模型基础上，假设了内存大小M远大于B，完美的Pager进行Swap等条件。虽然这个模型类似DAM，只是两层缓存架构，但是可以证明在现代多层缓存架构（CPU寄存器-L1-L2-L3-Memory-Disk）上也是最优的。已知的CO算法例如矩阵转置、矩阵相乘等等，具体请参考下面推荐的阅读资料。

要设计或改造出CO算法或数据结构可不是那么容易，但也是有方法可循，论文中列举了三个常用策略：van Emde Boas数据布局（vEB Layout，不是vEB树）、Weighted平衡树、紧凑内存数组（Packed Memory Array or PMA）。其中，vEB是种有趣的嵌套结构，在任意B大小的架构上都不会产生多余的I/O，而PMA则更加神奇，普通静态数组在空间不足或多余时会double或truncate，这会导致性能在某一次操作的突然下降。而PMA则将普通数组分段，每段中都始终保留一些gap空位，这样每个segment满了只会在小范围内发生数据移动。

关于算法，那些你不知道的事

推荐阅读：

  1. CO鼻祖Frigo论文：《Cache-Oblivious Algorithms》
  2. Erik D. Demaine整理的手册（强烈推荐！）：《Cache-Oblivious Algorithms and Data Structures》
  3. 论文：《Cache-Efficient Matrix Transposition》
  4. 论文（vEB、PMA）（强烈推荐！）：《Cache-Oblivious B-Trees》
  5. 论文（implict vEB）：《Cache Oblivious Search Trees via Binary Trees of Small Height》
  6. 论文（PMA）：《An Adaptive Packed-Memory Array》

6.基于SSD存储的算法优化

SSD现在已经不是什么稀罕物了，好多新出的个人笔记本电脑都配备了上百G的SSD，为什么要针对SSD做优化呢？这是因为SSD与传统磁盘物理结构上的有巨大差别。整块SSD分为很多个区域，每块区只能整体擦除。所以为了延迟使用寿命，从OS的I/O调度器和驱动方面和SSD内部的FTL（Flash Translation Layer）方面都会进行均衡。

关于算法，那些你不知道的事

在这种物理结构之上，SSD有两个特点：channel-level并行和package-level并行。简单来说，就是一次I/O的带宽更大了，以及操作的并行度更高了。所以我们优化数据结构也就有了两个方向：要么提高一次I/O的数据量，要么提高并行I/O操作数。分析SSD的模型也是在DAM模型上扩展了，额外增加了一个参数P，表示每一步可以并行进行的I/O数。

以B-Tree的搜索操作为例，对于一次操作来说，我们无法预先知道遍历路径，所以不能并行。所以我们从第二个方面，提高每次I/O的数据量，从单个块大小B提升到PB，这样就充分利用了SSD的特点。对于多个不相关的操作来说，我们可以直接并行请求B-Tree达到同样的目的。

推荐阅读：《B+-tree Index Optimization by Exploiting Internal： Parallelism of Flash-based Solid State Drives》

7.算法安全性

7.1 Complexity Attack

复杂度攻击在前面介绍Hash时提到过，对于普通的数据结构我们可以通过随机化来避免最坏情况的发生。但对于随机化算法，如果“敌人”知道了我们的内部信息，例如随机数产生器的规则，那么也是会出现同样问题的。例如Skip List变成了阶梯形状，而Treap退化成了链表等。

7.2 History-Independent

所谓的History-Independent就是：即便“敌人”得到了目前你数据结构的样子，它也无法推断出你调用增删改查API的操作顺序和参数，典型例子有Treap，反例则是Chaining Hash、AVL等等许多数据结构。关于这一部分只是老师上课时不经意提过几句，理解得还不是太好，感觉很新奇，但没找到具体专门讲解的资料，等找到后要好好学习一下！

标签：

相关文章