Efficient Amortised and Real-Time Queues in Haskell

Re:Efficient Amortised and Real-Time Queues in Haskell by wyager on Saturday January 16, 2016 @10:39AM (#10915528)

In my experience, bankers' Queues (like the one presented in the article) are not the best persistent queue solution.

The Finger Tree (available in the Haskell standard library under Data.Sequence) is a really impressive data structure. It's persistent, it has O(log(min(n,len-n))) access and modification (which means O(1) cons, snoc, head, and last), and O(log(min(m,n))) concatenation.

In my testing, it was several times faster than the fastest banker's queue library I found.

[ Parent | on HN ]

Re:Efficient Amortised and Real-Time Queues in Haskell by thesz on Friday January 22, 2016 @01:21PM (#10954545)

I had an experience changing code from using priority queue using finger tree to using sorted lists (regular Haskell's lazy lists, sorted, not even merged!) and obtaining an order of magnitude speedup and reduction of memory consumption.

So I would like to advise staying away from finger trees and other interesting data structures when lists suffice.

In case of queues they are very sufficient.

What article lacks, is the performance comparisons.

[ Parent | on HN ]