-
Notifications
You must be signed in to change notification settings - Fork 224
/
quantile.js
109 lines (98 loc) · 3.38 KB
/
quantile.js
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
import quantileSorted from "./quantile_sorted.js";
import quickselect from "./quickselect.js";
/**
* 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;