Different Tries
Tikhon Jelvis
tikhon@jelv.is
Tries
- key-value map
- simple
- persistent
- fast
Retrieval
Also Called
- digital trees
- prefix trees
- radix trees
Tries
- basic trie
- PATRICIA trie:
Data.IntMap - variations
- branching factor
- (Persistent) Adaptive Radix Tree
Example
lookup “b”
- b = 1
lookup “bab”
- b
lookup “bab”
- b → a
lookup “bab”
- b → a → b = 7
data Trie a =
Node (Maybe a) [(Char, Trie a)]
lookup :: String → Trie a → Maybe a
insert :: String → a → Trie a → Trie a
Prefixes
- every key starting with “ba”
PATRICIA
Practical Algorithm to Retrieve Information Coded in Alphanumeric
- developed in 1968
Okasaki and Gill, 1998
Data.IntMap
Intkeys- bit-by-bit
- persistent
ByteStringkeys?
Structure
- branch on each bit
Paths
two keys: 00011, 00001
Compressed Paths
Compressed Paths
Compressed Paths
Data.IntMap
type Prefix = Int
type Mask = Int
data IntMap a =
Branch !Prefix !Mask
!(IntMap a) !(IntMap a)
| Leaf !Prefix a
| Empty
Performance Considerations
- unbox as much as possible
- spine strict
highestBitSet~ bitwise trick
highestBitSet
-- Borrowed from Haskell's Data.IntMap
highestBitSet :: Int -> Int
highestBitSet n =
case (n .|. shiftR n 1) of
n -> case (n .|. shiftR n 2) of
n -> case (n .|. shiftR n 4) of
n -> case (n .|. shiftR n 8) of
n -> case (n .|. shiftR n 16) of
n -> case (n .|. shiftR n 32) of -- for 64 bit platforms
n -> (n `xor` (shiftR n 1))
Performance
- much faster than
Data.Map- fast lookup/insert
- fast scans and merges
- slower than mutable hash map
Branching Factor
n bits of key = 2ⁿ children per node
- from ART paper
- benchmark with mutable tries
Adaptive Radix Trees
Adaptive Radix Trees
- branching factor: 256
- byte at a time
Four Types of Nodes
Persistent Adaptive Radix Trees?
- Java version with promising benchmarks
- good fit for Haskell?
Functional Graph Library
Summary
- IntMap: binary radix tree
- different branching factors
- time/memory tradeoff
- (persistent) adaptive radix trees
- optimize for Haskell?