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

Louis Wasserman wasserman.louis at gmail.com
Wed Feb 23 03:28:26 CET 2011


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

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>

More information about the Haskell-Cafe mailing list