Fast and compact maps and sets with Billions of keys, based on finite-state-transducers.
Project description
Ducer documentation
This package provides fast and compact read-only
maps
and
sets
that scale up to Billions of keys, while being light on resources
with a streamable file format.
Complex search patterns that would be infeasible with Python's builtin
dict
and set
are not just possible, but very efficient.
All of these amazing things are achieved with finite-state-transducers
provided by the excellent Rust crate
fst by Andrew Gallant.
Performance
Ducer maps and sets can be built and queried at millions of keys per second. Consider the following example:
import ducer
n = 1_000_000_000
items = ((b"%09d" % i, n-i) for i in range(n))
data = ducer.Map.build(":memory:", items)
m = Map(data)
assert m[b"900000000"] == 100_000_000
In our example, most of the time is spent in Python creating item tuples. Regardless, building happens at almost 4 Million items per second on my humble laptop. Retrieving individual keys is similarly speedy, and simply iterating over all items is twice as fast at 8 Million items per second.
This toy example is almost a best case for FSTs, so the resulting output is just 464 bytes. A real-world example with 1.1 Billion keys, where the key-value pairs occupy 21 GiB without any kind of searchability (stored in already quite compact msgpack format), results in a 4.6 GiB file. Building and retrieval are naturally a bit slower, but still within the 2-3 Million items per second range.
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 non-negative integers less than 2^64
- Once built, maps and sets cannot be altered
Installation
Most users should be able to simply do:
pip install ducer
To build from source you will need a recent Rust toolchain. Use your preferred method of installation, or follow the official instructions to install Rust. Then run the following at the toplevel of the repository:
pip install .
Building
Above, we already showed that
Map.build
can build maps in memory by passing
":memory:"
as path:
data = ducer.Map.build(":memory:", items)
If you pass any other path
(either str
or Path
;
the parent directory must exist),
your map will be written directly to that file:
ducer.Map.build("path/to/my.map", items)
Building a map like this uses virtually no extra memory.
Opening
One key advantage of ducer maps is streamability.
Unlike the builtin dict
,
a Map
does not have to reside entirely in memory.
You can, e.g., use the builtin
mmap
to stream map data:
with open("path/to/my.map", "rb") as f:
mm = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ)
m = ducer.Map(mm)
High compression ratios can, however, allow storing maps entirely in memory. In our experience, at least for local SSD storage, performance is virtually identical, expect pre-loading data takes extra time. Pre-loading can still make sense though, e.g., with networked storage.
with open("path/to/my.map", "rb") as f:
data = f.read()
m = ducer.Map(data)
Access
To the extent that it's feasible,
Map
and Set
are intended to be direct replacements for the builtin Python
dict
and set
.
For m, o: Map
and k: bytes
, the following works as intended:
k in m
m == o
m[k]
m.get(k)
m.get(k, 42)
len(m)
for k in m:
pass
for k in m.keys():
pass
for v in m.values():
pass
for k, v in m.items():
pass
For s, o: Set
, and k: bytes
, the following works as intended:
k in s
s == o
len(s)
for k in s:
pass
s.isdisjoint(o)
s.issubset(o)
s <= o # subset
s < o # proper subset
s.issuperset(o)
s >= o # superset
s > o # proper superset
Note: Comparison operations are currently only implemented
for other Set
objects, not the builtin
set
.
This may change in a future version if there is demand for it.
Differences to builtins
Not implemented
Since Map
is immutable, the following are not implemented:
clear
fromkeys
pop
popitem
setdefault
update
,|=
Since Set
is immutable, the following are not implemented:
add
clear
difference_update
,-=
discard
intersection_update
,&=
pop
remove
symmetric_difference_update
,^=
update
,|=
Further, the |
, &
, -
, ^
operators are also not implemented,
since it is not possible to specify the storage path.
Use the respective union
, intersection
, difference
,
and symmetric_difference
methods instead.
Incompatible syntax
difference
, intersection
, symmetric_difference
, and union
have slightly different syntax to accomodate the necessary path.
For s: Set
and others: Iterable[Set]
:
s.difference("path/to/result.set", *others)
s.intersection("path/to/result.set", *others)
s.symmetric_difference("path/to/result.set", *others)
s.union("path/to/result.set", *others)
Like the standard library, difference will create the set of
all elements of s
that are not present in others
.
Set operations on maps
Unlike the builtin dict
,
the ducer Map
offers set operations.
The syntax is the same as for sets:
m.difference("path/to/result.map", *others)
m.intersection("path/to/result.map", *others)
m.symmetric_difference("path/to/result.map", *others)
m.union("path/to/result.map", *others)
To resolve conflicts between keys present in multiple maps,
a list of possible values is assembled.
If the key is present in self
, then it will be the first value.
Values from others
are added in given order.
By default the last values in the list is used to mimic the behavior
of dict.update
.
Currently, you can choose between these pre-defined operations:
ducer.Op.First
-- first elementducer.Op.Mid
-- middle element, left if even number of valuesducer.Op.Last
-- the defaultducer.Op.Min
-- minimum valueducer.Op.Avg
-- average value cast toint
ducer.Op.Median
-- median value cast toint
ducer.Op.Max
-- maximum value
Some examples:
m1 = ducer.Map(ducer.Map.build(":memory:", [(b"k1", 1), (b"k2", 1)]))
m2 = ducer.Map(ducer.Map.build(":memory:", [(b"k2", 2), (b"k3", 2)]))
m3 = ducer.Map(ducer.Map.build(":memory:", [(b"k3", 3)]))
mu = ducer.Map(m1.union(":memory:", m2, m3))
print(dict(mu.items()))
# {b'k1': 1, b'k2': 2, b'k3': 3}
mu = ducer.Map(m1.union(":memory:", m2, m3, select=ducer.Op.First))
print(dict(mu.items()))
# {b'k1': 1, b'k2': 1, b'k3': 2}
Advanced search patterns
The underlying FSTs allow for some advanced search patterns that would
otherwise be costly to implement on top of
dict
and set
.
Most basic, you can iterate over a range of keys, where
ge
= greater or equals,
gt
= greater than,
le
= less than or equals,
and lt
= less than:
m.range(ge=b"key17", lt=b"key42")
m.range(gt=b"key17", le=b"key42")
For maps this yields key-value tuples, meaning
m.range()
without limits is equivalent to
m.items()
.
You can also iterate over all keys that
start with
a certain prefix,
with optional limits same as range
:
m.starts_with(b"key", ge=b"key17", lt=b"key42")
m.starts_with(b"key", gt=b"key17", le=b"key42")
You can also search for
subsequences
, e.g., all keys matching *k*7*
,
again with optional limits:
m.subsequence(b"k7", ge=b"key17", lt=b"key42")
m.subsequence(b"k7", gt=b"key17", le=b"key42")
Finally, you can create an Automaton
to create your own search patterns.
The following automata are available:
For example, to recreate
Map.starts_with
,
you can use the following
automata with the
Map.search
method:
a = ducer.Automaton.str(b"key").starts_with()
m.search(a)
Add
complement
to search for keys that do not start with the string:
a = ducer.Automaton.str(b"key").starts_with().complement()
m.search(a)
Finally, you can combine multiple automata, e.g. with
union
:
a1 = ducer.Automaton.str(b"key").starts_with()
a2 = ducer.Automaton.str(b"other").starts_with()
a = a1.union(a2)
m.search(a)
Acknowledgements
Ducer is supported by the SustainML project.
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-1.0.2-cp312-cp312-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | be02036ec776a890281a707f44c2d89921029ec4a468de75fcfd0077b0250f28 |
|
MD5 | e468dcdbdb4182cb4674f62f9d833313 |
|
BLAKE2b-256 | 1b0b210f68961abed058f82b13939acd6e45b0d3c11e17bc0895825221ce4290 |
Hashes for ducer-1.0.2-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cda3690f42896b99cd2e478fdd006349c434a88f61183dd5c3c1c2d8bcfbcc83 |
|
MD5 | 1ac2db06ea80811b4bd18d5f30428c5e |
|
BLAKE2b-256 | 831aa1dd72c4654de9c6588a5454fec3e214836861881de68209dc64ea3ceac1 |
Hashes for ducer-1.0.2-cp312-cp312-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f5183c35555ee5b7e66924801bb0a0e8d640c79a4a3448ed32a5b6022fef8704 |
|
MD5 | e399ab151e66b35c6ccff33a39b19495 |
|
BLAKE2b-256 | 65d9fb7d6648f5f94323721d7edc44de81bbdb568115765429f4aaf2db10fe21 |
Hashes for ducer-1.0.2-cp312-cp312-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | aa558811145ab4597747535e1b3e019088b41736a4bb3c61ae58143e501cc3c5 |
|
MD5 | fe1d530495d5230a1a461f4c1ed653c0 |
|
BLAKE2b-256 | d8ac85c671b56c6aea8703d8c53b4451094ed62b2390fb531f46dce44c427ef0 |
Hashes for ducer-1.0.2-cp312-cp312-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a2751e2829f4cfc5f1345247ee5c35a01076dec4583793806d3dc5fd7190498b |
|
MD5 | 5e9414be53000f40282ede73a7453209 |
|
BLAKE2b-256 | a1ea0c06c58040516791155d852633c798f80ee177c0fa7ddf1175539a00fab9 |
Hashes for ducer-1.0.2-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cde62bcf01d463ead81664822e8fd2080cbc7a1baa9dd3018b3db2c6f0bd57c5 |
|
MD5 | 1c5e447d0bbfec8eeb4d69e1663a04b6 |
|
BLAKE2b-256 | edb3fceb54680825671b7ba5223ffeb1b7e056d0106a02c90064bfe14f1671d9 |
Hashes for ducer-1.0.2-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 038cdaf72da0571d3ff3a7b7056a610bbd08bd4da63d2d318c7f5aff87d65d2e |
|
MD5 | 29681f4393f2e99700f9ad8a6642176b |
|
BLAKE2b-256 | ec5d1c7d1f8789d2d26d4600e7734ce43c439ff0264c96666099d14a3cb6ad63 |
Hashes for ducer-1.0.2-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ce6045936911caf6f57f2dcc63d24e60cd1e2d9b3af13187aabd8502050f4f7a |
|
MD5 | ab02ca97f6e70cf9731d15d96ffb0195 |
|
BLAKE2b-256 | a668ed3f510c67368021dade88d4ea2b1add960d16bd2f6d3c09b15e5d8c30b7 |
Hashes for ducer-1.0.2-cp311-cp311-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 347bddeccb29c71bd3d75f3224fee16fbff0b9ae0ab512d77eb32139096cff9f |
|
MD5 | 26533d17a06e11b109dadcc4551ef5b8 |
|
BLAKE2b-256 | b4c19bad1b2346d1524efba145cfd0b3631e646a2e01219933f72ac738a88e23 |
Hashes for ducer-1.0.2-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9fd99e5f0c2a4c683f25c218b02b7d11a79851baf0eb605161bead304e5c52d2 |
|
MD5 | 4c993ecdf68bd89861711124666be3f4 |
|
BLAKE2b-256 | bc35b09b6449c1a5801230bf3ed1aa5f49cb5a943361c6d114143cfd01e856ec |
Hashes for ducer-1.0.2-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bdba11af2a515e074c7b4f91a445234c0a2bdfeecbfacb7741e23ae0c7acb087 |
|
MD5 | 1a3af44badf9df358dd2047308441fbd |
|
BLAKE2b-256 | 4dd7cfae892eb85054db053d18ee8c09a95a6709eedd4d7c7c08cae23855fb3a |
Hashes for ducer-1.0.2-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ed9d595ea8c570fbe9833528594d74171cd55467506a5e00ef1e81b0df3c90e1 |
|
MD5 | ccb9ee8f6b9fe64ef73ab8f1c761383b |
|
BLAKE2b-256 | ad49005cc10b90c144234cba256b24a20ca3745093cce1f18d36970b1da65877 |
Hashes for ducer-1.0.2-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 28922c62f3099e31c84af79497f801967372952e177b88ec9b74a5ebb51b88b8 |
|
MD5 | b9a0abc63f4723db89c70e0d9561542a |
|
BLAKE2b-256 | 074c4142a325d715de39a4e62a295ff16b988b189aa4eba93f9f1241be18c8a5 |
Hashes for ducer-1.0.2-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6db7c0d481bcc75d760e705c3e46227df28c47638476f0c26e8471e33359f5b2 |
|
MD5 | 8cd3267f7e22e9d346dd6f2d103da85f |
|
BLAKE2b-256 | fdc1ff2c79a61233d77b5a0c550ae4dad329b708015b458417c820c732b90936 |
Hashes for ducer-1.0.2-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0ddd52820e8c6147a029624979dc0c01af676b16d72db053a3eaf467392f4252 |
|
MD5 | a5d64f82496c7883918af84e74517639 |
|
BLAKE2b-256 | ba79dffa599af78b3823244d3767f65003e5743ee358f8ca2fe61b9ab9697c69 |
Hashes for ducer-1.0.2-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4d372666c69dfa1a3dd83510c9c92f9a071a5635232dc9423dce8f8a6df96583 |
|
MD5 | 62c59fcdc7b243149c1b654570ddd412 |
|
BLAKE2b-256 | 16d39b44804d57688a7794b7eda0f1603d6c57d6b6be054dcc01eec8fa673db5 |
Hashes for ducer-1.0.2-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 45eba01b9c8b4b0dce1a73dd98fa83d13e22c99bda3f581dcbce645b022d59ce |
|
MD5 | 4ba9ab5a2177e2e3e9673d16d363ff62 |
|
BLAKE2b-256 | b17b3d91a98b34e4da2ca1e2e23e6f831fe3f4602d1f7e4d56620b3ba63ec9d6 |
Hashes for ducer-1.0.2-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 573d78bb49fab094516441c58876af075454dbed8b891e1150b9ebfb13483de8 |
|
MD5 | 0736a0c8ce2e391e32fd6fd5a949572d |
|
BLAKE2b-256 | 1ad5a5e8c69052823b26268101c91f4878f05449dca05e2149041fe655f5509c |
Hashes for ducer-1.0.2-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fb25b780d6c9374243fdbb8735a39ef6f0d1a8b82a242548d4e7edaccff11b1c |
|
MD5 | 4b9ef3677c015e265a7309dbe055de0c |
|
BLAKE2b-256 | 3a9690c4b681d709068fc6dfdce94b1a8ace2a5fd57bd8958cb6aac809c114d4 |
Hashes for ducer-1.0.2-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 79c24b9630c03326e34b7e0ba50803b0a159c256af8575f65c4564d1496b9d19 |
|
MD5 | 078e9b38fa3fbfb6152309444356c9f8 |
|
BLAKE2b-256 | ae6db147928734bd0894cd2b17df32ab7ab274ddc8353c20a1cb1dcf7112bf43 |
Hashes for ducer-1.0.2-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4ece66c1016d3ae9b90294cdccf3c38936b21939078621fd4c9222c032ded552 |
|
MD5 | b878e07a9b757a13fbfc8fbb252c5fc9 |
|
BLAKE2b-256 | a1357d456cc54eb493aa8c3cbeb2552d44f69a062cd23ceed8bc9a084d98c163 |
Hashes for ducer-1.0.2-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 89bd111e7fe3be049e08a95b3d51f30aee7678657c0c42fc2115266d9ead7687 |
|
MD5 | 289a901d54ed29e7bb88187662e9885d |
|
BLAKE2b-256 | bb953865e4573472a888f41356310bd61091c4463a4f9fbebc2432455d201876 |
Hashes for ducer-1.0.2-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 83e1579fbe972a89557432cac92519ed08383c97cc4f6cde391b02e867b24ceb |
|
MD5 | f211d0cca7821dcdb968c56ed39b9089 |
|
BLAKE2b-256 | b875b08296ea2f7e344dd02027d47e8121b589fd697cdd6cae22b100c1773de4 |
Hashes for ducer-1.0.2-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f51a307948462742ed130b883eee80d873ef0884cecfbd9ac2e82b633973e1ee |
|
MD5 | f20450a3d208baa17226d483368d26f3 |
|
BLAKE2b-256 | 9d852f2e3c982ae1e5f27ff673a9be5791f4e499db61cc107f8bb14a3a27f10d |
Hashes for ducer-1.0.2-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6b0eb758a9338124e0689d8a390b8ea1646f356ca83a0466192d4301120a3697 |
|
MD5 | bfe2d389e645611e48d337eb2e3bcc4e |
|
BLAKE2b-256 | 540742a9b70f0e8ec0d1727d6c3c580ef3edebf8dde5a32ca205c5742193afb0 |