distinct

README

Distinct

This micro-library estimates the number of distinct elements in a stream:

import (
    "fmt"
    "github.com/betamos/distinct"
)

// Uses a map of size 200
c := distinct.NewCounter[int](200, nil)
for i := 0; i < 100000; i++ {
	c.Add(i % 300)
}
fmt.Println(c.Estimate()) // Should be somewhere around 300

It's based on Distinct Elements in Streams: An Algorithm for the (Text) Book.

Documentation

Index

• func Threshold(epsilon, delta float64, m int) int
• type Counter
  • func NewCounter[T comparable](threshold int, src rand.Source) *Counter[T]
  • func (c *Counter[T]) Add(el T)
  • func (c *Counter[T]) Estimate() uint64

Functions

func Threshold

func Threshold(epsilon, delta float64, m int) int

Returns a suitable threshold value given (see Chernoff Bounds):

• epsilon: relative error of the estimate, lower is more accurate
• delta: confidence level, lower is more accurate
• m: total expected elements in the stream

Types

type Counter

type Counter[T comparable] struct {
	// contains filtered or unexported fields
}

Counter of distinct elements, using https://arxiv.org/pdf/2301.10191

func NewCounter

func NewCounter[T comparable](threshold int, src rand.Source) *Counter[T]

Create a new counter with O(threshold) memory complexity. If src is nil, a source with a random seed will be used.

func (*Counter[T]) Add

func (c *Counter[T]) Add(el T)

Add an element to the counter

func (*Counter[T]) Estimate

func (c *Counter[T]) Estimate() uint64

Returns the current estimate