1 |
|
2 |
|
3 | const isInteger = require('../../utils/number').isInteger
|
4 |
|
5 | function factory (type, config, load, typed) {
|
6 | const isNumeric = load(require('../utils/isNumeric'))
|
7 | const isNaN = load(require('../utils/isNaN'))
|
8 | const asc = load(require('../relational/compare'))
|
9 |
|
10 | function desc (a, b) {
|
11 | return -asc(a, b)
|
12 | }
|
13 |
|
14 | /**
|
15 | * Partition-based selection of an array or 1D matrix.
|
16 | * Will find the kth smallest value, and mutates the input array.
|
17 | * Uses Quickselect.
|
18 | *
|
19 | * Syntax:
|
20 | *
|
21 | * math.partitionSelect(x, k)
|
22 | * math.partitionSelect(x, k, compare)
|
23 | *
|
24 | * Examples:
|
25 | *
|
26 | * math.partitionSelect([5, 10, 1], 2) // returns 10
|
27 | * math.partitionSelect(['C', 'B', 'A', 'D'], 1) // returns 'B'
|
28 | *
|
29 | * function sortByLength (a, b) {
|
30 | * return a.length - b.length
|
31 | * }
|
32 | * math.partitionSelect(['Langdon', 'Tom', 'Sara'], 2, sortByLength) // returns 'Langdon'
|
33 | *
|
34 | * See also:
|
35 | *
|
36 | * sort
|
37 | *
|
38 | * @param {Matrix | Array} x A one dimensional matrix or array to sort
|
39 | * @param {Number} k The kth smallest value to be retrieved zero-based index
|
40 | * @param {Function | 'asc' | 'desc'} [compare='asc']
|
41 | * An optional comparator function. The function is called as
|
42 | * `compare(a, b)`, and must return 1 when a > b, -1 when a < b,
|
43 | * and 0 when a == b.
|
44 | * @return {*} Returns the kth lowest value.
|
45 | */
|
46 | return typed('partitionSelect', {
|
47 | 'Array | Matrix, number': function (x, k) {
|
48 | return _partitionSelect(x, k, asc)
|
49 | },
|
50 |
|
51 | 'Array | Matrix, number, string': function (x, k, compare) {
|
52 | if (compare === 'asc') {
|
53 | return _partitionSelect(x, k, asc)
|
54 | } else if (compare === 'desc') {
|
55 | return _partitionSelect(x, k, desc)
|
56 | } else {
|
57 | throw new Error('Compare string must be "asc" or "desc"')
|
58 | }
|
59 | },
|
60 |
|
61 | 'Array | Matrix, number, function': _partitionSelect
|
62 | })
|
63 |
|
64 | function _partitionSelect (x, k, compare) {
|
65 | if (!isInteger(k) || k < 0) {
|
66 | throw new Error('k must be a non-negative integer')
|
67 | }
|
68 |
|
69 | if (type.isMatrix(x)) {
|
70 | const size = x.size()
|
71 | if (size.length > 1) {
|
72 | throw new Error('Only one dimensional matrices supported')
|
73 | }
|
74 | return quickSelect(x.valueOf(), k, compare)
|
75 | }
|
76 |
|
77 | if (Array.isArray(x)) {
|
78 | return quickSelect(x, k, compare)
|
79 | }
|
80 | }
|
81 |
|
82 | /**
|
83 | * Quickselect algorithm.
|
84 | * Code adapted from:
|
85 | * http://blog.teamleadnet.com/2012/07/quick-select-algorithm-find-kth-element.html
|
86 | *
|
87 | * @param {Array} arr
|
88 | * @param {Number} k
|
89 | * @param {Function} compare
|
90 | * @private
|
91 | */
|
92 | function quickSelect (arr, k, compare) {
|
93 | if (k >= arr.length) {
|
94 | throw new Error('k out of bounds')
|
95 | }
|
96 |
|
97 | // check for NaN values since these can cause an infinite while loop
|
98 | for (let i = 0; i < arr.length; i++) {
|
99 | if (isNumeric(arr[i]) && isNaN(arr[i])) {
|
100 | return arr[i] // return NaN
|
101 | }
|
102 | }
|
103 |
|
104 | let from = 0
|
105 | let to = arr.length - 1
|
106 |
|
107 | // if from == to we reached the kth element
|
108 | while (from < to) {
|
109 | let r = from
|
110 | let w = to
|
111 | const pivot = arr[Math.floor(Math.random() * (to - from + 1)) + from]
|
112 |
|
113 | // stop if the reader and writer meets
|
114 | while (r < w) {
|
115 | // arr[r] >= pivot
|
116 | if (compare(arr[r], pivot) >= 0) { // put the large values at the end
|
117 | const tmp = arr[w]
|
118 | arr[w] = arr[r]
|
119 | arr[r] = tmp
|
120 | --w
|
121 | } else { // the value is smaller than the pivot, skip
|
122 | ++r
|
123 | }
|
124 | }
|
125 |
|
126 | // if we stepped up (r++) we need to step one down (arr[r] > pivot)
|
127 | if (compare(arr[r], pivot) > 0) {
|
128 | --r
|
129 | }
|
130 |
|
131 | // the r pointer is on the end of the first k elements
|
132 | if (k <= r) {
|
133 | to = r
|
134 | } else {
|
135 | from = r + 1
|
136 | }
|
137 | }
|
138 |
|
139 | return arr[k]
|
140 | }
|
141 | }
|
142 |
|
143 | exports.name = 'partitionSelect'
|
144 | exports.factory = factory
|