-
Notifications
You must be signed in to change notification settings - Fork 5
/
bloomFilter_test.go
109 lines (87 loc) · 1.99 KB
/
bloomFilter_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
109
package go_blooms
import (
"hash"
"hash/fnv"
"math/rand"
"sort"
"testing"
"github.com/spaolacci/murmur3"
)
// 100 Million
var memberSize uint = 100000000
// 100 Thousand
var sampleSize int = 100000
// Test items if items may exist into set
func TestExistance(t *testing.T) {
bf := New(memberSize, DefaultHashFunctions)
for i := 0; i < sampleSize; i++ {
item := randomBytes(10)
bf.Add(item)
if bf.Test(item) != true {
t.Errorf("'%q' not found", item)
}
// Now lets create some items that don't exist
item2 := append(item, randomBytes(10)...)
// Test that item does NOT exist
if bf.Test(item2) == true {
t.Errorf("'%q' should not be found", item2)
}
}
}
func BenchmarkAdd(b *testing.B) {
bf := New(memberSize, DefaultHashFunctions)
for i := 0; i < b.N; i++ {
bf.Add(randomBytes(10))
}
}
func BenchmarkTest(b *testing.B) {
bf := New(memberSize, DefaultHashFunctions)
for i := 0; i < b.N; i++ {
bf.Add(randomBytes(10))
}
b.ResetTimer()
for i := 0; i < b.N; i++ {
bf.Test(randomBytes(10))
}
}
// Compare with a binary sort to make sure we're in the same ballpark
func BenchmarkBinarySearch(b *testing.B) {
var strings []string
for i := 0; i < sampleSize; i++ {
item := randomString()
strings = append(strings, item)
}
// Sort by byte order
sort.Strings(strings)
b.ResetTimer()
for i := 0; i < b.N; i++ {
item := randomString()
use(sort.SearchStrings(strings, item))
}
}
func BenchmarkHashFunctions(b *testing.B) {
item := []byte("hello world, how are you doing?")
hashFns := map[string]hash.Hash64{
"murmur3": murmur3.New64(),
"fnv64": fnv.New64(),
"fnv64a": fnv.New64a(),
}
for name, hashFunc := range hashFns {
b.Run(name, func(b *testing.B) {
for i := 0; i < b.N; i++ {
hashFunc.Write(item)
use(hashFunc.Sum64())
hashFunc.Reset()
}
})
}
}
func use(interface{}) {}
func randomBytes(size int) []byte {
b := make([]byte, size)
rand.Read(b)
return b
}
func randomString() string {
return string(randomBytes(10))
}