Efficient Hashtables for Haskell

As far as i can see, most of the important standard Haskell libraries seem to be already here. However I couldn’t find an efficient hashtable implementation. Common implementations like Data.Map work just fine, but are painfully slow. Games like MIME Type, which have a performance requirement, are not solvable with that. So i would ask, if you could install the hashtables package from Hackage, which should be of sufficient performance.

You don’t even need a Map to solve this problem, a list is fast enough. As a general rule, when a test case is labelled as “big”, its primary purpose is to defeat naive brute force approaches. That being said, this hashtables package could be useful for multiplayer contests.

1 Like

@Florent: Thanks for the hint! I was struggling with the Mime Type task for a while, because I didn’t realize that a map (supposedly tree-based) could be slower than a list for the lookup operation! :frowning:

This could have been the case in the past, but they work just fine for that purpose now.

And as @Aries1 mentioned, in a compiled language, that puzzle doesn’t even need that much performance. Browsing the published solutions list there for a bit, there are some pretty wild (on both sides of the theoretical speed spectrum) ideas out there.

We’ve got Data.HashMap.* in unordered-containers as part of the platform, who could be (they are in my code) a drop-in replacement.

Actually, what makes maps terrible here is the fact that you use it with keys of type String aka [Char].

One solution is to use a trie instead (with an i, no typo here).
Data.Trie is unfortunately not available, but it is quite fast to reimplement the basics.