lists, performance..

[Alex Martelli]

gabor wrote:

> hi,
> 
> i'm working on a graphic application ( python + opengl)..
> 
> and i have some lists of vertices... but that's not important..
> 
> let's say a have loooooooong ( long = 500 to 5000 ) lists of relatively
> simple objects..
> 
> 2 questions:
> 
> 1. is a list implemented as a vector? i mean looking up the n-th element
> is done in o[1] (constant time)?

Yes.

> 2. i want to insert several lists into a big list.. better to say i want
> to concatenate them... but i don't really like the 'extent' method,
> because i want to do a deep-copy... for example:
> list1 = [ ['a','b','c'], [1,2,3,4] ,[5,6,7]]
> list2 = []
> list2.extend(list1)
> but now if i modify an element in list1, list2 gets modified too..
> for now i'm doing:
> 
> list1 = ...
> list2 = ...
> 
> for item in list2:
> list1.append(item)

How do you think this helps you?

>>> list1 = [ ['a','b','c'], [1,2,3,4], [5,6,7]]
>>> list2 = []
>>> for item in list1: list2.append(item)
...
>>> list2
[['a', 'b', 'c'], [1, 2, 3, 4], [5, 6, 7]]
>>> list1[1].append('boo!')
>>> list2
[['a', 'b', 'c'], [1, 2, 3, 4, 'boo!'], [5, 6, 7]]
>>>

If you want a deep copy, ask for a deep copy:

>>> list1 = [ ['a','b','c'], [1,2,3,4], [5,6,7]]
>>> list2 = []
>>> import copy
>>> list2.extend(copy.deepcopy(list1))
>>> list2
[['a', 'b', 'c'], [1, 2, 3, 4], [5, 6, 7]]
>>> list1[1].append('boo!')
>>> list2
[['a', 'b', 'c'], [1, 2, 3, 4], [5, 6, 7]]
>>>

> but maybe this is too slow.. or isn't? ideally i'd like to have
> something like reserve in c++....

Unfortunately there's no "reserve" in Python, but sometimes you
can get the same (very modest) kind of speedup by making the
target list originally long, keeping its "actual active length"
as a separate variable, and assigning to appropriate slices.

However, we're talking about MICRO-optimizations here -- a few
percents here and there -- and compared to the inevitable, BIG
overhead of making deep copies I suspect they'll be barely
measurable in your case.

> so let's say i have a list which len() is 30. now i want to insert
> 20elements... wouldn't it be faster to somehow resize the list directly
> to 50, and then add the elements?

Marginally, yes.  Irrelevantly, of course...:

import time

def ex30_to_50_simple(list30, list20):
    for x in list20: list30.append(x)

def ex30_to_50_smart(list30, list20):
    list30.extend(20*[None])
    for i in xrange(20):
        list30[30+i] = list20[i]

def timit(ex30_to_50_func):
    list30_org = range(30)
    list20_org = range(20)
    totim = 0.0
    clock = time.clock
    for x in range(100000):
        list30_temp = list30_org[:]
        start = clock()
        ex30_to_50_func(list30_temp, list20_org)
        stend = clock()
        totim += stend-start
    return totim

def ex30_to_50_obvious(list30, list20):
    list30.extend(list20)

for n in range(3):
    for f in ex30_to_50_simple, ex30_to_50_smart, ex30_to_50_obvious:
        print '%.2f %s' % (timit(f), f.func_name)

[alex at lancelot pyRXP]$ python2.2 -O ba.py
2.39 ex30_to_50_simple
2.28 ex30_to_50_smart
0.36 ex30_to_50_obvious
2.44 ex30_to_50_simple
2.38 ex30_to_50_smart
0.34 ex30_to_50_obvious
2.32 ex30_to_50_simple
2.43 ex30_to_50_smart
0.26 ex30_to_50_obvious

the so-called 'smart' function generally beats the simple one
by a few hundreds of a second over 100,000 repetitions -- of
course, neither of them is anywhere close to a match for the
one obvious solution.  It's a bit sharper with Python 2.3, but
the overall indication remains the same:

[alex at lancelot pyRXP]$ python2.3 -O ba.py
2.17 ex30_to_50_simple
1.73 ex30_to_50_smart
0.37 ex30_to_50_obvious
2.22 ex30_to_50_simple
1.77 ex30_to_50_smart
0.36 ex30_to_50_obvious
2.30 ex30_to_50_simple
1.66 ex30_to_50_smart
0.27 ex30_to_50_obvious


Note that all three functions have identical semantics (for
lists of the indicated lengths): none of them deep-copies
anything at all.  Once you DO have deep copies, the overhead
of that dominates, though the obvious solution remains
marginally better (skipping the alleged 'smart' one here):

import time
import copy

def ex30_to_50_deep_simple(list30, list20):
    for x in copy.deepcopy(list20): list30.append(x)

def timit(ex30_to_50_func):
    list30_org = range(30)
    list20_org = range(20)
    totim = 0.0
    clock = time.clock
    for x in range(10000):
        list30_temp = list30_org[:]
        start = clock()
        ex30_to_50_func(list30_temp, list20_org)
        stend = clock()
        totim += stend-start
    return totim

def ex30_to_50_deep_obvious(list30, list20):
    list30.extend(copy.deepcopy(list20))

for n in range(3):
    for f in ex30_to_50_deep_simple, ex30_to_50_deep_obvious:
        print '%.2f %s' % (timit(f), f.func_name)

[alex at lancelot pyRXP]$ python2.2 -O ba.py
2.46 ex30_to_50_deep_simple
2.22 ex30_to_50_deep_obvious
2.50 ex30_to_50_deep_simple
2.24 ex30_to_50_deep_obvious
2.47 ex30_to_50_deep_simple
2.23 ex30_to_50_deep_obvious
[alex at lancelot pyRXP]$ python2.3 -O ba.py
2.20 ex30_to_50_deep_simple
1.96 ex30_to_50_deep_obvious
2.12 ex30_to_50_deep_simple
1.99 ex30_to_50_deep_obvious
2.11 ex30_to_50_deep_simple
1.94 ex30_to_50_deep_obvious

Note that I'm doing TEN thousand repetitions here, NOT a *hundred*
thousands like I did before.  *Deep copying AIN'T FAST*.



> i'm worried about how many times would the list resize itself to be able
> to contain the additional 20elements if i would add them one-by-one

I think you're worrying about the wrong things: study listobject.c in
the Python sources to see why.  Rather, I think you should worry about
the need for deep copies.  Do you REALLY need to keep and reuse the
small lists that you're adding to the large list, so that the deep
copy is truly needed, or could you get by in simpler, faster ways?


Alex