On 2006-08-25, Ben Sizer <[EMAIL PROTECTED]> wrote: > Neil Cerutti wrote: >> On 2006-08-24, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote: >> > It will run a lot faster if it doesn't have to keep resizing >> > the array. >> >> I don't see why it should run a lot faster that way. >> >> Appending elements to a vector with push_back takes amortized >> constant time. In the example above, preallocating 40000 >> strings saves (probably) math.log(40000, 2) reallocations of >> the vector's storage along with the consequent >> copy-construction and destruction of some fixed number of >> strings. Most of those reallocations take place while the >> vector is still proportionally quite small. > > Math.log(40000, 2) is not a small number when talking about a > relatively expensive operation such as memory allocation and > deallocation. And the superfluous copying amounts to probably > an extra 2^16 copies in this case - not exactly trivial.
Actually, I misread the suggestion. I thought I saw: vector<string> v; v.reserve(40000); instead of: vector<string> v(40000); The latter actually *slows* the program, according to my tests. I think the poster meant to suggest the former, and that's what I was discussing. I increased the number of iterations from 10000 to 100000 for the tests I'm reporting. The best of five, with reserve, was 2363 clock ticks. Without reserve, it was 3244. The suggestion to use an initial size resulted in 3655 clocks. So it appears you were more right (using reserve sped up the program by 35%, just about as the numbers predict), although we were both wrong. ;) -- Neil Cerutti 8 new choir robes are currently needed, due to the addition of several new members and to the deterioration of some of the older ones. --Church Bulletin Blooper -- http://mail.python.org/mailman/listinfo/python-list