Improving containers library

[Heinrich Apfelmus]

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).


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com