Rust高性能位集合库bitset使用指南

bitset是Rust中一个高性能的位集合库，提供了快速的位操作和集合运算功能。它特别适合需要高效处理大量布尔值或集合运算的场景。

基本用法

首先在Cargo.toml中添加依赖：

[dependencies]
bitset = "0.5"

创建位集合

use bitset::BitSet;

// 创建容量为100的位集合
let mut bs = BitSet::with_capacity(100);

// 也可以从已有的数据创建
let data = vec![0b10101010u64, 0b11001100u64];
let bs_from_data = BitSet::from_bytes(&data);

基本操作

let mut bs = BitSet::with_capacity(100);

// 设置位
bs.insert(5);
bs.insert(10);
bs.insert(15);

// 检查位
assert!(bs.contains(5));
assert!(!bs.contains(6));

// 移除位
bs.remove(10);
assert!(!bs.contains(10));

// 获取集合大小
println!("Cardinality: {}", bs.len());

集合运算

bitset支持高效的集合运算：

let mut bs1 = BitSet::with_capacity(100);
bs1.insert(1);
bs1.insert(2);
bs1.insert(3);

let mut bs2 = BitSet::with_capacity(100);
bs2.insert(2);
bs2.insert(3);
bs2.insert(4);

// 并集
let union = bs1.union(&bs2);
assert!(union.contains(1) && union.contains(4));

// 交集
let intersection = bs1.intersection(&bs2);
assert!(intersection.contains(2) && !intersection.contains(1));

// 差集
let difference = bs1.difference(&bs2);
assert!(difference.contains(1) && !difference.contains(2));

// 对称差集
let symmetric_diff = bs1.symmetric_difference(&bs2);
assert!(symmetric_diff.contains(1) && symmetric_diff.contains(4));

迭代器

let bs = BitSet::from_bytes(&[0b10101010]);

// 遍历所有设置的位
for bit in bs.iter() {
    println!("Bit {} is set", bit);
}

// 也可以使用into_iter()
let set_bits: Vec<_> = bs.into_iter().collect();
assert_eq!(set_bits, vec![1, 3, 5, 7]);

性能优化技巧

1. 预分配空间：如果知道大概需要多少位，使用with_capacity预先分配空间
2. 批量操作：使用union、intersection等批量操作代替单一位操作
3. 直接操作底层数据：对于高级用例，可以直接访问底层Vec<u64>进行优化

let mut bs = BitSet::with_capacity(1_000_000); // 处理大量数据时预分配

// 批量设置位
for i in 0..1_000_000 {
    if i % 2 == 0 {
        bs.insert(i);
    }
}

// 直接操作底层数据
let underlying_vec: &Vec<u64> = bs.as_ref();

实际应用示例

素数筛法

fn sieve_of_eratosthenes(n: usize) -> BitSet {
    let mut primes = BitSet::with_capacity(n + 1);
    primes.insert_range(2..=n);

    let mut p = 2;
    while p * p <= n {
        if primes.contains(p) {
            for multiple in (p * p..=n).step_by(p) {
                primes.remove(multiple);
            }
        }
        p += 1;
    }
    
    primes
}

let primes = sieve_of_eratosthenes(100);
println!("Primes up to 100: {:?}", primes.iter().collect::<Vec<_>>());

布隆过滤器简化版

struct SimpleBloomFilter {
    bitset: BitSet,
    size: usize,
}

impl SimpleBloomFilter {
    fn new(size: usize) -> Self {
        Self {
            bitset: BitSet::with_capacity(size),
            size,
        }
    }
    
    fn add(&mut self, item: &str) {
        let hash1 = self.hash(item, 17);
        let hash2 = self.hash(item, 31);
        self.bitset.insert(hash1 % self.size);
        self.bitset.insert(hash2 % self.size);
    }
    
    fn contains(&self, item: &str) -> bool {
        let hash1 = self.hash(item, 17);
        let hash2 = self.hash(item, 31);
        self.bitset.contains(hash1 % self.size) && 
        self.bitset.contains(hash2 % self.size)
    }
    
    fn hash(&self, item: &str, seed: u64) -> usize {
        item.chars().fold(seed, |acc, c| acc * seed + c as u64) as usize
    }
}

let mut filter = SimpleBloomFilter::new(1000);
filter.add("hello");
filter.add("world");

assert!(filter.contains("hello"));
assert!(!filter.contains("rust")); // 可能有误报

bitset库因其高性能和丰富的功能，非常适合需要处理大量布尔标志或进行集合运算的场景。

完整示例代码

下面是一个完整的bitset使用示例，展示了从创建到各种操作的完整流程：

use bitset::BitSet;

fn main() {
    // 1. 创建位集合
    let mut bs = BitSet::with_capacity(1000);
    
    // 2. 基本操作
    bs.insert(10);
    bs.insert(20);
    bs.insert(30);
    
    println!("Contains 10: {}", bs.contains(10)); // true
    println!("Contains 15: {}", bs.contains(15)); // false
    
    bs.remove(20);
    println!("Contains 20 after removal: {}", bs.contains(20)); // false
    
    // 3. 集合运算
    let mut bs1 = BitSet::with_capacity(100);
    bs1.insert(1);
    bs1.insert(2);
    bs1.insert(3);
    
    let mut bs2 = BitSet::with_capacity(100);
    bs2.insert(2);
    bs2.insert(3);
    bs2.insert(4);
    
    let union = bs1.union(&bs2);
    println!("Union: {:?}", union.into_iter().collect::<Vec<_>>()); // [1, 2, 3, 4]
    
    let intersection = bs1.intersection(&bs2);
    println!("Intersection: {:?}", intersection.into_iter().collect::<Vec<_>>()); // [2, 3]
    
    // 4. 迭代器使用
    let data = BitSet::from_bytes(&[0b10101010]);
    println!("Set bits:");
    for bit in data.iter() {
        println!("- {}", bit);
    }
    
    // 5. 性能优化示例
    let mut large_bs = BitSet::with_capacity(1_000_000);
    for i in 0..1_000_000 {
        if i % 3 == 0 {
            large_bs.insert(i);
        }
    }
    println!("Large bitset cardinality: {}", large_bs.len());
    
    // 6. 素数筛法应用
    let primes = sieve_of_eratosthenes(100);
    println!("Primes up to 100: {:?}", primes.iter().collect::<Vec<_>>());
}

fn sieve_of_eratosthenes(n: usize) -> BitSet {
    let mut primes = BitSet::with_capacity(n + 1);
    primes.insert_range(2..=n);

    let mut p = 2;
    while p * p <= n {
        if primes.contains(p) {
            for multiple in (p * p..=n).step_by(p) {
                primes.remove(multiple);
            }
        }
        p += 1;
    }
    
    primes
}

这个完整示例展示了bitset库的主要功能：

1. 创建位集合
2. 基本位操作（插入、移除、检查）
3. 集合运算（并集、交集等）
4. 迭代器使用
5. 性能优化实践
6. 实际应用（素数筛法）

通过这个示例，您可以全面了解如何在Rust项目中使用bitset库来高效处理位集合操作。