qwt 0.4.0

Rust implementation of Quad Wavelet Tree
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

use mem_dbg::{MemSize, SizeFlags};
use qwt::perf_and_test_utils::{gen_queries, type_of, TimingQueries};
use qwt::RSQVector256;

// traits
use qwt::{AccessQuad, RankQuad, SelectQuad};

const N_RUNS: usize = 5;
const N_QUERIES: usize = 10000000;

fn perf_rank<T>(ds: &T, queries: &[usize], n: usize, logn: usize, u: usize)
where
    T: RankQuad + MemSize,
{
    let mut result = 0;

    let mut t = TimingQueries::new(N_RUNS, N_QUERIES);
    for _ in 0..N_RUNS {
        t.start();
        for &query in queries.iter() {
            let i = (query + result) % n;
            result = unsafe { ds.rank_unchecked((result % 4) as u8, i) };
        }
        t.stop();
    }
    let (t_min, t_max, t_avg) = t.get();
    println!(
        "RANK: [ds_name: {}, n: {}, logn: {}, bitsize: {:?}, min_time (ns): {}, max_time (ns): {}, avg_time (ns): {}, space (bytes): {}, space (Mbyte): {:.2}]",
        type_of(&ds),
        n,
        logn,
        u,
        t_min,
        t_max,
        t_avg,
        ds.mem_size(SizeFlags::default()),
        ds.mem_size(SizeFlags::default()) as f64 / (1024.0 * 1024.0)
    );
}

fn perf_get<T>(ds: &T, queries: &[usize], n: usize, logn: usize, u: usize)
where
    T: AccessQuad + MemSize,
{
    let mut result = 0;

    let mut t = TimingQueries::new(N_RUNS, N_QUERIES);
    for _ in 0..N_RUNS {
        t.start();
        for &query in queries.iter() {
            let i = (query + result as usize) % n;
            result = unsafe { ds.get_unchecked(i) };
        }
        t.stop();
    }
    println!("Fake {}", result);
    let (t_min, t_max, t_avg) = t.get();
    println!(
        "GET: [ds_name: {}, n: {}, logn: {}, bitsize: {:?}, min_time (ns): {}, max_time (ns): {}, avg_time (ns): {}, space (bytes): {}, space (Mbytes): {:.2}]",
        type_of(&ds),
        n,
        logn,
        u,
        t_min,
        t_max,
        t_avg,
        ds.mem_size(SizeFlags::default()),
        ds.mem_size(SizeFlags::default()) as f64 / (1024.0 * 1024.0)
    );
}

fn perf_select<T>(ds: &T, queries: &[usize], n: usize, logn: usize, u: usize)
where
    T: SelectQuad + MemSize,
{
    let mut result = 0;

    let mut t = TimingQueries::new(N_RUNS, N_QUERIES);
    for _ in 0..N_RUNS {
        t.start();
        for &query in queries.iter() {
            let mut i = query + result % 2;
            if i == 0 {
                i = 1;
            }
            result = ds.select((result % 4) as u8, i).unwrap();
        }
        t.stop();
    }
    let (t_min, t_max, t_avg) = t.get();
    println!(
        "SELECT: [ds_name: {}, n: {}, logn: {}, bitsize: {:?}, min_time (ns): {}, max_time (ns): {}, avg_time (ns): {}, space (bytes): {}, space (Mbytes): {:.2}]",
        type_of(&ds),
        n,
        logn,
        u,
        t_min,
        t_max,
        t_avg,
        ds.mem_size(SizeFlags::default()),
        ds.mem_size(SizeFlags::default()) as f64 / (1024.0 * 1024.0)
    );
}

fn main() {
    for logn in 14..33 {
        let n = 1 << logn;

        let v: Vec<u8> = [0, 1, 2, 3].into_iter().cycle().take(n).collect();
        let rsqv = RSQVector256::new(&v);

        let queries = gen_queries(N_QUERIES, n);
        perf_rank(&rsqv, &queries, n, logn, 2 * n);

        let queries = gen_queries(N_QUERIES, n);
        perf_get(&rsqv, &queries, n, logn, 2 * n);

        let queries = gen_queries(N_QUERIES, n / 4 - 10);
        perf_select(&rsqv, &queries, n, logn, 2 * n);
    }
}