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 for ndarray with arbitrary memory layout (e.g., non-contiguous).

Example

use ndarray_slice::{Slice1Ext, ndarray::arr2};

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

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.

Algorithm	Stable	Allocation	Recursive	Average	Worse-Case
Sorting	yes	yes	no	O(n)	O(n log(n))
Sorting	no	no	yes	O(n)	O(n log(n))
Selection	no	no	no	O(n)	O(n log(n))

Roadmap

Lower worst-case complexity from O(n log(n)) to O(n) for selection algorithms.
Add SliceExt trait for n-dimensional array or (sub)view with methods expecting Axis as their first argument. Comparing methods will always be suffixed with _by or _by_key defining how to compare multi-dimensional elements (e.g., columns) along the provided axis of interest (e.g., rows).

See the release history to keep track of the development.

Features

alloc: Enables stable sort. Enabled by std.
std: Enables selection of many indices. Enabled by default.

License

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.