咆哮位图
roaringbitmap的Python项目详细描述
咆哮位图是存储集合的有效压缩数据结构 整数的。轰鸣的位图将一组32位整数存储在一系列 数组和位图，以占用空间最少的为准 2 ** 16位或更少）。
此数据结构对于存储大量整数非常有用，例如 搜索引擎和数据库使用的反向索引。尤其是 可以快速计算一系列集合的交集，可以是 用于将查询实现为子查询的连接。
此实现基于 https://github.com/lemire/RoaringBitmap 以及https://github.com/lemire/CRoaring
此实现的其他功能：
- 倒排列表表示：存储大部分已满的块 紧凑地作为非成员数组（而不是作为成员数组或 固定大小位图）。
- 可以使用 mmap在单个文件中。
缺少w.r.t.croaring功能：
- 运行长度编码块
- 各种AVX2/SSE优化
另请参见pyroaringbitmap，一个croaring的python包装： https://github.com/Ezibenroc/PyRoaringBitMap
许可证，要求
该代码是在gnu gpl v2或任何更高版本下授权的。
- python 2.7+/3.3+http://www.python.org（需要标题，例如python dev包）
- cython 0.20+http://www.cython.org
安装、使用
$ git clone https://github.com/andreasvc/roaringbitmap.git $ cd roaringbitmap $ make
（或者make py2对于python 2）
可以使用RoaringBitmap()替换普通的（可变的） 包含（无符号）32位整数的python集：
>>>fromroaringbitmapimportRoaringBitmap>>>RoaringBitmap(range(10))&RoaringBitmap(range(5,15))RoaringBitmap({5,6,7,8,9})
ImmutableRoaringBitmap是不可变的变量（类似于frozenset） 它作为一个连续的内存块紧凑地存储。
一系列不变的roaringbitmap可以存储在一个文件中，并且 使用mmap有效访问，无需复制或反序列化：
>>>fromroaringbitmapimportMultiRoaringBitmap>>>mrb=MultiRoaringBitmap([range(n,n+5)forninrange(10)],filename='index')>>>mrb=MultiRoaringBitmap.fromfile('index')>>>mrb[5]ImmutableRoaringBitmap({5,6,7,8,9})
用于API文档cf.http://roaringbitmap.readthedocs.io
基准
输出$ make bench：
small sparse set
100 runs with sets of 200 random elements n s.t. 0 <= n < 40000
set() RoaringBitmap() ratio
init 0.000834 0.00138 0.603
initsort 0.00085 0.000394 2.16
and 0.00102 8.49e-05 12.1
or 0.00171 0.000169 10.1
xor 0.00152 0.000213 7.11
sub 0.000934 0.000197 4.74
iand 1.29e-05 2.97e-06 4.35
ior 9.7e-06 3.26e-06 2.98
ixor 8.98e-06 3.43e-06 2.62
isub 6.83e-06 3.3e-06 2.07
eq 0.000438 1.17e-05 37.6
neq 6.37e-06 7.81e-06 0.816
jaccard 0.0029 0.000126 23.1
medium load factor
100 runs with sets of 59392 random elements n s.t. 0 <= n < 118784
set() RoaringBitmap() ratio
init 0.564 0.324 1.74
initsort 0.696 0.273 2.55
and 0.613 0.000418 1466
or 0.976 0.000292 3344
xor 0.955 0.000294 3250
sub 0.346 0.000316 1092
iand 0.00658 1.14e-05 575
ior 0.00594 1.08e-05 548
ixor 0.00434 1.12e-05 385
isub 0.00431 1.09e-05 397
eq 0.0991 0.000116 851
neq 9.62e-06 1.29e-05 0.743
jaccard 1.62 0.00025 6476
dense set / high load factor
100 runs with sets of 39800 random elements n s.t. 0 <= n < 40000
set() RoaringBitmap() ratio
init 0.33 0.0775 4.26
initsort 0.352 0.148 2.38
and 0.24 0.000223 1078
or 0.45 0.000165 2734
xor 0.404 0.000161 2514
sub 0.169 0.000173 973
iand 0.00287 6.02e-06 477
ior 0.00179 6.34e-06 282
ixor 0.00195 5.53e-06 353
isub 0.0017 6.35e-06 267
eq 0.0486 4.65e-05 1045
neq 1.01e-05 1.13e-05 0.888
jaccard 0.722 0.000118 6136
有关性能比较，请参见https://github.com/Ezibenroc/roaring_analysis/ 和这个图书馆。
参考文献
- http://roaringbitmap.org/
- Chambi，S.，Lemire，D.，Kaser，O.，和Godin，R.（2016年）。更好的位图 用咆哮的位图来表演。软件：实践与经验，46（5）， 第709-719页。http://arxiv.org/abs/1402.6407
- 使用倒排列表表示的思想基于 https://issues.apache.org/jira/browse/LUCENE-5983
欢迎加入QQ群-->： 979659372
