Rust の BTreeSet / BTreeMap で最大値を素早く取得する方法

1
use std::collections::BTreeSet;
2

3
let mut set = BTreeSet::new();
4
set.insert(42);
5
set.insert(1);
6
set.insert(3);
7
let first = set.iter().next(); // 最初の要素を取得
8

9
assert_eq!(first, Some(&1)); // 最初の要素は 1

1
use std::collections::BTreeSet;
2

3
let mut set = BTreeSet::new();
4
set.insert(42);
5
set.insert(1);
6
set.insert(3);
7
let last = set.iter().last(); // 「最後」の要素を取得
8

9
assert_eq!(last, Some(&42)); // 「最後」の要素は 42

1
use std::collections::BTreeSet;
2

3
let mut set = BTreeSet::new();
4
set.insert(42);
5
set.insert(1);
6
set.insert(3);
7
let last = set.iter().next_back(); // next_back を使う
8

9
assert_eq!(last, Some(&42));

1
#![feature(test)]
2

3
extern crate test;
4

5
use std::collections::{BTreeSet, HashSet};
6
use test::Bencher;
7

8
fn get_maximum_by_last(set: &BTreeSet<i32>) -> i32 {
9
    *set.iter().last().unwrap_or(&0)
10
}
11

12
fn get_maximum_of_hashset_by_last(set: &HashSet<i32>) -> i32 {
13
    *set.iter().last().unwrap_or(&0)
14
}
15

16
fn get_maximum_by_next_back(set: &BTreeSet<i32>) -> i32 {
17
    *set.iter().next_back().unwrap_or(&0)
18
}
19

20
#[bench]
21
fn last(b: &mut Bencher) {
22
    let set = {
23
        let mut s = BTreeSet::new();
24
        for i in 1..10_000_000 {
25
            s.insert(i);
26
        }
27
        s
28
    };
29

30
    b.iter(|| get_maximum_by_last(&set));
31
}
32

33
#[bench]
34
fn next_back(b: &mut Bencher) {
35
    let set = {
36
        let mut s = BTreeSet::new();
37
        for i in 1..10_000_000 {
38
            s.insert(i);
39
        }
40
        s
41
    };
42

43
    b.iter(|| get_maximum_by_next_back(&set));
44
}
45

46
#[bench]
47
fn last_hash(b: &mut Bencher) {
48
    let set = {
49
        let mut s = HashSet::new();
50
        for i in 1..10_000_000 {
51
            s.insert(i);
52
        }
53
        s
54
    };
55

56
    b.iter(|| get_maximum_of_hashset_by_last(&set));
57
}

1
blog-test is 📦 v0.1.0 via 🦀 v1.45.0-nightly took 1m57s ❯ cargo bench
2
   Compiling blog-test v0.1.0 (/private/tmp/blog-test)
3
    Finished bench [optimized] target(s) in 0.68s
4
     Running target/release/deps/blog_test-0aef6b7d2f434fa2
5

6
running 3 tests
7
test last      ... bench:          10 ns/iter (+/- 2)
8
test last_hash ... bench:  25,960,936 ns/iter (+/- 1,593,353)
9
test next_back ... bench:          10 ns/iter (+/- 2)
10

11
test result: ok. 0 passed; 0 failed; 0 ignored; 3 measured; 0 filtered out

1
impl<'a, K, V> Iterator for Keys<'a, K, V> {
2
    type Item = &'a K;
3

4
    fn next(&mut self) -> Option<&'a K> {
5
        self.inner.next().map(|(k, _)| k)
6
    }
7

8
    fn size_hint(&self) -> (usize, Option<usize>) {
9
        self.inner.size_hint()
10
    }
11

12
    fn last(mut self) -> Option<&'a K> {
13
        self.next_back() // <- 衝撃の事実！！！！！！！！
14
    }
15
}

1
use criterion::{criterion_group, criterion_main, Criterion};
2
use std::collections::{BTreeSet, HashSet};
3

4
use lazy_static::lazy_static;
5

6
lazy_static! {
7
    static ref BTREE_SET: BTreeSet<i32> = {
8
        let mut s = BTreeSet::new();
9
        for i in 0..10_000_000 {
10
            s.insert(i);
11
        }
12
        s
13
    };
14
    static ref HASHSET: HashSet<i32> = {
15
        let mut s = HashSet::new();
16
        for i in 0..10_000_000 {
17
            s.insert(i);
18
        }
19
        s
20
    };
21
}
22

23
pub fn btree_last(c: &mut Criterion) {
24
    let s = &*BTREE_SET;
25
    c.bench_function("btree_last", |b| b.iter(|| get_maximum_by_last(s)));
26
}
27

28
pub fn btree_next_back(c: &mut Criterion) {
29
    let s = &*BTREE_SET;
30
    c.bench_function("btree_next_back", |b| {
31
        b.iter(|| get_maximum_by_next_back(s))
32
    });
33
}
34

35
pub fn hash_last(c: &mut Criterion) {
36
    let s = &*HASHSET;
37
    c.bench_function("hash_last", |b| {
38
        b.iter(|| get_maximum_of_hashset_by_last(s))
39
    });
40
}
41

42
criterion_group!(benches, btree_last, btree_next_back, hash_last);
43
criterion_main!(benches);