pkg: github.com/jiaxwu/gommon/counter/cm
cpu: Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
BenchmarkAddAndEstimate/1-8              2289142               505.9 ns/op         1.98 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndEstimate/2-8              2357380               513.7 ns/op         3.89 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndEstimate/4-8              2342382               496.9 ns/op         8.05 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndEstimate/8-8              2039792               499.7 ns/op        16.01 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndEstimate/16-8             2350281               526.8 ns/op        30.37 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndEstimate/32-8             2558060               444.3 ns/op        72.03 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndEstimate/64-8             2540272               459.5 ns/op       139.29 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndEstimate/128-8            1919720               538.6 ns/op       237.67 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndEstimate/256-8            1601738               720.6 ns/op       355.28 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndEstimate/512-8             950584              1599 ns/op         320.18 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndEstimate/1024-8            363592              3169 ns/op         323.17 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndEstimate/2048-8            187500              5888 ns/op         347.81 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndEstimate/4096-8            130425              8825 ns/op         464.15 MB/s           0 B/op          0 allocs/op
BenchmarkAddAndEstimate/8192-8             67198             17460 ns/op         469.18 MB/s           0 B/op          0 allocs/op

n = 數(shù)據(jù)流大小 
m = 數(shù)組大小
k = 哈希函數(shù)數(shù)量 
eRange = 錯(cuò)誤范圍（ErrorRange）
eRate = 錯(cuò)誤率（ErrorRate）
ceil() = 向上取整操作
E = 2.718281828459045（自然常數(shù)）

m = ceil(E/(eRange/n))
k = ceil(ln(1/eRate))

package cm
import (
	"math"

	"github.com/jiaxwu/gommon/hash"
	mmath "github.com/jiaxwu/gommon/math"
	"github.com/jiaxwu/gommon/mem"
	"golang.org/x/exp/constraints"
)

// Count-Min Sketch 計(jì)數(shù)器，原理類似于布隆過(guò)濾器，根據(jù)哈希映射到多個(gè)位置，然后在對(duì)應(yīng)位置進(jìn)行計(jì)數(shù)
// 讀取時(shí)拿對(duì)應(yīng)位置最小的
// 適合需要一個(gè)比較小的計(jì)數(shù)，而且不需要這個(gè)計(jì)數(shù)一定準(zhǔn)確的情況
// 可以減少空間消耗
// https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.591.8351&rep=rep1&type=pdf
type Counter[T constraints.Unsigned] struct {
	counters    [][]T
	countersLen uint64       // 計(jì)數(shù)器長(zhǎng)度
	hashs       []*hash.Hash // 哈希函數(shù)列表
	maxCount    T            // 最大計(jì)數(shù)值
}

// 創(chuàng)建一個(gè)計(jì)數(shù)器
// size：數(shù)據(jù)流大小
// errorRange：計(jì)數(shù)值誤差范圍（會(huì)超過(guò)真實(shí)計(jì)數(shù)值）
// errorRate：錯(cuò)誤率
func New[T constraints.Unsigned](size uint64, errorRange T, errorRate float64) *Counter[T] {
	// 計(jì)數(shù)器長(zhǎng)度
	countersLen := uint64(math.Ceil(math.E / (float64(errorRange) / float64(size))))
	// 哈希個(gè)數(shù)
	hashsCnt := int(math.Ceil(math.Log(1.0 / errorRate)))
	hashs := make([]*hash.Hash, hashsCnt)
	counters := make([][]T, hashsCnt)
	for i := 0; i < hashsCnt; i++ {
		hashs[i] = hash.New()
		counters[i] = make([]T, countersLen)
	}
	return &Counter[T]{
		counters:    counters,
		countersLen: countersLen,
		hashs:       hashs,
		maxCount:    T(0) - 1,
	}
}

// 增加元素的計(jì)數(shù)
func (c *Counter[T]) Add(b []byte, val T) {
	for i, h := range c.hashs {
		index := h.Sum64(b) % c.countersLen
		if c.counters[i][index]+val <= c.counters[i][index] {
			c.counters[i][index] = c.maxCount
		} else {
			c.counters[i][index] += val
		}
	}
}

// 增加元素的計(jì)數(shù)
// 等同于Add(b, 1)
func (c *Counter[T]) Inc(b []byte) {
	c.Add(b, 1)
}

// 增加元素的計(jì)數(shù)
// 字符串類型
func (c *Counter[T]) AddString(s string, val T) {
	c.Add([]byte(s), val)
}

// 增加元素的計(jì)數(shù)
// 等同于Add(b, 1)
// 字符串類型
func (c *Counter[T]) IncString(s string) {
	c.Add([]byte(s), 1)
}

// 估算元素的計(jì)數(shù)
func (c *Counter[T]) Estimate(b []byte) T {
	minCount := c.maxCount
	for i, h := range c.hashs {
		index := h.Sum64(b) % c.countersLen
		count := c.counters[i][index]
		if count == 0 {
			return 0
		}
		minCount = mmath.Min(minCount, count)
	}
	return minCount
}

// 估算元素的計(jì)數(shù)
// 字符串類型
func (c *Counter[T]) EstimateString(s string) T {
	return c.Estimate([]byte(s))
}

// 計(jì)數(shù)衰減
// 如果factor為0則直接清空
func (c *Counter[T]) Attenuation(factor T) {
	for _, counter := range c.counters {
		if factor == 0 {
			mem.Memset(counter, 0)
		} else {
			for j := uint64(0); j < c.countersLen; j++ {
				counter[j] /= factor
			}
		}
	}
}

type Counter[T constraints.Unsigned] struct {
	counters    [][]T
	countersLen uint64       // 計(jì)數(shù)器長(zhǎng)度
	hashs       []*hash.Hash // 哈希函數(shù)列表
	maxCount    T            // 最大計(jì)數(shù)值
}

// 創(chuàng)建一個(gè)計(jì)數(shù)器
// size：數(shù)據(jù)流大小
// errorRange：計(jì)數(shù)值誤差范圍（會(huì)超過(guò)真實(shí)計(jì)數(shù)值）
// errorRate：錯(cuò)誤率
func New[T constraints.Unsigned](size uint64, errorRange T, errorRate float64) *Counter[T] {
	// 計(jì)數(shù)器長(zhǎng)度
	countersLen := uint64(math.Ceil(math.E / (float64(errorRange) / float64(size))))
	// 哈希個(gè)數(shù)
	hashsCnt := int(math.Ceil(math.Log(1.0 / errorRate)))
	hashs := make([]*hash.Hash, hashsCnt)
	counters := make([][]T, hashsCnt)
	for i := 0; i < hashsCnt; i++ {
		hashs[i] = hash.New()
		counters[i] = make([]T, countersLen)
	}
	return &Counter[T]{
		counters:    counters,
		countersLen: countersLen,
		hashs:       hashs,
		maxCount:    T(0) - 1,
	}
}

// 增加元素的計(jì)數(shù)
func (c *Counter[T]) Add(b []byte, val T) {
	for i, h := range c.hashs {
		index := h.Sum64(b) % c.countersLen
		if c.counters[i][index]+val <= c.counters[i][index] {
			c.counters[i][index] = c.maxCount
		} else {
			c.counters[i][index] += val
		}
	}
}

// 估算元素的計(jì)數(shù)
func (c *Counter[T]) Estimate(b []byte) T {
	minCount := c.maxCount
	for i, h := range c.hashs {
		index := h.Sum64(b) % c.countersLen
		count := c.counters[i][index]
		if count == 0 {
			return 0
		}
		minCount = mmath.Min(minCount, count)
	}
	return minCount
}