欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

GO?CountMinSketch計(jì)數(shù)器(布隆過(guò)濾器思想的近似計(jì)數(shù)器)

 更新時(shí)間:2022年09月14日 08:34:00   作者:jiaxwu??????  
這篇文章主要介紹了GO?CountMinSketch計(jì)數(shù)器(布隆過(guò)濾器思想的近似計(jì)數(shù)器),文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,需要的朋友可以參考一下

簡(jiǎn)介

CountMinSketch是一種計(jì)數(shù)器,用來(lái)統(tǒng)計(jì)一個(gè)元素的計(jì)數(shù),它能夠以一個(gè)非常小的空間統(tǒng)計(jì)大量元素的計(jì)數(shù),同時(shí)保證高的性能及準(zhǔn)確性。

與布隆過(guò)濾器類似,由于它是基于概率的,因此它所統(tǒng)計(jì)的計(jì)數(shù)是有一定概率存在誤差的,也就是可能會(huì)比真實(shí)的計(jì)數(shù)大。比如一個(gè)元素實(shí)際的計(jì)數(shù)是10,但是計(jì)算器的計(jì)算結(jié)果可能比10大。因此適合能夠容忍計(jì)數(shù)存在一定誤差的場(chǎng)景,比如社交網(wǎng)絡(luò)中推文的訪問(wèn)次數(shù)。

它一秒能夠進(jìn)行上百萬(wàn)次操作(主要取決于哈希函數(shù)的速度),并且如果我們每天有一個(gè)長(zhǎng)度為100億的數(shù)據(jù)流需要進(jìn)行計(jì)數(shù),計(jì)數(shù)值允許的誤差范圍是100,允許的錯(cuò)誤率是0.1%,計(jì)數(shù)器大小是32位,只需要7.2GB內(nèi)存,這完全可以單機(jī)進(jìn)行計(jì)數(shù)。

原理

數(shù)據(jù)結(jié)構(gòu)

CountMinSketch計(jì)數(shù)器的數(shù)據(jù)結(jié)構(gòu)是一個(gè)二維數(shù)組,每一個(gè)元素都是一個(gè)計(jì)數(shù)器,計(jì)數(shù)器可以使用一個(gè)數(shù)值類型進(jìn)行表示,比如無(wú)符號(hào)int

增加計(jì)數(shù)

每個(gè)元素會(huì)通過(guò)不同的哈希函數(shù)映射到每一行的某個(gè)位置,并增加對(duì)應(yīng)位置上的計(jì)數(shù):

估算計(jì)數(shù)

估算計(jì)數(shù)也是如上圖流程,根據(jù)哈希映射到每一行的對(duì)應(yīng)位置,然后讀取所有行的計(jì)數(shù),返回其中最小的一個(gè)。

返回最小的一個(gè)是因?yàn)槠渌渌匾部赡軙?huì)映射到自身所映射位置上面,導(dǎo)致計(jì)數(shù)比真實(shí)計(jì)數(shù)大,因此最小的一個(gè)計(jì)數(shù)最可能是真實(shí)計(jì)數(shù):

比如上圖元素123映射到了元素abc第一行的相同位置,因此這個(gè)位置的計(jì)數(shù)累加了元素abc和元素123的計(jì)數(shù)和。但是只要我們?nèi)∪欣锩孀钚〉囊粋€(gè)計(jì)數(shù),那么就能容忍這種情況。

當(dāng)然,如果一個(gè)元素的每一行的對(duì)應(yīng)位置都被其他元素所映射,那么這個(gè)估算的計(jì)數(shù)就會(huì)比真實(shí)計(jì)數(shù)大。

哈希函數(shù)

CountMinSketch計(jì)數(shù)器里面的哈希函數(shù)需要是彼此獨(dú)立且均勻分布(類似于哈希表的哈希函數(shù)),而且需要盡可能的快,比如murmur3就是一個(gè)很好的選擇。

CountMinSketch計(jì)數(shù)器的性能嚴(yán)重依賴于哈希函數(shù)的性能,而一般哈希函數(shù)的性能則依賴于輸入串(一般為字節(jié)數(shù)組)的長(zhǎng)度,因此為了提高CountMinSketch計(jì)數(shù)器的性能建議減少輸入串的長(zhǎng)度。

下面是一個(gè)簡(jiǎn)單的性能測(cè)試,單位是字節(jié),可以看到時(shí)間的消耗隨著元素的增大基本是線性增長(zhǎng)的:

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

數(shù)組大小、哈希函數(shù)數(shù)量、錯(cuò)誤范圍、錯(cuò)誤率

