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 untouched

Current Implementation

Complexities where n is the length of the (sub)view.

AlgorithmStableAllocationRecursiveAverageWorse-Case
SortingyesyesnoO(n)O(n log(n))
SortingnonoyesO(n)O(n log(n))
SelectionnononoO(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).

Features

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

Re-exports

Traits