海量数据排序总结资料

转载自http://jgzhen125.blog.163.com/blog/static/44508644201091254658679/?fromdm&fromSearch&isFromSearchEngine=yes 

 

问题: 假设一个文件中有9 亿条不重复的9 位整数，现在要求对这个文件进行排序。
一般解题思路:
1 、将数据导入到内存中
2 、将数据进行排序　（比如插入排序、快速排序）
3 、将排序好的数据存入文件

难题:
一个整数为4 个字节
即使使用数组也需要900,000,000 * 4byte = 3.4G 内存
对于32 位系统，访问2G 以上的内存非常困难，而且一般设备也没有这么多的物理内存
将数据完全导入到内存中的做法不现实

其他解决办法:
1 、导入数据库运算
2 、分段排序运算
3 、使用bit 位运算

解决方案一: 数据库排序
将文本文件导入到数据库，让数据库进行索引排序操作后提取数据到文件

优点：操作简单
缺点：运算速度慢，而且需要数据库设备。

解决方案二: 分段排序
操作方式：
规定一个内存大小，比如200M ，200M 可以记录(200*1024*1024/4) = 52428800 条记录，我们可以每次提取5000 万条记录到文件进行排序，要装满9 位整数需要20 次，所以一共要进行20 次排序，需要对文件进行20 次读操作

缺点：
编码复杂，速度也慢( 至少20 次搜索)

关键步骤：
先将整个9 位整数进行分段，亿条数据进行分成20 段，每段5000 万条
在文件中依次搜索0~5000 万，50000001~1 亿……
将排序的结果存入文件

解决方案三:bit 位操作
思考下面的问题:
一个最大的9 位整数为999999999
这9 亿条数据是不重复的
可不可以把这些数据组成一个队列或数组，让它有0~999999999(10 亿个) 元素
数组下标表示数值，节点中用0 表示这个数没有，1 表示有这个数
判断0 或1 只用一个bit 存储就够了

声明一个可以包含9 位整数的bit 数组(10 亿) ，一共需要10 亿/8=120M 内存
把内存中的数据全部初始化为0, 读取文件中的数据，并将数据放入内存。比如读到一个数据为341245909 这个数据，那就先在内存中找到341245909 这个bit ，并将bit 值置为1 遍历整个bit 数组，将bit 为1 的数组下标存入文件

关键代码
检查是某一个char 里面(first) 的第second 位中存储的数据是否为1

bool CompareBit (unsigned char first, int second)
{
const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};
if (second > .8)
return false;

return (first & mark_buf[second]) == mark_buf[second];
}

将某一个char(Desc) 中的第source 位置为 1

bool WriteToBit (unsigned char *Desc, int source)
{
const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};

if (source >  .8)
return false;

Desc[0] |= mark_buf[source];

return true;
}

案例
在某个项目中，我们需要对2 亿条手机号码删除重复记录( 过滤号码黑名单同样有效)

工作难点就在于如何处理这2 亿条电话号码, 直接用哈希表存放手机号码不大现实, 即使经过优化, 用一个unsigned int 存放一条记录, 那也得需要2 亿*4=8 亿byte, 远超过32 位系统的寻址能力

解决方案:
将电话号码由12 位单个数字组成的字符串转换为一个unsigned int 型数据( 这个完全可能, 手机号码由前三位数字和后面八位数字组成, 后面八位需要占到1~1000 万的空间, 而前面用0~100 的数字存储已经足够) 为简单起见, 默认为0~4G 的数字都有可能分布号码 , 为此我们分配4G/32=512M 的内存将这2 亿个号码整理成unsigned int 类型后按上述办法存放在这块内存中( 比如13512345678 我们整理后为112345678, 我们找到内存中112345678bit 的下标, 并将此bit 值设为1) 遍历整个bit 数组, 记录下所有的号码, 这些号码即是不重复的手机号码

总结
建立一个足够大的bit 数组当作hash 表
以bit 数组的下标来表示一个整数
以bit 位中的0 或1 来表示这个整数是否在这个数组中存在
适用于无重复原始数据的搜索
原来每个整数需要4byte 空间变为1bit ，空间压缩率为32 倍
扩展后可实现其他类型（包括重复数据）的搜索

 

 

主题： 3000w 数据的表，取某项字段前 50 项数据 ，内存 2G

