-
Notifications
You must be signed in to change notification settings - Fork 1
/
bloom_filter_test.go
108 lines (93 loc) · 2.25 KB
/
bloom_filter_test.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package bloom_filter
import (
"fmt"
"math"
"math/rand"
"strconv"
"testing"
)
type Key string
func (k Key) Bytes() []byte {
return []byte(k)
}
func TestSingleElement(t *testing.T) {
bf := NewBloomFilter[Key](10000, 0.10)
item := Key("Hello")
bf.Insert(item)
if !bf.LookUp(item) {
t.Errorf("Expected item to exist in the bloom filter")
}
}
func TestMultipleElements(t *testing.T) {
bf := NewBloomFilter[Key](10000, 0.10)
items := []string{
"Hello",
"World",
"Bloom",
"Filter",
}
for _, item := range items {
bf.Insert(Key(item))
if !bf.LookUp(Key(item)) {
t.Errorf("Expected item to exist in the bloom filter")
}
}
}
func TestNonExistentElement(t *testing.T) {
bf := NewBloomFilter[Key](10000, 0.10)
item := Key("Hello")
nonExistentItem := Key("NonExistent")
bf.Insert(item)
if bf.LookUp(nonExistentItem) {
t.Errorf("Expected item not to exist in the bloom filter")
}
}
func TestBoundaryCondition(t *testing.T) {
size := 10000
bf := NewBloomFilter[Key](uint32(size), 0.10)
for i := 0; i < size; i++ {
bf.Insert(Key(strconv.Itoa(i)))
}
for i := 0; i < size; i++ {
if !bf.LookUp(Key(strconv.Itoa(i))) {
t.Errorf("Expected item to exist in the bloom filter")
}
}
}
func TestFalsePositiveRate(t *testing.T) {
expectedFalsePositiveRate := 0.02
size := 100_0000
bf := NewBloomFilter[Key](uint32(size), expectedFalsePositiveRate)
dataNum := 10000_0000_0000
m := make(map[string]bool)
for i := 0; i < size; i++ {
num := rand.Int63n(int64(dataNum))
s := fmt.Sprintf("%d", num)
bf.Insert(Key(s))
m[s] = true
}
falsePositiveCount := 0
testCount := 1000000
for i := 0; i < testCount; i++ {
num := rand.Int63n(int64(dataNum))
s := fmt.Sprintf("%d", num)
_, found := m[s]
if bf.LookUp(Key(s)) && !found {
falsePositiveCount++
}
}
falsePositiveRate := float64(falsePositiveCount) / float64(testCount)
t.Logf("False positive rate: %f", falsePositiveRate)
if math.Abs(falsePositiveRate-expectedFalsePositiveRate) > 0.01 {
t.Errorf("False positive rate is too high")
}
}
func TestDataSetSize(t *testing.T) {
size := 100_0000
bf := NewBloomFilter[Key](uint32(size), 0.02)
t.Log(bf.m)
bf = NewBloomFilter[Key](uint32(size*100), 0.02)
t.Log(bf.m)
bf = NewBloomFilter[Key](uint32(size/100), 0.02)
t.Log(bf.m)
}