README
¶
CountMin
CountMin sketching algorithm.
Install
Install package
go get -u github.com/mtchavez/countmin
Usage
package main
import (
"fmt"
"github.com/mtchavez/countmin"
)
func main() {
cm := countmin.New(10, 100000000)
for _, i := range []int64{1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1} {
cm.Add([]byte(fmt.Sprintf("%d", i)), int64(i))
}
fmt.Printf("Estimate of %d is %d\n", 1, cm.Count([]byte("1")))
fmt.Printf("Estimate of %d is %d\n", 3, cm.Count([]byte("3")))
fmt.Printf("Estimate of %d is %d\n", 9, cm.Count([]byte("9")))
fmt.Println("Size: ", cm.Size())
fmt.Println("Err: ", cm.RelativeError())
fmt.Println("Confidence: ", cm.Confidence())
}
Tests
Run using go test ./... --cover
Run benchmarks go test --bench=.*
TODO
- Serialize/Deserialize
- TCP / HTTP server wrappers
Documentation
¶
Index ¶
Examples ¶
Constants ¶
const MAXINT64 = 1<<63 - 1
Max int 64 size
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CountMin ¶
type CountMin struct {
// contains filtered or unexported fields
}
CountMin holds count table and hashes for calculating frequencies from a given input (usually a stream of data)
func New ¶
New CountMin given a depth and width of the frequency table to use. Returns the newly created CountMin
func NewWithEpsCount ¶
NewWithEpsCount initializes a CountMin given a confidence to ensure between 0 < 1.0 which effects number of hashes used and an epsilon between 0 and 1 with a smaller value for higher precision as it affects the width of the table
func (*CountMin) Add ¶
Add inserts an item in bytes and a count associated which will also increment size of CountMin
Example ¶
cm := New(10, 100000000)
for _, i := range []int64{1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1} {
cm.Add([]byte(fmt.Sprintf("%d", i)), int64(i))
}
fmt.Printf("Estimate of %d is %d\n", 1, cm.Count([]byte("1")))
fmt.Printf("Estimate of %d is %d\n", 3, cm.Count([]byte("3")))
fmt.Printf("Estimate of %d is %d\n", 9, cm.Count([]byte("9")))
fmt.Println("Size: ", cm.Size())
fmt.Println("Err: ", cm.RelativeError())
fmt.Println("Confidence: ", cm.Confidence())
Output: Estimate of 1 is 3 Estimate of 3 is 6 Estimate of 9 is 18 Size: 91 Err: 2e-08 Confidence: 0.9990234375
func (*CountMin) Confidence ¶
Confidence returns confidence of CountMin
func (*CountMin) RelativeError ¶
RelativeError returns epsilon of CountMin
Source Files