Python and STL efficiency

[Ben Sizer]

Neil Cerutti wrote:
> On 2006-08-24, JSprenkle at gmail.com <JSprenkle at gmail.com> 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.

-- 
Ben Sizer