零基础学大数据算法

通过背景、计算复杂性、内外磁盘算法、MapReduce并行计算、Spark平台、众包、大数据挖掘这些精心选择的主题揭开大数据的七彩面纱。

零基础，有广度，从经典的并行处理框架到时兴的众包计算，书中都有精彩阐述。

有深度，不枯燥，生动鲜活的对话体，在愉悦中轻松进阶大数据处理的理论、应用和实践

《零基础学大数据算法》是通俗易懂的大数据算法教程。通篇采用师生对话的形式，旨在用通俗的语言、轻松的气氛，帮助读者理解大数据计算领域中的基础算法和思想。

《零基础学大数据算法》由背景篇、理论篇、应用篇和实践篇四部分组成。背景篇介绍大数据、算法、大数据算法等基本概念和背景；理论篇介绍解决大数据问题的亚线性算法、磁盘算法、并行算法、众包算法的基本思想和理论知识；应用篇介绍与大数据问题息息相关的数据挖掘和推荐系统的相关知识；实践篇从实际应用出发，引导读者动手操作，帮助读者通过实际程序和实验验证磁盘算法、并行算法和众包算法。

在讲解每一个大数据问题之前，《零基础学大数据算法》都会介绍大量的经典算法和基础数据结构知识，不仅可以帮助学习过数据结构与算法、算法设计与分析等课程的同学复习，同时能够让入门的“小菜鸟”们，不会因为没有学习过经典算法而对《零基础学大数据算法》望而却步，轻松地掌握大数据算法！

第1 篇　背景篇
第1 章　何谓大数据 4
1．1　身边的大数据 4
1．2　大数据的特点和应用 6
第2 章　何谓算法 8
2．1　算法的定义 8
2．2　算法的分析 14
2．3　基础数据结构――线性表 24
2．4　递归――以阶乘为例 28
第3 章　何谓大数据算法 31
第2 篇　理论篇
第4 章　窥一斑而见全豹――亚线性算法 34
4．1　亚线性算法的定义 34
4．2　空间亚线性算法 35
4．2．1　水库抽样 35
4．2．2　数据流中的频繁元素 37
4．3　时间亚线性计算算法 40
4．3．1　图论基础回顾 40
4．3．2　平面图直径 45
4．3．3　最小生成树 46
4．4　时间亚线性判定算法 53
4．4．1　全0 数组的判定 53
4．4．2　数组有序的判定 55
第5 章　价钱与性能的平衡――磁盘算法 58
5．1　磁盘算法概述 58
5．2　外排序 62
5．3　外存数据结构――磁盘查找树 71
5．3．1　二叉搜索树回顾 71
5．3．2　外存数据结构――B 树 78
5．3．3　高维外存查找结构――KD 树 80
5．4　表排序 83
5．5　表排序的应用 86
5．5．1　欧拉回路技术 86
5．5．2　父子关系判定 87
5．5．3　前序计数 88
5．6　时间前向处理技术 90
5．7　缩图法 98
第6 章　1+1＞2――并行算法 103
6．1　MapReduce 初探 103
6．2　MapReduce 算法实例 106
6．2．1　字数统计 106
6．2．2　平均数计算 108
6．2．3　单词共现矩阵计算 111
6．3　MapReduce 进阶算法 115
6．3．1　join 操作 115
6．3．2　MapReduce 图算法概述 122
6．3．3　基于路径的图算法 125
第7 章　超越MapReduce 的并行计算 131
7．1　MapReduce 平台的局限 131
7．2　基于图处理平台的并行算法 136
7．2．1　概述 136
7．2．2　BSP 模型下的单源最短路径 137
7．2．3　计算子图同构 141
第8 章　众人拾柴火焰高――众包算法 144
8．1　众包概述 144
8．1．1　众包的定义 144
8．1．2　众包应用举例 146
8．1．3　众包的特点 149
8．2　众包算法例析 152
第3 篇　应用篇
第9 章　大数据中有黄金――数据挖掘 158
9．1　数据挖掘概述 158
9．2　数据挖掘的分类 159
9．3　聚类算法――k-means 160
9．4　分类算法――Naive Bayes 166
第10 章　推荐系统 170
10．1　推荐系统概述 170
10．2　基于内容的推荐方法 173
10．3　协同过滤模型 176
第4 篇　实践篇
第11 章　磁盘算法实践 186
第12 章　并行算法实践 194
12．1　Hadoop MapReduce 实践 194
12．1．1　环境搭建 194
12．1．2　配置Hadoop 201
12．1．3　“Hello World”程序―― WordCount 203
12．1．4　Hadoop 实践案例――记录去重 213
12．1．5　Hadoop 实践案例――等值连接 216
12．1．6　多机配置 221
12．2　适于迭代并行计算的平台――Spark 224
12．2．1　Spark 初探 224
12．2．2　单词出现行计数 230
12．2．3　在Spark 上实现WordCount 236
12．2．4　在HDFS 上使用Spark 241
12．2．5　Spark 的核心操作――Transformation 和Action 244
12．2．6　Spark 实践案例――PageRank 247
第13 章　众包算法实践 251
13．1　认识AMT 251
13．2　成为众包工人 252

