BitMap 算法
引导
如果我们现在有一堆数据,[0 ,3 ,4 ,7 ,9 ,1 ,2 ,5 ,6 ,8 ,2 ,3 ,5 ,7 ,9 ,0 ,1 ,4 ,6 ,8],需要对数据进行排重,只留下最原始的数据。
那么我们可以用如下方式实现：
package main
import (
"fmt"
)
func main() {
//获取到一个数组
nums := []int{0, 3, 4, 7, 9, 1, 2, 5, 6, 8, 2, 3, 5, 7, 9, 0, 1, 4, 6, 8}
//获取一个排重数组
numMap := map[int]bool{}
//排重后的结果
newNums := []int{}
for _, num := range nums {
_, ok := numMap[num]
if ok { //已经存在了
continue
}
//记录重复状态
numMap[num] = true
newNums = append(newNums, num)
}
fmt.Println("排除重复前：", nums)
fmt.Println("排除重复后：", newNums)
//排除重复前： [0 3 4 7 9 1 2 5 6 8 2 3 5 7 9 0 1 4 6 8]
//排除重复后： [0 3 4 7 9 1 2 5 6 8]
}
流程如下
1 . 实例化一个map，存储标记。
image
2 . 如果数据存在，则改变状态。
3 . 不存在的数据，就加入到新的数组中。
4 . 排序完成。
不知小伙伴绝不觉得和计数排序的逻辑很像。当然优化方案也可以按照计数排序的方式。
缺点分析
针对数据量大的数据，我们需求的map就会很大。这样占用的空间特别高。所以针对这种情况我们需要一种替代方案来完成，海量数据排重操作。
BitMap
所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省
其实如果你知道计数排序的话，你就会发现这个和计数排序很像。
bitmap应用
- 可进行数据的快速查找，判重，删除。
- 去重数据而达到压缩数据.
目前bitmap在数据采集【大数据-爬虫】环节非常有用，比如对url去重。
bitmap 实现
package bitmap
import (
"bytes"
"sync"
)
type Bit uint64 //统一bit类型
const BitSize = 64 //每一个bit位存储数据量
const IndexBit = 6 //位置位移数量
type Bitmap []Bit //bitmap
var mux = sync.Mutex{}
var bitsMap [BitSize]Bit
//func init() {
// for i := 0; i < BitSize; i++ {
// bitsMap[i] = Bit(0x01) << Bit(i)
// }
//}
//设置bit
func (b *Bitmap) SetBit(value Bit, stat bool) *Bitmap {
mux.Lock()
defer mux.Unlock()
index, pos := b.ValueToIndexAndPos(value)
if stat {
b.UpCapToIndex(index)
//设置
(*b)[index] |= Bit(0x01) << pos
} else {
//取消
if index < len(*b) {
(*b)[index] &^= Bit(0x01) << pos
}
}
return b
}
func (b *Bitmap) Set(value Bit) *Bitmap {
b.SetBit(value, true)
return b
}
func (b *Bitmap) Unset(value Bit) *Bitmap {
b.SetBit(value, false)
return b
}
func (b *Bitmap) Get(value Bit) bool {
index, pos := b.ValueToIndexAndPos(value)
//(*b)[index] &^= Bit(0x01) << pos
return index < len(*b) && ((*b)[index]&(Bit(0x01)<<pos) != 0)
}
func (b *Bitmap) ValueToIndexAndPos(value Bit) (int, Bit) {
return int(value >> IndexBit), value % Bit(BitSize)
}
func (b *Bitmap) UpCapToIndex(index int) {
toIndex := index + 1
l := len(*b)
if l < toIndex {
l2 := 2 * l
if toIndex < l2 {
toIndex = l2
}
n := make([]Bit, toIndex, toIndex)
copy(n, *b)
*b = n
}
}
func (b *Bitmap) ToString(split ...string) string {
l := len(*b)
sl := len(split)
ss := ""
if sl > 0 {
ss = split[0]
}
str := ""
for i := 0; i < l; i++ {
if i > 0 && sl > 0 {
str += ss
}
str += (*b)[i].ToString()
}
return str
}
func (bit *Bit) ToString() string {
b := &bytes.Buffer{}
t := *bit
for i := 0; i < BitSize; i++ {
if (t & bitsMap[i]) != 0 {
b.WriteString("1")
} else {
b.WriteString("0")
}
}
return b.String()
}
关键技能解析
位运算
为了更好描述效果，这里我们使用较小的数据类型： byte ，一个byte包含8bit位。
package main
import (
"fmt"
"github.com/imroc/biu"
)
func main() {
var b byte
b = 1
fmt.Println("常规展示：", b) // 原始数据: 1
fmt.Println("二进制位：", biu.ByteToBinaryString(b)) //二进制方式：00000001
//向左移动一位
b = b << 1
fmt.Println("左边移动一位：", b) // 原始数据: 2
fmt.Println("二进制位：", biu.ByteToBinaryString(b)) //二进制方式：00000010
var b1 byte = 3
fmt.Println("b1=：", b1) // 原始数据: 3
fmt.Println("二进制位：", biu.ByteToBinaryString(b1)) //二进制方式：00000011
// 或（|） 运算: 二进制位中对应位置有1则为1，否则为0。
// 2 的二进制为： 10 ， 3 的二进制为： 11
// 那么 2|3 = 11
fmt.Println("（2|3）二进制位：", biu.ByteToBinaryString(2|3)) //二进制方式：00000011
// 与（&） 运算: 二进制位中对应位置都为1则为1，否则为0。
// 2 的二进制为： 10 ， 3 的二进制为： 11
// 那么 2&3 = 10
fmt.Println("（2&3）二进制位：", biu.ByteToBinaryString(2&3)) //二进制方式：00000010
//异或（^）运算： 二进制中对应位置不同的为1，否则为0.
// 2 的二进制为： 10 ， 3 的二进制为： 11
// 那么 2^3 = 01
fmt.Println("（2^3）二进制位：", biu.ByteToBinaryString(2^3)) //二进制方式：00000001
var c = byte(2)
//取反（^）:二进制中的所有位置 0 为1,1为 0.
fmt.Println("（^2）常规输出：", ^c) //二进制方式：253
fmt.Println("（^2）二进制位：", biu.ByteToBinaryString(^c)) //二进制方式：11111101
}
Bitmap使用
bm := &bitmap.Bitmap{} //实例化bitmap
bm.SetBit(100, true) //设置位置100
bm.SetBit(12, true)
bm.SetBit(1, true)
bm.SetBit(12, true) //设置位置12
//获取状态
fmt.Println("bit:100：",bm.Get(100)) //true
fmt.Println("bit:12：",bm.Get(12)) //true
//取消设置
bm.SetBit(12, false)
fmt.Println("bit:12：",bm.Get(12)) //false
长按二维码关注我们
网友评论