Sorted containers with state-of-the-art query performance and compressed memory usage
Project description
PyGM is a Python library that enables fast query operations on sorted lists of numbers (like integers and floats) with a tiny memory overhead. Internally, it features the PGM-index, a state-of-the-art learned data structure that robustly scales to billions of elements in just a few tens of megabytes.
Quick start
Install with pip:
pip install pygm
PyGM supports both standard and other useful list and set operations:
>>> from pygm import SortedList, SortedSet
>>> sl = SortedList([0, 1, 34, 144, 1, 55, 233, 2, 3, 21, 89, 5, 8, 13])
>>> sl
SortedList([0, 1, 1, ..., 144, 233])
>>> sl.find_gt(9) # smallest element > 9
13
>>> sl.count(1) # frequency of 1
2
>>> 42 in sl # membership test
False
>>> list(sl.range(0, 21, inclusive=(False, True))) # elements 0 < x <= 21
[1, 1, 2, 3, 5, 8, 13, 21]
>>> sl[2:10:3] # slicing syntax support
SortedList([1, 5, 21])
>>> (sl + [-3, -2, -1]).rank(0) # number of elements <= 0
4
>>> ss = SortedSet([1, 2, 3, 4]) ^ {3, 4, 5} # set symmetric difference
>>> ss.find_lt(5)
2
The full documentation is available online and in the Python interpreter via the help()
built-in function.
Installation
PyGM is compatible with Python 3.3+. The easiest way to install it is through PyPI:
pip install pygm
Otherwise, you can clone the repo, build it from source and install it as follows:
if [[ "$(uname)" == "Darwin" ]]; then brew install libomp; fi
git clone https://github.com/gvinciguerra/PyGM.git
cd PyGM
git submodule update --init --recursive
pip install .
Remember to leave the source directory PyGM/
and its parent before running Python.
Performance
Here are some plots that compare the performance of PyGM with two popular libraries, sortedcontainers and blist, on synthetic data.
All the graphs are log-log and show, for increasing data sizes, the average time it takes to perform each operation (lower is better). In particular, the __init__
plot shows the construction time, __contains__
measures membership queries, and __getitem__
shows the cost of accessing an element given its position.
The interesting operations on sorted lists are: (i) index
, which returns the position of the first occurrence of a given element; (ii) count
, which returns the number of occurrences of a given element; (iii) bisect_left
, which returns the insertion point for a given value in the list to maintain the sorted order (and is used to implement find_[ge|gt|le|lt]
).
You can run and plot the experiments on your computer and your data with the notebook in tests/benchmark.ipynb.
License
This project is licensed under the terms of the Apache License 2.0.
If you use the library in an academic setting, please cite the following paper:
Paolo Ferragina and Giorgio Vinciguerra. The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds. PVLDB, 13(8): 1162-1175, 2020.
@article{Ferragina:2020pgm,
Author = {Paolo Ferragina and Giorgio Vinciguerra},
Title = {The {PGM-index}: a fully-dynamic compressed learned index with provable worst-case bounds},
Year = {2020},
Volume = {13},
Number = {8},
Pages = {1162--1175},
Doi = {10.14778/3389133.3389135},
Url = {https://pgm.di.unipi.it},
Issn = {2150-8097},
Journal = {{PVLDB}}}
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for pygm-1.0.1-pp310-pypy310_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | be5158f5bf1e3e5f310515e211fef81a2acce65974286d9222bff5b1b564022f |
|
MD5 | 1c4449d3076d8718e4a243c1077d81e4 |
|
BLAKE2b-256 | 5bd33f97848752e2549334b7c76e1e914eb5cafbb0fd3a47de2aa078b34aff0f |
Hashes for pygm-1.0.1-pp310-pypy310_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ffa552710c39edd80f32903814b42a77d82faea1ebbf40115f425a5f84f86cde |
|
MD5 | 0e4a356d294edaa5826a96c7bfe31627 |
|
BLAKE2b-256 | 5bc19f868f4e18efda793cdc03b3ce49809a1d513c6b7b79cfce78d5a62c6df6 |
Hashes for pygm-1.0.1-pp39-pypy39_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b75202b3f3bddd1adb6901bc7b41dc5616143b22d203ccc4a52febe178939564 |
|
MD5 | 562f36993da793ce4dea6c7a2d39a7ac |
|
BLAKE2b-256 | e0fddb86d45b1021744d5f01f6ac9df6348db7d875146332dff12f0e7cd57708 |
Hashes for pygm-1.0.1-pp39-pypy39_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bdb51c5feaa29eba0716ddaf8d861875ffa1db873d50304633795cac95c0efc2 |
|
MD5 | 115bcc2ae9f2d1370bcb1247b0150139 |
|
BLAKE2b-256 | 8de8e22de084575e00a70c43371cc404692e75c4a94e6946e3356cf75a145707 |
Hashes for pygm-1.0.1-pp38-pypy38_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d2bd4a07745e03d10e4705eda1bcd58f22b6c9bb9f4f4a44081e6fbf08aee83f |
|
MD5 | 1888882debcf6e464e9b8865361e2435 |
|
BLAKE2b-256 | c8ecba7b7cdf52dc087b780c116d3fc4f6650b45997ac1f2efe690dc0f1cf00c |
Hashes for pygm-1.0.1-pp38-pypy38_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5d96aff0cb4ce84a88a3238d6192cd15d4f1a63b8e4d06694a760b0189a6f839 |
|
MD5 | 75438f544746747ed10aeec75b4cfb90 |
|
BLAKE2b-256 | c3f7c12ed5b75a7b9644ec3a15d45b0223ad0f5c35dadb5ec762d111f7a1c4ec |
Hashes for pygm-1.0.1-pp37-pypy37_pp73-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0b115e475e30085ca11b610bd236a2b79d5cc3d700a65099cb6d5e21d2f9470d |
|
MD5 | 4769163c1ed391c834d25124cb268764 |
|
BLAKE2b-256 | 5d5c9b3145c8dad6d0219d6692e3c57f1fa1fc9abc04c8e9b8043aac12b0f53a |
Hashes for pygm-1.0.1-pp37-pypy37_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 57486ad757f0a969128a6e00ce3fe577e4f89a751a11400dc8a2fbcc5fb78f2a |
|
MD5 | 016eee6fb53ad5fecf6c6b1998429ace |
|
BLAKE2b-256 | 2d1e0b8659c821ef2250653b82ccbf4f62f969c05b867ca90a916df032cdcafb |
Hashes for pygm-1.0.1-cp312-cp312-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f8916dd43b5a88535058c4737524dee44aa5e6d0913ce921e706819db8aac5f6 |
|
MD5 | c3587044029d774221ebf5c1cb2dd372 |
|
BLAKE2b-256 | fa0ea4bdcf7bd5479d05ef95ac04bc84ceb35febdc8542d034e773cc8988fef9 |
Hashes for pygm-1.0.1-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3aa929a4971febe3ded4c8221d0c3986622eaa4f18d7f71cb7bf2cd1c2b5f2ef |
|
MD5 | 28dcb911019ff35ecf9200659a3c6f8f |
|
BLAKE2b-256 | 119c144c1b6f24e1c92eb996a2ba23905832ebf348232fc726eb23f07d9faeca |
Hashes for pygm-1.0.1-cp312-cp312-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ab26bfdbedf7a7a91bbc10f90468315c1b60dc4dd15874c0f59c8c9195c767fc |
|
MD5 | a426fee97e9a65dcbccb6d463632f89d |
|
BLAKE2b-256 | b7c71817f65ea973b60d7b666c1e7e1338c730171f84764f696993187655d51d |
Hashes for pygm-1.0.1-cp311-cp311-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | da22e2fc9efc93f347fc46813989618456569c8d94b10e03f4b29d9884ddb237 |
|
MD5 | 92b9069c89ab5dd916a44ce337fe57d8 |
|
BLAKE2b-256 | 6a9f74e55ec126b1aaac1d710c342efb09ccc4b965bbab3f1b580f21b4b1d10d |
Hashes for pygm-1.0.1-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4a086f4711b3fc5486797c23eb558e792f1b78456d4e53e08464e26649949166 |
|
MD5 | ab115ff4f3e8bf06408f339abe27d41b |
|
BLAKE2b-256 | 07636e6cb3b5d43e21f1a382d524102d35cfe1dfb8163a954f0d0061ad205abc |
Hashes for pygm-1.0.1-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 41bff772a9fc7f24e047ef7658bf084a8296c30f23742793dd9bfc02858f7e74 |
|
MD5 | 2a6f2087c9d8ce49519765cbb9148f35 |
|
BLAKE2b-256 | 84b3d6a27bb373881fed08efb6d091a00005b3460a91c39cc1d9de0be1810e77 |
Hashes for pygm-1.0.1-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bd121e65719129e3f40fb272005b46131fe591f58aa845e247ecdd555b99dd6b |
|
MD5 | 673d801f66d666d2ae9df6bf0ee04b92 |
|
BLAKE2b-256 | a040b38e05fb6e263fb96f83f14981e6676e3d6711c6e44a0bbff5932d01dbb0 |
Hashes for pygm-1.0.1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 37c258199288bb0cdf89ea24042cfa77c2a114df66ee1bd78910f0e1c47d7560 |
|
MD5 | 93764be2d504351a0feb65030456b287 |
|
BLAKE2b-256 | 3231e0427e5e8ecbc2c646778b72b0298d62cffe2a1abd32e077877ec112bfc7 |
Hashes for pygm-1.0.1-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d0dd7124e08ecf425c4384798d437eeda1365d9f3a61cbab155f20385af0ddb5 |
|
MD5 | dab54628cec8b9aa4aadf9c1b7ce2f76 |
|
BLAKE2b-256 | e237d725a4b4777d6dedb093b3e1d21a88d1fce4bdaeea650f0ab06ea9b8a6b9 |
Hashes for pygm-1.0.1-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c9d212aaddaee844dae6fe74c718bea139097193087ce957ee4ff50651c9512b |
|
MD5 | dd20e7d16092dc97963e431756c8e5a4 |
|
BLAKE2b-256 | 1f603ff91708d5c0a0d9dd52d991bd20666c3ef71a74212e51a22d799ec18e3a |
Hashes for pygm-1.0.1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3f03419add86af192e1d7626bf6692b211776a5e8cfc089fe558367da3dec453 |
|
MD5 | 0fd11e4a16c156b4a1c4fff77adf33e6 |
|
BLAKE2b-256 | fc115216d0ec21097195b1cd36223093c79d1b68e072bde2af920aee130ad744 |
Hashes for pygm-1.0.1-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5f04cfa63cb45a6664e8aef95c5bf31ed2975856e2a51d4be50d5e1038b7b58c |
|
MD5 | 9623f86613a355707ee9eb5eb75c7070 |
|
BLAKE2b-256 | 88cd4cca3eb6ffccf0d14a6ee82eb544a930acee72dc6ac1f753bf210853d5a1 |
Hashes for pygm-1.0.1-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5b73a5baa2340cceb0dfeadc564c0e986bdb97685d66888bd6733b9a55269062 |
|
MD5 | 4778ddb89223f9a8de96a1a16bdb1344 |
|
BLAKE2b-256 | 8050e7d06a9f506f8a3351aba47fe1be2f31e6c5148b1bb57dd35982c2c7dc94 |
Hashes for pygm-1.0.1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | da117ee43fd750fc298d301ef14a044dbf4872dd41ba5aeeb85d236ee23af218 |
|
MD5 | 4271a5db0e594e0b137ba34fff82e32d |
|
BLAKE2b-256 | a41fb7bdffafd0b78937298cd481f23c937e690eb75e31ee0c57262a2eb89d7b |
Hashes for pygm-1.0.1-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5d225d20aaa14e59cac14151c525ffef3cd98f46a511ba330fbab9247591836e |
|
MD5 | 9e7899c9a45db23bdaccdeca6bd17909 |
|
BLAKE2b-256 | 388f2cf1e4c091838b3c597d4a3a4adf74c804a8b29f31c765c9ddb03ca8e389 |
Hashes for pygm-1.0.1-cp37-cp37m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0aaedb8e6bca344f5d8a9334db9d14ab39a601d68cefc22230f0c12a903d2188 |
|
MD5 | 7873630d3590765c8daf96677e6e572a |
|
BLAKE2b-256 | 10bf2df844bd0146d62c94e79c8ea802b1ee356982deb3a6bc90a22c6e5e029d |
Hashes for pygm-1.0.1-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 12bbfa3799f0ac2a2f162ae8c1acb4c30938c42c68d0ae0fac00ab1d336e0ace |
|
MD5 | c5ef1f75f7ba75eb708e3bf8867b8cb2 |
|
BLAKE2b-256 | 1cf2daedeeaa0495f0ce4762efa55f11e50295f6b91e3ed20cb285cb91acbfda |
Hashes for pygm-1.0.1-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4d070c0c5a1b284e74bdc3eab88783dcd237ddbfb43f719a241abfe27ddfae14 |
|
MD5 | 271e816a54e0f1e07b97aecd4557bfd0 |
|
BLAKE2b-256 | 8cb379732b09f42102d528ae5db927324f11370ed57a69ef9ee1d2c1904a9608 |
Hashes for pygm-1.0.1-cp36-cp36m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0d239efa148d4caaa1dfd96fa7962a6f7bcf8976d97c334c6c74f0d70b1bfdf4 |
|
MD5 | 910ecca5f70fda06a28ed977aba5d11a |
|
BLAKE2b-256 | 4b02a31e6b900d3951ef7088e2dec8d3a54f51ce9b6975938dd6df9323b27ae6 |
Hashes for pygm-1.0.1-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 95abd94aa18784897404deacdea6c15b2dfc963434ef1c4096deedf64ac1a182 |
|
MD5 | f78074e940c15877f698f0da58fa1251 |
|
BLAKE2b-256 | a154f30e3ee11f7631542bd5dbee702a3286f585a41099c72923a2ff01a89d16 |
Hashes for pygm-1.0.1-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d380c3f4ccf74a42c44b7139d27e4fcab12f9b57da4b41358fcd7321c6a486f4 |
|
MD5 | 9063cfd066f28e4eeb96894e33ff6417 |
|
BLAKE2b-256 | 86504517a375814007aab68453b8821d7cf606a89d6e084e086d143f54ec5c40 |