Roaring Bitmap 内部剖析：从 16 位分块、Array/Bitmap/Run 三态容器到列式引擎的高速集合运算

x = (high << 16) | low       # high = x >> 16，low = x & 0xFFFF
# 高 16 位决定"分块 key"，低 16 位决定"块内偏移"

import bisect

ARRAY_MAX = 4096   # Array 容器上限，超过自动转 Bitmap

class ArrayContainer:
    """排序 uint16 数组，适合稀疏分块。"""
    __slots__ = ('vals',)
    def __init__(self):
        self.vals = []                       # 保持升序、无重复
    def add(self, v):
        i = bisect.bisect_left(self.vals, v)
        if i == len(self.vals) or self.vals[i] != v:
            self.vals.insert(i, v)
    def iter(self):
        return iter(self.vals)
    def cardinality(self):
        return len(self.vals)

class BitmapContainer:
    """8192 字节定长位图，适合稠密分块。"""
    __slots__ = ('bits', 'card')
    def __init__(self):
        self.bits = bytearray(8192)          # 2**16 / 8
        self.card = 0
    def add(self, v):
        byte = v >> 3
        mask = 1 << (v & 7)
        if not (self.bits[byte] & mask):
            self.bits[byte] |= mask
            self.card += 1
    def iter(self):
        for i in range(65536):
            if self.bits[i >> 3] & (1 << (i & 7)):
                yield i
    def cardinality(self):
        return self.card

def _to_bitmap(c):
    if isinstance(c, BitmapContainer):
        return c
    nb = BitmapContainer()
    for v in c.iter():
        nb.add(v)
    return nb

class RoaringBitmap:
    def __init__(self):
        self.containers = {}                 # high16 -> Container
    def add(self, x):
        hi = (x >> 16) & 0xFFFF
        lo = x & 0xFFFF
        c = self.containers.get(hi)
        if c is None:
            c = ArrayContainer()
            self.containers[hi] = c
        c.add(lo)
        if isinstance(c, ArrayContainer) and c.cardinality() > ARRAY_MAX:
            self.containers[hi] = _to_bitmap(c)   # Array -> Bitmap 升级
    def cardinality(self):
        return sum(c.cardinality() for c in self.containers.values())
    def union(self, other):
        res = RoaringBitmap()
        for hi in set(self.containers) | set(other.containers):
            a, b = self.containers.get(hi), other.containers.get(hi)
            if a and b:
                res.containers[hi] = _union(a, b)
            else:
                res.containers[hi] = a or b
        return res
    def intersection(self, other):
        res = RoaringBitmap()
        for hi in set(self.containers) & set(other.containers):
            c = _intersect(self.containers[hi], other.containers[hi])
            if c is not None:
                res.containers[hi] = c
        return res

def _union(a, b):
    if isinstance(a, ArrayContainer) and isinstance(b, ArrayContainer):
        merged = sorted(set(a.vals) | set(b.vals))
        if len(merged) > ARRAY_MAX:
            r = _to_bitmap(a); 
            for v in b.vals: r.add(v)
            return r
        r = ArrayContainer(); r.vals = merged; return r
    ba, bb = _to_bitmap(a), _to_bitmap(b)
    res = BitmapContainer()
    for i in range(8192):
        res.bits[i] = ba.bits[i] | bb.bits[i]
    res.card = sum(bin(x).count('1') for x in res.bits)
    return res

def _intersect(a, b):
    if isinstance(a, ArrayContainer) and isinstance(b, ArrayContainer):
        sa = set(a.vals)
        inter = [v for v in b.vals if v in sa]
        if not inter:
            return None
        r = ArrayContainer(); r.vals = inter; return r
    ba, bb = _to_bitmap(a), _to_bitmap(b)
    res = BitmapContainer(); card = 0
    for i in range(8192):
        x = ba.bits[i] & bb.bits[i]
        res.bits[i] = x
        card += bin(x).count('1')
    if card == 0:
        return None
    res.card = card
    return res

if __name__ == '__main__':
    A, B = RoaringBitmap(), RoaringBitmap()
    for x in range(0, 10000, 3): A.add(x)     # 3 的倍数，约 3333 个
    for x in range(0, 10000, 5): B.add(x)     # 5 的倍数，约 2000 个
    print("|A|      =", A.cardinality())      # 3334
    print("|B|      =", B.cardinality())      # 2000
    print("|A ∪ B|  =", A.union(B).cardinality())
    print("|A ∩ B|  =", A.intersection(B).cardinality())  # 15 的倍数