3 releases

Uses old Rust 2015

0.1.2 Feb 12, 2021
0.1.1 Sep 1, 2017
0.1.0 Feb 3, 2017

#1078 in Algorithms

Download history 119/week @ 2023-11-20 108/week @ 2023-11-27 110/week @ 2023-12-04 143/week @ 2023-12-11 104/week @ 2023-12-18 108/week @ 2023-12-25 81/week @ 2024-01-01 180/week @ 2024-01-08 177/week @ 2024-01-15 214/week @ 2024-01-22 280/week @ 2024-01-29 288/week @ 2024-02-05 265/week @ 2024-02-12 141/week @ 2024-02-19 257/week @ 2024-02-26 223/week @ 2024-03-04

923 downloads per month
Used in 8 crates (4 directly)

MIT/Apache

9KB
73 lines

partition

partition slices in-place by a predicate

Build Status License: Apache 2.0/MIT

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 to false.

Warning

Note that since partition works by swapping values, the order of elements within the slice will not be preserved.

Example

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);

Performance

On a Core m3-6y30 with 4GB of RAM, I get the following benchmark results (in ns/iter):

Number of Elements partition(&[T], _) Iter::partition(_)
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.

License

Licensed under either of at your discretion:

No runtime deps