Discussion in 'Python' started by Ishwor, Dec 27, 2004.

1. IshworGuest

On Sun, 26 Dec 2004 18:37:35 -0500, Terry Reedy <> wrote:
>
> "Ishwor" <> wrote in message
> news:...
> > On Sun, 26 Dec 2004 04:57:17 -0500, Terry Reedy <> wrote:
> >>
> >> "Ishwor" <> wrote in message
> >> news:...
> >> > Hi all
> >> > I have just wrote a small script to compare the speed of list addition
> >> > methods.
> >>
> >> There are two meanings of 'list addition':
> >>
> >> li = li+[item] *copies* the list and adds item
> >>
> >> li += [item] is the same as li.extend([item]) which add item to the end
> >> of
> >> the list *without* copying.
> >>
> >> Of course, extending a list is faster than copying + one more.
> >>

> >
> > I agree with you that list extending is faster way to add as compared
> > to method 1. also that method 2 is mapped to 'extend()' anyway,

>
> As near as I could tell from what you posted (and I snipped), method 2 was
> about the same as 1 and not mapped to extend().

ah.. well....what to tell?? i wanted the method 2 to be l2.extend() @#\$@#\$!!!!!
hhah.. thanks for that anyway.

> > but
> > why is the method 3 ( l3.extend() ) in my example code talking only
> > nearly 1% of time to complete as compared to method 1/2???

>
> Because writing 1 pointer takes 1/100th as long as writing 100 pointers (in
> the C code of CPython). You used lists long enough for the difference
> between O(n) and O(n**2) behavior to show.

theres the correct output AFAIK is -

@@@@@@@
Method 1 done in (average finish time(out of 3)) - 1.3589999676
Method 2 done in (average finish time(out of 3)) - 0.0213334560
Method 3 done in (average finish time(out of 3)) - 0.0256667137
@@@@@@@

@@@@@@@
Method 1 done in (average finish time(out of 3)) - 1.3593332767
Method 2 done in (average finish time(out of 3)) - 0.0306665897
Method 3 done in (average finish time(out of 3)) - 0.0213334560
@@@@@@@

@@@@@@@
Method 1 done in (average finish time(out of 3)) - 1.3593332767
Method 2 done in (average finish time(out of 3)) - 0.0203335285
Method 3 done in (average finish time(out of 3)) - 0.0203332901
@@@@@@@

so indeed method 2 (l2.extend() ) is the fastest ?? In 2/3 times,
method 3 (l3 += [x] seems faster than method 1/2 in my P2.4GHZ machine
with 512mb??? :-(
Could u run the code in your machine and perhaps and let me know what
the average speed is??
The code is -

#compare the speeds of 3 different type of list element addition
import time
def method(TYPE):
if TYPE == 1:
l1 = [];
finish = 0;
start = 0;
start = time.time();
for y in range(0,3):
for x in range(0,10000):
l1 = l1 + [x];# type 1
l1 = [];
finish += time.time();
averageFinish = finish/3;
#m = float(finish-start);
print "Method 1 done in (average finish time(out of 3)) -
%.10f" %(averageFinish-start);

if TYPE == 2:
l2 = [];
finish = 0;
start = 0;
start = time.time();
for y in range(0,3):
for x in range(0,10000):
l2.extend([x]);# type 2
l2 = [];
finish += time.time();
averageFinish = finish/3;
#m = float(finish-start);
print "Method 2 done in (average finish time(out of 3)) -
%.10f" %(averageFinish-start);

if TYPE == 3:
l3 = [];
finish = 0;
start = 0;
start = time.time();
for y in range(0,3):
for x in range(0,10000):
l3 += [x];# type 3
l3 = [];
finish += time.time();
averageFinish = finish/3;
#m = float(finish-start);
print "Method 3 done in (average finish time(out of 3)) -
%.10f" %(averageFinish-start);

print "@@@@@@@";
method(1);
method(2);
method(3);
print "@@@@@@@";

[snip]

Thanks. ;-)
--
cheers,
Ishwor Gurung

Ishwor, Dec 27, 2004

2. Steven BethardGuest

Ishwor wrote:
> Could u run the code in your machine and perhaps and let me know what
> the average speed is??
> The code is -

[snip code not using timeit]

Are you aware of the timeit module? It can do most of these timings for
you. Here's the code I used:

------------------------------ extend.py ------------------------------
lst = []
for item in items:
lst = lst + [item]

lst = []
for item in items:
lst += [item]

def extend(items):
lst = []
for item in items:
lst.extend([item])

def extend_ext(items):
lst = []
ext = lst.extend
for item in items:
ext([item])

def append(items):
lst = []
for item in items:
lst.append(item)

----------------------------------------------------------------------

and here's the commands I ran (using Python 2.4)[1]:

\$ python -m timeit -s "import extend; items = range(10000)"
10 loops, best of 3: 588 msec per loop

\$ python -m timeit -s "import extend; items = range(10000)"
100 loops, best of 3: 9.68 msec per loop

\$ python -m timeit -s "import extend; items = range(10000)"
"extend.extend(items)"
100 loops, best of 3: 11.5 msec per loop

\$ python -m timeit -s "import extend; items = range(10000)"
"extend.extend_ext(items)"
100 loops, best of 3: 9.09 msec per loop

\$ python -m timeit -s "import extend; items = range(10000)"
"extend.append(items)"
100 loops, best of 3: 4.5 msec per loop

A few things worth noting:

(1) I didn't see the top of this thread, but I'm assuming that you've
got a conditional or something in your real loop or you could just use
lst.extend(items) without ever iterating over the items list. Your real
code may actually require extend-style functionality, but as the results
above show, if you really only have one item to add, list.append is
definitely the better way to go.

(2) Yes, using += is slightly faster than list.extend, but only because
"lst.extend" requires an extra attribute lookup. If you factor that out
(like I did with the line "ext = lst.extend") then list.extend is
slightly faster. (Not surprising, as the function list_inplace_concat
(+=) calls the function listextend (list.extend) in listobject.c)

(3) That being said, extend_ext is almost certainly premature
optimization. =)

Steve

[1] You can still use timeit without Python 2.4, but you'll have to call
timeit.py directly instead of the "python -m timeit" command I used.

Steven Bethard, Dec 27, 2004

3. Nick CoghlanGuest

Steven Bethard wrote:
> (1) I didn't see the top of this thread, but I'm assuming that you've
> got a conditional or something in your real loop or you could just use
> lst.extend(items) without ever iterating over the items list. Your real
> code may actually require extend-style functionality, but as the results
> above show, if you really only have one item to add, list.append is
> definitely the better way to go.

Just to prove Steven's point about avoiding the for loop if you can (timings
here use the same timeit command as Steven did):

10 loops, best of 3: 469 msec per loop

100 loops, best of 3: 6.88 msec per loop

"extend.extend(items)"
100 loops, best of 3: 8.77 msec per loop

"extend.extend_ext(items)"
100 loops, best of 3: 6.56 msec per loop

"extend.append(items)"
100 loops, best of 3: 3.68 msec per loop

"extend.extend_no_loop(items)"
10000 loops, best of 3: 82.3 usec per loop

The definition of 'extend_no_loop' is:

def extend_no_loop(items):
lst = []
lst.extend(items)

Note that if you do have a conditional expression in the for loop (e.g. "only
add items greater than zero", it is worth checking the timings for calling
extend with a generator expression or list comprehension that filters out the
values you don't want)

Cheers,
Nick.

--
Nick Coghlan | | Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net

Nick Coghlan, Dec 27, 2004