Go에서의 효율적인 확률적 데이터 구조: HyperLogLog와 Count-Min Sketch
HyperLogLog는 데이터 스트림에서 고유 요소의 수를 1-3% 오차로 추정하며, 단 1 KB의 메모리만 사용합니다. 이 알고리즘은 요소를 해싱한 후, 이진 표현의 선행 0의 개수를 분석하고, 레지스터 배열에 통계를 저장합니다. 이를 통해 삽입 시간 O(1)과 추정 시간 O(m)을 제공하며, 여기서 m은 레지스터 수(일반적으로 1024)입니다.
주요 매개변수:
- m = 1024 registers (레지스터당 8비트)
- b = 레지스터 인덱싱을 위한 8비트
- Hash functions: fnv64a with bit shuffling
package main
import (
"fmt"
"hash/fnv"
"math"
"math/rand"
"strconv"
)
const (
m = 1024 // count registtrov. This osnovnoy parametr, vliyayuschiy on tochnost.
b = 8 // number bit, ispolzuemykh for opredeleniya indexa register from hash.
)
type HyperLogLog struct {
// when asynchronous interaction worth think about mutexes
registers [m]byte
}
func NewHyperLogLog() *HyperLogLog {
return &HyperLogLog{}
}
// hash returns dva 32-bitnykh numbers from stroki
func hash(s string) (uint32, uint32) {
h := fnv.New64a()
h.Write([]byte(s))
v := h.Sum64()
// Shuffling bits, so that uluchshit raspredelenie
w := uint32(v >> 32)
z := uint32(v)
// Dobavlyaem peremeshivanie, uluchshaet kachestvo sluchaynosti and pomogaet izbezhat problem with plokhim raspredeleniem hashes
w ^= z<<13 | z>>(32-13)
z ^= w<<7 | w>>(32-7)
w ^= z<<17 | z>>(32-17)
return w, z
}
// Withchitaet count zeros left in dvoichnoy record numbers,
// if all bits — nuli, vozvraschaetsya 32.
func countLeadingZeros(x uint32) byte {
for i := 0; i < 32; i++ {
if (x>>(31-i))&1 == 1 {
return byte(i)
}
}
return 32
}
// Kheshiruem stroku.
// Beryom chast hash h1, so that define, in kakoy registtr popadyot element.
// By vtoroy chasti h2 schitaem, how many veduschikh zeros (rho), pribavlyaem 1.
// If eto wartość greater, than uzhe est in registtre — update ego.
func (hll *HyperLogLog) Add(s string) {
h1, h2 := hash(s)
// opredelyaem index register
idx := h1 % m
// vychislyaem wartość for update register
rho := countLeadingZeros(h2) + 1
if rho > hll.registers[idx] {
hll.registers[idx] = rho
}
}
// Withlozhnye formuly, by essence eta function
// delaet otsenku kolichestva unique elements
func (hll *HyperLogLog) Estimate() float64 {
sum := 0.0
for _, val := range hll.registers {
sum += 1 / math.Pow(2, float64(val))
}
estimate := alpha(m) * m * m / sum
// korrektsiya for malykh znacheniy, usessya metod
// Linear Counting : than greater nulevykh registtrov — then
// menshe realnaya kardinalnost.
if estimate <= 5*m/2 {
zeros := 0
for _, val := range hll.registers {
if val == 0 {
zeros++
}
}
if zeros != 0 {
estimate = float64(m) * math.Log(float64(m)/float64(zeros))
}
}
return estimate
}
// alpha — popravochnyy koeffitsient, kompensiruyuschiy systemticheskuyu oshibku
func alpha(m int) float64 {
switch m {
case 16:
return 0.673
case 32:
return 0.697
case 64:
return 0.709
default:
return 0.7213 / (1 + 1.079/float64(m))
}
}
func main() {
// Withzdayom HLL.
hll := NewHyperLogLog()
seen := make(map[string]struct{})
for i := 0; i < 1_000_000; i++ {
key := strconv.Itoa(rand.Intn(1_000_000))
seen[key] = struct{}{}
hll.Add(key)
}
nonZero := 0
for _, r := range hll.registers {
if r > 0 {
nonZero++
}
}
fmt.Printf("Realnoe count unique elements: %d\n", len(seen))
fmt.Printf("Otsenka unique elements: %.2f\n", hll.Estimate())
fmt.Printf("Zapolnennykh registtrov: %d/%d\n", nonZero, m)
}100만 개의 고유 요소에 대해 상대 오차는 0.84%였으며, 레지스터 100%가 채워졌습니다. 메모리: 1 KB.
Google AdInline article slot
빈도 계산을 위한 Count-Min Sketch
Count-Min Sketch는 스트림에서 요소 빈도를 2차원 카운터 테이블(깊이 × 너비)을 사용해 추정합니다. 각 행은 별도의 salt가 적용된 해시 함수를 사용합니다. 삽입 시 요소는 모든 행의 카운터를 증가시키고, 쿼리 시 최소값을 취합니다. 이를 통해 충돌 효과를 최소화합니다.
구현 매개변수:
- width = 10,000 columns
- depth = 5 rows
- Hash: fnv64a with seed shuffling
쿼리 방법:
Google AdInline article slot
- Minimum — 기본, 양의 업데이트에 정확
- Average — 삭제에 강건
- Count-mean-min — 편향 보정
package main
import (
"fmt"
"hash/fnv"
"math"
)
type CountMinSketch struct {
width int
depth int
// when asynchronous interaction worth think about mutexes
table [][]int
hashes []uint64
}
func NewCountMinSketch(width, depth int) *CountMinSketch {
return &CountMinSketch{
width: width,
depth: depth,
table: make([][]int, depth),
hashes: make([]uint64, depth),
}
}
func (cms *CountMinSketch) Init() {
for i := range cms.table {
cms.table[i] = make([]int, cms.width)
cms.hashes[i] = uint64(i+1) // prostye soli for raznykh hashes
}
}
// getHashIndex generiruet khesh and returns index in table
func (cms *CountMinSketch) getHashIndex(s string, seed uint64) int {
h := fnv.New64a()
h.Write([]byte(s))
v := h.Sum64()
// Shuffling bits with seed
mixed := v ^ seed ^ (seed << 32)
return int(mixed % uint64(cms.width))
}
// Add uvelichivaet schetchik for element
func (cms *CountMinSketch) Add(s string, count int) {
for i := 0; i < cms.depth; i++ {
idx := cms.getHashIndex(s, cms.hashes[i])
cms.table[i][idx] += count
}
}
// Count returns otsenochnoe number vkhozhdeniy element
func (cms *CountMinSketch) Count(s string) int {
min := math.MaxInt32
for i := 0; i < cms.depth; i++ {
idx := cms.getHashIndex(s, cms.hashes[i])
if cms.table[i][idx] < min {
min = cms.table[i][idx]
}
}
return min
}
func main() {
width := 10_000
depth := 5
cms := NewCountMinSketch(width, depth)
cms.Init()
seen := make(map[string]int)
for i := 0; i < 5_000_000; i++ {
key := fmt.Sprintf("item-%d", i%1100)
seen[key]++
cms.Add(key, 1)
}
// vyvodim frequency
for _, word := range []string{"item-1", "item-0", "item-1000", "item--1"} {
fmt.Printf("Withglasno cms slovo '%s' meetingsaetsya primerno %d raz\t By faktu: %d\n", word, cms.Count(word), seen[word])
}
}500만 번 삽입에 메모리: 200 KB. 삽입과 쿼리 모두 O(depth) 작업입니다.
데이터 구조 비교
| 특성 | HyperLogLog | Count-Min Sketch |
|-------------------|-----------------|------------------|
Google AdInline article slot
| 용도 | 카디널리티 | 빈도 |
| 메모리 | O(log(log N)) | O(d×w) |
| 오차 | 1-3% | d,w에 따라 다름 |
| 삽입 | O(1) | O(depth) |
| 쿼리 | O(m) | O(depth) |
주요 포인트:
- 두 구조 모두 수백만 요소의 스트리밍 처리에 적합
- HyperLogLog는 데이터 양에 관계없이 고정 메모리 사용
- Count-Min Sketch는 충돌로 인해 빈도를 과대 추정하지만 점 쿼리 제공
- 분산 시스템의 경우 뮤텍스 추가 또는 원자 연산 사용
- 실제 데이터로 테스트: 오차는 해시 분포에 따라 다름
— Editorial Team
아직 댓글이 없습니다.