### 9 releases

0.3.1 | Jun 13, 2024 |
---|---|

0.3.0 | Mar 19, 2024 |

0.2.4 | Jan 23, 2024 |

0.2.3 | May 28, 2023 |

0.1.1 | Apr 7, 2023 |

#**95** in Algorithms

**666** downloads per month

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

and
`slice`

for `rayon ::`slice

`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

trait for`SliceExt`*n*-dimensional array or (sub)view with methods expecting

as their first argument. Comparing methods will always be suffixed with`Axis`

or`_by`

defining how to compare multi-dimensional elements (e.g., rows) along the provided axis of interest (e.g., columns).`_by_key`

See the release history to keep track of the development.

## Features

for stable`alloc`

/`sort`

/`sort_by`

. Enabled by`sort_by_key`

.`std`

for stable`std`

. Enabled by`sort_by_cached_key`

or`default`

.`rayon`

for spilling recursion stack over to heap if necessary. Enabled by`stacker`

.`default`

for parallel`rayon`

/`par_sort``*`

.`par_select_many_nth_unstable``*`

# License

Copyright © 2023 Rouven Spreckels rs@qu1x.dev

This project contains derivative works of

and `rust`

. For full authorship information,
see their version control histories. Respective copyrights are retained by their contributors.`rayon`

Like the original works, 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.

#### Dependencies

~1.4–2.1MB

~39K SLoC