1 import { randomInt } from 'node:crypto'
3 import Benchmark from 'benchmark'
5 import { LIST_FORMATTER } from '../benchmarks-utils.cjs'
7 function generateRandomTasksMap (
9 maxNumberOfTasksPerWorker = 10
12 for (let i = 0; i < numberOfWorkers; i++) {
13 const task = [i, randomInt(maxNumberOfTasksPerWorker)]
16 return new Map(tasksArray)
19 const tasksMap = generateRandomTasksMap(60, 20)
21 function loopSelect (tasksMap) {
23 let minValue = Infinity
24 for (const [key, value] of tasksMap) {
27 } else if (value < minValue) {
32 return [minKey, minValue]
35 function arraySortSelect (tasksMap) {
36 const tasksArray = Array.from(tasksMap)
37 return tasksArray.sort((a, b) => {
40 } else if (a[1] > b[1]) {
47 const defaultComparator = (a, b) => {
51 const defaultPivotIndexSelect = (leftIndex, rightIndex) => {
52 return leftIndex + Math.floor((rightIndex - leftIndex) / 2)
55 const randomPivotIndexSelect = (leftIndex, rightIndex) => {
56 return randomInt(leftIndex, rightIndex)
59 function swap (array, index1, index2) {
60 const tmp = array[index1]
61 array[index1] = array[index2]
70 compare = defaultComparator
72 const pivotValue = array[pivotIndex]
73 swap(array, pivotIndex, rightIndex)
74 let storeIndex = leftIndex
75 for (let i = leftIndex; i < rightIndex; i++) {
76 if (compare(array[i], pivotValue)) {
77 swap(array, storeIndex, i)
81 swap(array, rightIndex, storeIndex)
90 compare = defaultComparator,
91 pivotIndexSelect = defaultPivotIndexSelect
94 if (leftIndex === rightIndex) return array[leftIndex]
95 let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
96 pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
97 if (k === pivotIndex) {
99 } else if (k < pivotIndex) {
100 rightIndex = pivotIndex - 1
102 leftIndex = pivotIndex + 1
107 function selectRecursion (
112 compare = defaultComparator,
113 pivotIndexSelect = defaultPivotIndexSelect
115 if (leftIndex === rightIndex) return array[leftIndex]
116 let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
117 pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
118 if (k === pivotIndex) {
120 } else if (k < pivotIndex) {
121 return selectRecursion(array, k, leftIndex, pivotIndex - 1, compare)
123 return selectRecursion(array, k, pivotIndex + 1, rightIndex, k, compare)
127 function quickSelectLoop (tasksMap) {
128 const tasksArray = Array.from(tasksMap)
130 return selectLoop(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
135 function quickSelectLoopRandomPivot (tasksMap) {
136 const tasksArray = Array.from(tasksMap)
142 tasksArray.length - 1,
146 randomPivotIndexSelect
150 function quickSelectRecursion (tasksMap) {
151 const tasksArray = Array.from(tasksMap)
153 return selectRecursion(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
158 function quickSelectRecursionRandomPivot (tasksMap) {
159 const tasksArray = Array.from(tasksMap)
161 return selectRecursion(
165 tasksArray.length - 1,
169 randomPivotIndexSelect
173 new Benchmark.Suite('Least used worker tasks distribution')
174 .add('Loop select', () => {
177 .add('Array sort select', () => {
178 arraySortSelect(tasksMap)
180 .add('Quick select loop', () => {
181 quickSelectLoop(tasksMap)
183 .add('Quick select loop with random pivot', () => {
184 quickSelectLoopRandomPivot(tasksMap)
186 .add('Quick select recursion', () => {
187 quickSelectRecursion(tasksMap)
189 .add('Quick select recursion with random pivot', () => {
190 quickSelectRecursionRandomPivot(tasksMap)
192 .on('cycle', event => {
193 console.info(event.target.toString())
195 .on('complete', function () {
197 'Fastest is ' + LIST_FORMATTER.format(this.filter('fastest').map('name'))