大数据处理问题

发表于 | 分类于 | | 热度: |
大数据处理问题，总之大化小

分而治之/Hash映射 + Hash_map统计 + 堆/快速/归并排序

  • 分而治之/hash映射：针对数据太大，内存受限，只能是：把大文件化成(取模映射)小文件，即16字方针：大而化小，各个击破，缩小规模，逐个解决
  • hash_map统计：当大文件转化了小文件，那么我们便可以采用常规的hash_map(ip，value)来进行频率统计。
  • 堆/快速排序：统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP。
1
2
3
4
5
6
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。
注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如%1000，
把整个大文件映射为1000个小文件，
再找出每个小文中出现频率最大的IP（可以采用hash_map对那1000个文件中的所有IP进行频率统计，
然后依次找出各个文件中频率最大的那个IP）及相应的频率。
然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求

多层划分

  • 其实本质上还是分而治之的思想，重在“分”的技巧上！
    适用范围：第k大，中位数，不重复或重复的数字
    基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行
1
2
3
4
5
6
7
8
9
10
11
12
13
5亿个int找它们的中位数
方法同基数排序有些像，开一个大小为65536的Int数组，第一遍读取，
统计Int32的高16位的情况，也就是0-65535，都算作0,65536 - 131071都算作1。
就相当于用该数除以65536。
Int32 除以 65536的结果不会超过65536种情况，因此开一个长度为65536的数组计数就可以。
每读取一个数，数组中对应的计数+1，考虑有负数的情况，需要将结果加32768后，记录在相应的数组内。
第一遍统计之后，遍历数组，逐个累加统计，看中位数处于哪个区间，比如处于区间k，
那么0- k-1的区间里数字的数量sum应该<n/2（2.5亿）。
而k+1 - 65535的计数和也<n/2，第二遍统计同上面的方法类似，
但这次只统计处于区间k的情况，也就是说(x / 65536) + 32768 = k。
统计只统计低16位的情况。并且利用刚才统计的sum，比如sum = 2.49亿，
那么现在就是要在低16位里面找100万个数(2.5亿-2.49亿)。
这次计数之后，再统计一下，看中位数所处的区间，最后将高位和低位组合一下就是结果了。

Bloom filter/Bitmap

  • 适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集
    　　基本原理及要点：
    　　对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。
    1
    2
    3
    在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数

    采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

Trie树/数据库/倒排索引

  • 适用范围：数据量大，重复多，但是数据种类小可以放入内存
    　　基本原理及要点：实现方式，节点孩子的表示方式
    　　扩展：压缩实现。

外排序

  • 适用范围：大数据的排序，去重
    　　基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树
    1
    2
    3
    4
    有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。
    返回频数最高的100个词。
    这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1M做hash明显不够，所以可以用来排序。
    内存可以当输入缓冲区使用。

分布式处理之Mapreduce

  • MapReduce是一种计算模型，简单的说就是将大批量的工作（数据）分解（MAP）执行，然后再将结果合并成最终结果（REDUCE）。
    这样做的好处是可以在任务被分解后，可以通过大量机器进行并行计算，减少整个操作的时间。但如果你要我再通俗点介绍，那么，说白了，Mapreduce的原理就是一个归并排序
  • 适用范围：数据量大，但是数据种类小可以放入内存
    基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。
谢谢您请我喝咖啡！