Proposal: BinaryHeap::remove

libs
14

Or you could use a BTreeSet? How does that performance compare for you? Also, toy examples kinda suck; there’s so many ways to “improve” this code (up to the point of making it do nothing at all) and it’s impossible to deduce almost anything about actual, practical use-cases[1] from analyzing this example.

fn main() {
    let prime = 104729;
    let gen = 12;
    let mut elt = gen;

    let mut xs = BTreeSet::new();
    let start = Instant::now();
    for i in 1..prime {
        xs.insert(elt);
        elt *= gen;
        elt %= prime;
    }

    for i in (prime / 2 - 1000)..(prime / 2 + 1000) {
        xs.remove(&i);
    }
    let stop = Instant::now();
    println!("{}", stop.duration_since(start).as_millis());
}

  1. which might have different access patterns, a different balance of push/pop vs. remove, etc… (this toy example doesn’t have any pop at all) ↩︎

2 Likes