3 ms·
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
by wyager 11y ago
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.
- thesz 11y agoI 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.