list addition methods compared.

[Ishwor]

On Sun, 26 Dec 2004 18:37:35 -0500, Terry Reedy <tjreedy at udel.edu> wrote:
> 
> "Ishwor" <ishwor.gurung at gmail.com> wrote in message 
> news:34534aed04122615176056a0a9 at mail.gmail.com...
> > On Sun, 26 Dec 2004 04:57:17 -0500, Terry Reedy <tjreedy at udel.edu> wrote:
> >>
> >> "Ishwor" <ishwor.gurung at gmail.com> wrote in message
> >> news:34534aed0412252012638c85fd at mail.gmail.com...
> >> > 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