算法的力量：位运算在排序与搜索中的应用

kon3155

网上有一篇这样的文章，http://www.cnblogs.com/Geometry/archive/2009/04/11/1433679.html

楔子: 问题:假设一个文件中有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倍，扩展后可实现其他类型（包括重复数据）的搜索

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

kon3155

我对“位”没什么概念，只知道1byte=8bit
文章有一句话“声明一个可以包含9位整数的bit数组(10亿)，一共需要10亿/8=120M内存”
不知道是怎么声明的？有bit这个数据类型吗？

无心人

x86 CPU是支持位数组和位操作的
最大支持4G bit

gxqcn

如果是寻址能力，单位应该是 byte 而不是 bit 吧？

而且，寻址能力还与操作系统相关。

shshsh_0510

原帖由 kon3155 于 2009-4-15 17:09 发表
我对“位”没什么概念，只知道1byte=8bit
文章有一句话“声明一个可以包含9位整数的bit数组(10亿)，一共需要10亿/8=120M内存”
不知道是怎么声明的？有bit这个数据类型吗？

他这个使用内存较大，自己构造数据类型的好。
对于他这个应用，实际上在不在内存没关系，反正是遍历一边，结果存在硬盘一样。
这个是在说这个道理：当样本的数目多到和整个空间相近似，排序就意义不大了

gxqcn

虽没有bit这样的原生数据类型，
但仍可以通过位运算进行操作间接实现。
即用一个 DWORD 可记录 32 个独立信息。

在STL中，也有可直接操作位数据流的容器，
当然我们也可以自己去包装设计，很简单的。

litaoye

呵呵,这道题有个漏洞,9亿个无重复的9位整数,9位整数不重复的话,总共还差1个才9亿!

gxqcn

如果规定首位非0，则有9个数字可选，后面每位均有10个数字可选，
则总共正好有9亿种组合，而不是楼上说的还差1个。

不过，如果是该规定，显然无须特殊排序，可对任意值直接定位。

也就是说，这里的9位整数应该是允许首位为0情形的。

winxos

原帖由 kon3155 于 2009-4-15 16:30 发表
网上有一篇这样的文章，http://www.cnblogs.com/Geometry/archive/2009/04/11/1433679.html

楔子: 问题:假设一个文件中有9亿条不重复的9位整数，现在要求对这个文件进行排序。
一般解题思路: 1、将数据导入到内存 ...

思路确实很新颖，以前没考虑过，不过如果重复就不行了。

无心人

TO GxQ 4#
确实是4G bit而不是Byte啊
但位操作的偏移是有符号数

即实际的范围是操作数的正负2^31范围内