On Tue, Mar 25, 2008 at 7:29 AM, Scott McMurray <me22.ca+boost@gmail.com> wrote:
On Mon, Mar 24, 2008 at 9:30 PM, chintan rao <chintanraoh@gmail.com> wrote:
PATRICIA Tries optimize space. I don't know about how much it improves
the
time efficiency over normal tries as one could be using TST in it to conserve space. But as far i remember a person #boost channel reported some thing like 2x speed over std::map.
(I use PATRICIA to mean joining chains of nodes with only one outbound link. Whether that's right not no, I don't know.)
I expect the time efficiciency improvement isn't significant. It's probably similar to the difference between iterating list and vector, in that the memory locality is better. It's essential, as far as I'm concerned, though, to keep the node space overhead from getting excessive, particularly since it does not worsen the time costs.
And that "person in #boost" was likely me. I got roughly a 2x speed up for 2x the memory cost, in a non-generic, proof-of-concept tst-patricia-trie.
Must have been you. You had spoken about tst patricia trie. :).
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost