implement sorting, including argsort

haydnv / ha-ndarray

An n-dimensional array for Rust with support for OpenCL

Apache License 2.0

1 stars 1 forks source link

implement sorting, including argsort #1

Open haydnv opened 1 year ago

haydnv commented 1 year ago

The fastest general-case parallel sort is IBR (interval-based rearrangement) bi-tonic: https://arxiv.org/abs/1511.03404

Simple bi-tonic sort and IBR bi-tonic sort performance converges around 2^17-2^20 keys

haydnv commented 1 year ago

This requires:

slice: https://github.com/haydnv/ha-ndarray/issues/2
concat: https://github.com/haydnv/ha-ndarray/issues/3
write: https://docs.rs/custos/0.5.0/custos/trait.WriteBuf.html#tymethod.write

Sorting a key-value set (e.g. a (Matrix, Buffer) tuple of coordinates and values in a sparse tensor) will also require an argsort op which sorts a range of indices (for the Buffer according to the order of the keys in the coordinate Matrix)