data structure

Bitmap

General Storage Question

• give 4,000,000,000 numbers, each range in 1-2^31 -> int type, unsigned, 4 Bytes
• 4,000,000,000 *4 /1024(KB) /1024(MB) /1024(GB) = 14.901G

With Bitmap

• 1B = 8 bits
• 1MB = 8 1024 1024 = 8,388,608
• 4,000,000,000 / 8,388,608 = 476.837MB
• BitMap的存储与取值时间复杂度为O(1)，根据数值可直接映射下标。
• BitMap占用内存空间复杂度为O(n)，与集合中元素的最大值正相关，不是集合中元素的数量。
• Space size is matters with the max value, as even only has one number as 4,000,000,000, still need 476MB space, as only 4bil position is 1, all rest are 0s.

Roaring Bitmap

• Base on Bitmap
• 用于解决空间复杂度
• 将32位的数字，拆分为高位和低位，高位用于确定容器/桶（Container），低位用于确认位置（Position）
• 实际是一个分置的思想，不存在元素的容器/桶，不进行初始化

• 举例：

  • 31 = 0x1F =0000 001F
  • 高位：0000 -> Container 0
  • 低位：001F -> 31位置
  • 310000 = 0x4BAF0 = 0004 BAF0
  • 高位：0004 -> Container 4
  • 低位：BAF0 -> 47856 位置

• 为了进一步压缩空间，Container的类型分为Array，Bitmap，Run

  • ArrayConatiner：当元素最大位置< 4096时，使用Array，unsigned short类型
  • BitmapContainer：当元素最大位置> 4096，使用bitmap，unsigned long类型，最大65535
  • RunContainer：当元素大量存在连续情况，通过特定算法压缩存储空间，需要自定义实现AC/BC转换RC的逻辑
• 关于4096
  

‍

本文由 Ivan Dong 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jun 13, 2023 at 10:15 am