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 | |
9 | */ | |
292ad316 JB |
10 | function generateRandomTasksMap ( |
11 | numberOfWorkers, | |
12 | maxNumberOfTasksPerWorker = 10 | |
13 | ) { | |
14 | const tasksArray = [] | |
15 | for (let i = 0; i < numberOfWorkers; i++) { | |
c7ed5d3b | 16 | const task = [i, randomInt(maxNumberOfTasksPerWorker)] |
292ad316 JB |
17 | tasksArray.push(task) |
18 | } | |
19 | return new Map(tasksArray) | |
20 | } | |
21 | ||
22 | const tasksMap = generateRandomTasksMap(60, 20) | |
74750c7f | 23 | |
3a502712 JB |
24 | /** |
25 | * | |
26 | * @param tasksMap | |
27 | */ | |
74750c7f | 28 | function loopSelect (tasksMap) { |
74750c7f | 29 | let minKey |
80115618 | 30 | let minValue = Number.POSITIVE_INFINITY |
74750c7f JB |
31 | for (const [key, value] of tasksMap) { |
32 | if (value === 0) { | |
33 | return key | |
34 | } else if (value < minValue) { | |
35 | minKey = key | |
36 | minValue = value | |
37 | } | |
38 | } | |
39 | return [minKey, minValue] | |
40 | } | |
41 | ||
3a502712 JB |
42 | /** |
43 | * | |
44 | * @param tasksMap | |
45 | */ | |
74750c7f JB |
46 | function arraySortSelect (tasksMap) { |
47 | const tasksArray = Array.from(tasksMap) | |
48 | return tasksArray.sort((a, b) => { | |
49 | if (a[1] < b[1]) { | |
50 | return -1 | |
51 | } else if (a[1] > b[1]) { | |
52 | return 1 | |
53 | } | |
54 | return 0 | |
55 | })[0] | |
56 | } | |
57 | ||
58 | const defaultComparator = (a, b) => { | |
59 | return a < b | |
60 | } | |
61 | ||
62 | const defaultPivotIndexSelect = (leftIndex, rightIndex) => { | |
63 | return leftIndex + Math.floor((rightIndex - leftIndex) / 2) | |
64 | } | |
65 | ||
292ad316 | 66 | const randomPivotIndexSelect = (leftIndex, rightIndex) => { |
c7ed5d3b | 67 | return randomInt(leftIndex, rightIndex) |
292ad316 JB |
68 | } |
69 | ||
3a502712 JB |
70 | /** |
71 | * | |
72 | * @param array | |
73 | * @param index1 | |
74 | * @param index2 | |
75 | */ | |
74750c7f JB |
76 | function swap (array, index1, index2) { |
77 | const tmp = array[index1] | |
78 | array[index1] = array[index2] | |
79 | array[index2] = tmp | |
80 | } | |
81 | ||
3a502712 JB |
82 | /** |
83 | * | |
84 | * @param array | |
85 | * @param leftIndex | |
86 | * @param rightIndex | |
87 | * @param pivotIndex | |
88 | * @param compare | |
89 | */ | |
74750c7f 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 | |
292ad316 | 100 | for (let i = leftIndex; i < rightIndex; i++) { |
74750c7f JB |
101 | if (compare(array[i], pivotValue)) { |
102 | swap(array, storeIndex, i) | |
292ad316 | 103 | storeIndex++ |
74750c7f JB |
104 | } |
105 | } | |
106 | swap(array, rightIndex, storeIndex) | |
107 | return storeIndex | |
108 | } | |
109 | ||
3a502712 JB |
110 | /** |
111 | * | |
112 | * @param array | |
113 | * @param k | |
114 | * @param leftIndex | |
115 | * @param rightIndex | |
116 | * @param compare | |
117 | * @param pivotIndexSelect | |
118 | */ | |
74750c7f 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 | ||
3a502712 JB |
141 | /** |
142 | * | |
143 | * @param array | |
144 | * @param k | |
145 | * @param leftIndex | |
146 | * @param rightIndex | |
147 | * @param compare | |
148 | * @param pivotIndexSelect | |
149 | */ | |
74750c7f 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 | ||
3a502712 JB |
170 | /** |
171 | * | |
172 | * @param tasksMap | |
173 | */ | |
74750c7f 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 | ||
3a502712 JB |
182 | /** |
183 | * | |
184 | * @param tasksMap | |
185 | */ | |
74750c7f 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 | }, | |
292ad316 | 197 | randomPivotIndexSelect |
74750c7f JB |
198 | ) |
199 | } | |
200 | ||
3a502712 JB |
201 | /** |
202 | * | |
203 | * @param tasksMap | |
204 | */ | |
74750c7f 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 | ||
3a502712 JB |
213 | /** |
214 | * | |
215 | * @param tasksMap | |
216 | */ | |
74750c7f 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 | }, | |
292ad316 | 228 | randomPivotIndexSelect |
74750c7f JB |
229 | ) |
230 | } | |
231 | ||
0804b9b4 JB |
232 | group('Least used worker tasks distribution', () => { |
233 | bench('Loop select', () => { | |
74750c7f | 234 | loopSelect(tasksMap) |
f1c674cd | 235 | }) |
0804b9b4 | 236 | bench('Array sort select', () => { |
74750c7f | 237 | arraySortSelect(tasksMap) |
f1c674cd | 238 | }) |
0804b9b4 | 239 | bench('Quick select loop', () => { |
74750c7f | 240 | quickSelectLoop(tasksMap) |
f1c674cd | 241 | }) |
0804b9b4 | 242 | bench('Quick select loop with random pivot', () => { |
74750c7f | 243 | quickSelectLoopRandomPivot(tasksMap) |
f1c674cd | 244 | }) |
0804b9b4 | 245 | bench('Quick select recursion', () => { |
74750c7f | 246 | quickSelectRecursion(tasksMap) |
f1c674cd | 247 | }) |
0804b9b4 | 248 | bench('Quick select recursion with random pivot', () => { |
74750c7f | 249 | quickSelectRecursionRandomPivot(tasksMap) |
f1c674cd | 250 | }) |
0804b9b4 JB |
251 | }) |
252 | ||
253 | await run({ units: true }) |