使用位图做整型ID去重的一种方法
程序员文章站
2024-01-05 09:03:34
...
什么是位图算法
英文叫做bitmap,也有叫做bitset,Java SDK的util包中就包含一个BitSet的实现。
《编程珠玑》中提到一个位图算法的例子:
输入:一个文件,里面大约有1千万行数据,每个数据是7位整数,同时每个数是唯一的,即不允许有2个数相同,这些整数不与其他任何数产生关联。
输出:将这个整数按升序排列,并生成到一文件中
限制:能够使用内存为1M,但是附存足够大,运行时间最多为几分钟,10s为最合适的时间。
用位图算法解决可以这么做:用含有1千万个位的整型数组来表示这个文件,文件中有的数据则标识为1,没有则标识为0,最后从第一位读至最后一位,即为有序的集合。
利用位图算法过滤重复ID
首先阐述一下算法思路:
使用一个足够大的位图,每一位表示一个整数的ID,有ID需要处理前,去位图里面查找对应的位是否为0,0表示未处理过,等处理过后就置成1.比如现在有个位图,二进制是00000000,来个id值是3,那么我们需要把位图置成00001000,如果重复的id值3再过来,通过判断这个位图的第三位是1就知道已经处理过了。
。。。。
详情请到我的新博客:
http://xiaofengmetis.com/?p=60