前言 本书旨在帮助人们构建可扩展的应用程序并了解大规模数据系统下的算法构建块。本书涵盖了构建大规模应用程序的不同算法，包括使用概率数据结构节省空间、处理流式数据、使用磁盘上的数据以及了解数据库系统中的性能权衡。 本书读者对象 本书适合了解基本数据结构和算法的读者。书中的许多内容都以早期数据结构/算法课程中通常涵盖的内容为基础：大部分章节都从展示问题的传统解决方案开始并说明该算法或数据结构在大规模数据的背景下失败的原因。尽管各章的介绍部分讨论了一些基本算法，但这些内容只是对读者本应了解的主题的简短复习。本书的读者还应该掌握中级编程知识以及基本的概率知识。除了需要熟悉Python和伪代码这些基本知识，学习本书无须了解其他任何特定系统或架构(这就是算法的奥妙之处)。 本书主要结构 本书分为3 部分，共11 章。第Ⅰ部分介绍概率型简洁数据结构，第Ⅱ部分介绍流式数据结构和算法，第Ⅲ部分介绍外部存储器数据结构和算法。以下是各章内容的简要说明。 第Ⅰ部分：基于哈希的草图 第1 章解释大规模数据在现代系统中存在严峻挑战的原因，以及这些挑战对算法和数据结构设计的影响。 第2 章回顾哈希并解释哈希表如何发展以满足大型数据集和复杂分布式系统的需求(如一致性哈希)。哈希方法将在接下来的章节中大量使用，因此该章是第Ⅰ部分的基础。 第3 章介绍近似成员关系问题和有助于解决该问题的两种数据结构：Bloom 过滤器和商过滤器。该章展示用例和误报率分析，以及使用每种数据结构的优缺点。 第4 章描述频率估计问题并介绍count-min sketch(计数-最小草图，这是一种以非常节省空间的方式解决频率估计问题的数据结构)。该章讨论NLP、传感器数据和其他领域的用例，以及count-min sketch 在范围查询等问题中的应用。 第5 章深入了解基数估计、HyperLogLog 算法及其应用。该章通过一个小型实验，展示了从简单的概率计数到完整的HyperLogLog 数据结构在准确性方面的演变。 第Ⅱ部分：实时分析 第6 章循序渐进地介绍数据流这一算法概念，以及其现实世界表现形式——流式数据(应用程序)。该章使用流式数据架构中的几个实际用例，展示了前几章中的数据结构如何用于流式数据上下文。 第7 章介绍如何保留数据流中的代表性样本或数据流上的滑动窗口。该章指出人们何时可能对有偏差的样本感兴趣，并给出代码示例来展示如何实现将样本偏向于最近看到的数据元组。 第8 章涉及计算连续数据流中数值数据的近似分位数，描述了两种草图数据结构：t-digest 和q-digest。该章还解释了它们背后的算法并在一个真实的数据集上将两者进行对比。 第Ⅲ部分：数据库的数据结构和外部存储器算法 第9 章介绍外部存储器模型及相关示例，这些示例用于说明在远程存储上处理数据时，输入/输出成本如何支配CPU。 对于习惯于从CPU 成本方面考虑优化算法的算法设计者来说，该章会转换他们的视角。 第10 章展示支持主流数据库的数据结构(例如，B 树和LSM树)，并且涵盖数据库引擎设计中的各种读/写权衡。从高层次上理解这些数据结构的工作原理有助于辨别不同风格的数据库，并为应用程序选择适合的数据库。 第11 章着眼于对外部存储器的排序，并且展示了使用合并排序和快速排序的外部存储器优化版本对磁盘上的文件进行排序的最佳算法。该章以排序为例，说明在将批处理问题移至外部存储器时可以进行哪些优化。 本书的各部分相互关联，但第Ⅰ、Ⅱ部分之间的联系更紧密，因为这两部分都涉及RAM 中的数据结构以及在节省空间的同时最大限度地提高准确性这一主题。第Ⅲ部分具有独立的主题，只对它感兴趣的读者可以直接跳至这一部分。第Ⅰ、Ⅱ部分之间的阅读顺序也并不绝对，但先阅读第Ⅰ部分可能比直接跳入第Ⅱ部分更容易理解第Ⅱ部分。 第Ⅱ部分和第Ⅲ部分都以解释模型和背景的章节(第6 章和第9章)开始，强烈建议阅读这些章节，为理解相应部分中的其他章节奠定基础。了解这一点后，可以随意探索本书。编写时，我们尽力使各章自成体系。如果需要，可以随时返回前置章节以获取更多相关知识。我们建议所有读者阅读第1 章，因为该章解释了当涉及部署在繁忙的大型基础设施中的算法和数据结构时，大规模数据会产生范式转变的原因。 配套资源 书中示例的完整代码及配套资源可通过扫描本书封底的二维码获取并下载。 书中有几章包含代码，对于一些较复杂的算法以及上下文会明显加大代码复杂度的算法(如外部存储器算法)，我们会返回使用伪代码。我们将Python 和R 用于大多数代码片段，并在某些章节中用其创建一些小型实验来演示数据结构性能。读者应能够随意用自己选择的语言来实现编程练习，因为所涵盖的主题并不特定于某一语言或技术。 本书包含代码清单和类似普通文本形式的许多源代码示例。这两种情况下，源代码都被格式化为Courier New 字体，从而区分于普通文本。有时代码也以粗体突出显示与书中先前步骤相比发生变化的代码，例如将新特性添加到现有代码行时。 许多情况下，原始源代码已被重新格式化；我们添加了换行符并重新设置缩进以适合纸质书中可用的页面空间。极少数情况下，这些还不够，代码清单中还包含续行符(➥)。此外，在正文中描述代码时，源代码中的注释通常已删除。不过许多代码清单都带有代码注释，突出了重要的概念。

• 暂无课件
• 暂无样章
• 暂无网络资源

扫描二维码
下载APP了解更多

版权图片链接