sosorted 0.2.0

A set of methods to efficiently manipulated sorted arrays
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

//! Standard datasets for binary operation benchmarks (intersect, union, difference).

use super::generators::*;
use super::rng::*;

/// A named dataset pair for binary benchmarks.
pub struct BinaryDataset {
    pub name: &'static str,
    pub a: Vec<u64>,
    pub b: Vec<u64>,
}

/// A group of related binary datasets with a common theme.
pub struct BinaryDatasetGroup {
    pub name: &'static str,
    pub datasets: Vec<BinaryDataset>,
}

/// Generate all standard binary dataset groups for a given size.
pub fn standard_binary_datasets(size: usize) -> Vec<BinaryDatasetGroup> {
    vec![
        overlap_datasets(size),
        asymmetric_datasets(size),
        scaling_datasets(),
    ]
}

/// Datasets testing different overlap/intersection densities.
fn overlap_datasets(size: usize) -> BinaryDatasetGroup {
    let base = generate_sorted_unique(SEED_A, size);
    let max_val = size as u64 * 10;

    // 0% overlap - completely disjoint
    let disjoint = generate_disjoint(&base, 0.5);

    // 1% overlap
    let mut overlap_1pct = generate_disjoint(&base, 0.5);
    add_spread_intersections(&mut overlap_1pct, &base, size / 100);

    // 10% overlap
    let mut overlap_10pct = generate_disjoint(&base, 0.5);
    add_spread_intersections(&mut overlap_10pct, &base, size / 10);

    // 50% overlap
    let mut overlap_50pct = generate_disjoint(&base, 0.5);
    add_spread_intersections(&mut overlap_50pct, &base, size / 2);

    // 100% overlap - identical
    let identical = base.clone();

    BinaryDatasetGroup {
        name: "overlap",
        datasets: vec![
            BinaryDataset {
                name: "0pct",
                a: base.clone(),
                b: disjoint,
            },
            BinaryDataset {
                name: "1pct",
                a: base.clone(),
                b: overlap_1pct,
            },
            BinaryDataset {
                name: "10pct",
                a: base.clone(),
                b: overlap_10pct,
            },
            BinaryDataset {
                name: "50pct",
                a: base.clone(),
                b: overlap_50pct,
            },
            BinaryDataset {
                name: "100pct",
                a: base,
                b: identical,
            },
        ],
    }
}

/// Datasets testing asymmetric array sizes (Lemire-style).
fn asymmetric_datasets(size: usize) -> BinaryDatasetGroup {
    let max_val = size as u64 * 10;

    BinaryDatasetGroup {
        name: "asymmetric",
        datasets: vec![
            BinaryDataset {
                name: "1:1",
                a: generate_sorted_unique_bounded(SEED_A, size, max_val),
                b: generate_sorted_unique_bounded(SEED_B, size, max_val),
            },
            BinaryDataset {
                name: "10:1",
                a: generate_sorted_unique_bounded(SEED_A, size, max_val),
                b: generate_sorted_unique_bounded(SEED_B, size / 10, max_val),
            },
            BinaryDataset {
                name: "50:1",
                a: generate_sorted_unique_bounded(SEED_A, size, max_val),
                b: generate_sorted_unique_bounded(SEED_B, size / 50, max_val),
            },
            BinaryDataset {
                name: "100:1",
                a: generate_sorted_unique_bounded(SEED_A, size, max_val),
                b: generate_sorted_unique_bounded(SEED_B, size / 100, max_val),
            },
            BinaryDataset {
                name: "1000:1",
                a: generate_sorted_unique_bounded(SEED_A, size, max_val),
                b: generate_sorted_unique_bounded(SEED_B, size / 1000, max_val),
            },
        ],
    }
}

/// Datasets for testing size scaling behavior.
fn scaling_datasets() -> BinaryDatasetGroup {
    BinaryDatasetGroup {
        name: "scaling",
        datasets: vec![
            BinaryDataset {
                name: "1K",
                a: generate_sorted_unique_bounded(SEED_A, 1_000, 10_000),
                b: generate_sorted_unique_bounded(SEED_B, 1_000, 10_000),
            },
            BinaryDataset {
                name: "10K",
                a: generate_sorted_unique_bounded(SEED_A, 10_000, 100_000),
                b: generate_sorted_unique_bounded(SEED_B, 10_000, 100_000),
            },
            BinaryDataset {
                name: "100K",
                a: generate_sorted_unique_bounded(SEED_A, 100_000, 1_000_000),
                b: generate_sorted_unique_bounded(SEED_B, 100_000, 1_000_000),
            },
            BinaryDataset {
                name: "1M",
                a: generate_sorted_unique_bounded(SEED_A, 1_000_000, 10_000_000),
                b: generate_sorted_unique_bounded(SEED_B, 1_000_000, 10_000_000),
            },
        ],
    }
}