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

[Louis Wasserman]

Apologies!

I was, in point of fact, working on such a patch, but I think I've been
convinced that it's a legitimate position for a package to take.  (I'm also
curious, Johann, about the approach you figured out that didn't cost a word
per node!)

That said, I've been working with somewhat similar structures for my TrieMap
package, and I hadn't honestly considered the possibility of having size run
in anything but O(1).  (When I was comparing benchmarks with
bytestring-trie, I didn't realize for a few hours that all of my benchmarks
called size, so O(W) operations were being benchmarked at O(n).  That threw
me off..)

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


On Tue, Feb 22, 2011 at 4:28 PM, Don Stewart <dons at galois.com> wrote:

> bos:
> >    On Sat, Feb 19, 2011 at 11:58 AM, Louis Wasserman
> >    <[1]wasserman.louis at gmail.com> wrote:
> >
> >      size takes O(n).  That's just depressing.  Really.
> >
> >    That's rather thoughtless wording for some code that's (a) free (b)
> faster
> >    than anything else currently available (c) in its very first release
> and
> >    (d) available in source form for you to improve as you see fit. Just
> >    depressing. Really.
>
> Agreed. This is open source: patches or it stays at O(n).
>
> -- Don
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110222/bc97970d/attachment.htm>