Refactor generateRandomFloat() helper
[benchmarks-js.git] / quick-select.js
CommitLineData
e2bfb549
JB
1const Benchmark = require('benny')
2const { generateRandomInteger } = require('./benchmark-utils')
ed2968f2 3
e9bfc28e
JB
4/**
5 * @param numberOfWorkers
6 * @param maxNumberOfTasksPerWorker
7fd91296 7 * @returns
e9bfc28e 8 */
ed2968f2
JB
9function 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
21const tasksMap = generateRandomTasksMap(60, 20)
22
e9bfc28e
JB
23/**
24 * @param tasksMap
7fd91296 25 * @returns
e9bfc28e 26 */
ed2968f2
JB
27function 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
e9bfc28e
JB
41/**
42 * @param tasksMap
7fd91296 43 * @returns
e9bfc28e 44 */
ed2968f2
JB
45function 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
57const defaultComparator = (a, b) => {
58 return a < b
59}
60
61const defaultPivotIndexSelect = (leftIndex, rightIndex) => {
62 return leftIndex + Math.floor((rightIndex - leftIndex) / 2)
63}
64
65const randomPivotIndexSelect = (leftIndex, rightIndex) => {
da504870 66 return generateRandomInteger(rightIndex, leftIndex)
ed2968f2
JB
67}
68
e9bfc28e
JB
69/**
70 * @param array
71 * @param index1
72 * @param index2
73 */
ed2968f2
JB
74function swap (array, index1, index2) {
75 const tmp = array[index1]
76 array[index1] = array[index2]
77 array[index2] = tmp
78}
79
e9bfc28e
JB
80/**
81 * @param array
82 * @param leftIndex
83 * @param rightIndex
84 * @param pivotIndex
85 * @param compare
7fd91296 86 * @returns
e9bfc28e 87 */
ed2968f2
JB
88function 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
e9bfc28e
JB
108/**
109 * @param array
110 * @param k
111 * @param leftIndex
112 * @param rightIndex
113 * @param compare
114 * @param pivotIndexSelect
7fd91296 115 * @returns
e9bfc28e 116 */
ed2968f2
JB
117function 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
e9bfc28e
JB
139/**
140 * @param array
141 * @param k
142 * @param leftIndex
143 * @param rightIndex
144 * @param compare
145 * @param pivotIndexSelect
7fd91296 146 * @returns
e9bfc28e 147 */
ed2968f2
JB
148function 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
e9bfc28e
JB
168/**
169 * @param tasksMap
7fd91296 170 * @returns
e9bfc28e 171 */
ed2968f2
JB
172function 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
e9bfc28e
JB
180/**
181 * @param tasksMap
7fd91296 182 * @returns
e9bfc28e 183 */
ed2968f2
JB
184function 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
e9bfc28e
JB
199/**
200 * @param tasksMap
7fd91296 201 * @returns
e9bfc28e 202 */
ed2968f2
JB
203function 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
e9bfc28e
JB
211/**
212 * @param tasksMap
7fd91296 213 * @returns
e9bfc28e 214 */
ed2968f2
JB
215function 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
e2bfb549
JB
230Benchmark.suite(
231 'Quick select',
232 Benchmark.add('Loop select', () => {
ed2968f2 233 loopSelect(tasksMap)
e2bfb549
JB
234 }),
235 Benchmark.add('Array sort select', () => {
ed2968f2 236 arraySortSelect(tasksMap)
e2bfb549
JB
237 }),
238 Benchmark.add('Quick select loop', () => {
ed2968f2 239 quickSelectLoop(tasksMap)
e2bfb549
JB
240 }),
241 Benchmark.add('Quick select loop with random pivot', () => {
ed2968f2 242 quickSelectLoopRandomPivot(tasksMap)
e2bfb549
JB
243 }),
244 Benchmark.add('Quick select recursion', () => {
ed2968f2 245 quickSelectRecursion(tasksMap)
e2bfb549
JB
246 }),
247 Benchmark.add('Quick select recursion with random pivot', () => {
ed2968f2 248 quickSelectRecursionRandomPivot(tasksMap)
e2bfb549
JB
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
ed2968f2 266 })
e2bfb549 267)