Velocity Reviews > Re: list addition methods compared.

Re: list addition methods compared.

Ishwor
Guest
Posts: n/a

 12-27-2004
On Sun, 26 Dec 2004 18:37:35 -0500, Terry Reedy <(E-Mail Removed)> wrote:
>
> "Ishwor" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
> > On Sun, 26 Dec 2004 04:57:17 -0500, Terry Reedy <(E-Mail Removed)> wrote:
> >>
> >> "Ishwor" <(E-Mail Removed)> wrote in message
> >> news:(E-Mail Removed)...
> >> > 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 -

C:\Python24\file\PyFiles>python -O listadditioncompare.py
@@@@@@@
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
@@@@@@@

C:\Python24\file\PyFiles>python -O listadditioncompare.py
@@@@@@@
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
@@@@@@@

C:\Python24\file\PyFiles>python -O listadditioncompare.py
@@@@@@@
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

Steven Bethard
Guest
Posts: n/a

 12-27-2004
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 ------------------------------
def add(items):
lst = []
for item in items:
lst = lst + [item]

def iadd(items):
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)"
"extend.add(items)"
10 loops, best of 3: 588 msec per loop

\$ python -m timeit -s "import extend; items = range(10000)"
"extend.iadd(items)"
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.

Nick Coghlan
Guest
Posts: n/a

 12-27-2004
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):

"extend.add(items)"
10 loops, best of 3: 469 msec per loop

"extend.iadd(items)"
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 | http://www.velocityreviews.com/forums/(E-Mail Removed) | Brisbane, Australia
---------------------------------------------------------------
http://boredomandlaziness.skystorm.net

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post DG Python 3 07-22-2009 07:24 PM Kenneth McDonald Ruby 5 09-26-2008 03:09 PM Daniel Mark Python 9 09-19-2006 01:16 PM Barret Bonden Cisco 0 06-24-2005 02:49 AM floydkelley@gmail.com Cisco 0 04-12-2005 03:15 AM

Advertisments