Re: [Haskell-cafe] ANN: unordered-containers - a new, faster hashing-based containers library

If you want to use the library and need a short term fix, just write a small wrapper type/module newtype SizedMap = SizedMap (Int, HashMap) and track the size yourself. only complication is that on inserts and deletes you'll need to check if the key existed. other than that, it shouldn't be too difficult. This way, the library stays super optimized but, if you need, you can track the size. As Johan said, it would slow down insert and delete a bit. shouldn't affect lookup though.. max On Feb 20, 2011, at 11:40 AM, Louis Wasserman wrote:

I'd like to complain about that, too ;)

Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis

On Sat, Feb 19, 2011 at 9:02 PM, Edward Kmett wrote: On Sat, Feb 19, 2011 at 7:27 PM, Sterling Clover wrote: On Sat, Feb 19, 2011 at 3:04 PM, Johan Tibell wrote:

...

On Sat, Feb 19, 2011 at 11:58 AM, Louis Wasserman wrote:

...

A couple thoughts: size takes O(n). That's just depressing. Really.

This applies to all the container types. We could support O(1) size at the cost of slowing down e.g lookup, insert, and delete a little bit. I haven't measure how much yet. Would it be worth it?

Getting a bit picky, but for the record, Data.Map and Data.Sequence provide O(1) size, and Data.HashTable I believe stores the information but doesn't expose it from its tiny API. That's not an argument either way for what a HashMap should do, however :-)

NB: Data.IntMap, which Data.HashMap is based on, actually only provides O(n) size.

-Edward

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe