Uses old Rust 2015
|0.1.2||Feb 12, 2021|
|0.1.1||Sep 1, 2017|
|0.1.0||Feb 3, 2017|
#629 in Algorithms
315 downloads per month
Used in 5 crates (4 directly)
partition slices in-place by a predicate
Rust has the
Iterator::partition(_) method, but this requires allocating two
Vecs to hold the values. This has the benefit of preserving order, at the
cost of spending time and RAM to do the allocation, which also makes this API
unavailable on systems without an allocator.
This crate has a
partition(..) function to partition a mutable slice of
values by a predicate. It will swap around values to separate those the
predicate holds for and those it doesn't and return the two mutable sub-slices.
This crate also provides
partition_index(..) which operates similarly, but
instead returns the index of the first element to evaluate to false. All
elements before this index evaluate to true, and all elements after evaluate
Note that since partition works by swapping values, the order of elements within the slice will not be preserved.
let mut even_odd = [0u8, 1, 2, 3, 4, 5, 6]; let (even, odd) = partition(&mut even_odd, |x| x & 1 == 0);
let mut less_than_4 = [0u8, 3, 6, 2, 1, 5, 4]; let idx = partition_index(&mut less_than_4, |x| x < 4);
On a Core m3-6y30 with 4GB of RAM, I get the following benchmark results (in ns/iter):
|Number of Elements||
|10000||8,738 ± 665||101,625 ± 10,930|
|1000||896 ± 75||6,826 ± 760|
|100||118 ± 11||1,013 ± 116|
|10||14 ± 2||295 ± 93|
|1||4 ± 1||51 ± 7|
So it's safe to say performance compares very favorably.
Licensed under either of at your discretion: