5 Mar
2010
5 Mar
'10
5:04 a.m.
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