partition-point-veb-layout
| Crates.io | partition-point-veb-layout |
| lib.rs | partition-point-veb-layout |
| version | 0.1.1 |
| source | src |
| created_at | 2022-03-11 15:17:42.047861 |
| updated_at | 2023-03-04 07:06:16.317717 |
| description | partition_point van Emde Boas layout |
| homepage | |
| repository | https://gitlab.com/Toru3/partition-point-veb-layout |
| max_upload_size | |
| id | 548253 |
| size | 87,732 |
(Toru3)
documentation
https://docs.rs/partition-point-veb-layout/
README
vEB(van Emde Boas) layout partition_point (cache oblivious)
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()));
On larger than LLC(Last Level Cache), veb_partition_point is faster than slice's partition_point.
But, get &v[lower_bound..upper_bound] is not fast. It takes O((upper_bound-lower_bound)*log(v.len())).
CPU: Ryzen7 2700X MEM: DDR4 2666MHz 2ch 64GB RUSTC: rustc 1.60.0-beta.3