preallocate list

[Dan Christensen]

Bill Mill <bill.mill at gmail.com> writes:

> Bill Mill <bill.mill at gmail.com> writes:
>
>> I would profile your app to see that it's your append which is taking
>> ages, but to preallocate a list of strings would look like:
>> 
>> ["This is an average length string" for i in range(approx_length)]

I don't think there's any point putting strings into the preallocated
list.  A list is just an array of pointers to objects, so any object
will do fine for preallocation, no matter what the list will be used for.

>> My guess is that it won't help to preallocate, but time it and let us
>> know. A test to back my guess:
>> 
>> import timeit, math
>> 
>> def test1():
>>     lst = [0 for i in range(100000)]
>>     for i in xrange(100000):
>>         lst[i] = math.sin(i) * i
>> 
>> def test2():
>>     lst = []
>>     for i in xrange(100000):
>>         lst.append(math.sin(i) * i)

...

> The results change slightly when I actually insert an integer, instead
> of a float, with lst[i] = i and lst.append(i):
>
> 09:14 AM ~$ python test.py
> time1: 3.352000
> time2: 3.672000

If you use

      lst = range(100000)

or even better

      lst = [None]*100000

then test1 is more than twice as fast as test2:

time1: 2.437730
time2: 5.308054

(using python 2.4).

Your code

     lst = [0 for i in range(100000)]

made python do an extra 100000-iteration loop.

Dan