<|start_filename|>loglogbeta_test.go<|end_filename|>
package loglogbeta

import (
	"math"
	"math/rand"
	"testing"
)

const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

func estimateError(got, exp uint64) float64 {
	var delta uint64
	if got > exp {
		delta = got - exp
	} else {
		delta = exp - got
	}
	return float64(delta) / float64(exp)
}

func TestZeros(t *testing.T) {
	registers := [m]uint8{}
	exp := 0.0
	for i := range registers {
		val := uint8(rand.Intn(32))
		if val == 0 {
			exp++
		}
		registers[i] = val
	}
	_, got := regSumAndZeros(registers[:])
	if got != exp {
		t.Errorf("expected %.2f, got %.2f", exp, got)
	}
}

func RandStringBytesMaskImprSrc(n uint32) string {
	b := make([]byte, n)
	for i := uint32(0); i < n; i++ {
		b[i] = letterBytes[rand.Int()%len(letterBytes)]
	}
	return string(b)
}

func TestCardinality(t *testing.T) {
	llb := New()
	step := 10000
	unique := map[string]bool{}

	for i := 1; len(unique) <= 1000000; i++ {
		str := RandStringBytesMaskImprSrc(rand.Uint32() % 32)
		llb.Add([]byte(str))
		unique[str] = true

		if len(unique)%step == 0 {
			exact := uint64(len(unique))
			res := uint64(llb.Cardinality())
			step *= 10

			ratio := 100 * estimateError(res, exact)
			if ratio > 2 {
				t.Errorf("Exact %d, got %d which is %.2f%% error", exact, res, ratio)
			}

		}
	}
}

func TestMerge(t *testing.T) {
	llb1 := New()
	llb2 := New()

	unique := map[string]bool{}

	for i := 1; i <= 3500000; i++ {
		str := RandStringBytesMaskImprSrc(rand.Uint32() % 32)
		llb1.Add([]byte(str))
		unique[str] = true

		str = RandStringBytesMaskImprSrc(rand.Uint32() % 32)
		llb2.Add([]byte(str))
		unique[str] = true
	}

	llb1.Merge(llb2)
	exact := len(unique)
	res := int(llb1.Cardinality())

	ratio := 100 * math.Abs(float64(res-exact)) / float64(exact)
	expectedError := 1.04 / math.Sqrt(float64(m))

	if float64(res) < float64(exact)-(float64(exact)*expectedError) || float64(res) > float64(exact)+(float64(exact)*expectedError) {
		t.Errorf("Exact %d, got %d which is %.2f%% error", exact, res, ratio)
	}

	llb1.Merge(llb2)
	exact = res
	res = int(llb1.Cardinality())

	if float64(res) < float64(exact)-(float64(exact)*expectedError) || float64(res) > float64(exact)+(float64(exact)*expectedError) {
		t.Errorf("Exact %d, got %d which is %.2f%% error", exact, res, ratio)
	}
}

func TestMarshal(t *testing.T) {
	llb := New()
	unique := map[string]bool{}

	for i := 1; len(unique) <= 1000000; i++ {
		str := RandStringBytesMaskImprSrc(rand.Uint32() % 32)
		llb.Add([]byte(str))
		unique[str] = true
	}

	bytes := llb.Marshal()
	ullb, err := Unmarshal(bytes)
	if err != nil {
		t.Errorf("Expected no error, got %v", err)
	}
	if *ullb != *llb {
		t.Errorf("Expected %d,\n\n got %d", llb, ullb)
	}
}


<|start_filename|>loglogbeta.go<|end_filename|>
package loglogbeta

import (
	"fmt"
	"math"
	bits "math/bits"

	metro "github.com/dgryski/go-metro"
)

const (
	precision = 14
	m         = uint32(1 << precision) // 16384
	max       = 64 - precision
	maxX      = math.MaxUint64 >> max
	alpha     = 0.7213 / (1 + 1.079/float64(m))
)

