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
10 function generateRandomTasksMap (
12 maxNumberOfTasksPerWorker
= 10
15 for (let i
= 0; i
< numberOfWorkers
; i
++) {
16 const task
= [i
, generateRandomInteger(maxNumberOfTasksPerWorker
)]
19 return new Map(tasksArray
)
22 const tasksMap
= generateRandomTasksMap(60, 20)
27 function loopSelect (tasksMap
) {
28 let minValue
= Infinity
30 for (const [key
, value
] of tasksMap
) {
33 } else if (value
< minValue
) {
38 return [minKey
, minValue
]
44 function arraySortSelect (tasksMap
) {
45 const tasksArray
= Array
.from(tasksMap
)
46 return tasksArray
.sort((a
, b
) => {
49 } else if (a
[1] > b
[1]) {
56 const defaultComparator
= (a
, b
) => {
60 const defaultPivotIndexSelect
= (leftIndex
, rightIndex
) => {
61 return leftIndex
+ Math
.floor((rightIndex
- leftIndex
) / 2)
64 const randomPivotIndexSelect
= (leftIndex
, rightIndex
) => {
65 return generateRandomInteger(leftIndex
, rightIndex
)
73 function swap (array
, index1
, index2
) {
74 const tmp
= array
[index1
]
75 array
[index1
] = array
[index2
]
91 compare
= defaultComparator
93 const pivotValue
= array
[pivotIndex
]
94 swap(array
, pivotIndex
, rightIndex
)
95 let storeIndex
= leftIndex
96 for (let i
= leftIndex
; i
< rightIndex
; i
++) {
97 if (compare(array
[i
], pivotValue
)) {
98 swap(array
, storeIndex
, i
)
102 swap(array
, rightIndex
, storeIndex
)
112 * @param pivotIndexSelect
114 function selectLoop (
119 compare
= defaultComparator
,
120 pivotIndexSelect
= defaultPivotIndexSelect
123 if (leftIndex
=== rightIndex
) return array
[leftIndex
]
124 let pivotIndex
= pivotIndexSelect(leftIndex
, rightIndex
)
125 pivotIndex
= partition(array
, leftIndex
, rightIndex
, pivotIndex
, compare
)
126 if (k
=== pivotIndex
) {
128 } else if (k
< pivotIndex
) {
129 rightIndex
= pivotIndex
- 1
131 leftIndex
= pivotIndex
+ 1
142 * @param pivotIndexSelect
144 function selectRecursion (
149 compare
= defaultComparator
,
150 pivotIndexSelect
= defaultPivotIndexSelect
152 if (leftIndex
=== rightIndex
) return array
[leftIndex
]
153 let pivotIndex
= pivotIndexSelect(leftIndex
, rightIndex
)
154 pivotIndex
= partition(array
, leftIndex
, rightIndex
, pivotIndex
, compare
)
155 if (k
=== pivotIndex
) {
157 } else if (k
< pivotIndex
) {
158 return selectRecursion(array
, k
, leftIndex
, pivotIndex
- 1, compare
)
160 return selectRecursion(array
, k
, pivotIndex
+ 1, rightIndex
, k
, compare
)
167 function quickSelectLoop (tasksMap
) {
168 const tasksArray
= Array
.from(tasksMap
)
170 return selectLoop(tasksArray
, 0, 0, tasksArray
.length
- 1, (a
, b
) => {
178 function quickSelectLoopRandomPivot (tasksMap
) {
179 const tasksArray
= Array
.from(tasksMap
)
185 tasksArray
.length
- 1,
189 randomPivotIndexSelect
196 function quickSelectRecursion (tasksMap
) {
197 const tasksArray
= Array
.from(tasksMap
)
199 return selectRecursion(tasksArray
, 0, 0, tasksArray
.length
- 1, (a
, b
) => {
207 function quickSelectRecursionRandomPivot (tasksMap
) {
208 const tasksArray
= Array
.from(tasksMap
)
210 return selectRecursion(
214 tasksArray
.length
- 1,
218 randomPivotIndexSelect
222 // console.log(Array.from(tasksMap))
223 // console.log(loopSelect(tasksMap))
224 // console.log(arraySortSelect(tasksMap))
225 // console.log(quickSelectLoop(tasksMap))
226 // console.log(quickSelectLoopRandomPivot(tasksMap))
227 // console.log(quickSelectRecursion(tasksMap))
228 // console.log(quickSelectRecursionRandomPivot(tasksMap))
231 .add('Loop select', function () {
234 .add('Array sort select', function () {
235 arraySortSelect(tasksMap
)
237 .add('Quick select loop', function () {
238 quickSelectLoop(tasksMap
)
240 .add('Quick select loop with random pivot', function () {
241 quickSelectLoopRandomPivot(tasksMap
)
243 .add('Quick select recursion', function () {
244 quickSelectRecursion(tasksMap
)
246 .add('Quick select recursion with random pivot', function () {
247 quickSelectRecursionRandomPivot(tasksMap
)
249 .on('cycle', function (event
) {
250 console
.log(event
.target
.toString())
252 .on('complete', function () {
254 'Fastest is ' + LIST_FORMATTER
.format(this.filter('fastest').map('name'))
256 // eslint-disable-next-line no-process-exit