[ROOT] TEventList -- or the resize policy of flexible containers

From: Walter F.J. Mueller (W.F.J.Mueller@gsi.de)
Date: Fri Aug 18 2000 - 11:08:47 MEST


Dear Rooters,

I was wondering why building an TEventList with a call like
 
   ntuple->Draw(">>el2id", "cp==2&&a2>0","",10000000,0); 

tends to take progressively more time when the size of the final
eventlist gets larger. A short inspection of the code showed that
the list is increased by a fixed number, given by fDelta and
setable by SetDelta, with a rather small default of 100 !

Unfortunately, such a constant increment resize policy leads always
to a quadratic increase of the CPU time as a function of final size,
no matter what the value of fDelta is !

A much better strategy is to increase the size by a constant factor.
This leads to an N ln(N) rather than a N^2 behaviour. The factor is
not critical, just doubling is fine. Using the doubling strategy one
gets after all on average a 75% filling, so the memory efficiency is
adequate.

I propose to change TEventList along those lines. If there are other
flexible containers in ROOT with the same algorithmic problem I propose
the same cure for them too.


			With best regards,	Walter


--
Walter F.J. Mueller   Mail:  W.F.J.Mueller@gsi.de
GSI,  Abteilung KP3   Phone: +49-6159-71-2766
D-64291 Darmstadt     FAX:   +49-6159-71-2989
WWW:   http://www-kp3.gsi.de/www/kp3/people/mueller.html



This archive was generated by hypermail 2b29 : Tue Jan 02 2001 - 11:50:31 MET