func beta(ez float64) float64 {
	zl := math.Log(ez + 1)
	return -0.370393911*ez +
		0.070471823*zl +
		0.17393686*math.Pow(zl, 2) +
		0.16339839*math.Pow(zl, 3) +
		-0.09237745*math.Pow(zl, 4) +
		0.03738027*math.Pow(zl, 5) +
		-0.005384159*math.Pow(zl, 6) +
		0.00042419*math.Pow(zl, 7)
}

func regSumAndZeros(registers []uint8) (float64, float64) {
	sum, ez := 0.0, 0.0
	for _, val := range registers {
		if val == 0 {
			ez++
		}
		sum += 1.0 / math.Pow(2.0, float64(val))
	}
	return sum, ez
}

// LogLogBeta is a sketch for cardinality estimation based on LogLog counting
type LogLogBeta [m]uint8

// New returns a LogLogBeta
func New() *LogLogBeta {
	return new(LogLogBeta)
}

// AddHash takes in a "hashed" value (bring your own hashing)
func (llb *LogLogBeta) AddHash(x uint64) {
	k := x >> uint(max)
	val := uint8(bits.LeadingZeros64((x<<precision)^maxX)) + 1
	if llb[k] < val {
		llb[k] = val
	}
}

// Add inserts a value into the sketch
func (llb *LogLogBeta) Add(value []byte) {
	llb.AddHash(metro.Hash64(value, 1337))
}

// Cardinality returns the number of unique elements added to the sketch
func (llb *LogLogBeta) Cardinality() uint64 {
	sum, ez := regSumAndZeros(llb[:])
	m := float64(m)
	return uint64(alpha * m * (m - ez) / (beta(ez) + sum))
}

// Merge takes another LogLogBeta and combines it with llb one, making llb the union of both.
func (llb *LogLogBeta) Merge(other *LogLogBeta) {
	for i, v := range llb {
		if v < other[i] {
			llb[i] = other[i]
		}
	}
}

// Marshal returns a byte slice representation
func (llb *LogLogBeta) Marshal() []byte {
	return llb[:]
}

// Unmarshal returns a LogLogBeta for given bytes
func Unmarshal(bytes []byte) (*LogLogBeta, error) {
	if uint32(len(bytes)) != m {
		return nil, fmt.Errorf("Invalid byte slice length: expected %d, got %d", m, len(bytes))
	}
	llb := new(LogLogBeta)
	copy(llb[:], bytes)
	return llb, nil
}


<|start_filename|>llbdemo/main.go<|end_filename|>
package main

import (
	"bufio"
	"fmt"
	"os"
	"path/filepath"

	"github.com/seiflotfy/loglogbeta"

	"log"
)

func main() {
	files, err := filepath.Glob(fmt.Sprintf("%s/*", os.Args[1]))
	if err != nil {
		log.Fatalln(err)
		return
	}

	totalUnique := map[string]bool{}
	tllb := loglogbeta.New()

	for _, f := range files {
		f, err := os.Open(f)
		if err != nil {
			log.Fatalln(err)
			return
		}
		reader := bufio.NewReader(f)
		unique := map[string]bool{}

		llb := loglogbeta.New()

		for {
			text, _, err := reader.ReadLine()
			if err != nil {
				break
			}
			unique[string(text)] = true
			totalUnique[string(text)] = true
			llb.Add([]byte(text))
			tllb.Add([]byte(text))
		}

		est := llb.Cardinality()
		ratio := fmt.Sprintf("%2f%%", 100*(1-float64(len(unique))/float64(est)))
		log.Println("\n\tfile: ", f.Name(), "\n\texact:", len(unique), "\n\testimate:", est, "\n\tratio:", ratio)
	}

	est := tllb.Cardinality()
	ratio := fmt.Sprintf("%2f%%", 100*(1-float64(len(totalUnique))/float64(est)))
	log.Println("\n\ttotal\n\texact:", len(totalUnique), "\n\testimate:", est, "\n\tratio:", ratio)
}
