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