Prefix Tree vs Hash Table

[aklepatc]

Prefix trees are known as an alternative implementation for dictionaries/maps. Applied like this, they sometimes significantly outperform hash tables. In particular, it works well when key space consists of thousands not-very-long strings. I saw this in action as a part of a smart order router code at a big sell-side firm where the keys were US

Comments

[morfizm]

Nice application of prefix trees!

[aklepatc]

Thank you!

[yatur]

Nice research, thanks!

Have you gathered any statistics on how much the prefix tree is faster than dictionary search?

As for Aho-Corasick, I think it should be possible to build a big regular expression along the lines of "(C\+\+)|(Java)|(\.Net)|(Data Integration)", match against it, and then iterate over the list of matched subgroups to assign the resume to the corresponding bucket(s). E.g. if the text matches subgroup 0 and subgroup 2, it goes to "C++" and ".Net" buckets. I am quite positive that the algorithm used in RegExes is similar to Aho-Corasick (a linear state machine), but you won't need to code it by hand.

[aklepatc]

My benchmark shows prefix tree to be 2.5-3 times faster than map[string]*something in Go. That scenario I'm testing for is rather language and application specific. So I would not call any of this "statistics". More like war story or professional anecdote : )

[yatur]

2-3 times is impressive indeed, even if it's for some specific case.

[aklepatc]

Based on the previous experiences with Go standard library (vs my custom implementations), I hoped for 10 times, TBH. So 2-3 felt like a minor disappointment...

[zveriozha]

Давненько вас не было. :)

[aklepatc]

Верно. Интересные (даже мне самому) мысли, к сожалению, не часто приходят в голову. В основном, сплошная рутина.

[zveriozha]

А вы в фейсбуке не сидите?

[aklepatc]

Нет. Когда мне что-то нужно посмотреть в ФБ, я прошу у жены заглянуть в её account : )

Вот на Tommy Carruthers иногда смотрю, по вашей рекомендации.