On Fri, Oct 29, 2010 at 1:17 PM, Daryoush Mehrtash <dmehrt...@gmail.com> wrote: > In the lessons you say: > >> Haskell proved too slow with String Map, so we ended up interning strings >> and working with an IntMap and a dictionary to disintern back to strings as >> a last step. Daniel Fisher was instrumental in bringing Haskell up to speed >> with OCaml and then beating it. Don Stewart provided awesome leadership and >> amazing modification of Haskell's core data structured before your very >> eyes.
A quick tip for anyone who needs to work on large maps with string keys in the future: try Milan Straka's hashmap package. String comparison is expensive and using a size balanced tree causes O(log n) of them. The HashMap data type uses an IntMap internally and typically (in the absence of collisions) needs to traverse the string only once, to compute the hash, and can then perform O(log n) cheap Int comparisons. I'm working on a more efficient hash function for ByteString and Text: an implementation of MurmurHash. The HashMap data type and the need hash function together should give us good performance for maps with string keys. Johan _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
