之前写了一个100W条记录中查找特定数据的性能测试,和遍历算法做了比较,二分法性能强很多.
今天我用二分法和bitmap数据结构存储来比较下:
场景一:
在200W条手机号码记录中查找特定手机号码的记录需要花费的时间:
可以看到查找手机号码: 19998600000,两种算法所用的时间差距还是比较明显的,
bitmap强于二分法,效率大概是7倍,效果也比较明显,bitmap属于使用空间换时间,因此bitmap所要占用的内存空间会更大,需要事先根据数据量和存储的数据大小来申请存储空间,对于两种算法的取舍还是要基于当前的业务场景
大家如果有更好的想法,欢迎交流学习!!!!!
下面就是go实现的bitmap算法的主要代码:
type BitMap []byte
func NewBitMap(max int) BitMap {
return make([]byte, (max>>3) 1)
}
func (b BitMap) Set(n uint) {
if (n >> 3) > uint(len(b)) {
fmt.Println("数字太大超过最大存放范围")
return
}
index := n >> 3
pos := n & 0x07
b[index] = b[index] | 1<<pos
}
func (b BitMap) Get(n uint) bool {
if (n >> 3) > uint(len(b)) {
fmt.Println("数字太大超过最大存放范围")
return false
}
index := n >> 3
pos := n & 0x07
return b[index]&(1<<pos) != 0
}
,
