其他算法
Last updated
Last updated
每当用户登录Facebook时，Facebook都必须在一个庞大的数组中 查找，核实其中是否包含指定的用户名。前面说过，在这种数组中查找时，最快的方式是二分查 找，但问题是每当有新用户注册时，都必须将其用户名插入该数组并重新排序，因为二分查找仅 在数组有序时才管用。如果能将用户名插入到数组的正确位置就好了，这样就无需在插入后再排 序。为此，有人设计了一种名为二叉查找树（binary search tree）的数据结构。
如果你对数据库或高级数据结构感兴趣，请研究如下数据结构：B树，红黑树，堆， 伸展树。
这是一种很有用的数据结构：一个散 列表，将单词映射到包含它的页面。这种数据结构被称为反向索引（inverted index），常用于创 建搜索引擎。如果你对搜索感兴趣，从反向索引着手研究是不错的选择。
给定一首歌曲，傅里叶变换能够将其中的各种频 率分离出来。 这种理念虽然简单，应用却极其广泛。例如，如果能够将歌曲分解为不同的频率，就可强化 你关心的部分，如强化低音并隐藏高音。傅里叶变换非常适合用于处理信号，可使用它来压缩音 乐。为此，首先需要将音频文件分解为音符。
傅里叶变换能够准确地指出各个音符对整个歌曲的 贡献，让你能够将不重要的音符删除。这就是MP3格式的工作原理！ 数字信号并非只有音乐一种类型。JPG也是一种压缩格式，也采用了刚才说的工作原理。傅 里叶变换还被用来地震预测和DNA分析。 使用傅里叶变换可创建类似于Shazam这样的音乐识别软件。傅里叶变换的用途极其广泛，你 遇到它的可能性极高！
有一种特殊的并行算法正越来越流行，它就是分布式算法。在并行算法只需两到四个内核时， 完全可以在笔记本电脑上运行它，但如果需要数百个内核呢？在这种情况下，可让算法在多台计 算机上运行。MapReduce是一种流行的分布式算法，你可通过流行的开源工具Apache Hadoop来 使用它。
分布式算法非常适合用于在短时间内完成海量工作，其中的MapReduce基于两个简单的理 念：映射（map）函数和归并（reduce）函数。
映射是将一个数组转换为另一个数组。
而归并是将一个数组转换为一个元素。
假设你管理着网站Reddit。每当有人发布链接时，你都要检查它以前是否发布过，因为之前 未发布过的故事更有价值。 又假设你在Google负责搜集网页，但只想搜集新出现的网页，因此需要判断网页是否搜集过。 在假设你管理着提供网址缩短服务的bit.ly，要避免将用户重定向到恶意网站。你有一个清单，其中记录了恶意网站的URL。你需要确定要将用户重定向到的URL是否在这个清单中。 这些都是同一种类型的问题，涉及庞大的集合。
给定一个元素，你需要判断它是否包含在这个集合中。为快速做出这种判断，可使用散列表。 例如，Google可能有一个庞大的散列表，其中的键是已搜集的网页。
只是Google需要建立数万亿个网页的索引，因此这个散列表非常大，需要占用大量的存储空 间。Reddit和bit.ly也面临着这样的问题。面临海量数据，你需要创造性的解决方案！
布隆过滤器提供了解决之道。布隆过滤器是一种概率型数据结构，它提供的答案有可能不对， 但很可能是正确的。为判断网页以前是否已搜集，可不使用散列表，而使用布隆过滤器。使用散 列表时，答案绝对可靠，而使用布隆过滤器时，答案却是很可能是正确的。
可能出现错报的情况，即Google可能指出“这个网站已搜集”，但实际上并没有搜集。
不可能出现漏报的情况，即如果布隆过滤器说“这个网站未搜集”，就肯定未搜集。
布隆过滤器的优点在于占用的存储空间很少。使用散列表时，必须存储Google搜集过的所有 URL，但使用布隆过滤器时不用这样做。布隆过滤器非常适合用于不要求答案绝对准确的情况， 前面所有的示例都是这样的。对bit.ly而言，这样说完全可行：“我们认为这个网站可能是恶意的， 请倍加小心。
HyperLogLog是一种类似于布隆过滤器的算法。如果Google要计算用户执行的不同搜索的数 量，或者Amazon要计算当天用户浏览的不同商品的数量，要回答这些问题，需要耗用大量的空 间！对Google来说，必须有一个日志，其中包含用户执行的不同搜索。有用户执行搜索时，Google 必须判断该搜索是否包含在日志中：如果答案是否定的，就必须将其加入到日志中。即便只记录 一天的搜索，这种日志也大得不得了！
HyperLogLog近似地计算集合中不同的元素数，与布隆过滤器一样，它不能给出准确的答案， 但也八九不离十，而占用的内存空间却少得多。 面临海量数据且只要求答案八九不离十时，可考虑使用概率型算法！
安全散列算法（secure hash algorithm，SHA）函数。给定一个字符串，SHA 返回其散列值。
用于创建散列表的散列函数根据字符串生成数组索引，而SHA根据字符串生成另一个字符串。 对于每个不同的字符串，SHA生成的散列值都不同。
两个文件是否相同比较
你可使用SHA来判断两个文件是否相同，这在比较超大型文件时很有用。假设你有一个4 GB 的文件，并要检查朋友是否也有这个大型文件。为此，你不用通过电子邮件将这个大型文件发送 给朋友，而可计算它们的SHA散列值，再对结果进行比较。
密码检查
SHA还让你能在不知道原始字符串的情况下对其进行比较。例如，假设Gmail遭到攻击，攻 击者窃取了所有的密码！你的密码暴露了吗？没有，因为Google存储的并非密码，而是密码的 SHA散列值！你输入密码时，Google计算其散列值，并将结果同其数据库中的散列值进行比较。
你可以通过字符串计算出散列值，但却不能从散列值逆推出字符串；而且稍微修改一下字符串，计算出的散列值也很不相同；
有时候，你希望结果相反，即希望散列函数是局部敏感的。在这种情况下，可使用Simhash。
如果你对字符串做细微的修改，Simhash生成的散列值也只存在细微的差别。这让你能够通过比 较散列值来判断两个字符串的相似程度，这很有用！
Google使用Simhash来判断网页是否已搜集。
老师可以使用Simhash来判断学生的论文是否是从网上抄的。
Scribd允许用户上传文档或图书，以便与人分享，但不希望用户上传有版权的内容！这个 网站可使用Simhash来检查上传的内容是否与小说《哈利·波特》类似，如果类似，就自动拒绝。
这里有必要提一提Diffie-Hellman算法，它以优雅的方式解决了一个古老的问题：如何对消息 进行加密，以便只有收件人才能看懂呢？ 最简单的方式是设计一种加密算法，如将a转换为1，b转换为2，以此类推。
Diffie-Hellman使用两个密钥：公钥和私钥。顾名思义，公钥就是公开的，可将其发布到网站 上，通过电子邮件发送给朋友，或使用其他任何方式来发布。你不必将它藏着掖着。有人要向你 发送消息时，他使用公钥对其进行加密。加密后的消息只有使用私钥才能解密。只要只有你知道 私钥，就只有你才能解密消息！
Diffie-Hellman算法及其替代者RSA依然被广泛使用。如果你对加密感兴趣，先着手研究 Diffie-Hellman算法是不错的选择：它既优雅又不难理解。
最好的东西留到最后介绍。线性规划是我知道的最酷的算法之一。 线性规划用于在给定约束条件下最大限度地改善指定的指标。
例如，假设你所在的公司生产 两种产品：衬衫和手提袋。衬衫每件利润2美元，需要消耗1米布料和5粒扣子；手提袋每个利润3 美元，需要消耗2米布料和2粒扣子。你有11米布料和20粒扣子，为最大限度地提高利润，该生产 多少件衬衫、多少个手提袋呢？ 在这个例子中，目标是利润最大化，而约束条件是拥有的原材料数量。
再举一个例子。你是个政客，要尽可能多地获得支持票。你经过研究发现，平均而言，对于 每张支持票，在旧金山需要付出1小时的劳动（宣传、研究等）和2美元的开销，而在芝加哥需要 付出1.5小时的劳动和1美元的开销。在旧金山和芝加哥，你至少需要分别获得500和300张支持票。 你有50天的时间，总预算为1500美元。请问你最多可从这两个地方获得多少支持票？
这里的目标是支持票数最大化，而约束条件是时间和预算。
你可能在想，本书花了很大的篇幅讨论最优化，这与线性规划有何关系？所有的图算法都可 使用线性规划来实现。线性规划是一个宽泛得多的框架，图问题只是其中的一个子集。但愿你听 到这一点后心潮澎湃！ 线性规划使用Simplex算法，这个算法很复杂，因此本书没有介绍。如果你对最优化感兴趣， 就研究研究线性规划吧！
