ndarray-slice
Fast and robust slice-based algorithms (e.g., sorting, selection, search) for non-contiguous (sub)views into n-dimensional arrays.
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
SliceExttrait for n-dimensional array or (sub)view with methods expectingAxisas
their first argument. Comparing methods will always be suffixed with_byor_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
-
allocfor stablesort/sort_by/sort_by_key. Enabled bystd. -
stdfor stablesort_by_cached_key. Enabled bydefaultorrayon. -
stackerfor spilling recursion stack over to heap if necessary. Enabled bydefault. -
rayonfor parallelpar_sort*/par_select_many_nth_unstable*.
License
Copyright © 2023 Rouven Spreckels [email protected]
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.
