`
chroya
  • 浏览: 661594 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

BitSet位图算法

阅读更多

    位图算法,使用bit存储数据并排序,优点是快速、占用资源少,缺点是只能对整数使用。
    Java和C++中都有已经实现的的BitSet类,可以直接使用。
    举个例子,0到10000中随机出1000个数,然后用位图算法排序:
   

import java.util.BitSet;

public class BitSetDemo {

	public static void main(String[] args) {
		int count = 10000;
		BitSet bit = new BitSet(count);
		int i = 1000;
		while(i > 0) {		
			bit.set((int)(Math.random()*count));
			i--;
		}
		
		for(int index=0; index<count; index++) {
			if(bit.get(index)) {
				System.out.print(index+",");
			}
		}
		System.out.println("end");			
	}
}
 

    Java中的BitSet还有很多其他用法,比如and、or、xor等操作,看下文档就明白了。

 

      下面是我自己的一个简单实现:

package chroya.java;

/**
 * 
 * @author chroya
 *
 */
public class BitSet {

	private int[] mBits;
	private int mSize;
	
	/**
	 * 初始化指定个bit
	 * @param size 初始化的bit数目
	 */
	public BitSet(int size) {
		mSize = size;
		initBits();
	}
	
	/**
	 * 将指定bit位置设为1
	 * @param pos 
	 */
	public void set(int pos) {
		//得到此pos在数组中的索引
		int index = (int)Math.floor(pos/32f);
		//把当前整数的第n位设置为1
		mBits[index] = mBits[index] | (1<<(pos%32));
	}
	
	/**
	 * 获取指定位是否存在
	 * @param pos
	 * @return
	 */
	public boolean get(int pos) {
		int index = (int)Math.floor(pos/32f);
		return mBits[index] == (mBits[index] | 1<<(pos%32));
	}
	
	/**
	 * 指定bit位置设为0
	 * @param pos
	 */
	public void reset(int pos) {
		int index = (int)Math.floor(pos/32f);
		//把当前整数的第n位设置为0
		mBits[index] = mBits[index] & ~(1<<(pos%32));
	}
	
	/**
	 * 初始化整型数组
	 */
	private void initBits() {
		//Java中整型为32位,所以数组长度为位长度/32。
		int count = (int) Math.ceil(mSize/32f);
		mBits = new int[count];
		clear();
	}
	
	/**
	 * 清空,全部置零
	 */
	private void clear() {
		int len = mBits.length;
		for(int index=0; index<len; index++) {
			mBits[index] = 0;
		}
	}
}

重点在:

set:     mBits[index] | (1<<(pos%32))    1移到指定位,加到原数上。如原数为4,pos为3,则0100 | 1000 = 1100
get:     mBits[index] == (mBits[index] | 1<<(pos%32)) 判断重新set指定位之后是否跟原数相等
reset:     mBits[index] & ~(1<<(pos%32))    原数减去1移到指定位的数。如原数为6,pos为2,则0110 & 1011 = 0010

3
1
分享到:
评论
4 楼 chroya 2010-12-12  
Coding.Ghost 写道

呵呵,多谢捧场。
3 楼 Coding.Ghost 2010-12-12  
2 楼 chroya 2010-10-22  
kimmking 写道
不错,
为啥叫位图?


因为每个数据都只用一个bit来存储
1 楼 kimmking 2010-10-21  
不错,
为啥叫位图?

相关推荐

    数据结构之位图(bitmap)详解

    2. 函数库实现:C++的STL库提供了一个`bitset`类,该类提供了丰富的接口来操作位图,包括设置、测试和清除位,以及转换为其他数据类型等。 位图在多个领域有广泛应用: 3.1 枚举: - 全组合字符串:位图可以用来...

    C++实现位图排序实例

    位图排序是一种特殊的排序算法,尤其适用于数据量大但内存空间有限的情况。它利用了二进制位的特性,以非常节省空间的方式表示和处理数据。在C++中,我们可以通过`std::bitset`库来方便地实现位图排序。 在上述的...

    最小集合覆盖

    1. **初始化**:定义了若干基本数据结构,如`vector&lt;set&lt;int&gt;&gt; vs`表示输入的所有集合,`bitset&lt;MAXNUM&gt;`用于存储位图表示的集合状态。 2. **并行环境设置**:使用MPI初始化并获取当前进程的排名(rank)和总进程数量...

    你要找的这里~滴滴滴1

    在给定的代码示例中,使用了C++的`bitset`库来实现位图。在主函数中,程序会提示用户输入多个QQ号,并将它们设置在位图中。之后,用户可以输入一个QQ号,程序会检查位图,如果位为1,则表示该QQ号已存在于位图中,...

    bitwiser-0.0.2.zip

    10. **位集(Bitset)**:Bitset是C++标准库中的一种容器,它提供了类似于数组但以位为单位的操作。在"bitwiser"中,可能有对位集的高级操作和扩展。 通过"bitwiser-master"这个文件名,我们可以猜测这是项目的源...

    bit-operation datalab answers

    10. **并行计算**:在多核处理器或GPU编程中,位操作可以用于并行处理,例如在位图并行化算法中。 "easily get full points" 提示这些答案可能展示了如何高效、准确地解决数据实验室中的问题。掌握位操作技巧,不仅...

    英文文本单词分类排序

    例如,通过使用位图(Bitset)存储单词出现信息,可以极大地减少内存占用。另外,合理利用CPU缓存和数据局部性原理也能提升性能。 8. **测试与评估**: “pj1_test_new”可能是一个测试数据集,用于验证算法的正确...

    十道海量数据处理面试题(卷).doc

    利用位图(Bitset)表示,或者使用 Hash 表结合布隆过滤器,如果内存不足以容纳所有整数,可以考虑分块处理,使用 MapReduce 分布式计算。 6. 40 亿个无序整数中快速判断某个数是否存在: 哈希函数(例如 Murmur...

    面试题目-大数据量海量数据处理.pdf

    5. **整数去重**:可以使用位图(Bitset)或基数排序(Radix Sort),后者适用于整数范围较小的情况,不需额外内存。 6. **TOP10统计**:MapReduce模型可以并行处理每个节点的数据,然后在reduce阶段计算top10,或者...

    lucene索引结构原理

    8. **位图(Bitset)**:对于布尔查询,Lucene使用位图来快速过滤匹配的文档。位图中的每个比特位对应一个文档ID,如果文档匹配某个条件,相应的比特位就设置为1。 9. **术语字典压缩(Term Dictionary Compression...

    c++位运算c++位运算

    - **内存管理**:利用位运算可以更高效地管理内存空间,例如,可以通过位图来标记已分配或未分配的内存块。 - **数据压缩**:位运算可以用来实现高效的压缩算法,比如Huffman编码。 - **图形处理**:在图像处理中,...

    大规模分布式数据库标签场景应用.pptx

    - **高效圈人**:roaringbitmap是一种高效的位图压缩算法,特别适合处理大集合的交、并、差运算。在精准营销中,它可以帮助快速定位满足特定条件的用户群体。 - **节省资源**:相比于Hive全量扫描和Spark+Elastic...

    Java 项目-搜索引擎的设计与实现.zip

    8. **性能优化**:为了处理大规模数据,可能需要对算法和数据结构进行优化,比如使用位图(Bitset)进行高效查询,或者利用Lucene等成熟的全文搜索引擎库。 9. **测试与评估**:项目中应包括单元测试和集成测试,...

    listoverlap2

    对于大数据量,可能需要考虑更高效的算法,如布隆过滤器(Bloom Filter)或位图(Bitset)。 6. **编程语言**:尽管没有明确指出,但根据文件名,这个项目可能使用Python,因为Python在处理列表和集合操作时非常...

    Python库 | pyroaring-0.3.0-cp39-cp39-macosx_10_14_x86_64.whl

    Roaring Bitmap通常比传统的位图(如Java中的BitSet)更节省空间,并且在处理大量元素时,其性能往往更好。 **PyRoaring的安装与使用** `pyroaring-0.3.0-cp39-cp39-macosx_10_14_x86_64.whl` 是一个预编译的...

    lucene-3.0.0-src.zip

    3. 位图过滤(Bitset Filter):用于快速排除不匹配的文档,显著提升查询速度。 五、总结 Apache Lucene 3.0.0源码的学习,不仅能帮助我们理解其内部工作机制,还能让我们掌握如何利用其构建高效的全文搜索引擎。...

    Binary-Buddy-System:操作系统项目

    为了实现位图,可能会使用`BitSet`类或者自定义的数据结构。此外,测试用例对于验证算法的正确性至关重要。 6. **挑战与应用场景**:虽然二元伙伴系统在很多场景下表现出色,但处理动态变化的内存需求时可能会面临...

    当当网笔试题

    一种可能的解法是使用位图(Bitset)来记录每个数字是否出现过,这样可以有效地利用空间。具体实现时,可以定义一个长度为256的位数组,每一位表示对应数字是否出现过。 #### 题目八:λͼ1ĸ0111000011110рҵ֪ʶ...

    Lucene 3.0 原理

    6. **搜索优化**:Lucene 3.0 在搜索性能上做了很多优化,如位图过滤(BitSet)用于快速排除不相关的文档,跳跃表(Skip List)加速跳过低得分文档,以及缓存机制来提高后续查询的速度。 7. **多线程支持**:为了...

Global site tag (gtag.js) - Google Analytics