benchmarks/internal/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 function generateRandomTasksMap (
   7   numberOfWorkers,
   8   maxNumberOfTasksPerWorker = 10
   9 ) {
  10   const tasksArray = []
  11   for (let i = 0; i < numberOfWorkers; i++) {
  12     const task = [i, generateRandomInteger(maxNumberOfTasksPerWorker)]
  13     tasksArray.push(task)
  14   }
  15   return new Map(tasksArray)
  16 }
  17
  18 const tasksMap = generateRandomTasksMap(60, 20)
  19
  20 function loopSelect (tasksMap) {
  21   let minValue = Infinity
  22   let minKey
  23   for (const [key, value] of tasksMap) {
  24     if (value === 0) {
  25       return key
  26     } else if (value < minValue) {
  27       minKey = key
  28       minValue = value
  29     }
  30   }
  31   return [minKey, minValue]
  32 }
  33
  34 function arraySortSelect (tasksMap) {
  35   const tasksArray = Array.from(tasksMap)
  36   return tasksArray.sort((a, b) => {
  37     if (a[1] < b[1]) {
  38       return -1
  39     } else if (a[1] > b[1]) {
  40       return 1
  41     }
  42     return 0
  43   })[0]
  44 }
  45
  46 const defaultComparator = (a, b) => {
  47   return a < b
  48 }
  49
  50 const defaultPivotIndexSelect = (leftIndex, rightIndex) => {
  51   return leftIndex + Math.floor((rightIndex - leftIndex) / 2)
  52 }
  53
  54 const randomPivotIndexSelect = (leftIndex, rightIndex) => {
  55   return generateRandomInteger(leftIndex, rightIndex)
  56 }
  57
  58 function swap (array, index1, index2) {
  59   const tmp = array[index1]
  60   array[index1] = array[index2]
  61   array[index2] = tmp
  62 }
  63
  64 function partition (
  65   array,
  66   leftIndex,
  67   rightIndex,
  68   pivotIndex,
  69   compare = defaultComparator
  70 ) {
  71   const pivotValue = array[pivotIndex]
  72   swap(array, pivotIndex, rightIndex)
  73   let storeIndex = leftIndex
  74   for (let i = leftIndex; i < rightIndex; i++) {
  75     if (compare(array[i], pivotValue)) {
  76       swap(array, storeIndex, i)
  77       storeIndex++
  78     }
  79   }
  80   swap(array, rightIndex, storeIndex)
  81   return storeIndex
  82 }
  83
  84 function selectLoop (
  85   array,
  86   k,
  87   leftIndex,
  88   rightIndex,
  89   compare = defaultComparator,
  90   pivotIndexSelect = defaultPivotIndexSelect
  91 ) {
  92   while (true) {
  93     if (leftIndex === rightIndex) return array[leftIndex]
  94     let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
  95     pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
  96     if (k === pivotIndex) {
  97       return array[k]
  98     } else if (k < pivotIndex) {
  99       rightIndex = pivotIndex - 1
 100     } else {
 101       leftIndex = pivotIndex + 1
 102     }
 103   }
 104 }
 105
 106 function selectRecursion (
 107   array,
 108   k,
 109   leftIndex,
 110   rightIndex,
 111   compare = defaultComparator,
 112   pivotIndexSelect = defaultPivotIndexSelect
 113 ) {
 114   if (leftIndex === rightIndex) return array[leftIndex]
 115   let pivotIndex = pivotIndexSelect(leftIndex, rightIndex)
 116   pivotIndex = partition(array, leftIndex, rightIndex, pivotIndex, compare)
 117   if (k === pivotIndex) {
 118     return array[k]
 119   } else if (k < pivotIndex) {
 120     return selectRecursion(array, k, leftIndex, pivotIndex - 1, compare)
 121   } else {
 122     return selectRecursion(array, k, pivotIndex + 1, rightIndex, k, compare)
 123   }
 124 }
 125
 126 function quickSelectLoop (tasksMap) {
 127   const tasksArray = Array.from(tasksMap)
 128
 129   return selectLoop(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
 130     return a[1] < b[1]
 131   })
 132 }
 133
 134 function quickSelectLoopRandomPivot (tasksMap) {
 135   const tasksArray = Array.from(tasksMap)
 136
 137   return selectLoop(
 138     tasksArray,
 139     0,
 140     0,
 141     tasksArray.length - 1,
 142     (a, b) => {
 143       return a[1] < b[1]
 144     },
 145     randomPivotIndexSelect
 146   )
 147 }
 148
 149 function quickSelectRecursion (tasksMap) {
 150   const tasksArray = Array.from(tasksMap)
 151
 152   return selectRecursion(tasksArray, 0, 0, tasksArray.length - 1, (a, b) => {
 153     return a[1] < b[1]
 154   })
 155 }
 156
 157 function quickSelectRecursionRandomPivot (tasksMap) {
 158   const tasksArray = Array.from(tasksMap)
 159
 160   return selectRecursion(
 161     tasksArray,
 162     0,
 163     0,
 164     tasksArray.length - 1,
 165     (a, b) => {
 166       return a[1] < b[1]
 167     },
 168     randomPivotIndexSelect
 169   )
 170 }
 171
 172 // console.log(Array.from(tasksMap))
 173 // console.log(loopSelect(tasksMap))
 174 // console.log(arraySortSelect(tasksMap))
 175 // console.log(quickSelectLoop(tasksMap))
 176 // console.log(quickSelectLoopRandomPivot(tasksMap))
 177 // console.log(quickSelectRecursion(tasksMap))
 178 // console.log(quickSelectRecursionRandomPivot(tasksMap))
 179
 180 suite
 181   .add('Loop select', function () {
 182     loopSelect(tasksMap)
 183   })
 184   .add('Array sort select', function () {
 185     arraySortSelect(tasksMap)
 186   })
 187   .add('Quick select loop', function () {
 188     quickSelectLoop(tasksMap)
 189   })
 190   .add('Quick select loop with random pivot', function () {
 191     quickSelectLoopRandomPivot(tasksMap)
 192   })
 193   .add('Quick select recursion', function () {
 194     quickSelectRecursion(tasksMap)
 195   })
 196   .add('Quick select recursion with random pivot', function () {
 197     quickSelectRecursionRandomPivot(tasksMap)
 198   })
 199   .on('cycle', function (event) {
 200     console.log(event.target.toString())
 201   })
 202   .on('complete', function () {
 203     console.log(
 204       'Fastest is ' + LIST_FORMATTER.format(this.filter('fastest').map('name'))
 205     )
 206     // eslint-disable-next-line no-process-exit
 207     process.exit()
 208   })
 209   .run()