偶然看到这个题，就想了一下怎么做，大体实现思路是这样子的， 3000w 的数据划分为 1000 段，也就是 1-3w 为一段， 30001-6w 项为第二段，依次类推，从每 3w 的数据中提取出前 50 条数据（这个根据 sql 排序就能取出来， 2 个 g 的内存够了），最后 1000 个 50 就会产生 5w 个数据，最后提取出来的 5w 的数据放置到 ArrayList 中去，最后 5w 的数据统一排序，取出前 50 条。 5w*5w 的对比与交换是可以搞定的。具体实现，等最近的项目完了 用多线程试试！

 

主题：【探讨】给你 1G 内存，如何从 3000 万个手机号码中检索出你要的号码，要求每秒检索 >1000 次

 

 

主题： 3 亿数据快速检索实现

上周有个需求，就是要做一个检索库：
　　１　３亿个手机号码，并且每个号码２０个左右的属性例：地区，订阅等信息。
　　２　在最短的时候内 select 出来（５分钟，１０分钟） [ 最重要 ]
　　３　允许更新。对这些号码进行发送信息后，状态改变。 [ 可以让他慢慢更新 ]
　　和几个同事讨论了一下，具体要注意以下几点：
　　１　如果发送下去状态改变，但是只发送一半，但状态改变了如何办？
　　２　如果多个产品线一起下发，状态会不会混乱。
　　解决以上第二个问题，决定采用，队列等待的方式。第一个问题没想到好的解决办法，回滚也想过了，但感觉不是很现实！

　　解决方案：
　　经过实验 500w 条的数据在用 plsql 直接 select ，只需要０ . ２秒，所以总体采用分表的方式，每 500w 条分一个表，然后同时查询！  
----------------------------------------- 重新描述一下需求 -------------------------------
很多人说需求不是很的清楚，这里重新整理了一下！
不过要注意的是数据库里已经有 3 亿个手机基数了！
一． 号码入库。
不定期会有新的号码需要入库，入库需要记录号码的常规属性，如：手机号，省份，城市，入库时间，手机卡类型，是否支持彩信，号码来源情况等。
二． 入库手机号源文件管理
入库手机号源文件要以文件形式保存在服务器上。
三． 按需要提取号码（最关键部分）
要按照需求提取所需的号码。

例如：
提号要求：
1. 此号码非黑名单用户。
2. 此号码为的订购和退订用户。
3. 此号码 2 个月内没有活动。
4. 省份要求：辽宁，云南，广东
5. 号段要求： 137 和 138 和 139 号段
6. 数量要求：每个省 10w
7. 是否支持彩信：是（是，否，忽略三种情况）
……

最后，符合条件的号码，按照固定格式（每个手机号占一行），形成文本文件，将此文件测试号码，是否需要状态报告等信息形成最终可发送文件并提供下载功能，同时记录本次提取信息（发送时间，发送标识等）
注：文件格式如下：
139***85185#09#0
139***71283
139***33190
第 1 列：手机号
第 2 列：产品类型（ #09 ）
第 3 列：是否需要状态报告（ #0 ）

四． 统计功能
一．号码情况统计
1. 统计当前号码总量。
2. 按照 2 个基本要求，统计现在库中可以使用的号码数量。
注：统计需要显示，全国总量，各省总量，各省省会总量，各省去除省会总量，各省 7 天未下发总量（省会与其他城市分开显示），各省可以发送总量（省会与其他城市分开显示，所以单独列出来）。

二．发送产品统计
1. 按时间段、业务线等统计发送产品的情况，如：发送时间，最终发送文件等

五． 黑名单及特殊号码管理
1. 添加黑名单
2. 去除黑名单
3. 过滤黑名单
4. 查询黑名单

以上除黑名单外都是迫切需要的，黑名单功能可以以后完善。

 

 

 

现在有一万（ 1-10000 ）的个数，从中拿掉一个数，还剩 9999 个数，现在用一个数组来存储这 9999 个数，问怎么才能找出拿掉的数？

用 10000 个数的数组循环匹配 9999 个数，匹配成功，从 9999 数组中去除，不成功就是该数。

大家还有什么好的思路没有？

 

问题: 假设一个文件中有9 亿条不重复的9 位整数，现在要求对这个文件进行排序。

一般解题思路:  1 、将数据导入到内存中 2 、将数据进行排序　（比如插入排序、快速排序） 3 、将排序好的数据存入文件

