Computer scientists invent an efficient new way to count(quantamagazine.org)

    > Round 1. Keep going through Hamlet, adding new words as you go. If you come to a word that’s already on your list, flip a coin again. If it’s tails, delete the word;

    if hash_set.contains(word) {
        if !keep_a_word(round) {
            hash_set.remove(word);
            continue;
        }
    } else {
        hash_set.insert(word.to_string());
    }

    Total word count: 31955 | limit: 1000
    End Round: 20, word count: 737
    Unique word count: 7233
    Estimated unique word count: 772800512

    hash_set.insert(word.to_string());

    if !keep_a_word(round) {
        hash_set.remove(word);
        continue;
    }

    Total word count: 31955 | 1000
    End Round: 3, word count: 905
    Unique word count: 7233
    Estimated unique word count: 7240

  def streaming_algorithm(A, epsilon, delta):
      # Initialize parameters
      p = 1
      X = set()
      thresh = math.ceil((12 / epsilon ** 2) * math.log(8 * len(A) / delta))

      # Process the stream
      for ai in A:
          if ai in X:
              X.remove(ai)
          if random.random() < p:
              X.add(ai)
          if len(X) == thresh:
              X = {x for x in X if random.random() >= 0.5}
              p /= 2
              if len(X) == thresh:
                  return '⊥'

      return len(X) / p


  # Example usage
  A = [1, 2, 3, 1, 2, 3]
  epsilon = 0.1
  delta = 0.01

  output = streaming_algorithm(A, epsilon, delta)
  print(output)

    import std/[random, math, sets, times]; type F = float
    
    template uniqCEcvm*(it; xfm; k=100, alpha=0.05): untyped =
      ## Return (unbiased estim. cardinality of `it`, 1-alpha CI ebound*(1 +- e)).
      var x1 = initHashSet[type(xfm)](k); var x  = x1.addr
      var x2 = initHashSet[type(xfm)](k); var y  = x2.addr
      var p  = 1.0          # p always 2^-i means could ditch FP
      var n  = 0            #..RNG & arith for bit shifts/masks.
      let t0 = epochTime()
      for e in it:
        inc n   #; let e = xfm # to compute randState.next here
        x[].excl e          # 'd be nice to reduce to 1 hash by
        if rand(1.0) < p:   #..excl w/prob 1 - p but then cannot
          x[].incl e        #..add new keys.  p -> 0 anyway.
        while x[].len == k: # KnuthLoop not CVMIf guards against
          for e in x[]:     #..unlikely case of freeing nothing.
            if rand(1.0) < 0.5: y[].incl e
          p *= 0.5
          swap x, y; y[].clear # ↓ e.bound conservative by ~15X
      (int(x[].len.F/p), sqrt(12.0*ln(8.0*n.F/alpha)/k.F),
       (epochTime() - t0)*1e9/n.F)
    
    when isMainModule:  # Takes nItem/trial dupMask space nTrial
      when defined danger: randomize()
      import std/[strutils, os, strformat]
      let n   =  if paramCount()>0: parseInt(paramStr(1)) else: 100000
      let msk = (if paramCount()>1: parseInt(paramStr(2)) else: 0xFFFF).uint64
      let k   =  if paramCount()>2: parseInt(paramStr(3)) else: 512 # 32KiB
      let m   =  if paramCount()>3: parseInt(paramStr(4)) else: 35
      var ex  = initHashSet[uint64]()
      var xs  = newSeq[uint64](n)
      for j in 1..m:
        xs.setLen 0; ex.clear
        for i in 1..n: xs.add randState.next and msk
        for e in xs: ex.incl e
        let (apx, err, t) = uniqCEcvm(xs, uint64, k)
        let ap = apx.F; let an = ex.len.F
        echo ex.len," ",apx,&" eb: {err:.4f} |x-a|/x: {abs(ap-an)/an:.4f} {t:.1f}ns"

    51160 49152 eb: 0.6235 |x-a|/x: 0.0392 10.5ns
    51300 51840 eb: 0.6235 |x-a|/x: 0.0105 10.7ns
    51250 55168 eb: 0.6235 |x-a|/x: 0.0764 10.9ns
    51388 52352 eb: 0.6235 |x-a|/x: 0.0188 10.5ns

    func CountUnique(scanner *bufio.Scanner, epsilon float64, delta float64, m int) int {

    X := make(map[string]bool)
    p := 1.0
    thresh := int(math.Ceil((12 / (epsilon * epsilon)) \* math.Log(8*float64(m)/delta)))

    for scanner.Scan() {
        a := scanner.Text()
        delete(X, a)
        if rand.Float64() < p {
            X[a] = true
        }

        if len(X) == thresh {
            for key := range X {
                if rand.Float64() < 0.5 {
                    delete(X, key)
                }
            }
            p /= 2
            if len(X) == thresh {
                panic("Error")
            }
        }
    }

    return int(float64(len(X)) / p)

  func CountUnique2(scanner *bufio.Scanner, thresh int) int {

     //threshold passed in, based on system memory / estimates
    X := make(map[string]bool)
    p := 1.0

    for scanner.Scan() {
        a := scanner.Text()
        delete(X, a)
        if rand.Float64() < p {
            X[a] = true
        }

        if len(X) >= thresh {  // >= instead of == and remove the panic below
            for key := range X {
                if rand.Float64() < 0.5 {
                    delete(X, key)
                }
            }
            p /= 2
        }
    }

    return int(float64(len(X)) / p)