quick-select.mjs

   1 import { randomInt } from 'node:crypto'
   2
   3 import { bench, group, run } from 'tatami-ng'
   4
   5 /**
   6  * @param numberOfWorkers
   7  * @param maxNumberOfTasksPerWorker
   8  * @returns
   9  */
  10 function generateRandomTasksMap (
  11   numberOfWorkers,
  12   maxNumberOfTasksPerWorker = 10
  13 ) {
  14   const tasksArray = []
  15   for (let i = 0; i < numberOfWorkers; i++) {
  16     const task = [i, randomInt(maxNumberOfTasksPerWorker)]
  17     tasksArray.push(task)
  18   }
  19   return new Map(tasksArray)
  20 }
  21
  22 const tasksMap = generateRandomTasksMap(60, 20)
  23
  24 /**
  25  * @param tasksMap
  26  * @returns
  27  */
  28 function loopSelect (tasksMap) {
  29   let minKey
  30   let minValue = Infinity
  31   for (const [key, value] of tasksMap) {
  32     if (value === 0) {
  33       return key
  34     } else if (value < minValue) {
  35       minKey = key
  36       minValue = value
  37     }
  38   }
  39   return [minKey, minValue]
  40 }
  41
  42 /**
  43  * @param tasksMap
  44  * @returns
  45  */
  46 function arraySortSelect (tasksMap) {
  47   const tasksArray = Array.from(tasksMap)
  48   return tasksArray.sort((a, b) => {
  49     if (a[1] < b[1]) {
  50       return -1
  51     } else if (a[1] > b[1]) {
  52       return 1
  53     }
  54     return 0
  55   })[0]
  56 }
  57
  58 const defaultComparator = (a, b) => {
  59   return a < b
  60 }
  61
  62 const defaultPivotIndexSelect = (leftIndex, rightIndex) => {
  63   return leftIndex + Math.floor((rightIndex - leftIndex) / 2)
  64 }
  65
  66 const randomPivotIndexSelect = (leftIndex, rightIndex) => {
  67   return randomInt(leftIndex, rightIndex)
  68 }
  69
  70 /**
  71  * @param array
  72  * @param index1
  73  * @param index2
  74  */
  75 function swap (array, index1, index2) {
  76   const tmp = array[index1]
  77   array[index1] = array[index2]
  78   array[index2] = tmp
  79 }
  80
  81 /**
  82  * @param array
  83  * @param leftIndex
  84  * @param rightIndex
  85  * @param pivotIndex
  86  * @param compare
  87  * @returns
  88  */
  89 function partition (
  90   array,
  91   leftIndex,
  92   rightIndex,
  93   pivotIndex,
  94   compare = defaultComparator
  95 ) {
  96   const pivotValue = array[pivotIndex]
  97   swap(array, pivotIndex, rightIndex)
  98   let storeIndex = leftIndex
  99   for (let i = leftIndex; i < rightIndex; i++) {
 100     if (compare(array[i], pivotValue)) {
 101       swap(array, storeIndex, i)
 102       storeIndex++
 103     }
 104   }
 105   swap(array, rightIndex, storeIndex)
 106   return storeIndex
 107 }
 108
 109 /**
 110  * @param array
 111  * @param k
 112  * @param leftIndex
 113  * @param rightIndex
 114  * @param compare
 115  * @param pivotIndexSelect
 116  * @returns
 117  */
 118 function selectLoop (
 119   array,
 120   k,
 121   leftIndex,
 122   rightIndex,
 123   compare = defaultComparator,
 124   pivotIndexSelect = defaultPivotIndexSelect
 125 ) {
 126   while (true) {
 127     if (leftIndex === rightIndex) return array[leftIndex]
 128     let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
 129     pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
 130     if (k === pivotIndex) {
 131       return array[k]
 132     } else if (k < pivotIndex) {
 133       rightIndex = pivotIndex - 1
 134     } else {
 135       leftIndex = pivotIndex + 1
 136     }
 137   }
 138 }
 139
 140 /**
 141  * @param array
 142  * @param k
 143  * @param leftIndex
 144  * @param rightIndex
 145  * @param compare
 146  * @param pivotIndexSelect
 147  * @returns
 148  */
 149 function selectRecursion (
 150   array,
 151   k,
 152   leftIndex,
 153   rightIndex,
 154   compare = defaultComparator,
 155   pivotIndexSelect = defaultPivotIndexSelect
 156 ) {
 157   if (leftIndex === rightIndex) return array[leftIndex]
 158   let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
 159   pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
 160   if (k === pivotIndex) {
 161     return array[k]
 162   } else if (k < pivotIndex) {
 163     return selectRecursion(array, k, leftIndex, pivotIndex - 1, compare)
 164   } else {
 165     return selectRecursion(array, k, pivotIndex + 1, rightIndex, k, compare)
 166   }
 167 }
 168
 169 /**
 170  * @param tasksMap
 171  * @returns
 172  */
 173 function quickSelectLoop (tasksMap) {
 174   const tasksArray = Array.from(tasksMap)
 175
 176   return selectLoop(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
 177     return a[1] < b[1]
 178   })
 179 }
 180
 181 /**
 182  * @param tasksMap
 183  * @returns
 184  */
 185 function quickSelectLoopRandomPivot (tasksMap) {
 186   const tasksArray = Array.from(tasksMap)
 187
 188   return selectLoop(
 189     tasksArray,
 190     0,
 191     0,
 192     tasksArray.length - 1,
 193     (a, b) => {
 194       return a[1] < b[1]
 195     },
 196     randomPivotIndexSelect
 197   )
 198 }
 199
 200 /**
 201  * @param tasksMap
 202  * @returns
 203  */
 204 function quickSelectRecursion (tasksMap) {
 205   const tasksArray = Array.from(tasksMap)
 206
 207   return selectRecursion(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
 208     return a[1] < b[1]
 209   })
 210 }
 211
 212 /**
 213  * @param tasksMap
 214  * @returns
 215  */
 216 function quickSelectRecursionRandomPivot (tasksMap) {
 217   const tasksArray = Array.from(tasksMap)
 218
 219   return selectRecursion(
 220     tasksArray,
 221     0,
 222     0,
 223     tasksArray.length - 1,
 224     (a, b) => {
 225       return a[1] < b[1]
 226     },
 227     randomPivotIndexSelect
 228   )
 229 }
 230
 231 group('Quick select', () => {
 232   bench('Loop select', () => {
 233     loopSelect(tasksMap)
 234   })
 235   bench('Array sort select', () => {
 236     arraySortSelect(tasksMap)
 237   })
 238   bench('Quick select loop', () => {
 239     quickSelectLoop(tasksMap)
 240   })
 241   bench('Quick select loop with random pivot', () => {
 242     quickSelectLoopRandomPivot(tasksMap)
 243   })
 244   bench('Quick select recursion', () => {
 245     quickSelectRecursion(tasksMap)
 246   })
 247   bench('Quick select recursion with random pivot', () => {
 248     quickSelectRecursionRandomPivot(tasksMap)
 249   })
 250 })
 251
 252 await run({
 253   units: true
 254 })