1 import { randomInt } from 'node:crypto'
3 import { bench, group, run } from 'tatami-ng'
7 * @param numberOfWorkers
8 * @param maxNumberOfTasksPerWorker
11 function generateRandomTasksMap (
13 maxNumberOfTasksPerWorker = 10
16 for (let i = 0; i < numberOfWorkers; i++) {
17 const task = [i, randomInt(maxNumberOfTasksPerWorker)]
20 return new Map(tasksArray)
23 const tasksMap = generateRandomTasksMap(60, 20)
30 function loopSelect (tasksMap) {
32 let minValue = Number.POSITIVE_INFINITY
33 for (const [key, value] of tasksMap) {
36 } else if (value < minValue) {
41 return [minKey, minValue]
49 function arraySortSelect (tasksMap) {
50 const tasksArray = Array.from(tasksMap)
51 return tasksArray.sort((a, b) => {
54 } else if (a[1] > b[1]) {
61 const defaultComparator = (a, b) => {
65 const defaultPivotIndexSelect = (leftIndex, rightIndex) => {
66 return leftIndex + Math.floor((rightIndex - leftIndex) / 2)
69 const randomPivotIndexSelect = (leftIndex, rightIndex) => {
70 return randomInt(leftIndex, rightIndex)
79 function swap (array, index1, index2) {
80 const tmp = array[index1]
81 array[index1] = array[index2]
99 compare = defaultComparator
101 const pivotValue = array[pivotIndex]
102 swap(array, pivotIndex, rightIndex)
103 let storeIndex = leftIndex
104 for (let i = leftIndex; i < rightIndex; i++) {
105 if (compare(array[i], pivotValue)) {
106 swap(array, storeIndex, i)
110 swap(array, rightIndex, storeIndex)
121 * @param pivotIndexSelect
124 function selectLoop (
129 compare = defaultComparator,
130 pivotIndexSelect = defaultPivotIndexSelect
133 if (leftIndex === rightIndex) return array[leftIndex]
134 let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
135 pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
136 if (k === pivotIndex) {
138 } else if (k < pivotIndex) {
139 rightIndex = pivotIndex - 1
141 leftIndex = pivotIndex + 1
153 * @param pivotIndexSelect
156 function selectRecursion (
161 compare = defaultComparator,
162 pivotIndexSelect = defaultPivotIndexSelect
164 if (leftIndex === rightIndex) return array[leftIndex]
165 let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
166 pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
167 if (k === pivotIndex) {
169 } else if (k < pivotIndex) {
170 return selectRecursion(array, k, leftIndex, pivotIndex - 1, compare)
172 return selectRecursion(array, k, pivotIndex + 1, rightIndex, k, compare)
181 function quickSelectLoop (tasksMap) {
182 const tasksArray = Array.from(tasksMap)
184 return selectLoop(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
194 function quickSelectLoopRandomPivot (tasksMap) {
195 const tasksArray = Array.from(tasksMap)
201 tasksArray.length - 1,
205 randomPivotIndexSelect
214 function quickSelectRecursion (tasksMap) {
215 const tasksArray = Array.from(tasksMap)
217 return selectRecursion(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
227 function quickSelectRecursionRandomPivot (tasksMap) {
228 const tasksArray = Array.from(tasksMap)
230 return selectRecursion(
234 tasksArray.length - 1,
238 randomPivotIndexSelect
242 group('Least used worker tasks distribution', () => {
243 bench('Loop select', () => {
246 bench('Array sort select', () => {
247 arraySortSelect(tasksMap)
249 bench('Quick select loop', () => {
250 quickSelectLoop(tasksMap)
252 bench('Quick select loop with random pivot', () => {
253 quickSelectLoopRandomPivot(tasksMap)
255 bench('Quick select recursion', () => {
256 quickSelectRecursion(tasksMap)
258 bench('Quick select recursion with random pivot', () => {
259 quickSelectRecursionRandomPivot(tasksMap)
263 await run({ units: true })