#sorting #array #ndarray #memory-layout #numpy #select

no-std ndarray-slice

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

10 unstable releases (3 breaking)

0.4.0 Sep 14, 2024
0.3.1 Jun 13, 2024
0.3.0 Mar 19, 2024
0.2.4 Jan 23, 2024
0.1.1 Apr 7, 2023

#106 in Algorithms

Download history 163/week @ 2024-07-14 191/week @ 2024-07-21 174/week @ 2024-07-28 126/week @ 2024-08-04 201/week @ 2024-08-11 167/week @ 2024-08-18 150/week @ 2024-08-25 142/week @ 2024-09-01 288/week @ 2024-09-08 243/week @ 2024-09-15 241/week @ 2024-09-22 160/week @ 2024-09-29 90/week @ 2024-10-06 103/week @ 2024-10-13 115/week @ 2024-10-20 98/week @ 2024-10-27

416 downloads per month
Used in 2 crates

MIT/Apache

240KB
3.5K SLoC

ndarray-slice

Build Documentation Downloads Version Rust License

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 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*.

License

Copyright © 2023 Rouven Spreckels rs@qu1x.dev

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

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.

Dependencies

~1.4–8.5MB
~78K SLoC