On Mon, Jun 22, 2009 at 10:10 AM, Ketil Malde <ke...@malde.org> wrote:
> Kamil Dworakowski <ka...@dworakowski.name> writes: > > > Right... Python uses hashtables while here I have a tree with log n > > access time. I did not want to use the Data.HashTable, it would > > pervade my program with IO. The alternative is an ideal hashmap that > never > > gets changed. This program creates a dictionary at start which then is > only > > being used to read from: an ideal application for the Data.PerfectHash > > by Mark Wotton available on Hackage [3]. > > If you are considering alternative data structures, you might want to > look at tries or Bloom filters, both have O(n) lookup, both have > Haskell implementations. The latter is probably faster but > probabilistic (i.e. it will occasionally fail to detect a > misspelling - which you can of course check against a "real" > dictionary). Typo? Bloom filters have O(1) lookup and tries O(m) lookup where m is the number of characters in the string. Cheers, Johan
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
