Metadata-Version: 1.1
Name: roaringbitmap
Version: 0.1
Summary: Roaring Bitmap
Home-page: https://github.com/andreasvc/roaringbitmap/
Author: Andreas van Cranenburgh
Author-email: A.W.vanCranenburgh@uva.nl
License: UNKNOWN
Description: Roaring Bitmap in Cython
        ========================
        
        A roaring bitmap is an efficient compressed datastructure to store a set
        of integers. A Roaring bitmap stores a set of 32-bit integers in a series of
        arrays and bitmaps, whichever takes the least space (which is always
        ``2 ** 16`` bits or less).
        
        This datastructure is useful for storing a large number of integers, e.g., for
        an inverted index used in search indexes and databases. In particular, it is
        possible to quickly compute the intersection of a series of sets, which can be
        used to implement a query as the conjunction of subqueries.
        
        This implementation is mostly a translation from the Java implementation at
        https://github.com/lemire/RoaringBitmap
        
        An additional feature of this implementation is that it uses arrays not only
        when a block contains less than ``2 ** 12`` elements, but also when it contains
        more than ``2 ** 32 - 2 ** 12`` elements; i.e., blocks that are mostly full are
        stored just as compactly as blocks that are mostly empty. Other blocks are
        encoded as bitmaps of fixed size. This trick is based on the implementation in
        Lucene, cf. https://issues.apache.org/jira/browse/LUCENE-5983
        
        Requirements
        ------------
        - Python 2.7+/3   http://www.python.org (headers required, e.g. python-dev package)
        - Cython 0.20+    http://www.cython.org
        
        Installation
        ------------
        ``$ make``
        
        Usage
        -----
        A ``RoaringBitmap()`` can be used as a replacement for a normal (mutable)
        Python set containing (unsigned) 32-bit integers::
        
            >>> from roaringbitmap import RoaringBitmap
            >>> RoaringBitmap(range(10)) & RoaringBitmap(range(5, 15))
            RoaringBitmap({5, 6, 7, 8, 9})
        
        Benchmarks
        ----------
        Output of ``$ python benchmarks.py``::
        
            sparse set
            100 runs with sets of 200 random elements n s.t. 0 <= n < 40000
                        set()  RoaringBitmap()    ratio
            init      0.00217          0.00941    0.231
            and       0.00116         0.000166     6.97
            or        0.00189         0.000255     7.42
            xor       0.00171         0.000231      7.4
            sub       0.00104         0.000166     6.26
            eq       0.000513         0.000487     1.05
            neq      9.06e-06          3.7e-05    0.245
        
            dense set / high load factor
            100 runs with sets of 39800 random elements n s.t. 0 <= n < 40000
                        set()  RoaringBitmap()    ratio
            init        0.294             1.16    0.252
            and         0.217         0.000246      883
            or          0.427         0.000262     1628
            xor         0.391          0.00024     1629
            sub          0.16         0.000234      682
            eq         0.0569          0.00741     7.67
            neq      8.82e-06         4.51e-05    0.196
        
            medium load factor
            100 runs with sets of 59392 random elements n s.t. 0 <= n < 118784
                        set()  RoaringBitmap()    ratio
            init        0.481             1.96    0.246
            and           0.6         0.000478     1255
            or          0.964         0.000478     2015
            xor         0.862         0.000487     1769
            sub         0.341         0.000485      703
            eq          0.116            0.017     6.83
            neq      1.22e-05         4.98e-05    0.244
        
        References
        ----------
        Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin (2014),
        Better bitmap performance with Roaring bitmaps,
        http://arxiv.org/abs/1402.6407
        
        - http://roaringbitmap.org/
        - https://github.com/lemire/RoaringBitmap
        - https://issues.apache.org/jira/browse/LUCENE-5983
        
Platform: UNKNOWN
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: GNU General Public License (GPL)
Classifier: Operating System :: POSIX
Classifier: Programming Language :: Python :: 2.7
Classifier: Programming Language :: Python :: 3.3
Classifier: Programming Language :: Cython
Requires: cython (>=0.20)
