[Haskell-cafe] ANN: unordered-containers - a new, faster hashing-based containers library
ekmett at gmail.com
Sun Feb 20 04:02:02 CET 2011
On Sat, Feb 19, 2011 at 7:27 PM, Sterling Clover <s.clover at gmail.com> wrote:
> On Sat, Feb 19, 2011 at 3:04 PM, Johan Tibell <johan.tibell at gmail.com>
> > On Sat, Feb 19, 2011 at 11:58 AM, Louis Wasserman
> > <wasserman.louis at gmail.com> 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)
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe