[erlang-questions] Trie Data Structure

Ryan Zezeski <>
Thu Dec 30 06:04:57 CET 2010


On Wed, Dec 29, 2010 at 9:21 PM, Michael Truog <> wrote:

> Hi,
>
> I implemented a trie data structure that has performed 20% faster lookups
> than the dict implementation in R14B01.  I have tested the code but it can
> always benefit from more testing.  The trie module provides the same
> interface as the dict module, but requires a list of integers for the key.
> Please tell me if you find issues in the code.
>
> Code:
>
> https://github.com/okeuday/CloudI/blob/master/src/lib/cloud_stdlib/src/trie.erl
>
> Blog posts:
> http://okeuday.livejournal.com/16454.html
> http://okeuday.livejournal.com/16182.html (dict as the fastest general
> tree
> data structure)
>
> I know you can use ETS for similar problems, but avoiding shared data helps
> utilize Erlang's scalability advantages.
>
> Thanks,
> Michael Truog
>

Do you have the benchmark and dataset available as well?  I wrote a trie in
Erlang a few weeks ago and I'm just curious how it stacks up.

-- 
*.........01010...00..00...0100...00..00.
.........10..11...0100...11..00..101.01.
.111010..01100.....10....101110..01.101.
.........10..10....11....01..10..10..01.
.........00..00....00....00..00..00..00.
........................................*


More information about the erlang-questions mailing list