Re: list addition methods compared.

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

  1. Ishwor

    Ishwor Guest

    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 -

    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
    Ishwor, Dec 27, 2004
    #1
    1. Advertising

  2. 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.
    Steven Bethard, Dec 27, 2004
    #2
    1. Advertising

  3. Ishwor

    Nick Coghlan Guest

    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 | | Brisbane, Australia
    ---------------------------------------------------------------
    http://boredomandlaziness.skystorm.net
    Nick Coghlan, Dec 27, 2004
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Marc H.
    Replies:
    2
    Views:
    328
    Martin Franklin
    Mar 13, 2005
  2. Daniel Mark
    Replies:
    9
    Views:
    12,448
    Simon Brunning
    Sep 19, 2006
  3. Kenneth McDonald
    Replies:
    5
    Views:
    315
    Kenneth McDonald
    Sep 26, 2008
  4. Robert Yacobellis
    Replies:
    1
    Views:
    156
    Steven D'Aprano
    Apr 21, 2013
  5. Lele Gaifax
    Replies:
    0
    Views:
    129
    Lele Gaifax
    Apr 21, 2013
Loading...

Share This Page