Crate ndarray_slice
source ·Expand description
Fast and robust slice-based algorithms (e.g., sorting, selection, search) for
non-contiguous (sub)views into n-dimensional arrays. Reimplements algorithms in 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 untouchedCurrent 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 | Expected | 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 log n) | O(n log n log m) |
| Space | Best | O(1) | O(1) | O(1) | O(m) |
| Space | Expected | O(n/2) | O(log n) | O(log n) | O(m+log n) |
| Spoce | Worst | O(n/2) | O(log n) | O(log n) | O(m+log n) |
Roadmap
- Lower worst-case time complexity from O(n log n) to O(n) for selection algorithms.
- Add
SliceExttrait for n-dimensional array or (sub)view with methods expectingAxisas their first argument. Comparing methods will always be suffixed with_byor_by_keydefining how to compare multi-dimensional elements (e.g., columns) along the provided axis of interest (e.g., rows).
Features
alloc: Enables stable sort. Enabled bystd.std: Enables selection of many indices. Enabled by default.
Re-exports
pub use ndarray;
Traits
- Extension trait for 1-dimensional
ArrayBase<S, Ix1>array or (sub)view with arbitrary memory layout (e.g., non-contiguous) providing methods (e.g., sorting, selection, search) similar toslice.