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