参考:
一、背景:
首先,明确两点:
- QQ号是 unsigned int 类型(4字节无符号整数,共32bit), 也就是说 QQ号的取值范围是:[0,2³²−1]。
- QQ号是一个长度为10位的整数,大约是43亿,这也是QQ号码的理论最大值。
- QQ号码的最小值是 10001, 为什么tx要做这种限制呢?仅仅是早期的一个设定而已。
二、43亿QQ号所占内存大小计算:
其次,43亿QQ号所占内存大小是多少呢?512M!
- 一个 unsigned int 类型数据可以标识 0 ~ 31 这32个整数的存在与否(4Byte,0 ~ 31 )
- 两个 unsigned int 类型数据可以标识 0 ~ 64 这64个整数的存在与否(8Byte,0 ~ 64 )
又因为QQ号是 unsigned int 类型(无符号整数,4Byte,32位),也就是说 QQ号的取值范围是:[0,2³²−1]。
因此可对 2³² 次方范围内的QQ号所占大小进行推导:
- 1Byte所能标识数的范围为0~7(1字节,8 位)
- 4Byte所能标识数的范围为0~31(4字节,32 位)
- ...
- 那么多少Byte才能够标识 数的范围为 0 ~ 2³²-1(2³² 位)呢?
综上,用 2³² / 32 来表示:0 ~ 2³²-1(2³² 位)
能包含多少个 0 ~ 31(32位)
范围的块。并且每个 0 ~ 31(32位)
的块儿大小为4字节,因此 2³² / 32 × 4字节 的结果就是 0 ~ 2³²-1 范围所占字节的总大小,也就是 43亿 QQ号所占字节总大小。
2³²位 / 32位 × 4字节 / 1024 / 1024 = 512M(1M=1024KB,1KB=1024Byte)
由此可见,512M的内存大小,就可以用来标识所有QQ号的存在与否。
三、bitmap的具体实现:
- 把所有 bitMap 位数组依次拼接后可表示 0 ~ 2³² 范围内43亿的数,所以足够存储40亿不重复的账号了
- bitmap数组中的一个uint32类型元素,由4字节组成(每个字节占8位):
{[8位][8位][8位][8位]}
{[8位][8位][8位][8位]}
{[8位][8位][8位][8位]}
{[8位][8位][8位][8位]}
... - 如:
[0 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]
...[...]
[...]
[...]
[... 40亿]
- 共需 40亿/8位 = 5亿字节,5亿字节/4字节 = 1.25亿 个uint32类型元素数组来串联拼接表示(uint32类型大小占4字节),所占内存大小为:4000000000/8/1024/1024 ≈ 477M
- 还原qq号(数组下标从0开始):当前第block块数 * 每个uint32 block块的固定大小为32 + 当前block块内的偏移量余数 yushu
- 每次新增QQ号时,都只需要在 bitMap[block] 的结果基础上继续进行异或 ^ 运算即可 ~
- 比如原本"QQ号=9(二进制表示
1 0000 0000
,位下标为 9)"是有值的,现在又新增了"qq号=10(二进制表示10 0000 0000
,位下标为 10)" - 那么9和10相异或后得:
1
0000 0000 ^1
0 0000 0000 =11
0000 0000,表示第 9 位和第 10 位的QQ号都有值了 - 0x1<<(yuShu-1):比如原本"QQ号=9"时,那就把 0x1 左移8位,即:0x1 << 8,得到
1
00000000,最后从右至左第9位为1 - 关键代码:bitMap[block] = bitMap[block] ^ (0x1 << (yuShu - 1)) // 设置标记位:在之前bitMap已有结果的基础上,设置第block块上的第 "(0x1 << (yuShu - 1))" bit位为1
// 把所有位数组依次拼接后可表示 0~2³² 范围内的数,所以足够存储40亿不重复的账号了
// bitmap数组中的一个uint32类型元素,由4字节组成(每个字节占8位):{[8位][8位][8位][8位]} {[8位][8位][8位][8位]} {[8位][8位][8位][8位]} {[8位][8位][8位][8位]} ...
// 如:[0 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] ... [...][...][...][... 40亿]
// 共需 40亿/8bit = 5亿byte,5亿byte/4byte = 1.25亿个uint32类型元素数组来串联表示(uint32类型大小占4字节),所占内存大小为:4000000000/8/1024/1024≈477M
// 还原qq号(数组下标从0开始):当前第block块数 * 每个block块的固定大小32 + 当前block块内的偏移量余数yushu
// 每次新增QQ号时,都只需要在bitMap[block]的结果上继续进行异或^运算即可~
// 比如原本"QQ号=9(二进制表示 1 0000 0000,位下标为9)"是有值的,现在又新增了"qq号=10(二进制表示 10 0000 0000,位下标为10)"
// 那么相异或后得: 1 0000 0000 ^ 10 0000 0000 = 11 0000 0000,表示第9位和第10位的QQ号都有值了
// 0x1<<(yuShu-1):比如原本"QQ号=9"时,那就把0x1左移8位,即:0x1 << 8,得到 100000000,从右至左第9位为1
// 根据QQ号来设置其在bitMap中bit位
func BitCalculation(bitMap []uint32, everyBlockSize, qq uint32) {
// 判断是属于第几块的第几个bit位
block := qq / everyBlockSize // 块数:第block块(bitmap数组从第0块开始,无需根据yuShu是否为0来判断block是否+1)
yuShu := qq % everyBlockSize // 余数:第block块中的具体第几个bit位
// fmt.Printf("block=%v, yuShu=%v \n", block, yuShu)
fmt.Printf("在对%v(%b)位运算设置标记位1之前,bitMap的第%v块上二进制表示: %b\n", qq, 0x1<<(yuShu-1), block, bitMap[block])
bitMap[block] = bitMap[block] ^ (0x1 << (yuShu - 1)) // 设置标记位:在之前bitMap已有结果的基础上,设置第block块上的第 "(0x1 << (yuShu - 1))" bit位为1
fmt.Printf("在对%v(%b)位运算设置标记位1之后,bitMap的第%v块上二进制表示: %b,还原qq号为: %v\n\n", qq, 0x1<<(yuShu-1), block, bitMap[block], block*everyBlockSize+yuShu)
}
// 初始化相关参数
func TestBit(qqCnt uint32, qqArr []uint32) {
var everyBlockSize uint32 = 4 * 8 // uint32类型占32位:一个uint32能标记0~31范围内32个QQ号
blockCnt := qqCnt / everyBlockSize // 40亿QQ号所需uint32类型的块数
bitMap := make([]uint32, blockCnt) // 存储40亿QQ号的bitmap,统一初始化为0
// fmt.Println("blockCnt 40亿QQ号所需uint32类型的块数: ", blockCnt) // 1.25亿块
for i := 0; i < len(qqArr); i++ {
// 设置每个测试QQ到bitMap中
BitCalculation(bitMap, everyBlockSize, qqArr[i])
}
}
func main() {
// 以下均默认在64位操作系统下执行:
// i := int(1) // int在64位系统下默认大小为8,即:int64
// fmt.Println(unsafe.Sizeof(i)) // 8
//
// j := int32(1)
// fmt.Println(unsafe.Sizeof(j)) // 4
//
// k := int64(1)
// fmt.Println(unsafe.Sizeof(k)) // 8 相当于long/double类型,占8字节(64位) 最大能表示范围为:2⁶⁴
//
// ll := float64(1)
// fmt.Println(unsafe.Sizeof(ll))
// int32 表示范围: -2147483648 ~ 2147483647,因为账号数有40亿个,所以采用无符号类型 uint32 类型,表示范围: 0 ~ 4294967295
var qqAccountCnt uint32 = 4000000000
testNumArr := []uint32{9, 399999999, 1234567890} // test data
TestBit(qqAccountCnt, testNumArr)
return
}
AI 代码解读
示例结果展示:
四、扩展
练习一: 文件中有40亿个互不相同的QQ号码,请设计算法对QQ号码进行排序,内存限制1G。
很显然,直接用bitmap,
标记这40亿个QQ号码的存在性,然后从小到大遍历正整数,当bitmapFlag的值为1时,就输出该值,输出后的正整数序列就是排序后的结果。
请注意,这里必须限制40亿个QQ号码互不相同。通过bitmap记录,客观上就自动完成了排序功能。练习二:文件中有40亿个互不相同的QQ号码,求这些QQ号码的中位数,内存限制1G。
一些刷题经验丰富的人,最开始想到的肯定是用堆或者文件切割,这明显是犯了本本主义错误。直接用bitmap排序,当场搞定中位数。练习三:文件中有40亿个互不相同的QQ号码,求这些QQ号码的topK,内存限制1G。
很多人背诵过topK问题,信心满满,想到用小顶堆或者文件切割,这明显又是犯了本本主义错误。直接用bitmap排序,当场搞定topK问题。练习四:文件中有80亿个QQ号码,试判断其中是否存在相同的QQ号码,内存限制1G。
一些吸取了经验教训的人肯定说,直接bitmap啊。然而,又一次错了。根据容斥原理可知:
因为QQ号码的个数是43亿左右(理论值2^32 - 1),所以80亿个QQ号码必然存在相同的QQ号码。
五、总结:
- QQ号理论上的范围为:10001 - 43亿(2³²),其类型为
unsigned int
- 43亿QQ号所占内存大小,经计算后大约占 512M (满足小于1G的要求)
- 40亿QQ号所占内存大小,经计算后大约占 477M (满足小于1G的要求)
- bitMap实现方案 及 异或 ^ 等位运算
- 利用 bitMap 来处理海量数据问题,内存占用低,满足要求且可以取得不错的效果。包括:排序、中位数、topK、去重 等等...