跳至主要內容

大数据处理 - Overview

gavin-james算法和数据结构领域算法大约 3 分钟

大数据处理 - Overview

本文主要介绍大数据处理的一些思路。

何谓海量数据处理?

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

那解决办法呢?

  • 针对时间: 我们可以采用巧妙的算法搭配合适的数据结构,如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie树;
  • 针对空间: 无非就一个办法: 大而化小,分而治之(hash映射);
  • 集群|分布式: 通俗点来讲,单机就是处理装载数据的机器有限(只要考虑cpu,内存,硬盘的数据交互); 而集群适合分布式处理,并行计算(更多考虑节点和节点间的数据交互)。

具体思路

  • 大数据处理 - 分治/hash/排序
    • 就是先映射,而后统计,最后排序:
    • 分而治之/hash映射: 针对数据太大,内存受限,只能是: 把大文件化成(取模映射)小文件,即16字方针: 大而化小,各个击破,缩小规模,逐个解决
    • hash_map统计: 当大文件转化了小文件,那么我们便可以采用常规的hash_map(ip,value)来进行频率统计。
    • 堆/快速排序: 统计完了之后,便进行排序(可采取堆排序),得到次数最多的IP。
  • 大数据处理 - Bitmap & Bloom Filter
    • 布隆过滤器有着广泛的应用,对于大量数据的“存不存在”的问题在空间上有明显优势,但是在判断存不存在是有一定的错误率(false positive),也就是说,有可能把不属于这个集合的元素误认为属于这个集合(False Positive),但不会把属于这个集合的元素误认为不属于这个集合(False Negative)
  • 大数据处理 - 双层桶划分
    • 其实本质上还是分而治之的思想,重在“分”的技巧上!适用范围: 第k大,中位数,不重复或重复的数字;基本原理及要点: 因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。
  • 大数据处理 - Trie树/数据库/倒排索引
    • 适用范围: 数据量大,重复多,但是数据种类小可以放入内存;基本原理及要点: 实现方式,节点孩子的表示方式;扩展: 压缩实现
  • 大数据处理 - 外排序
    • 适用范围: 大数据的排序,去重;基本原理及要点: 外排序的归并方法,置换选择败者树原理,最优归并树
  • 大数据处理 - Map & Reduce
    • MapReduce是一种计算模型,简单的说就是将大批量的工作(数据)分解(MAP)执行,然后再将结果合并成最终结果(REDUCE)。这样做的好处是可以在任务被分解后,可以通过大量机器进行并行计算,减少整个操作的时间。但如果你要我再通俗点介绍,那么,说白了,Mapreduce的原理就是一个归并排序

参考文章