Given samplePick and sampleRes, which are the two random sampling algorithms, determines which is fastest for a given number of samples and collections

randoms.wren

import "random" for Random

var TRIALS = 10
var RANDOM = Random.new()

class FindCutoffs {
  // Determine the time ratio between picking and reservoir sampling [samples]
  // from [list].
  static calculateRatio(list, samples) {
    System.gc()

    var start = System.clock
    for (i in 1..TRIALS) {
      RANDOM.samplePick(list, samples)
    }
    var pickTime = System.clock - start

    start = System.clock
    for (i in 1..TRIALS) {
      RANDOM.sampleRes(list, samples)
    }
    var resTime = System.clock - start

    //System.print("%(samples)/%(list.count) pick %(pickTime) res %(resTime) = %(pickTime / resTime)")
    return pickTime / resTime
  }

  // Calculates the number of samples taken from list where the two algorithms
  // are equivalent in speed.
  static findCutOff(list) {
    var min = 1
    var max = list.count

    while (max > min + 1) {
      var mid = ((max + min) / 2).floor
      var ratio = calculateRatio(list, mid)
      if (ratio > 1.0) {
        max = mid
      } else {
        min = mid
      }
    }

    return ((min + max) / 2).floor
  }

  static run() {
    var size = 100
    while (size <= 10000) {
      var list = (1..size).toList
      var cutoff = findCutOff(list)
      System.print("%(list.count) %(cutoff)")
      size = size + 100
    }
  }
}

FindCutoffs.run()