这是一个互联网的时代，也是一个大数据的时代。经常有朋友问起：什么是大数据？大数据是做什么用的？我们为什么要研究大数据？应该怎么研究大数据？在寻找这些问题的答案时，许多朋友找到的内容常常是专业的概念、复杂的公式和难懂的“算法”，这让他们望而却步。很多计算机专业的新生或低年级学生在听到大数据的概念后对其非常好奇，却因没有足够扎实的专业基础知识而无法认识和理解大数据问题，更无法对大数据问题给出很好的解决办法。于是，笔者决定编写一本新生乃至非专业人士也能读懂的大数据算法教程。

本书以一个计算机专业新生小可的口吻，将他内心对大数据的好奇一一询问学识渊博的Mr. 王。虽然书中的他不懂数据结构，也不懂经典算法的设计与分析，却在Mr. 王的耐心教导下一一突破了大数据背景下的亚线性算法、磁盘算法、并行算法、众包算法，了解了数据挖掘和推荐算法的基本思想，更是在Mr. 王的指导下完成了各种大数据算法的实现。在所有大数据算法的讲授中，本书无处不渗透着对各种经典算法的回顾，学过的读者可以进行充分的复习，没有学过的读者更是可以借此机会提前掌握各种经典数据结构和经典算法，使得其在今后的学习中事半功倍。这些贯穿全书的前置知识，也使得新生甚至是非专业人士能够通过本书读懂大数据，读懂大数据算法。相信非专业人士也能通过大数据算法的思想，重新认识大数据，并获得一些启迪。

本书前半部分主要以理论知识为主，文中涉及的伪代码、算法等均以简单易懂的自然语言进行了步骤描述和解释，同时给出了小规模运行的例子，使得读者可以轻松地理解。同时，笔者也深知理论与实践相结合的重要性。后半部分包含一些让读者进行实践的实验和程序。这需要具有一些基础程序设计能力，如果读者觉得不能很好地理解它们也不要心急，可以待学会这些语言后，再来尝试。即使并不完全理解这几种语言的语法，也可以按照书中详尽的步骤进行实验，体会成果出现在屏幕上的喜悦，其实尝试之后就会发现，阅读它们并不困难。

虽然本书气氛轻松、语言活泼，但讲授的知识和内容却是非常“专业”的，“算法设计与分析”是计算机学科的核心主题之一，计算机科学中所有问题的解决，都离不开算法设计与分析。本书虽讲解大数据，但无处不紧扣算法设计与分析这一要点，这也让本书带上了浓厚的计算机学科的味道，让读者能够在学习和认识大数据的过程中，学会算法设计与分析，为其他领域知识

的学习打下基础。

本书亦算是大数据算法领域的“敲门砖”，本书可以引导读者形成设计大数据算法的思维。在阅读本书之后，读者可以带着设计大数据算法的基本思想去阅读更加深入的专著或论文，进一步的阅读必对大数据算法的学习大有裨益。

本书成书时间仓促，笔者水平亦有限，书中内容、表述、推理等方面的各种不当之处在所难免，敬请各位读者在阅读过程中不吝提出宝贵意见。