10 unstable releases (3 breaking)
0.4.0 | Sep 14, 2024 |
---|---|
0.3.1 | Jun 13, 2024 |
0.3.0 | Mar 19, 2024 |
0.2.4 | Jan 23, 2024 |
0.1.1 | Apr 7, 2023 |
#106 in Algorithms
416 downloads per month
Used in 2 crates
240KB
3.5K
SLoC
ndarray-slice
Fast and robust slice-based algorithms (e.g., sorting, selection, search) for
non-contiguous (sub)views into n-dimensional arrays. Reimplements algorithms in slice
and
rayon::slice
for ndarray
with arbitrary memory layout (e.g., non-contiguous).
Example
use ndarray_slice::{ndarray::arr2, Slice1Ext};
// 2-dimensional array of 4 rows and 5 columns.
let mut v = arr2(&[[-5, 4, 1, -3, 2], // row 0, axis 0
[ 8, 3, 2, 4, 8], // row 1, axis 0
[38, 9, 3, 0, 3], // row 2, axis 0
[ 4, 9, 0, 8, -1]]); // row 3, axis 0
// \ \ \
// column 0 \ column 4 axis 1
// column 2 axis 1
// Mutable subview into the last column.
let mut column = v.column_mut(4);
// Due to row-major memory layout, columns are non-contiguous
// and hence cannot be sorted by viewing them as mutable slices.
assert_eq!(column.as_slice_mut(), None);
// Instead, sorting is specifically implemented for non-contiguous
// mutable (sub)views.
column.sort_unstable();
assert!(v == arr2(&[[-5, 4, 1, -3, -1],
[ 8, 3, 2, 4, 2],
[38, 9, 3, 0, 3],
[ 4, 9, 0, 8, 8]]));
// \
// column 4 sorted, others untouched
Current Implementation
Complexities where n is the length of the (sub)view and m the count of indices to select.
Resource | Complexity | Sorting (stable) | Sorting (unstable) | Selection (unstable) | Bulk Selection (unstable) |
---|---|---|---|---|---|
Time | Best | O(n) | O(n) | O(n) | O(n log m) |
Time | Average | O(n log n) | O(n log n) | O(n) | O(n log m) |
Time | Worst | O(n log n) | O(n log n) | O(n) | O(n log m) |
Space | Best | O(1) | O(1) | O(1) | O(m) |
Space | Average | O(n/2) | O(log n) | O(1) | O(m+log m) |
Space | Worst | O(n/2) | O(log n) | O(1) | O(m+log m) |
Roadmap
- Add
SliceExt
trait for n-dimensional array or (sub)view with methods expectingAxis
as their first argument. Comparing methods will always be suffixed with_by
or_by_key
defining how to compare multi-dimensional elements (e.g., rows) along the provided axis of interest (e.g., columns).
See the release history to keep track of the development.
Features
alloc
for stablesort
/sort_by
/sort_by_key
. Enabled bystd
.std
for stablesort_by_cached_key
. Enabled bydefault
orrayon
.stacker
for spilling recursion stack over to heap if necessary. Enabled bydefault
.rayon
for parallelpar_sort*
/par_select_many_nth_unstable*
.
License
Copyright © 2023 Rouven Spreckels rs@qu1x.dev
This project contains derivative works of rust
and rayon
. For full authorship information,
see their version control histories. Respective copyrights are retained by their contributors.
Like the original works, this project is licensed under either of
- Apache License, Version 2.0, (LICENSES/Apache-2.0 or https://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSES/MIT or https://opensource.org/licenses/MIT)
at your option.
Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this project by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.
Dependencies
~1.4–8.5MB
~78K SLoC