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
