Apply dependencies update (#439)
[poolifier.git] / benchmarks / internal / quick-select.js
1 const Benchmark = require('benchmark')
2 const { generateRandomInteger, LIST_FORMATTER } = require('./benchmark-utils')
3
4 const suite = new Benchmark.Suite()
5
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)
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
54 const randomPivotIndexSelect = (leftIndex, rightIndex) => {
55 return generateRandomInteger(leftIndex, rightIndex)
56 }
57
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
74 for (let i = leftIndex; i < rightIndex; i++) {
75 if (compare(array[i], pivotValue)) {
76 swap(array, storeIndex, i)
77 storeIndex++
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 },
145 randomPivotIndexSelect
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 },
168 randomPivotIndexSelect
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()