难题:   一个整数为4 个字节即使使用数组也需要900,000,000 * 4byte = 3.4G 内存对于32 位系统，访问2G 以上的内存非常困难，而且一般设备也没有这么多的物理内存将数据完全导入到内存中的做法不现实。

其他解决办法:  1 、导入数据库运算 2 、分段排序运算 3 、使用bit 位运算

解决方案一: 数据库排序  将文本文件导入到数据库，让数据库进行索引排序操作后提取数据到文件

优点：操作简单缺点：运算速度慢，而且需要数据库设备。

解决方案二: 分段排序   操作方式：规定一个内存大小，比如200M ，200M 可以记录52428800 条记录，我们可以每次提取5000 万条记录到文件进行排序，要装满9 位整数需要20 次，所以一共要进行20 次排序，需要对文件进行20 次读操作

缺点：   编码复杂，速度也慢( 至少20 次搜索)

关键步骤：先将整个9 位整数进行分段，亿条数据进行分成20 段，每段5000 万条，在文件中依次搜索0~5000 万，50000001~1 亿…… 将排序的结果存入文件

解决方案三:bit 位操作  思考下面的问题: 一个最大的9 位整数为999999999 这9 亿条数据是不重复的，可不可以把这些数据组成一个队列或数组，让它有0~999999999(10 亿个) 元素数组下标表示数值，节点中用0 表示这个数没有，1 表示有这个数，判断0 或1 只用一个bit 存储就够了

声明一个可以包含9 位整数的bit 数组(10 亿) ，一共需要10 亿/8=120M 内存，把内存中的数据全部初始化为0 ，读取文件中的数据，并将数据放入内存。比如读到一个数据为341245909 这个数据，那就先在内存中找到341245909 这个bit ，并将bit 值置为1 ，遍历整个bit 数组，将bit 为1 的数组下标存入文件

关键代码   检查是某一个char 里面(first) 的第second 位中存储的数据是否为1

bool CompareBit (unsigned char first, int second)

 {

const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};

if (second > 8) return false;

return (first & mark_buf[second]) == mark_buf[second];

 }

将某一个char(Desc) 中的第source 位置为1

bool WriteToBit (unsigned char *Desc, int source)

{

const static int mark_buf[] = {0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80};

if (source > 8) return false;

Desc[0] |= mark_buf[source];

return true;

}

案例   在某个项目中，我们需要对2 亿条手机号码删除重复记录( 过滤号码黑名单同样有效)

工作难点就在于如何处理这2 亿条电话号码, 直接用哈希表存放手机号码不大现实, 即使经过优化, 用一个unsigned int 存放一条记录, 那也得需要2 亿*4=8 亿byte, 远超过32 位系统的寻址能力

解决方案:   将电话号码由12 位单个数字组成的字符串转换为一个unsigned int 型数据( 这个完全可能, 手机号码由前三位数字和后面八位数字组成，后面八位需要占到1~1000 万的空间, 而前面用0~100 的数字存储已经足够) ，为简单起见，默认为0~4G 的数字都有可能分布号码，为此我们分配4G/32=512M 的内存，将这2 亿个号码整理成unsigned int 类型后按上述办法存放在这块内存中( 比如13512345678 我们整理后为112345678, 我们找到内存中112345678bit 的下标, 并将此bit 值设为1) ，遍历整个bit 数组, 记录下所有的号码, 这些号码即是不重复的手机号码

总结   建立一个足够大的bit 数组当作hash 表，以bit 数组的下标来表示一个整数，以bit 位中的0 或1 来表示这个整数是否在这个数组中存在，适用于无重复原始数据的搜索，原来每个整数需要4byte 空间变为1bit ，空间压缩率为32 倍，扩展后可实现其他类型（包括重复数据）的搜索

注意   由于操作系统和编程语言本身的限制，有可能内存足够，但无法分配一块连续大内存的情况，这样的话可以申请多块稍微小一点的内存，然后用链表或其他的方式连接起来使用

 

 

关于海量数据处理

常用的数据结构：

1.Bloom Filter

   大致思想是这样，把一个数据通过N 个哈希函数映射到一个长度为M 的数组的一位上， 将 hash 函数对应的值的位数组置 1 ，查找时如果发现所有 hash 函数对应位都是 1 说明该数据的存在。但不能保证完全正确性，但是此方法无比高效。

【实例】给你 A,B 两个文件，各存放 50 亿条 URL ，每条 URL 占用 64 字节，内存限制是 4G ，让你找出 A,B 文件共同的 URL 。如果是三个乃至 n 个文件呢？  

