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