數(shù)組大小、哈希函數(shù)數(shù)量、錯(cuò)誤范圍和錯(cuò)誤率之間是互相影響的,如果我們想減少錯(cuò)誤率和錯(cuò)誤范圍,則需要更大的數(shù)組和更多的哈希函數(shù)。但是我們很難直觀的計(jì)算出這些參數(shù),還好有兩個(gè)公式可以幫助我們計(jì)算出準(zhǔn)確的數(shù)值:

在我們可以確定我們的數(shù)據(jù)流大小和能夠容忍的錯(cuò)誤范圍錯(cuò)誤率的情況下,我們可以根據(jù)下面公式計(jì)算數(shù)組大小哈希函數(shù)數(shù)量

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))

應(yīng)用

TopK(海量數(shù)據(jù)計(jì)數(shù)器)

對(duì)于海量數(shù)據(jù)流中頻率最高的K個(gè)數(shù),如果使用常規(guī)的map<key, uint>,由于內(nèi)存大小限制,一般情況下單機(jī)無(wú)法完成計(jì)算,需要把數(shù)據(jù)路由到多臺(tái)機(jī)器上進(jìn)行計(jì)數(shù)。

而如果我們使用CountMinSketch則能夠在單機(jī)情況下處理大量的數(shù)據(jù),比如開(kāi)頭所提到對(duì)于一個(gè)長(zhǎng)度為100億的數(shù)據(jù)流進(jìn)行計(jì)數(shù),只需要7.2GB內(nèi)存。這個(gè)計(jì)數(shù)結(jié)果可能存在一定誤差,不過(guò)我們可以在這個(gè)基礎(chǔ)上再進(jìn)行過(guò)濾。

TinyLFU

TinyLFU是一個(gè)緩存淘汰策略,它里面有LFU策略的思想,LFU是一個(gè)基于訪問(wèn)頻率的淘汰策略,因此需要統(tǒng)計(jì)每個(gè)元素被訪問(wèn)的次數(shù)。如果對(duì)每個(gè)元素使用一個(gè)獨(dú)立的計(jì)數(shù)器,那么這個(gè)成本會(huì)很大,而且對(duì)于一個(gè)緩存淘汰策略來(lái)說(shuō),我們并不需要這個(gè)計(jì)數(shù)器非常大且非常準(zhǔn)確。

因此TinyLFU使用一個(gè)計(jì)數(shù)器長(zhǎng)度為4位的CountMinSketch計(jì)數(shù)器統(tǒng)計(jì)每個(gè)元素的頻率,減少計(jì)數(shù)所消耗的內(nèi)存空間,同時(shí)還引入了計(jì)數(shù)衰減機(jī)制避免某些之前熱門但是當(dāng)前已經(jīng)很少被訪問(wèn)的元素很難被淘汰。

實(shí)現(xiàn)

這里給出一個(gè)Golang的泛型實(shí)現(xiàn),這個(gè)實(shí)現(xiàn)支持uint8、uint16uint32、uint64等基本類型計(jì)數(shù)器,實(shí)際上還可以實(shí)現(xiàn)比如長(zhǎng)度為2bit、4bit、6bit的計(jì)數(shù)器,但是代碼會(huì)稍微復(fù)雜一點(diǎn)(特別是非2的次方的計(jì)數(shù)器)。

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
			}
		}
	}
}

數(shù)據(jù)結(jié)構(gòu)

這里的數(shù)據(jù)結(jié)構(gòu)核心是一個(gè)k*m的二維數(shù)組counters,k是哈希函數(shù)數(shù)量,m是數(shù)組每一行的長(zhǎng)度;countersLen其實(shí)就是m;hashs是哈希函數(shù)列表;maxCount是當(dāng)前類型的最大值,比如uint8就是255,下面的計(jì)算需要用到它。

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

初始化

我們首先使用上面提到的兩個(gè)公式計(jì)算數(shù)組每一行長(zhǎng)度和哈希函數(shù)的數(shù)量,然后初始化哈希函數(shù)列表和二維數(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ù)

對(duì)于一個(gè)元素,我們需要把它根據(jù)每個(gè)哈希函數(shù)計(jì)算出它在每一行數(shù)組的位置,然后增加對(duì)應(yīng)位置計(jì)數(shù)器的計(jì)數(shù)值。

這里需要注意的是,計(jì)數(shù)值可能會(huì)溢出,因此我們首先判斷是否溢出,如果溢出則設(shè)置為最大值。

// 增加元素的計(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ù)

同增加計(jì)數(shù)原理,把元素根據(jù)哈希函數(shù)映射到每一行數(shù)組的對(duì)應(yīng)位置,然后選擇所有行中最小的那個(gè)計(jì)數(shù)值。

