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