位图算法,使用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
分享到:
相关推荐
2. 函数库实现:C++的STL库提供了一个`bitset`类,该类提供了丰富的接口来操作位图,包括设置、测试和清除位,以及转换为其他数据类型等。 位图在多个领域有广泛应用: 3.1 枚举: - 全组合字符串:位图可以用来...
位图排序是一种特殊的排序算法,尤其适用于数据量大但内存空间有限的情况。它利用了二进制位的特性,以非常节省空间的方式表示和处理数据。在C++中,我们可以通过`std::bitset`库来方便地实现位图排序。 在上述的...
1. **初始化**:定义了若干基本数据结构,如`vector<set<int>> vs`表示输入的所有集合,`bitset<MAXNUM>`用于存储位图表示的集合状态。 2. **并行环境设置**:使用MPI初始化并获取当前进程的排名(rank)和总进程数量...
在给定的代码示例中,使用了C++的`bitset`库来实现位图。在主函数中,程序会提示用户输入多个QQ号,并将它们设置在位图中。之后,用户可以输入一个QQ号,程序会检查位图,如果位为1,则表示该QQ号已存在于位图中,...
10. **位集(Bitset)**:Bitset是C++标准库中的一种容器,它提供了类似于数组但以位为单位的操作。在"bitwiser"中,可能有对位集的高级操作和扩展。 通过"bitwiser-master"这个文件名,我们可以猜测这是项目的源...
10. **并行计算**:在多核处理器或GPU编程中,位操作可以用于并行处理,例如在位图并行化算法中。 "easily get full points" 提示这些答案可能展示了如何高效、准确地解决数据实验室中的问题。掌握位操作技巧,不仅...
例如,通过使用位图(Bitset)存储单词出现信息,可以极大地减少内存占用。另外,合理利用CPU缓存和数据局部性原理也能提升性能。 8. **测试与评估**: “pj1_test_new”可能是一个测试数据集,用于验证算法的正确...
利用位图(Bitset)表示,或者使用 Hash 表结合布隆过滤器,如果内存不足以容纳所有整数,可以考虑分块处理,使用 MapReduce 分布式计算。 6. 40 亿个无序整数中快速判断某个数是否存在: 哈希函数(例如 Murmur...
5. **整数去重**:可以使用位图(Bitset)或基数排序(Radix Sort),后者适用于整数范围较小的情况,不需额外内存。 6. **TOP10统计**:MapReduce模型可以并行处理每个节点的数据,然后在reduce阶段计算top10,或者...
8. **位图(Bitset)**:对于布尔查询,Lucene使用位图来快速过滤匹配的文档。位图中的每个比特位对应一个文档ID,如果文档匹配某个条件,相应的比特位就设置为1。 9. **术语字典压缩(Term Dictionary Compression...
- **内存管理**:利用位运算可以更高效地管理内存空间,例如,可以通过位图来标记已分配或未分配的内存块。 - **数据压缩**:位运算可以用来实现高效的压缩算法,比如Huffman编码。 - **图形处理**:在图像处理中,...
- **高效圈人**:roaringbitmap是一种高效的位图压缩算法,特别适合处理大集合的交、并、差运算。在精准营销中,它可以帮助快速定位满足特定条件的用户群体。 - **节省资源**:相比于Hive全量扫描和Spark+Elastic...
8. **性能优化**:为了处理大规模数据,可能需要对算法和数据结构进行优化,比如使用位图(Bitset)进行高效查询,或者利用Lucene等成熟的全文搜索引擎库。 9. **测试与评估**:项目中应包括单元测试和集成测试,...
对于大数据量,可能需要考虑更高效的算法,如布隆过滤器(Bloom Filter)或位图(Bitset)。 6. **编程语言**:尽管没有明确指出,但根据文件名,这个项目可能使用Python,因为Python在处理列表和集合操作时非常...
Roaring Bitmap通常比传统的位图(如Java中的BitSet)更节省空间,并且在处理大量元素时,其性能往往更好。 **PyRoaring的安装与使用** `pyroaring-0.3.0-cp39-cp39-macosx_10_14_x86_64.whl` 是一个预编译的...
3. 位图过滤(Bitset Filter):用于快速排除不匹配的文档,显著提升查询速度。 五、总结 Apache Lucene 3.0.0源码的学习,不仅能帮助我们理解其内部工作机制,还能让我们掌握如何利用其构建高效的全文搜索引擎。...
为了实现位图,可能会使用`BitSet`类或者自定义的数据结构。此外,测试用例对于验证算法的正确性至关重要。 6. **挑战与应用场景**:虽然二元伙伴系统在很多场景下表现出色,但处理动态变化的内存需求时可能会面临...
一种可能的解法是使用位图(Bitset)来记录每个数字是否出现过,这样可以有效地利用空间。具体实现时,可以定义一个长度为256的位数组,每一位表示对应数字是否出现过。 #### 题目八:λͼ1ĸ0111000011110рҵ֪ʶ...
6. **搜索优化**:Lucene 3.0 在搜索性能上做了很多优化,如位图过滤(BitSet)用于快速排除不相关的文档,跳跃表(Skip List)加速跳过低得分文档,以及缓存机制来提高后续查询的速度。 7. **多线程支持**:为了...