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