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

Louis Wasserman wasserman.louis at gmail.com
Sun Feb 20 04:40:19 CET 2011


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

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


On Sat, Feb 19, 2011 at 9:02 PM, Edward Kmett <ekmett at gmail.com> wrote:

> 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>
>> wrote:
>> > 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) size.
>
> -Edward
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110219/ea77a6aa/attachment.htm>


More information about the Haskell-Cafe mailing list