build(deps-dev): apply updates
[benchmarks-js.git] / quick-select.mjs
1 import { randomInt } from 'node:crypto'
2
3 import { bench, group, run } from 'tatami-ng'
4
5 /**
6 * @param numberOfWorkers
7 * @param maxNumberOfTasksPerWorker
8 * @returns
9 */
10 function generateRandomTasksMap (
11 numberOfWorkers,
12 maxNumberOfTasksPerWorker = 10
13 ) {
14 const tasksArray = []
15 for (let i = 0; i < numberOfWorkers; i++) {
16 const task = [i, randomInt(maxNumberOfTasksPerWorker)]
17 tasksArray.push(task)
18 }
19 return new Map(tasksArray)
20 }
21
22 const tasksMap = generateRandomTasksMap(60, 20)
23
24 /**
25 * @param tasksMap
26 * @returns
27 */
28 function loopSelect (tasksMap) {
29 let minKey
30 let minValue = Number.POSITIVE_INFINITY
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
42 /**
43 * @param tasksMap
44 * @returns
45 */
46 function 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
58 const defaultComparator = (a, b) => {
59 return a < b
60 }
61
62 const defaultPivotIndexSelect = (leftIndex, rightIndex) => {
63 return leftIndex + Math.floor((rightIndex - leftIndex) / 2)
64 }
65
66 const randomPivotIndexSelect = (leftIndex, rightIndex) => {
67 return randomInt(leftIndex, rightIndex)
68 }
69
70 /**
71 * @param array
72 * @param index1
73 * @param index2
74 */
75 function swap (array, index1, index2) {
76 const tmp = array[index1]
77 array[index1] = array[index2]
78 array[index2] = tmp
79 }
80
81 /**
82 * @param array
83 * @param leftIndex
84 * @param rightIndex
85 * @param pivotIndex
86 * @param compare
87 * @returns
88 */
89 function 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
109 /**
110 * @param array
111 * @param k
112 * @param leftIndex
113 * @param rightIndex
114 * @param compare
115 * @param pivotIndexSelect
116 * @returns
117 */
118 function 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
140 /**
141 * @param array
142 * @param k
143 * @param leftIndex
144 * @param rightIndex
145 * @param compare
146 * @param pivotIndexSelect
147 * @returns
148 */
149 function 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
169 /**
170 * @param tasksMap
171 * @returns
172 */
173 function 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
181 /**
182 * @param tasksMap
183 * @returns
184 */
185 function 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
200 /**
201 * @param tasksMap
202 * @returns
203 */
204 function 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
212 /**
213 * @param tasksMap
214 * @returns
215 */
216 function 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
231 group('Quick select', () => {
232 bench('Loop select', () => {
233 loopSelect(tasksMap)
234 })
235 bench('Array sort select', () => {
236 arraySortSelect(tasksMap)
237 })
238 bench('Quick select loop', () => {
239 quickSelectLoop(tasksMap)
240 })
241 bench('Quick select loop with random pivot', () => {
242 quickSelectLoopRandomPivot(tasksMap)
243 })
244 bench('Quick select recursion', () => {
245 quickSelectRecursion(tasksMap)
246 })
247 bench('Quick select recursion with random pivot', () => {
248 quickSelectRecursionRandomPivot(tasksMap)
249 })
250 })
251
252 await run({
253 units: true,
254 })