median-quickselect
v1.0.1
Published
Fast implementation of median search using quickselect algorithm
Downloads
107,199
Readme
median-quickselect
Fast implementation of lower median search using Quick select algorithm. Ported from this C implementation.
Please read "Fast median search: an ANSI C implementation" by Nicolas Devillard for more info.
Note that result can be different from other packages, as median-quickselect
calculates lower median, because taking an average of the two central elements requires two calls to the routine, doubling the processing time.
Installation
Install from npm:
npm install --save median-quickselect
Or hot-link via unpkg.com
<script src="https://unpkg.com/median-quickselect"></script>
Usage
const median = require('median-quickselect');
median([1, 4, 10, 2, 5, 0, -5]); // 2
Note that the **order of elements ** on array passed to median()
will be changed after call.
Benchmark
$ npm run bench 1001 ms master
> node test/benchmark.js
benchmarking dataset of 100 numbers
median: 0.891ms
fast-median: 0.999ms
compute-median: 0.269ms
stats-median: 0.159ms
median-quickselect: 0.230ms
benchmarking dataset of 1000 numbers
median: 0.849ms
fast-median: 1.713ms
compute-median: 0.562ms
stats-median: 0.210ms
median-quickselect: 0.204ms
benchmarking dataset of 10000 numbers
median: 6.249ms
fast-median: 9.413ms
compute-median: 5.816ms
stats-median: 5.101ms
median-quickselect: 2.027ms
benchmarking dataset of 1000000 numbers
median: 576.688ms
fast-median: 886.843ms
compute-median: 786.714ms
stats-median: 662.177ms
median-quickselect: 13.027ms
benchmarking dataset of 10000000 numbers
median: 6347.193ms
fast-median: 8722.377ms
compute-median: 7278.490ms
stats-median: 7089.452ms
median-quickselect: 119.298ms