Sample without replacement (v3)

Revision 3 of this benchmark created on

Setup

const smallKOverN = 0.01
const largeKOverN = 0.1
const k = 100
const largeArr = [...Array(Math.floor(k/smallKOverN )).keys()]
const smallArr = [...Array(Math.floor(k/largeKOverN )).keys()]

const swrs = {
  bestOfVerbose: (arr, k) => {
    if (k/arr.length < 0.02) { return swrs.indexOf(arr, k); }
    return swrs.shuffle(arr, k);
  },
  bestOfShort: (arr, k) => bestSwr[k/arr.length < 0.02](arr, k),
  indexOf: (arr, k) => {
      const idxs= [];
      const n = arr.length;
      while(idxs.length < k) {
          const r = Math.floor(Math.random() * n);
          if(idxs.indexOf(r) === -1) {
              idxs.push(r);
          }
      }
      return idxs.map(i => arr[i]);
  },
  shuffle: (arr, k) => {
    arr = arr.slice();
    const n = arr.length;
    for (let i=0; i<k; ++i) {
      const index = Math.floor(Math.random() * (n - i)) + i;
      const t = arr[index];
      arr[i] = arr[index];
      arr[index] = t;
    }
    return arr.slice(0, k);
  },
  shuffleEcma: (arr, k) => {
    arr = arr.slice();
    const n = arr.length;
    for (let i=0; i<k; ++i) {
      const index = Math.floor(Math.random() * (n - i)) + i;
      [arr[i], arr[index]] = [arr[index], arr[i]]
    }
    return arr.slice(0, k);
    
  },
  shuffleRev: (arr, k) => {
    arr = arr.slice()
    const n = arr.length
    for (let i=n-1; i>n-k; --i) {
      const index = Math.floor(Math.random() * (i + 1));
      const t = arr[index]
      arr[i] = arr[index]
      arr[index] = t
    }
    return arr.slice(n-k);
  },
  shuffleEcmaRev: (arr, k) => {
    arr = arr.slice();
    const n = arr.length;
    for (let i=n-1; i>n-k; --i) {
      const index = Math.floor(Math.random() * (i + 1));
      [arr[index], arr[i]] = [arr[i], arr[index]]
    }
    return arr.slice(n-k);
  },
  takenMapArr: (arr, k) => {
    const taken = []
    const result = []
    const n = arr.length;
    while (result.length < k) {
      const i = Math.floor(Math.random() * n);
      if (!taken[i]) {
        taken[i] = true;
        result.push(arr[i]);
      }
    }
    return result
  },
  takenMapObj: (arr, k) => {
    const taken = {}
    const n = arr.length;
    const result = []
    while (result.length < k) {
      const i = Math.floor(Math.random() * n);
      if (!taken[i]) {
        taken[i] = true;
        result.push(arr[i]);
      }
    }
    return result
  }
}
const bestSwr = {true: swrs.indexOf, false: swrs.shuffleRev}

Test runner

Ready to run.

Testing in
TestOps/sec
bestOfVerbose (small k/n)
swrs.bestOfVerbose(largeArr, k)
ready
bestOfShort (small k/n)
swrs.bestOfShort(largeArr, k)
ready
shuffle (small k/n)
swrs.shuffle(largeArr, k)
ready
shuffleRev (small k/n)
swrs.shuffleRev(largeArr, k)
ready
shuffleEcma (small k/n)
swrs.shuffleEcma(largeArr, k)
ready
shuffleEcmaRev (small k/n)
swrs.shuffleEcmaRev(largeArr, k)
ready
takenMapObj (small k/n)
swrs.takenMapObj(largeArr, k)
ready
takenMapArr (small k/n)
swrs.takenMapArr(largeArr, k)
ready
indexOf (small k/n)
swrs.indexOf(largeArr, k)
ready
bestOfVerbose (large k/n)
swrs.bestOfVerbose(smallArr, k)
ready
bestOfShort (large k/n)
swrs.bestOfShort(smallArr, k)
ready
shuffle (large k/n)
swrs.shuffle(smallArr, k)
ready
shuffleRev (large k/n)
swrs.shuffleRev(smallArr, k)
ready
shuffleEcma (large k/n)
swrs.shuffleEcma(smallArr, k)
ready
shuffleEcmaRev (large k/n)
swrs.shuffleEcmaRev(smallArr, k)
ready
takenMapObj (large k/n)
swrs.takenMapObj(smallArr, k)
ready
takenMapArr (large k/n)
swrs.takenMapArr(smallArr, k)
ready
indexOf (large k/n)
swrs.indexOf(smallArr, k)
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.