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