[Haskell] Trie vs FiniteMap

Krasimir Angelov kr.angelov at gmail.com
Fri Jan 21 05:56:33 EST 2005


  Hello, Guys

I am playing with the attached implementation of Trie. My first test I compared 
(Trie Char Int) with (FiniteMap String Int). The test is shows that
the trie is much faster in lookup but the insertion is slower for
large data sets. The lookup in Trie is about 65% faster and this
doesn't depend from the size of the trie. When the trie has up to 5000
keys then the insertion is about 30% faster than in FiniteMap. When
the number of keys is about 10000 then the Trie and the FiniteMap have
comparative performance, but when there are about 100000 keys then the
Trie is about 20-30% slower. I am interested whether there is a better
implementation of Trie. Does anyone have an another implementation of
tries which can show better performance?

Cheers,
  Krasimir
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Trie.hs
Type: application/octet-stream
Size: 7762 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell/attachments/20050121/1cacb366/Trie.obj


More information about the Haskell mailing list