[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
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>
More information about the Haskell-Cafe
mailing list