Re:Aguri: Coolest Data Structure You've Never Heard Of
by tptacek on Tuesday January 22, 2008 @08:31AM
(#102171)
You're ignoring table load factor in your memory comparison, you can attack any dictionary "in terms of memory", I conceded the O(n)/O(k) lookup thing before you wrote this, and why do you think "balancing" a red-black tree is expensive?
[ Parent
| on HN ]
Re:Aguri: Coolest Data Structure You've Never Heard Of
by mojuba on Tuesday January 22, 2008 @10:15AM
(#102212)
You're ignoring table load factor in your memory comparison
I believe I don't ignore anything, I'm measuring precise memory usage by two identical programs doing same thing but based on different algorithms. I also believe I got the most out of radix in my tests. The 4-bit version of radix wasn't trivial, but it was reasonably fast and the mem usage was twice as better than the 8-bit one, as I said before.
But even speculatively, on paper if you wish, radix consumes more memory than some good hash table implementation.
Upd. forgot to mention, I did some more optimizations as well, like compressing the pointer tables in tree nodes.
Re:Aguri: Coolest Data Structure You've Never Heard Of
by tptacek on Tuesday January 22, 2008 @03:14PM
(#102399)
I'm sorry, you're talking about a totally different algorithm than I am either here or in the article you're responding to. There's no such thing as a "4 bit PATRICIA" trie. Obviously, if you want to burn memory, you can increase the arity of your tree nodes to "speed up" (heh) fetches.