bitset-fixed 0.1.0

Bitset for DP.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#![feature(test)]

extern crate test;

use bitset_fixed::BitSet;

#[bench]
fn bench_bitset_dp(b: &mut test::Bencher) {
    use rand::prelude::*;
    let size = 1000;
    let mut v = Vec::new();
    let mut rng = StdRng::seed_from_u64(114514);

    for _ in 0..size {
        v.push(rng.next_u32() as usize % size);
    }

    b.iter(|| {
        let mut bset = BitSet::new(100000);
        bset.set(0, true);

        for &x in &v {
            bset |= &(&bset << x);
        }
    });
}

#[bench]
fn bench_bitset_dp_shl_or(b: &mut test::Bencher) {
    use rand::prelude::*;
    let size = 1000;
    let mut v = Vec::new();
    let mut rng = StdRng::seed_from_u64(114514);

    for _ in 0..size {
        v.push(rng.next_u32() as usize % size);
    }

    b.iter(|| {
        let mut bset = BitSet::new(100000);
        bset.set(0, true);

        for &x in &v {
            bset.shl_or(x);
        }
    });
}