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