build(deps-dev): apply updates
[benchmarks-js.git] / quick-select.mjs
CommitLineData
1ccd0724 1import { randomInt } from 'node:crypto'
0c01f51c 2
4676a95c 3import { bench, group, run } from 'tatami-ng'
ed2968f2 4
e9bfc28e
JB
5/**
6 * @param numberOfWorkers
7 * @param maxNumberOfTasksPerWorker
7fd91296 8 * @returns
e9bfc28e 9 */
ed2968f2
JB
10function generateRandomTasksMap (
11 numberOfWorkers,
12 maxNumberOfTasksPerWorker = 10
13) {
14 const tasksArray = []
15 for (let i = 0; i < numberOfWorkers; i++) {
1ccd0724 16 const task = [i, randomInt(maxNumberOfTasksPerWorker)]
ed2968f2
JB
17 tasksArray.push(task)
18 }
19 return new Map(tasksArray)
20}
21
22const tasksMap = generateRandomTasksMap(60, 20)
23
e9bfc28e
JB
24/**
25 * @param tasksMap
7fd91296 26 * @returns
e9bfc28e 27 */
ed2968f2 28function loopSelect (tasksMap) {
ed2968f2 29 let minKey
ae56b43d 30 let minValue = Number.POSITIVE_INFINITY
ed2968f2
JB
31 for (const [key, value] of tasksMap) {
32 if (value === 0) {
33 return key
34 } else if (value < minValue) {
35 minKey = key
36 minValue = value
37 }
38 }
39 return [minKey, minValue]
40}
41
e9bfc28e
JB
42/**
43 * @param tasksMap
7fd91296 44 * @returns
e9bfc28e 45 */
ed2968f2
JB
46function arraySortSelect (tasksMap) {
47 const tasksArray = Array.from(tasksMap)
48 return tasksArray.sort((a, b) => {
49 if (a[1] < b[1]) {
50 return -1
51 } else if (a[1] > b[1]) {
52 return 1
53 }
54 return 0
55 })[0]
56}
57
58const defaultComparator = (a, b) => {
59 return a < b
60}
61
62const defaultPivotIndexSelect = (leftIndex, rightIndex) => {
63 return leftIndex + Math.floor((rightIndex - leftIndex) / 2)
64}
65
66const randomPivotIndexSelect = (leftIndex, rightIndex) => {
1ccd0724 67 return randomInt(leftIndex, rightIndex)
ed2968f2
JB
68}
69
e9bfc28e
JB
70/**
71 * @param array
72 * @param index1
73 * @param index2
74 */
ed2968f2
JB
75function swap (array, index1, index2) {
76 const tmp = array[index1]
77 array[index1] = array[index2]
78 array[index2] = tmp
79}
80
e9bfc28e
JB
81/**
82 * @param array
83 * @param leftIndex
84 * @param rightIndex
85 * @param pivotIndex
86 * @param compare
7fd91296 87 * @returns
e9bfc28e 88 */
ed2968f2
JB
89function partition (
90 array,
91 leftIndex,
92 rightIndex,
93 pivotIndex,
94 compare = defaultComparator
95) {
96 const pivotValue = array[pivotIndex]
97 swap(array, pivotIndex, rightIndex)
98 let storeIndex = leftIndex
99 for (let i = leftIndex; i < rightIndex; i++) {
100 if (compare(array[i], pivotValue)) {
101 swap(array, storeIndex, i)
102 storeIndex++
103 }
104 }
105 swap(array, rightIndex, storeIndex)
106 return storeIndex
107}
108
e9bfc28e
JB
109/**
110 * @param array
111 * @param k
112 * @param leftIndex
113 * @param rightIndex
114 * @param compare
115 * @param pivotIndexSelect
7fd91296 116 * @returns
e9bfc28e 117 */
ed2968f2
JB
118function selectLoop (
119 array,
120 k,
121 leftIndex,
122 rightIndex,
123 compare = defaultComparator,
124 pivotIndexSelect = defaultPivotIndexSelect
125) {
126 while (true) {
127 if (leftIndex === rightIndex) return array[leftIndex]
128 let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
129 pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
130 if (k === pivotIndex) {
131 return array[k]
132 } else if (k < pivotIndex) {
133 rightIndex = pivotIndex - 1
134 } else {
135 leftIndex = pivotIndex + 1
136 }
137 }
138}
139
e9bfc28e
JB
140/**
141 * @param array
142 * @param k
143 * @param leftIndex
144 * @param rightIndex
145 * @param compare
146 * @param pivotIndexSelect
7fd91296 147 * @returns
e9bfc28e 148 */
ed2968f2
JB
149function selectRecursion (
150 array,
151 k,
152 leftIndex,
153 rightIndex,
154 compare = defaultComparator,
155 pivotIndexSelect = defaultPivotIndexSelect
156) {
157 if (leftIndex === rightIndex) return array[leftIndex]
158 let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
159 pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
160 if (k === pivotIndex) {
161 return array[k]
162 } else if (k < pivotIndex) {
163 return selectRecursion(array, k, leftIndex, pivotIndex - 1, compare)
164 } else {
165 return selectRecursion(array, k, pivotIndex + 1, rightIndex, k, compare)
166 }
167}
168
e9bfc28e
JB
169/**
170 * @param tasksMap
7fd91296 171 * @returns
e9bfc28e 172 */
ed2968f2
JB
173function quickSelectLoop (tasksMap) {
174 const tasksArray = Array.from(tasksMap)
175
176 return selectLoop(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
177 return a[1] < b[1]
178 })
179}
180
e9bfc28e
JB
181/**
182 * @param tasksMap
7fd91296 183 * @returns
e9bfc28e 184 */
ed2968f2
JB
185function quickSelectLoopRandomPivot (tasksMap) {
186 const tasksArray = Array.from(tasksMap)
187
188 return selectLoop(
189 tasksArray,
190 0,
191 0,
192 tasksArray.length - 1,
193 (a, b) => {
194 return a[1] < b[1]
195 },
196 randomPivotIndexSelect
197 )
198}
199
e9bfc28e
JB
200/**
201 * @param tasksMap
7fd91296 202 * @returns
e9bfc28e 203 */
ed2968f2
JB
204function quickSelectRecursion (tasksMap) {
205 const tasksArray = Array.from(tasksMap)
206
207 return selectRecursion(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
208 return a[1] < b[1]
209 })
210}
211
e9bfc28e
JB
212/**
213 * @param tasksMap
7fd91296 214 * @returns
e9bfc28e 215 */
ed2968f2
JB
216function quickSelectRecursionRandomPivot (tasksMap) {
217 const tasksArray = Array.from(tasksMap)
218
219 return selectRecursion(
220 tasksArray,
221 0,
222 0,
223 tasksArray.length - 1,
224 (a, b) => {
225 return a[1] < b[1]
226 },
227 randomPivotIndexSelect
228 )
229}
230
ab9a08f3
JB
231group('Quick select', () => {
232 bench('Loop select', () => {
ed2968f2 233 loopSelect(tasksMap)
ab9a08f3
JB
234 })
235 bench('Array sort select', () => {
ed2968f2 236 arraySortSelect(tasksMap)
ab9a08f3
JB
237 })
238 bench('Quick select loop', () => {
ed2968f2 239 quickSelectLoop(tasksMap)
ab9a08f3
JB
240 })
241 bench('Quick select loop with random pivot', () => {
ed2968f2 242 quickSelectLoopRandomPivot(tasksMap)
ab9a08f3
JB
243 })
244 bench('Quick select recursion', () => {
ed2968f2 245 quickSelectRecursion(tasksMap)
ab9a08f3
JB
246 })
247 bench('Quick select recursion with random pivot', () => {
ed2968f2
JB
248 quickSelectRecursionRandomPivot(tasksMap)
249 })
ab9a08f3
JB
250})
251
252await run({
ebf80fe4 253 units: true,
ab9a08f3 254})