1 import Benchmark from 'benny'
2 import { generateRandomInteger } from './benchmark-utils.mjs'
5 * @param numberOfWorkers
6 * @param maxNumberOfTasksPerWorker
9 function generateRandomTasksMap (
11 maxNumberOfTasksPerWorker = 10
14 for (let i = 0; i < numberOfWorkers; i++) {
15 const task = [i, generateRandomInteger(maxNumberOfTasksPerWorker)]
18 return new Map(tasksArray)
21 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]
45 function arraySortSelect (tasksMap) {
46 const tasksArray = Array.from(tasksMap)
47 return tasksArray.sort((a, b) => {
50 } else if (a[1] > b[1]) {
57 const defaultComparator = (a, b) => {
61 const defaultPivotIndexSelect = (leftIndex, rightIndex) => {
62 return leftIndex + Math.floor((rightIndex - leftIndex) / 2)
65 const randomPivotIndexSelect = (leftIndex, rightIndex) => {
66 return generateRandomInteger(rightIndex, leftIndex)
74 function swap (array, index1, index2) {
75 const tmp = array[index1]
76 array[index1] = array[index2]
93 compare = defaultComparator
95 const pivotValue = array[pivotIndex]
96 swap(array, pivotIndex, rightIndex)
97 let storeIndex = leftIndex
98 for (let i = leftIndex; i < rightIndex; i++) {
99 if (compare(array[i], pivotValue)) {
100 swap(array, storeIndex, i)
104 swap(array, rightIndex, storeIndex)
114 * @param pivotIndexSelect
117 function selectLoop (
122 compare = defaultComparator,
123 pivotIndexSelect = defaultPivotIndexSelect
126 if (leftIndex === rightIndex) return array[leftIndex]
127 let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
128 pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
129 if (k === pivotIndex) {
131 } else if (k < pivotIndex) {
132 rightIndex = pivotIndex - 1
134 leftIndex = pivotIndex + 1
145 * @param pivotIndexSelect
148 function selectRecursion (
153 compare = defaultComparator,
154 pivotIndexSelect = defaultPivotIndexSelect
156 if (leftIndex === rightIndex) return array[leftIndex]
157 let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
158 pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
159 if (k === pivotIndex) {
161 } else if (k < pivotIndex) {
162 return selectRecursion(array, k, leftIndex, pivotIndex - 1, compare)
164 return selectRecursion(array, k, pivotIndex + 1, rightIndex, k, compare)
172 function quickSelectLoop (tasksMap) {
173 const tasksArray = Array.from(tasksMap)
175 return selectLoop(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
184 function quickSelectLoopRandomPivot (tasksMap) {
185 const tasksArray = Array.from(tasksMap)
191 tasksArray.length - 1,
195 randomPivotIndexSelect
203 function quickSelectRecursion (tasksMap) {
204 const tasksArray = Array.from(tasksMap)
206 return selectRecursion(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
215 function quickSelectRecursionRandomPivot (tasksMap) {
216 const tasksArray = Array.from(tasksMap)
218 return selectRecursion(
222 tasksArray.length - 1,
226 randomPivotIndexSelect
232 Benchmark.add('Loop select', () => {
235 Benchmark.add('Array sort select', () => {
236 arraySortSelect(tasksMap)
238 Benchmark.add('Quick select loop', () => {
239 quickSelectLoop(tasksMap)
241 Benchmark.add('Quick select loop with random pivot', () => {
242 quickSelectLoopRandomPivot(tasksMap)
244 Benchmark.add('Quick select recursion', () => {
245 quickSelectRecursion(tasksMap)
247 Benchmark.add('Quick select recursion with random pivot', () => {
248 quickSelectRecursionRandomPivot(tasksMap)
251 Benchmark.complete(),
253 file: 'quick-select',
258 file: 'quick-select',
259 format: 'chart.html',
263 file: 'quick-select',
264 format: 'table.html',