海量数据排序总结.docVIP

问题: 假设一个文件中有9 亿条不重复的9 位整数，现在要求对这个文件进行排序。 一般解题思路: 1 、将数据导入到内存中 2 、将数据进行排序　（比如插入排序、快速排序） 3 、将排序好的数据存入文件 难题: 一个整数为4 个字节 即使使用数组也需要900,000,000 * 4byte = 3.4G 内存 对于32 位系统，访问2G 以上的内存非常困难，而且一般设备也没有这么多的物理内存 将数据完全导入到内存中的做法不现实 其他解决办法: 1 、导入数据库运算 2 、分段排序运算 3 、使用bit 位运算 解决方案一: 数据库排序 将文本文件导入到数据库，让数据库进行索引排序操作后提取数据到文件 优点：操作简单 缺点：运算速度慢，而且需要数据库设备。 解决方案二: 分段排序 操作方式： 规定一个内存大小，比如200M ，200M 可以记录(200*1024*1024/4) =条记录，我们可以每次提取5000 万条记录到文件进行排序，要装满9 位整数需要20 次，所以一共要进行20 次排序，需要对文件进行20 次读操作 缺点： 编码复杂，速度也慢( 至少20 次有哪些信誉好的足球投注网站) 关键步骤： 先将整个9 位整数进行分段，亿条数据进行分成20 段，每段5000 万条 在文件中依次有哪些信誉好的足球投注网站0~5000 万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 类型后按上述办法存放在这块内存中( 比我们整理后为112345678, 我们找到内存中112345678bit 的下标, 并将此bit 值设为1) 遍历整个bit 数组, 记录下所有的号码, 这些号码即是不重复的手机号码 总结 建立一个足够大的bit 数组当作hash 表 以bit 数组的下标来表示一个整数 以bit 位中的0