Fast and compact maps and sets with Billions of keys, based on finite-state-transducers.
Project description
Ducer
This package provides Python bindings for the excellent Rust crate
fst by Andrew Gallant.
Map
and Set
classes allow building compact representations from sorted
Python iterables.
Performance
Ducer maps and sets can be built and queried at millions of keys per second. Consider the following example:
n = 1_000_000_000
items = ((b"%09d" % i, n-i) for i in range(n))
data = ducer.Map.build(items, ":memory:")
print(len(data))
Creating this map takes about 4 minutes on my humble laptop, which translates to almost 4 Million items per second. About 3 minutes is spent in Python just creating the item tuples. This is a pathological scenario, the resulting output is just 464 bytes. A real-world example with 1.1 Billion keys, where the msgpacked key-value pairs occupy 21 GiB (without any kind of searchability), results in a 4.6 GiB file.
Limitations
Performance is rarely free, so there are some limitations you should consider before proceeding:
- Keys must be
bytes
- Keys must be inserted in lexicographical order
- Map values must be positive integers less than 2^64
- Once built, maps and sets cannot be altered
Usage
Building & opening
Above, we created a map with data stored in memory. If you want to store your map in a file, you can also give a path instead:
ducer.Map.build(items, "path/to/my.map")
Building a map like this is a very memory-efficient. You can also stream a map without loading all data into memory, e.g., using the builtin mmap:
with open("path/to/my.map", "rb") as f:
mm = mmap.mmap(f.fileno(), 0, prot=mmap.PROT_READ)
mm.madvise(mmap.MADV_RANDOM)
m = ducer.Map(mm)
Access
Other than being read-only, maps and sets behave the same as the builtin
Python dict
and set
.
Please open an issue if you find something that doesn't work.
For map m: Map
and key k: bytes
, the following all work as intended:
k in m # bool
m[k] # value except KeyError
m.get(k) # value or None
m.get(k, 0) # value or 0
len(m) # number of items
for k in m: # iterate over keys
pass
for v in m.values(): # iterate over values
pass
for k, v in m.items(): # iterate over items
pass
TODO advanced search & operations
Project details
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 ducer-0.2.1-cp312-cp312-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7597f54b2e55c2d0fdca1c5aa4cd6113161599d0647fa4b3e454a7d9f5c81055 |
|
MD5 | 013b81529ecf69b386fb4f13d813e324 |
|
BLAKE2b-256 | 443c2b23b3ff60628319c7ae5b3fbc94db436488baaf8d9fb8cb66b393c79ad1 |
Hashes for ducer-0.2.1-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9ed65223ebe0f2a2e71eb324d744502261cdd2b803edfcf041036d0e6eafc333 |
|
MD5 | 3f81a4320f7aeb065a4ec5b0447b7869 |
|
BLAKE2b-256 | 9aba898900766bb6e22524be0d765222144ab4cab9c307c96457b11d121d03b4 |
Hashes for ducer-0.2.1-cp312-cp312-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9f4fe8627cb6794f26766c75af1d281fd83fddece67b3384240b8b458484b652 |
|
MD5 | a554d99b316804c153bf15149c260f8c |
|
BLAKE2b-256 | ef50431c1d78f459c2b62cea7910ba30029e7c1d8222dbe840d04e0da7b237cb |
Hashes for ducer-0.2.1-cp312-cp312-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4fca03f54d8aaccd2e4c87269b885e29bdd7da535ece7e717837094b767fd11f |
|
MD5 | d5e1fdd4b5c496112cb9492c50cc4f92 |
|
BLAKE2b-256 | 4b263cb9e5b8fe571fccc8a04770a3635981184fce0a3cd95aa75030afda42d4 |
Hashes for ducer-0.2.1-cp312-cp312-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 82014375059d997262df34f00c7a849e35e64ff97f6c486eae943ba684fc91d4 |
|
MD5 | 3829462c618b31c032d624e18cfd3006 |
|
BLAKE2b-256 | 5b2d0133aad4352866bce9a04d974f3a3d8dfdcfe0453328d21045256e271e28 |
Hashes for ducer-0.2.1-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | aea8802e2ea36e877ae19003667e6602e908dfdb1836f4e03b61c92307f028da |
|
MD5 | 7be3da4d9988542af143f3730e0920a7 |
|
BLAKE2b-256 | 05fea51b46fcb07c1f1929a7202eb5b9df47507c69a1bc12114c6e9f2fbaf814 |
Hashes for ducer-0.2.1-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f6cddd8a45b353a70881bfa76315f8a38333744bcb78687599ef852c6f4518ed |
|
MD5 | 30f67a7f6ed8facfea555b2a18cfbeb1 |
|
BLAKE2b-256 | d22b89b79ba1a5fb282919cb813e22e2060500be79d6d2afb17105e2d768f744 |
Hashes for ducer-0.2.1-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 20983e04d23cb0a7e624a857b4b75191ac91136ecb3a1888c28bfadd426c2ff6 |
|
MD5 | 191ce291f87fb68e31a3c3b780579a2d |
|
BLAKE2b-256 | 76d3ccd1d66ab508d5e72841a43504199c386d09df2a19b8a7b1502f6a18ca62 |
Hashes for ducer-0.2.1-cp311-cp311-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 560b922d1776ffb242a36247a1c391b2594a8f5f55b884789b8e6e52f9df39fb |
|
MD5 | 4134a6257858fb28b4e7d9194e74c584 |
|
BLAKE2b-256 | f7a3f0ed56fa7e784c73abffe1188282b5e66050b9eadfeea786ddb9cfee92fd |
Hashes for ducer-0.2.1-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5d8a8cf4346c8fea08f35e3a3cc2cd45170e04e1eba1ee66d5a5146df8dc0ea3 |
|
MD5 | f6995a504228a1b82e7510864065a370 |
|
BLAKE2b-256 | 2c58b99d3fd9f2484f118d6f3612daba0c20859f6c1bd05f2025443433874ce0 |
Hashes for ducer-0.2.1-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a3cdbb93ddf39d2dcd6b0556f2bb9fd2e097021477af7311a1cabf2647e10a05 |
|
MD5 | 7c78e26eee1d2f873080338b5e18401d |
|
BLAKE2b-256 | 5acf07b282953a7af10102975b38826226d448cb2b9e4397e114ca7a6e60e35a |
Hashes for ducer-0.2.1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4cc7a93149823f813c16b1e88486ce4c04fd1457e24573dc0f0de0b8faa9c7e9 |
|
MD5 | 6ec5bec84208021cdc9534cb6b9a2a36 |
|
BLAKE2b-256 | 0a81cb112ac551492a170336f2745a7a2c6c6fb71999aed8587beec36b03dd11 |
Hashes for ducer-0.2.1-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 506130c26727756bceb6e7e408b17f2a978f515bd87b5e03ab3ce1ec2af5d8e0 |
|
MD5 | d24ea00ff252faa37dc4ebb502193237 |
|
BLAKE2b-256 | 47b364fc30f8aa477ede481e232646f8ace0c66341366a93d01794ba9d8eb573 |
Hashes for ducer-0.2.1-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a09ce13c8e1aa8b130a1102f18318c936e71902b41eeb73194798a47eab14b1d |
|
MD5 | d81e7b9179b5489dd0d9da274bb48c1d |
|
BLAKE2b-256 | 15adc7de9a5444971e3d61de4a4502ff20acbfd3dd2fce611cf1f3d9324e0235 |
Hashes for ducer-0.2.1-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9493bacbddae6d3ea4913287bbfbc150f0fc9632a745a957086c2166229e416d |
|
MD5 | 70525dd27c6fdbf0c7b44056867a191a |
|
BLAKE2b-256 | c7e1aad9b8f4ae37f9220d0ec5c478c13befb3f9e13d550d324e906bca6c36bf |
Hashes for ducer-0.2.1-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6e0cc06edf63bb5f07bf1464576ea6da432a7bec1e9e8f066609a7a48df1877b |
|
MD5 | f1bc97315ce370fa5c5d0d0b4153562f |
|
BLAKE2b-256 | 2e94f17fb73e1811a77a2a133859b22ded9c0db8ab41c1a9d9e9ff914ffd8bdb |
Hashes for ducer-0.2.1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | faf4bf7e644d07781473186b4032a45e3f00366df6bd564f06ed0793194a0b7b |
|
MD5 | 3e276182231d52faf24f71cefa85fdd8 |
|
BLAKE2b-256 | 26152d01f8c15d0e8ed638f8e2e869c2973336961122f7f4541210d767cb8c9f |
Hashes for ducer-0.2.1-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3f2b3a2656b09c5544d3ba9559156b6ad264703efb7234c570610dc217a98ab6 |
|
MD5 | 20bf7966043b09bcade4a61686ee35fa |
|
BLAKE2b-256 | 37c9646f4261471442ce970b4f20554122ea59857f1d8361b1a0e47c41a18187 |
Hashes for ducer-0.2.1-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 41bf9406867054c4b639d1bca6a224b186ad77791ecac5acced72b0e060dc7bb |
|
MD5 | 74a4df924f4fd8dd6f47656af6ca15e5 |
|
BLAKE2b-256 | d6f7f6bdc69add1c17f86b57a171d4b46ce0271027d63c78ad109c973009c25a |
Hashes for ducer-0.2.1-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a13ef70d46d670ae4e6b34bfa3f486d0b976725dfa86663fe853c24e77b19458 |
|
MD5 | f0cbfe89a94f356387bc7c78f58ffff2 |
|
BLAKE2b-256 | 7417be9bbfb2cedfeb2a71d7c149a7095103673c999ae7fa19db242dd708fcde |
Hashes for ducer-0.2.1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d9e101c2de0ed1c7de86902d0efc8e95378060707f3bdfaaf038fd097e05ae2c |
|
MD5 | 2178d5a843104758d03cb5556bb7b806 |
|
BLAKE2b-256 | c26bc5647760a9829f1e0017506c528a6586896088d90d909bd2574e1f2f86d7 |
Hashes for ducer-0.2.1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 23307d8d49bf9e010d1cb526aea2d62a6b88b7fee1bab5f630026bdb7c9ed0b8 |
|
MD5 | b83565e6402265863d06295c756e65b2 |
|
BLAKE2b-256 | 934cc29447e141c33b75203a51582b0705fd133152ac53127282ad56ceeceac2 |
Hashes for ducer-0.2.1-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1ce2ed3f60d66c581a9d4b5301dcdc40ca989dd5fe52deb9bf3591d0e05322da |
|
MD5 | bd526954e853ea1ac374c7c27f32b52f |
|
BLAKE2b-256 | 762cb321514dac02624ef06aa665b8cdc820d0551b9eed80a59a04fc421367f1 |
Hashes for ducer-0.2.1-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 270b386f98ab30fc00b5fcb91430c5d24e71360b854202960825ab79f5046bbb |
|
MD5 | 2d94e0c68e41ab135dab9ebe343973e8 |
|
BLAKE2b-256 | 7b51e4efaf3d912adcd902f33368b0b2966913dbaa93990628d027d80e28871d |
Hashes for ducer-0.2.1-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8cdc975cb01c36fb92f1211d8dc56d41d599088b19b07f71664f4836229a0439 |
|
MD5 | c83f1a285e900990ed859da4f2a7f8f8 |
|
BLAKE2b-256 | 8408b9abbf31fe8fce5bc8ab764f2107ba6496522cb8d1d33f12122e2aeeee18 |