1 const Benchmark
= require('benchmark')
2 const { generateRandomInteger
} = require('./benchmark-utils')
4 const suite
= new Benchmark
.Suite()
6 const LIST_FORMATTER
= new Intl
.ListFormat('en-US', {
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)]
44 function loopSelect (tasksMap
) {
45 let minValue
= Infinity
47 for (const [key
, value
] of tasksMap
) {
50 } else if (value
< minValue
) {
55 return [minKey
, minValue
]
58 function arraySortSelect (tasksMap
) {
59 const tasksArray
= Array
.from(tasksMap
)
60 return tasksArray
.sort((a
, b
) => {
63 } else if (a
[1] > b
[1]) {
70 const defaultComparator
= (a
, b
) => {
74 const defaultPivotIndexSelect
= (leftIndex
, rightIndex
) => {
75 return leftIndex
+ Math
.floor((rightIndex
- leftIndex
) / 2)
78 function swap (array
, index1
, index2
) {
79 const tmp
= array
[index1
]
80 array
[index1
] = array
[index2
]
89 compare
= defaultComparator
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
)
100 swap(array
, rightIndex
, storeIndex
)
104 function selectLoop (
109 compare
= defaultComparator
,
110 pivotIndexSelect
= defaultPivotIndexSelect
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
) {
118 } else if (k
< pivotIndex
) {
119 rightIndex
= pivotIndex
- 1
121 leftIndex
= pivotIndex
+ 1
126 function selectRecursion (
131 compare
= defaultComparator
,
132 pivotIndexSelect
= defaultPivotIndexSelect
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
) {
139 } else if (k
< pivotIndex
) {
140 return selectRecursion(array
, k
, leftIndex
, pivotIndex
- 1, compare
)
142 return selectRecursion(array
, k
, pivotIndex
+ 1, rightIndex
, k
, compare
)
146 function quickSelectLoop (tasksMap
) {
147 const tasksArray
= Array
.from(tasksMap
)
149 return selectLoop(tasksArray
, 0, 0, tasksArray
.length
- 1, (a
, b
) => {
154 function quickSelectLoopRandomPivot (tasksMap
) {
155 const tasksArray
= Array
.from(tasksMap
)
161 tasksArray
.length
- 1,
165 (leftIndex
, rightIndex
) => {
166 return generateRandomInteger(leftIndex
, rightIndex
)
171 function quickSelectRecursion (tasksMap
) {
172 const tasksArray
= Array
.from(tasksMap
)
174 return selectRecursion(tasksArray
, 0, 0, tasksArray
.length
- 1, (a
, b
) => {
179 function quickSelectRecursionRandomPivot (tasksMap
) {
180 const tasksArray
= Array
.from(tasksMap
)
182 return selectRecursion(
186 tasksArray
.length
- 1,
190 (leftIndex
, rightIndex
) => {
191 return generateRandomInteger(leftIndex
, rightIndex
)
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))
205 .add('Loop select', function () {
208 .add('Array sort select', function () {
209 arraySortSelect(tasksMap
)
211 .add('Quick select loop', function () {
212 quickSelectLoop(tasksMap
)
214 .add('Quick select loop with random pivot', function () {
215 quickSelectLoopRandomPivot(tasksMap
)
217 .add('Quick select recursion', function () {
218 quickSelectRecursion(tasksMap
)
220 .add('Quick select recursion with random pivot', function () {
221 quickSelectRecursionRandomPivot(tasksMap
)
223 .on('cycle', function (event
) {
224 console
.log(event
.target
.toString())
226 .on('complete', function () {
228 'Fastest is ' + LIST_FORMATTER
.format(this.filter('fastest').map('name'))
230 // eslint-disable-next-line no-process-exit