1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
import quantileSorted from "./quantile_sorted";import quickselect from "./quickselect";
/** * The [quantile](https://en.wikipedia.org/wiki/Quantile): * this is a population quantile, since we assume to know the entire * dataset in this library. This is an implementation of the * [Quantiles of a Population](http://en.wikipedia.org/wiki/Quantile#Quantiles_of_a_population) * algorithm from wikipedia. * * Sample is a one-dimensional array of numbers, * and p is either a decimal number from 0 to 1 or an array of decimal * numbers from 0 to 1. * In terms of a k/q quantile, p = k/q - it's just dealing with fractions or dealing * with decimal values. * When p is an array, the result of the function is also an array containing the appropriate * quantiles in input order * * @param {Array<number>} x sample of one or more numbers * @param {Array<number> | number} p the desired quantile, as a number between 0 and 1 * @returns {number} quantile * @example * quantile([3, 6, 7, 8, 8, 9, 10, 13, 15, 16, 20], 0.5); // => 9 */function quantile(x, p) {    const copy = x.slice();
    if (Array.isArray(p)) {        // rearrange elements so that each element corresponding to a requested        // quantile is on a place it would be if the array was fully sorted        multiQuantileSelect(copy, p);        // Initialize the result array        const results = [];        // For each requested quantile        for (let i = 0; i < p.length; i++) {            results[i] = quantileSorted(copy, p[i]);        }        return results;    } else {        const idx = quantileIndex(copy.length, p);        quantileSelect(copy, idx, 0, copy.length - 1);        return quantileSorted(copy, p);    }}
function quantileSelect(arr, k, left, right) {    if (k % 1 === 0) {        quickselect(arr, k, left, right);    } else {        k = Math.floor(k);        quickselect(arr, k, left, right);        quickselect(arr, k + 1, k + 1, right);    }}
function multiQuantileSelect(arr, p) {    const indices = [0];    for (let i = 0; i < p.length; i++) {        indices.push(quantileIndex(arr.length, p[i]));    }    indices.push(arr.length - 1);    indices.sort(compare);
    const stack = [0, indices.length - 1];
    while (stack.length) {        const r = Math.ceil(stack.pop());        const l = Math.floor(stack.pop());        if (r - l <= 1) continue;
        const m = Math.floor((l + r) / 2);        quantileSelect(            arr,            indices[m],            Math.floor(indices[l]),            Math.ceil(indices[r])        );
        stack.push(l, m, m, r);    }}
function compare(a, b) {    return a - b;}
function quantileIndex(len, p) {    const idx = len * p;    if (p === 1) {        // If p is 1, directly return the last index        return len - 1;    } else if (p === 0) {        // If p is 0, directly return the first index        return 0;    } else if (idx % 1 !== 0) {        // If index is not integer, return the next index in array        return Math.ceil(idx) - 1;    } else if (len % 2 === 0) {        // If the list has even-length, we'll return the middle of two indices        // around quantile to indicate that we need an average value of the two        return idx - 0.5;    } else {        // Finally, in the simple case of an integer index        // with an odd-length list, return the index        return idx;    }}
export default quantile;