1 const Benchmark
= require('benchmark')
2 const { generateRandomInteger
, LIST_FORMATTER
} = require('./benchmark-utils')
4 const suite
= new Benchmark
.Suite()
7 * @param numberOfWorkers
8 * @param maxNumberOfTasksPerWorker
11 function generateRandomTasksMap (
13 maxNumberOfTasksPerWorker
= 10
16 for (let i
= 0; i
< numberOfWorkers
; i
++) {
17 const task
= [i
, generateRandomInteger(maxNumberOfTasksPerWorker
)]
20 return new Map(tasksArray
)
23 const tasksMap
= generateRandomTasksMap(60, 20)
29 function loopSelect (tasksMap
) {
30 let minValue
= Infinity
32 for (const [key
, value
] of tasksMap
) {
35 } else if (value
< minValue
) {
40 return [minKey
, minValue
]
47 function arraySortSelect (tasksMap
) {
48 const tasksArray
= Array
.from(tasksMap
)
49 return tasksArray
.sort((a
, b
) => {
52 } else if (a
[1] > b
[1]) {
59 const defaultComparator
= (a
, b
) => {
63 const defaultPivotIndexSelect
= (leftIndex
, rightIndex
) => {
64 return leftIndex
+ Math
.floor((rightIndex
- leftIndex
) / 2)
67 const randomPivotIndexSelect
= (leftIndex
, rightIndex
) => {
68 return generateRandomInteger(leftIndex
, rightIndex
)
76 function swap (array
, index1
, index2
) {
77 const tmp
= array
[index1
]
78 array
[index1
] = array
[index2
]
95 compare
= defaultComparator
97 const pivotValue
= array
[pivotIndex
]
98 swap(array
, pivotIndex
, rightIndex
)
99 let storeIndex
= leftIndex
100 for (let i
= leftIndex
; i
< rightIndex
; i
++) {
101 if (compare(array
[i
], pivotValue
)) {
102 swap(array
, storeIndex
, i
)
106 swap(array
, rightIndex
, storeIndex
)
116 * @param pivotIndexSelect
119 function selectLoop (
124 compare
= defaultComparator
,
125 pivotIndexSelect
= defaultPivotIndexSelect
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
) {
133 } else if (k
< pivotIndex
) {
134 rightIndex
= pivotIndex
- 1
136 leftIndex
= pivotIndex
+ 1
147 * @param pivotIndexSelect
150 function selectRecursion (
155 compare
= defaultComparator
,
156 pivotIndexSelect
= defaultPivotIndexSelect
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
) {
163 } else if (k
< pivotIndex
) {
164 return selectRecursion(array
, k
, leftIndex
, pivotIndex
- 1, compare
)
166 return selectRecursion(array
, k
, pivotIndex
+ 1, rightIndex
, k
, compare
)
174 function quickSelectLoop (tasksMap
) {
175 const tasksArray
= Array
.from(tasksMap
)
177 return selectLoop(tasksArray
, 0, 0, tasksArray
.length
- 1, (a
, b
) => {
186 function quickSelectLoopRandomPivot (tasksMap
) {
187 const tasksArray
= Array
.from(tasksMap
)
193 tasksArray
.length
- 1,
197 randomPivotIndexSelect
205 function quickSelectRecursion (tasksMap
) {
206 const tasksArray
= Array
.from(tasksMap
)
208 return selectRecursion(tasksArray
, 0, 0, tasksArray
.length
- 1, (a
, b
) => {
217 function quickSelectRecursionRandomPivot (tasksMap
) {
218 const tasksArray
= Array
.from(tasksMap
)
220 return selectRecursion(
224 tasksArray
.length
- 1,
228 randomPivotIndexSelect
232 // console.log(Array.from(tasksMap))
233 // console.log(loopSelect(tasksMap))
234 // console.log(arraySortSelect(tasksMap))
235 // console.log(quickSelectLoop(tasksMap))
236 // console.log(quickSelectLoopRandomPivot(tasksMap))
237 // console.log(quickSelectRecursion(tasksMap))
238 // console.log(quickSelectRecursionRandomPivot(tasksMap))
241 .add('Loop select', function () {
244 .add('Array sort select', function () {
245 arraySortSelect(tasksMap
)
247 .add('Quick select loop', function () {
248 quickSelectLoop(tasksMap
)
250 .add('Quick select loop with random pivot', function () {
251 quickSelectLoopRandomPivot(tasksMap
)
253 .add('Quick select recursion', function () {
254 quickSelectRecursion(tasksMap
)
256 .add('Quick select recursion with random pivot', function () {
257 quickSelectRecursionRandomPivot(tasksMap
)
259 .on('cycle', function (event
) {
260 console
.log(event
.target
.toString())
262 .on('complete', function () {
264 'Fastest is ' + LIST_FORMATTER
.format(this.filter('fastest').map('name'))
266 // eslint-disable-next-line n/no-process-exit