## no-std ndarray-slice

Fast and robust slice-based algorithms (e.g., sorting, selection, search) for non-contiguous (sub)views into n-dimensional arrays

### 9 releases

 0.3.1 Jun 13, 2024 Mar 19, 2024 Jan 23, 2024 May 28, 2023 Apr 7, 2023

#95 in Algorithms

Used in 2 crates

MIT/Apache

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)

• 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., rows) along the provided axis of interest (e.g., columns).

See the release history to keep track of the development.

## Features

• `alloc` for stable `sort`/`sort_by`/`sort_by_key`. Enabled by `std`.
• `std` for stable `sort_by_cached_key`. Enabled by `default` or `rayon`.
• `stacker` for spilling recursion stack over to heap if necessary. Enabled by `default`.
• `rayon` for parallel `par_sort*`/`par_select_many_nth_unstable*`.

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.