Commit | Line | Data |
---|---|---|
c7ed5d3b | 1 | import { randomInt } from 'node:crypto' |
ded253e2 | 2 | |
f1c674cd | 3 | import Benchmark from 'benchmark' |
ded253e2 | 4 | |
c7ed5d3b | 5 | import { LIST_FORMATTER } from '../benchmarks-utils.cjs' |
74750c7f | 6 | |
292ad316 JB |
7 | function generateRandomTasksMap ( |
8 | numberOfWorkers, | |
9 | maxNumberOfTasksPerWorker = 10 | |
10 | ) { | |
11 | const tasksArray = [] | |
12 | for (let i = 0; i < numberOfWorkers; i++) { | |
c7ed5d3b | 13 | const task = [i, randomInt(maxNumberOfTasksPerWorker)] |
292ad316 JB |
14 | tasksArray.push(task) |
15 | } | |
16 | return new Map(tasksArray) | |
17 | } | |
18 | ||
19 | const tasksMap = generateRandomTasksMap(60, 20) | |
74750c7f JB |
20 | |
21 | function loopSelect (tasksMap) { | |
74750c7f | 22 | let minKey |
2d909eab | 23 | let minValue = Infinity |
74750c7f JB |
24 | for (const [key, value] of tasksMap) { |
25 | if (value === 0) { | |
26 | return key | |
27 | } else if (value < minValue) { | |
28 | minKey = key | |
29 | minValue = value | |
30 | } | |
31 | } | |
32 | return [minKey, minValue] | |
33 | } | |
34 | ||
35 | function arraySortSelect (tasksMap) { | |
36 | const tasksArray = Array.from(tasksMap) | |
37 | return tasksArray.sort((a, b) => { | |
38 | if (a[1] < b[1]) { | |
39 | return -1 | |
40 | } else if (a[1] > b[1]) { | |
41 | return 1 | |
42 | } | |
43 | return 0 | |
44 | })[0] | |
45 | } | |
46 | ||
47 | const defaultComparator = (a, b) => { | |
48 | return a < b | |
49 | } | |
50 | ||
51 | const defaultPivotIndexSelect = (leftIndex, rightIndex) => { | |
52 | return leftIndex + Math.floor((rightIndex - leftIndex) / 2) | |
53 | } | |
54 | ||
292ad316 | 55 | const randomPivotIndexSelect = (leftIndex, rightIndex) => { |
c7ed5d3b | 56 | return randomInt(leftIndex, rightIndex) |
292ad316 JB |
57 | } |
58 | ||
74750c7f JB |
59 | function swap (array, index1, index2) { |
60 | const tmp = array[index1] | |
61 | array[index1] = array[index2] | |
62 | array[index2] = tmp | |
63 | } | |
64 | ||
65 | function partition ( | |
66 | array, | |
67 | leftIndex, | |
68 | rightIndex, | |
69 | pivotIndex, | |
70 | compare = defaultComparator | |
71 | ) { | |
72 | const pivotValue = array[pivotIndex] | |
73 | swap(array, pivotIndex, rightIndex) | |
74 | let storeIndex = leftIndex | |
292ad316 | 75 | for (let i = leftIndex; i < rightIndex; i++) { |
74750c7f JB |
76 | if (compare(array[i], pivotValue)) { |
77 | swap(array, storeIndex, i) | |
292ad316 | 78 | storeIndex++ |
74750c7f JB |
79 | } |
80 | } | |
81 | swap(array, rightIndex, storeIndex) | |
82 | return storeIndex | |
83 | } | |
84 | ||
85 | function selectLoop ( | |
86 | array, | |
87 | k, | |
88 | leftIndex, | |
89 | rightIndex, | |
90 | compare = defaultComparator, | |
91 | pivotIndexSelect = defaultPivotIndexSelect | |
92 | ) { | |
93 | while (true) { | |
94 | if (leftIndex === rightIndex) return array[leftIndex] | |
95 | let pivotIndex = pivotIndexSelect(leftIndex, rightIndex) | |
96 | pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare) | |
97 | if (k === pivotIndex) { | |
98 | return array[k] | |
99 | } else if (k < pivotIndex) { | |
100 | rightIndex = pivotIndex - 1 | |
101 | } else { | |
102 | leftIndex = pivotIndex + 1 | |
103 | } | |
104 | } | |
105 | } | |
106 | ||
107 | function selectRecursion ( | |
108 | array, | |
109 | k, | |
110 | leftIndex, | |
111 | rightIndex, | |
112 | compare = defaultComparator, | |
113 | pivotIndexSelect = defaultPivotIndexSelect | |
114 | ) { | |
115 | if (leftIndex === rightIndex) return array[leftIndex] | |
116 | let pivotIndex = pivotIndexSelect(leftIndex, rightIndex) | |
117 | pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare) | |
118 | if (k === pivotIndex) { | |
119 | return array[k] | |
120 | } else if (k < pivotIndex) { | |
121 | return selectRecursion(array, k, leftIndex, pivotIndex - 1, compare) | |
122 | } else { | |
123 | return selectRecursion(array, k, pivotIndex + 1, rightIndex, k, compare) | |
124 | } | |
125 | } | |
126 | ||
127 | function quickSelectLoop (tasksMap) { | |
128 | const tasksArray = Array.from(tasksMap) | |
129 | ||
130 | return selectLoop(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => { | |
131 | return a[1] < b[1] | |
132 | }) | |
133 | } | |
134 | ||
135 | function quickSelectLoopRandomPivot (tasksMap) { | |
136 | const tasksArray = Array.from(tasksMap) | |
137 | ||
138 | return selectLoop( | |
139 | tasksArray, | |
140 | 0, | |
141 | 0, | |
142 | tasksArray.length - 1, | |
143 | (a, b) => { | |
144 | return a[1] < b[1] | |
145 | }, | |
292ad316 | 146 | randomPivotIndexSelect |
74750c7f JB |
147 | ) |
148 | } | |
149 | ||
150 | function quickSelectRecursion (tasksMap) { | |
151 | const tasksArray = Array.from(tasksMap) | |
152 | ||
153 | return selectRecursion(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => { | |
154 | return a[1] < b[1] | |
155 | }) | |
156 | } | |
157 | ||
158 | function quickSelectRecursionRandomPivot (tasksMap) { | |
159 | const tasksArray = Array.from(tasksMap) | |
160 | ||
161 | return selectRecursion( | |
162 | tasksArray, | |
163 | 0, | |
164 | 0, | |
165 | tasksArray.length - 1, | |
166 | (a, b) => { | |
167 | return a[1] < b[1] | |
168 | }, | |
292ad316 | 169 | randomPivotIndexSelect |
74750c7f JB |
170 | ) |
171 | } | |
172 | ||
f1c674cd JB |
173 | new Benchmark.Suite('Least used worker tasks distribution') |
174 | .add('Loop select', () => { | |
74750c7f | 175 | loopSelect(tasksMap) |
f1c674cd JB |
176 | }) |
177 | .add('Array sort select', () => { | |
74750c7f | 178 | arraySortSelect(tasksMap) |
f1c674cd JB |
179 | }) |
180 | .add('Quick select loop', () => { | |
74750c7f | 181 | quickSelectLoop(tasksMap) |
f1c674cd JB |
182 | }) |
183 | .add('Quick select loop with random pivot', () => { | |
74750c7f | 184 | quickSelectLoopRandomPivot(tasksMap) |
f1c674cd JB |
185 | }) |
186 | .add('Quick select recursion', () => { | |
74750c7f | 187 | quickSelectRecursion(tasksMap) |
f1c674cd JB |
188 | }) |
189 | .add('Quick select recursion with random pivot', () => { | |
74750c7f | 190 | quickSelectRecursionRandomPivot(tasksMap) |
f1c674cd JB |
191 | }) |
192 | .on('cycle', event => { | |
193 | console.info(event.target.toString()) | |
194 | }) | |
195 | .on('complete', function () { | |
196 | console.info( | |
197 | 'Fastest is ' + LIST_FORMATTER.format(this.filter('fastest').map('name')) | |
198 | ) | |
199 | }) | |
200 | .run() |