// 估算元素的計(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
}

到此這篇關(guān)于GO CountMinSketch計(jì)數(shù)器(布隆過(guò)濾器思想的近似計(jì)數(shù)器)的文章就介紹到這了,更多相關(guān)GO CountMinSketch內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • golang使用mapstructure解析json

    golang使用mapstructure解析json

    mapstructure?是一個(gè)?Go?庫(kù),用于將通用映射值解碼為結(jié)構(gòu),這篇文章主要來(lái)和大家介紹一下golang如何使用mapstructure解析json,需要的可以參考下
    2023-12-12
  • Golang并發(fā)操作中常見(jiàn)的讀寫(xiě)鎖詳析

    Golang并發(fā)操作中常見(jiàn)的讀寫(xiě)鎖詳析

    Golang中的鎖機(jī)制主要包含互斥鎖和讀寫(xiě)鎖互斥鎖互斥鎖是傳統(tǒng)并發(fā)程序?qū)蚕碣Y源進(jìn)行控制訪問(wèn)的主要手段,這篇文章主要給大家介紹了關(guān)于Golang并發(fā)操作中常見(jiàn)的讀寫(xiě)鎖的相關(guān)資料,需要的朋友可以參考下
    2021-08-08
  • go for range遍歷二維數(shù)組的示例

    go for range遍歷二維數(shù)組的示例

    今天小編就為大家分享一篇關(guān)于go for range遍歷二維數(shù)組的示例,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧
    2019-04-04
  • go reflect要不要傳指針原理詳解

    go reflect要不要傳指針原理詳解

    這篇文章主要為大家介紹了go reflect要不要傳指針原理詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-01-01
  • Go并發(fā)原語(yǔ)之SingleFlight請(qǐng)求合并方法實(shí)例

    Go并發(fā)原語(yǔ)之SingleFlight請(qǐng)求合并方法實(shí)例

    本文我們來(lái)學(xué)習(xí)一下 Go 語(yǔ)言的擴(kuò)展并發(fā)原語(yǔ):SingleFlight,SingleFlight 的作用是將并發(fā)請(qǐng)求合并成一個(gè)請(qǐng)求,以減少重復(fù)的進(jìn)程來(lái)優(yōu)化 Go 代碼
    2023-12-12
  • 基于HLS創(chuàng)建Golang視頻流服務(wù)器的優(yōu)缺點(diǎn)

    基于HLS創(chuàng)建Golang視頻流服務(wù)器的優(yōu)缺點(diǎn)

    HLS 是 HTTP Live Streaming 的縮寫(xiě),是蘋果開(kāi)發(fā)的一種基于 HTTP 的自適應(yīng)比特率流媒體傳輸協(xié)議。這篇文章主要介紹了基于 HLS 創(chuàng)建 Golang 視頻流服務(wù)器,需要的朋友可以參考下
    2021-08-08
  • Go編寫(xiě)定時(shí)器與定時(shí)任務(wù)詳解(附第三方庫(kù)gocron用法)

    Go編寫(xiě)定時(shí)器與定時(shí)任務(wù)詳解(附第三方庫(kù)gocron用法)

    當(dāng)需要每天執(zhí)行定時(shí)任務(wù)的時(shí)候就需要定時(shí)器來(lái)處理了,周期任務(wù),倒計(jì)時(shí)任務(wù),定點(diǎn)任務(wù)等,下面這篇文章主要給大家介紹了關(guān)于Go編寫(xiě)定時(shí)器與定時(shí)任務(wù)的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2022-07-07
  • 解決go echo后端處理跨域的兩種操作方式

    解決go echo后端處理跨域的兩種操作方式

    這篇文章主要介紹了解決go echo后端處理跨域的兩種操作方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2020-12-12
  • go語(yǔ)言的工作空間和GOPATH環(huán)境變量介紹

    go語(yǔ)言的工作空間和GOPATH環(huán)境變量介紹

    這篇文章主要介紹了go語(yǔ)言的工作空間和GOPATH環(huán)境變量介紹,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2020-12-12
  • 在go語(yǔ)言中安裝與使用protobuf的方法詳解

    在go語(yǔ)言中安裝與使用protobuf的方法詳解

    protobuf以前只支持C++, Python和Java等語(yǔ)言, Go語(yǔ)言出來(lái)后, 作為親兒子, 那有不支持的道理呢? 這篇文章主要給大家介紹了關(guān)于在go語(yǔ)言中使用protobuf的相關(guān)資料,文中介紹的非常詳細(xì),需要的朋友可以參考借鑒,下面來(lái)一起看看吧。
    2017-08-08

最新評(píng)論