quick-select.js

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