quick-select.js

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