1 import { randomInt } from 'node:crypto'
3 import { bench, group, run } from 'tatami-ng'
7 * @param numberOfWorkers
8 * @param maxNumberOfTasksPerWorker
10 function generateRandomTasksMap (
12 maxNumberOfTasksPerWorker = 10
15 for (let i = 0; i < numberOfWorkers; i++) {
16 const task = [i, randomInt(maxNumberOfTasksPerWorker)]
19 return new Map(tasksArray)
22 const tasksMap = generateRandomTasksMap(60, 20)
28 function loopSelect (tasksMap) {
30 let minValue = Number.POSITIVE_INFINITY
31 for (const [key, value] of tasksMap) {
34 } else if (value < minValue) {
39 return [minKey, minValue]
46 function arraySortSelect (tasksMap) {
47 const tasksArray = Array.from(tasksMap)
48 return tasksArray.sort((a, b) => {
51 } else if (a[1] > b[1]) {
58 const defaultComparator = (a, b) => {
62 const defaultPivotIndexSelect = (leftIndex, rightIndex) => {
63 return leftIndex + Math.floor((rightIndex - leftIndex) / 2)
66 const randomPivotIndexSelect = (leftIndex, rightIndex) => {
67 return randomInt(leftIndex, rightIndex)
76 function swap (array, index1, index2) {
77 const tmp = array[index1]
78 array[index1] = array[index2]
95 compare = defaultComparator
97 const pivotValue = array[pivotIndex]
98 swap(array, pivotIndex, rightIndex)
99 let storeIndex = leftIndex
100 for (let i = leftIndex; i < rightIndex; i++) {
101 if (compare(array[i], pivotValue)) {
102 swap(array, storeIndex, i)
106 swap(array, rightIndex, storeIndex)
117 * @param pivotIndexSelect
119 function selectLoop (
124 compare = defaultComparator,
125 pivotIndexSelect = defaultPivotIndexSelect
128 if (leftIndex === rightIndex) return array[leftIndex]
129 let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
130 pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
131 if (k === pivotIndex) {
133 } else if (k < pivotIndex) {
134 rightIndex = pivotIndex - 1
136 leftIndex = pivotIndex + 1
148 * @param pivotIndexSelect
150 function selectRecursion (
155 compare = defaultComparator,
156 pivotIndexSelect = defaultPivotIndexSelect
158 if (leftIndex === rightIndex) return array[leftIndex]
159 let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
160 pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
161 if (k === pivotIndex) {
163 } else if (k < pivotIndex) {
164 return selectRecursion(array, k, leftIndex, pivotIndex - 1, compare)
166 return selectRecursion(array, k, pivotIndex + 1, rightIndex, k, compare)
174 function quickSelectLoop (tasksMap) {
175 const tasksArray = Array.from(tasksMap)
177 return selectLoop(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
186 function quickSelectLoopRandomPivot (tasksMap) {
187 const tasksArray = Array.from(tasksMap)
193 tasksArray.length - 1,
197 randomPivotIndexSelect
205 function quickSelectRecursion (tasksMap) {
206 const tasksArray = Array.from(tasksMap)
208 return selectRecursion(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
217 function quickSelectRecursionRandomPivot (tasksMap) {
218 const tasksArray = Array.from(tasksMap)
220 return selectRecursion(
224 tasksArray.length - 1,
228 randomPivotIndexSelect
232 group('Least used worker tasks distribution', () => {
233 bench('Loop select', () => {
236 bench('Array sort select', () => {
237 arraySortSelect(tasksMap)
239 bench('Quick select loop', () => {
240 quickSelectLoop(tasksMap)
242 bench('Quick select loop with random pivot', () => {
243 quickSelectLoopRandomPivot(tasksMap)
245 bench('Quick select recursion', () => {
246 quickSelectRecursion(tasksMap)
248 bench('Quick select recursion with random pivot', () => {
249 quickSelectRecursionRandomPivot(tasksMap)
253 await run({ units: true })