编程之法:面试和算法心得

 主页   资讯   文章   代码   电子书 

本章导读

所谓海量数据处理,是指基于海量数据的存储、处理、和操作。正因为数据量太大,所以导致要么无法在较短时间内迅速解决,要么无法一次性装入内存。

事实上,针对时间问题,可以采用巧妙的算法搭配合适的数据结构(如布隆过滤器、哈希、位图、堆、数据库、倒排索引、Trie树)来解决;而对于空间问题,可以采取分而治之(哈希映射)的方法,也就是说,把规模大的数据转化为规模小的,从而各个击破。

此外,针对常说的单机及集群问题,通俗来讲,单机就是指处理装载数据的机器有限(只要考虑CPU、内存、和硬盘之间的数据交互),而集群的意思是指机器有多台,适合分布式处理或并行计算,更多考虑节点与节点之间的数据交互。

一般说来,处理海量数据问题,有以下十种典型方法:

  • 1.哈希分治;
  • 2.simhash算法;
  • 3.外排序;
  • 4.MapReduce;
  • 5.多层划分;
  • 6.位图;
  • 7.布隆过滤器;
  • 8.Trie树;
  • 9.数据库;
  • 10.倒排索引。

受理论之限,本章将摒弃绝大部分的细节,只谈方法和模式论,注重用最通俗、最直白的语言阐述相关问题。最后,有一点必须强调的是,全章行文是基于面试题的分析基础之上的,具体实践过程中,还得视具体情况具体分析,且各个场景下需要考虑的细节也远比本章所描述的任何一种解决方案复杂得多。