Improving containers library
apfelmus at quantentunnel.de
Fri Mar 5 05:04:55 EST 2010
Ross Paterson wrote:
> On Thu, Mar 04, 2010 at 03:40:56PM +0100, Heinrich Apfelmus wrote:
>> How about the real time version of the banker's queue? That would be a
>> definite improvement upon Data.Sequence, at least.
> We used to have that. It gives the real time guarantee, but the average
> performance is about twice as slow as Data.Sequence.
Oh? I would have thought that the finger tree has a higher constant
factor since every element has to be "carried over" a few times while
traveling from back to front. In contrast, it's clear that the real time
queue touches each element only 2-3 times (add to rear, force the
suspension in the front, remove from front).
More information about the Libraries