He sounds like a bit of a troll, but I agree the question itself is an
interesting one and I'd be interested to see if anyone has an "answer"
(although given the lack of criteria, it'll be hard to address his
points exactly)
On Tue, Jun 16, 2009 at 6:50 PM, Richard O'Keefe
On 15 Jun 2009, at 7:54 pm, Luke Palmer wrote:
One of the correspondents in that thread claims that it is provably impossible to have an efficient priority queue implementation without mutability.
If he so claims, maybe you can challenge him by asking for a proof?
He claims that the burden is on my end.
Such a proof would probably only involve asymptotics, since it's very hard to prove anything when actual raw speed is involved. If that's the case, you can use Okasaki to back yourself up (or back him up; I am not familiar with the results in this area).
He is aware of Okasaki's book, about which he was somewhat offensive. One thing that's clear is that he _isn't_ talking about asymptotics.
I've now done some benchmarks myself in C, Java, and Smalltalk, comparing "imperative" versions of leftist heaps with "functional" ones. For what it's worth, on a 2.16GHz Intel Core 2 Duo Mac, the coefficient in front of the log(n) part was
C Java ST(A) ST(B) "Imperative" 40 70 150 1123 "Functional" 240 126 290 1895
where ST(A) was a native-code Smalltalk and ST(B) a byte-code one. The C/Functional case used the Boehm collector, untuned. Times are in nanoseconds. Values of n ranged from 2 to 100; the correspondent was saying that small sizes were important.
It seems that a factor of 2 for *this* problem is credible; a factor of 10 is not.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe