Lib.rs

vEB(van Emde Boas)布局 partition_point (无缓存感知)

use partition_point_veb_layout::*;
let v = vec![0, 0, 1, 2, 2, 4, 6];
let lb = v.partition_point(|x| x < &2);
let w = veb_layout(&v);
let vlb = veb_partition_point(&w, |x| x < &2);
assert_eq!(lb, veb_index_rev(vlb, v.len()));

对于大于LLC（最后一级缓存），veb_partition_point 比标准库中slice的 partition_point 更快。

但是，获取 &v[lower_bound..upper_bound] 速度不快。它需要 O((upper_bound-lower_bound)*log(v.len()))。

CPU: Ryzen7 2700X 内存：DDR4 2666MHz 2ch 64GB RUSTC: rustc 1.60.0-beta.3