Distinct Elements in Streams: An Algorithm for the (Text) Book

index.js

// Paper: https://arxiv.org/pdf/2301.10191
// Article: https://www.quantamagazine.org/computer-scientists-invent-an-efficient-new-way-to-count-20240516/

function generateRandomNumbers(c, n) {
  let randomNumbers = new Array(c);
  for (let i = 0; i < randomNumbers.length; i++) {
    let randomNumber = Math.floor(Math.random() * (n + 1));
    randomNumbers[i] = randomNumber;
  }
  return randomNumbers;
}

function run(w, wS, m, r) {
  function round(r) {
    while (wS.size < m) {
      const next = w.next()
      if (next.done) return true;
      wS.add(next.value)
      prune(next.value, r)
    }
    return false
  }

  function prune(v, r) {
    for (let i = 0; i < r; i++) {
      const flip = new Boolean(Math.round(Math.random()))
      if (flip == false) {
        wS.delete(v)
      }
    }
  }

  function purge(wS) {
    const copy = new Set(wS)
    copy.forEach(ith => {
      const flip = new Boolean(Math.round(Math.random()))
      if (flip == false) {
        wS.delete(ith)
      }
    })
  }
  const done = round(r);
  if (!done) {
    purge(wS)
    /* return run(w, wS, r+1,m) */
    return run(w, wS, m, r + 1)
  }
  console.log(`Round ${r} done. ${wS.size} Estimate: ${wS.size / (1/Math.pow(2,r))}`)
}
const memory = 1000
const words = generateRandomNumbers(3000000, 15000)
const w = words[Symbol.iterator]() // create an iterator
const wS = new Set();

run(w, wS, memory, 0);