## 本章导读
所谓海量数据处理,是指基于海量数据的存储、处理、和操作。正因为数据量太大,所以导致要么无法在较短时间内迅速解决,要么无法一次性装入内存。
事实上,针对时间问题,可以采用巧妙的算法搭配合适的数据结构(如布隆过滤器、哈希、位图、堆、数据库、倒排索引、Trie树)来解决;而对于空间问题,可以采取分而治之(哈希映射)的方法,也就是说,把规模大的数据转化为规模小的,从而各个击破。
此外,针对常说的单机及集群问题,通俗来讲,单机就是指处理装载数据的机器有限(只要考虑CPU、内存、和硬盘之间的数据交互),而集群的意思是指机器有多台,适合分布式处理或并行计算,更多考虑节点与节点之间的数据交互。
一般说来,处理海量数据问题,有以下十种典型方法:
- 1.哈希分治;
- 2.simhash算法;
- 3.外排序;
- 4.MapReduce;
- 5.多层划分;
- 6.位图;
- 7.布隆过滤器;
- 8.Trie树;
- 9.数据库;
- 10.倒排索引。
受理论之限,本章将摒弃绝大部分的细节,只谈方法和模式论,注重用最通俗、最直白的语言阐述相关问题。最后,有一点必须强调的是,全章行文是基于面试题的分析基础之上的,具体实践过程中,还得视具体情况具体分析,且各个场景下需要考虑的细节也远比本章所描述的任何一种解决方案复杂得多。
- 程序员如何准备面试中的算法
- 第一部分 数据结构
- 第一章 字符串
- 1.0 本章导读
- 1.1 旋转字符串
- 1.2 字符串包含
- 1.3 字符串转换成整数
- 1.4 回文判断
- 1.5 最长回文子串
- 1.6 字符串的全排列
- 1.10 本章习题
- 第二章 数组
- 2.0 本章导读
- 2.1 寻找最小的 k 个数
- 2.2 寻找和为定值的两个数
- 2.3 寻找和为定值的多个数
- 2.4 最大连续子数组和
- 2.5 跳台阶
- 2.6 奇偶排序
- 2.7 荷兰国旗
- 2.8 矩阵相乘
- 2.9 完美洗牌
- 2.15 本章习题
- 第三章 树
- 3.0 本章导读
- 3.1 红黑树
- 3.2 B树
- 3.3 最近公共祖先LCA
- 3.10 本章习题
- 第二部分 算法心得
- 第四章 查找匹配
- 4.1 有序数组的查找
- 4.2 行列递增矩阵的查找
- 4.3 出现次数超过一半的数字
- 第五章 动态规划
- 5.0 本章导读
- 5.1 最大连续乘积子串
- 5.2 字符串编辑距离
- 5.3 格子取数
- 5.4 交替字符串
- 5.10 本章习题
- 第三部分 综合演练
- 第六章 海量数据处理
- 6.0 本章导读
- 6.1 关联式容器
- 6.2 分而治之
- 6.3 simhash算法
- 6.4 外排序
- 6.5 MapReduce
- 6.6 多层划分
- 6.7 Bitmap
- 6.8 Bloom filter
- 6.9 Trie树
- 6.10 数据库
- 6.11 倒排索引
- 6.15 本章习题
- 第七章 机器学习
- 7.1 K 近邻算法
- 7.2 支持向量机
- 附录 更多题型
- 附录A 语言基础
- 附录B 概率统计
- 附录C 智力逻辑
- 附录D 系统设计
- 附录E 操作系统
- 附录F 网络协议
- sift算法
- sift算法的编译与实现
- 教你一步一步用c语言实现sift算法、上
- 教你一步一步用c语言实现sift算法、下
- 其它
- 40亿个数中快速查找
- hash表算法
- 一致性哈希算法
- 倒排索引关键词不重复Hash编码
- 傅里叶变换算法、上
- 傅里叶变换算法、下
- 后缀树
- 基于给定的文档生成倒排索引的编码与实践
- 搜索关键词智能提示suggestion
- 最小操作数
- 最短摘要的生成
- 最长公共子序列
- 木块砌墙原稿
- 附近地点搜索
- 随机取出其中之一元素