#patricia #radix #trie

patricia_tree

Memory-efficient data structures based on patricia tree

10 releases

✓ Uses Rust 2018 edition

new 0.1.9 Dec 2, 2019
0.1.8 Oct 11, 2018
0.1.7 May 18, 2018
0.1.4 Apr 27, 2018
0.1.1 Sep 25, 2017

#59 in Data structures

Download history 169/week @ 2019-08-19 331/week @ 2019-08-26 43/week @ 2019-09-02 79/week @ 2019-09-09 88/week @ 2019-09-16 118/week @ 2019-09-23 62/week @ 2019-09-30 36/week @ 2019-10-07 51/week @ 2019-10-14 98/week @ 2019-10-21 26/week @ 2019-10-28 30/week @ 2019-11-04 75/week @ 2019-11-11 64/week @ 2019-11-18 38/week @ 2019-11-25

267 downloads per month
Used in 3 crates (1 directly)

MIT license

83KB
2K SLoC

patricia_tree

patricia_tree Documentation Build Status Code Coverage License: MIT

Memory-efficient data structures based on patricia tree (a.k.a, radix tree).

Documentation

A common prefixes of the keys in a patricia tree are represented by a shared path. So if the prefixes of the key set is highly redundant, the memory usage of the resulting patricia tree will be drastically less than more generic data structures (e.g., BTreeMap).

See Radix tree for more details.

Examples

use patricia_tree::PatriciaMap;

let mut map = PatriciaMap::new();
map.insert("foo", 1);
map.insert("bar", 2);
map.insert("baz", 3);
assert_eq!(map.len(), 3);

assert_eq!(map.get("foo"), Some(&1));
assert_eq!(map.get("bar"), Some(&2));
assert_eq!(map.get("baz"), Some(&3));

Benchmarks

$ cargo run --example insert_lines --release -- --version 2> /dev/null
insert_lines 0.1.0

///
/// INPUT: Wikipedia
///
$ curl -s https://dumps.wikimedia.org/enwiki/latest/enwiki-latest-all-titles-in-ns0.gz | gzip -d > enwiki-latest-all-titles-in-ns0
$ du -hs enwiki-latest-all-titles-in-ns0
271M    enwiki-latest-all-titles-in-ns0

// HashSet
$ /usr/bin/time -f "# ELAPSED: %E\n# MEMORY: %M" cargo run --example insert_lines --release -- --kind hash < enwiki-latest-all-titles-in-ns0
# LINES: 13450823
# ELAPSED: 0:10.23
# MEMORY: 1001548  // 978 MB

// BTreeSet
$ /usr/bin/time -f "# ELAPSED: %E\n# MEMORY: %M" cargo run --example insert_lines --release -- --kind btree < enwiki-latest-all-titles-in-ns0
# LINES: 13450823
# ELAPSED: 0:10.90
# MEMORY: 1112068  // 1,086 MB

// PatriciaSet
$ /usr/bin/time -f "# ELAPSED: %E\n# MEMORY: %M" cargo run --example insert_lines --release -- --kind patricia < enwiki-latest-all-titles-in-ns0
# LINES: 13450823
# ELAPSED: 1:12.55
# MEMORY: 434340   // 424 MB

///
/// INPUT: Google 5-gram
///
$ curl -s http://storage.googleapis.com/books/ngrams/books/googlebooks-eng-all-5gram-20120701-0.gz | gzip -d > googlebooks-eng-all-5gram-20120701-0
$ du -hs googlebooks-eng-all-5gram-20120701-0
331M    googlebooks-eng-all-5gram-20120701-0

// HashSet
$ /usr/bin/time -f "# ELAPSED: %E\n# MEMORY: %M" cargo run --example insert_lines --release -- --kind hash < googlebooks-eng-all-5gram-20120701-0
# LINES: 9814743
# ELAPSED: 0:08.36
# MEMORY: 1115544  // 1,089 MB

// BTreeSet
$ /usr/bin/time -f "# ELAPSED: %E\n# MEMORY: %M" cargo run --example insert_lines --release -- --kind btree < googlebooks-eng-all-5gram-20120701-0
# LINES: 9814743
# ELAPSED: 0:06.85
# MEMORY: 942236   // 920 MB

// PatriciaSet
$ /usr/bin/time -f "# ELAPSED: %E\n# MEMORY: %M" cargo run --example insert_lines --release -- --kind patricia < googlebooks-eng-all-5gram-20120701-0
# LINES: 9814743
# ELAPSED: 0:25.62
# MEMORY: 223616   // 218 MB

Dependencies

~18–300KB