海量数据

  • 大量数据去重(对空间的利用到达极致)
    • Bitmap算法:把一个数存储在一个bit位里,比如2,就把第二个bit置为1
      • 排序:遍历bit,直接把这一位是1的编号输出
      • 去重:用2bit来表示状态:00不存在,01存在,11存在2次(以上)
      • 查询:一个数组元素可以存储32位,把要查询的数/32,再%32得到位置,查看位置状态
    • Bloom Filter布隆过滤器:引入了k个哈希函数,通过哈希函数映射k个位置置为1,这样子更加节约内存,但是会出现一定的误判率
  • 怎么在海量数据中找出重复次数最多的一个
    • 先做hash,然后求模映射为小文件,求出每个小文件中重复次数最多的一个,并记录重复次数。
    • 然后找出上一步求出的数据中重复次数最多的一个
  • 访问次数最多的IP
    • 算法思想:分而治之+Hash
    • 1、IP地址最多有2^32=4G种取值情况,所以不能完全加载到内存中处理;
    • 2、可以考虑采用分而治之的思想,按照IP地址的Hash(IP) % 1024值,把海量IP日志分别存储到1024个小文件中,这样,每个小文件最多包含4MB个IP地址;
  • 在海量数据中统计出现次数最多的n个
    • 先Hash分成多个小数据集,
    • 如果是求最大的,直接维护一个最小堆;
    • 如果求频率最高的,先用Hash统计每个小数据集中的词频,再维护一个最小堆
  • 5亿个int,找出他们的中位数
    • 一个最大堆存储左半边元素,一个最小堆存储右半边元素
    • 如果是偶数,就算堆顶平均,如果是奇数,就算最小堆的堆顶;
  • 两个文件,各存放50亿条URL,每个URL占64字节。内存限制是4G,找出两个文件中相同的URL
    • Bloom filter
    • 1)分而治之/hash映射:遍历文件a,对每个url求取,然后根据所取得的值将url分别存储到1000个小文件(记为)中。这样每个小文件的大约为300M。遍历文件b,采取和a相同的方式将url分别存储到1000小文件中(记为)。这样处理后,所有可能相同的url都在对应的小文件()中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
    • 2)hash统计:求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了
  • 40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
    • 又因为2^32为40亿多,所以给定一个数可能在,也可能不在其中;
    • 这里我们把40亿个数中的每一个用32位的二进制来表示
    • 假设这40亿个数开始放在一个文件
    • 然后将这40亿个数分成两类:
      • 1.最高位为0
      • 2.最高位为1
    • 并将这两类分别写入到两个文件中,其中一个文件中数的个数<=20亿,而另一个>=20亿(这相当于折半了);
    • 与要查找的数的最高位比较并接着进入相应的文件再查找
Table of Contents