2. 哈希法

   这个简单，无非是通过一些哈希函数把元素搞到一个指定的位置，简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。这个很一般啊感觉。无非就是分类查找么，完全不如1 猛。

3. 最大或最小堆

     就是一个完全的最大或最小二叉树，用途，比如:1)100w 个数中找最大的前100 个数。  用一个100 个元素大小的最小堆即可。感觉还是不错的。

4.Bit-map

所谓的Bit-map 就是用一个bit 位来标记某个元素对应的Value ， 而Key 即是该元素。由于采用了Bit 为单位来存储数据，因此在存储空间方面，可以大大节省。

【问题实例】

1) 已知某个文件内包含一些电话号码，每个号码为8 位数字，统计不同号码的个数。

8 位最多99 999 999 ，大概需要99M 个bit ，大概10 几m 字节的内存即可。 （可以理解为从0-99 999 999 的数字，每个数字对应一个Bit 位，所以只需要99M 个Bit==1.2MBytes ，这样，就用了小小的1.2M 左右的内存表示了所有的8 位数的电话）

2)2.5 亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5 亿个整数。

将bit-map 扩展一下，用2bit 表示一个数即可，0 表示未出现，1 表示出现一次，2 表示出现2 次及以上，在遍历这些数的时候，如果对应位置的值是0 ，则将其置为1 ；如果是1 ，将其置为2 ；如果是2 ，则保持不变。或者我们不用2bit 来进行表示，我们用两个bit-map 即可模拟实现这个2bit-map ，都是一样的道理。

公司的一道考试题算法分析 —— 大数据量整数排序

    题目大意：移动公司需要对已经发放的所有 139 段的号码进行统计排序，已经发放的 139 号码段的文件都存放在一个文本文件中（原题是放在两个文件中），一个号码一行，现在需要将文件里的所有号码进行排序，并写入到一个新的文件中；号码可能会有很多，最多可能有一亿个不同的号码（所有的 139 段号码），存入文本文件中大概要占 1.2G 的空间； jvm 最大的内存在 300 以内，程序要考虑程序的可执行性及效率；只能使用 Java 标准库，不得使用第三方工具。
    这是个典型的大数据量的排序算法问题，首先要考虑空间问题，一下把 1.2G 的数据读入内存是不太可能的，就算把 1 一亿条数据，转都转换成 int 类型存储也要占接近 400M 的空间。当时做个题目我并没有想太多的执行效率问题，主要就考虑了空间，而且习惯性的想到合并排序，基本思想是原文件分割成若干个小文件并排序，再将排序好的小文件合并得到最后结果，算法大概如下：

     1. 顺序读取存放号码文件的中所有号码，并取 139 之后的八位转换为 int 类型；每读取号码数满一百万个，（这个数据可配置）将已经读取的号码排序并存入新建的临时文件。
    2. 将所有生成的号码有序的临时文件合并存入结果文件。

    这个算法虽然解决了空间问题，但是运行效率极低，由于 IO 读写操作太多，加上步骤 1 中的排序的算法（快速排序）本来效率就不高（对于电话排序这种特殊情况来说），导致 1 亿条数据排序运行 3 个小时才有结果。

    如果和能够减少排序的时间呢？首当其冲的减少 IO 操作，另外如果能够有更加好排序算法也行。前天无聊再看这个题目时突然想到大三时看《编程珠玑》时上面也有个问题的需求这个这个题目差不多，记得好像使用是位向量（实际上就是一个 bit 数组），用电话作为 index ，心中大喜，找到了解决此问题的最完美方案啦：用位向量存储电话号码，一个号码占一个 bit ，一亿个电话号码也只需要大概 12M 的空间；算法大概如下：
      1. 初始化 bits[capacity] ；
      2. 顺序所有读入电话号码，并转换为 int 类型，修改位向量值： bits[phoneNum]=1 ；
      3. 遍历 bits 数组，如果 bits[index]=1 ，转换 index 为电话号码输出。
    Java 中没有 bit 类型，一个 boolean 值占空间为 1byte （感兴趣的可以自己写程序验证），我自己写个用 int 模拟 bit 数组的类，代码如下：
   

Java 代码

1. public  class  BitArray {   
2.     private  int [] bits = null ;   
3.     private  int  length;   
4.     // 用于设置或者提取 int 类型的数据的某一位 (bit) 的值时使用    </