Timeline for Data structure for fast StartsWith filtering of a dictionary
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2016 at 17:42 | comment | added | c-smile |
@JonathanDickinson I agree that patricia tries have less nodes but each node in PT is of variable size. While node in TT is a fixed size structure and so the whole tree can be contained in single and compact vector<tt_node>.
|
|
| Mar 3, 2016 at 13:11 | comment | added | Jonathan Dickinson | Upvote, with a caveat. If you're really concerned about performance (e.g. router firmware), patricia tries are friendlier to the cache. Much the same as the ternary search tree, albeit child nodes are only created at the start of unique runs (thus inherently have fewer nodes). Deference is bad for the cache, so fewer nodes are better. en.wikipedia.org/wiki/Radix_tree | |
| Feb 5, 2013 at 3:33 | vote | accept | ConditionRacer | ||
| Feb 4, 2013 at 0:17 | history | answered | c-smile | CC BY-SA 3.0 |