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