Closed
Description
Hello,
The use of iterator's max
and min
function do not seams to take advantage of the specific ordering of BTreeMap and looks like it is browsing the whole container.
Although it is still possible to have fast access to minimum and maximum element by using first
and first_back
, this is not semantically explicite and you can expect that developers may not know the subtilities regarding BTreeMap's implementation and could assume the complexity should be the same.
Here is the benchmark result
running 4 tests
test bench_first ... bench: 9 ns/iter (+/- 0)
test bench_last ... bench: 8 ns/iter (+/- 0)
test bench_max ... bench: 3,603 ns/iter (+/- 536)
test bench_min ... bench: 3,755 ns/iter (+/- 328)
and here is the benchmark code:
#![feature(test)]
extern crate test;
#[macro_use]
extern crate lazy_static;
use test::Bencher;
use std::collections::BTreeMap;
lazy_static! {
static ref MAP: BTreeMap<i32, i32> = {
let mut map = BTreeMap::new();
for i in 0..1000 {map.insert(i, i);}
map
};
}
#[bench]
fn bench_max(b: &mut Bencher) {
b.iter(|| {MAP.iter().max()});
}
#[bench]
fn bench_first(b: &mut Bencher) {
b.iter(|| {MAP.iter().next()});
}
#[bench]
fn bench_last(b: &mut Bencher) {
b.iter(|| {MAP.iter().next_back()});
}
#[bench]
fn bench_min(b: &mut Bencher) {
b.iter(|| {MAP.iter().min()});
}
I don't know the details of the trait implementation, but I think it would be very nice for the community if you can make std::collections::btree_map::Iter
take advantage of the ordering. :)