Re: [Haskell-cafe] Performance of functional priority queues
One of the correspondents in that thread claims that it is provably impossible to have an efficient priority queue implementation without mutability. I think he's cuckoo. But I'd like to have some numbers to back me up.
He is cuckoo, and here's proof: http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdfThis demonstrates a functional priority queue that performs every desired operation in asymptotically optimal time. Granting that its constant factor could be significantly improved, realize that there are more complicated functional data structures with similar asymptotic guarantees. (Observation: I'm pretty sure that the Fibonacci heap is actually surprisingly functional.) Louis Wasserman wasserman.louis@gmail.com http://profiles.google.com/wasserman.louis
On Friday 25 December 2009 19:59:39 Louis Wasserman wrote:
One of the correspondents in that thread claims that it is provably impossible to have an efficient priority queue implementation without mutability. I think he's cuckoo. But I'd like to have some numbers to back me up.
He is cuckoo, and here's proof: http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf
http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdfThis demonstrates a functional priority queue that performs every desired operation in asymptotically optimal time...
You're assuming he meant asymptotic time complexity. -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e
participants (2)
-
Jon Harrop -
Louis Wasserman