scijs / ndarray-select

Quick select algorithm for ndarrays
MIT License
8 stars 0 forks source link

ndarray-select

Finds the kth element in an ndarray in linear time with high probability. This implementation is based on the quick select algorithm and mutates the array in place.

build status

Examples

Single list

var pack = require("ndarray-pack")
var ndselect = require("ndarray-select")

var points = pack([0, 0, 1, 2.5, -1])

//Find the median element in the list
var median = ndselect(points, points.shape[0]>>1)

console.log(median.get())

Output

0 2.5 -1

Multiple lists

It is also possible to select vectors (using lexicographical comparisons):

var pack = require("ndarray-pack")
var ndselect = require("ndarray-select")

var points = pack([
  [0, 0, 1],
  [100, 0, 10],
  [50, 1, 10],
  [0, 2.5, -1],
  [-1, -1, -1]
])

//Find the median element in the list
var median = ndselect(points, points.shape[0]>>1)

console.log(median.get(0), median.get(1), median.get(2))

Output

0 2.5 -1

Install

Install using npm:

npm install ndarray-select

API

var ndselect = require("ndarray-select")

ndselect(array, k[, compare])

Selects the kth item from the ndarray array along the first axis of array.

Returns An ndarray view of array.pick(k)

Note This method modifies array. After completion, the element at position k will be in sorted order, with all elements <array.pick(k) occuring before k and all elements >array.pick(k) after k in the list.

ndselect.compile(order, useCompare, dtype)

Precompiles an optimized selection algorithm for an array with the given index order and datatype.

Returns An optimized ndselect function

License

(c) 2014 Mikola Lysenko. MIT License