Re: looping versus comprehension

Discussion in 'Python' started by Chris Angelico, Jan 30, 2013.

  1. On Thu, Jan 31, 2013 at 1:58 AM, Robin Becker <> wrote:
    > however, when I tried an experiment in python 2.7 using the script below I
    > find that the looping algorithms perform better. A naive loop using list +=
    > list would appear to be an O(n**2) operation, but python seems to be doing
    > better than that. Also why does the append version fail so dismally. Is my
    > test coded wrongly or is pre-allocation of the list making this better than
    > expected?


    First off, are you aware that your first three blocks of code and your
    last four produce different results? The first ones flatten the list,
    the others simply convert tuples to lists. With n = 3:

    >>> points = []
    >>> for xy in row:

    points += [xy[0],xy[1]]
    >>> points

    [0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
    >>> map(list,row)

    [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]

    Once that's sorted out, then timings can be played with. But it's
    worth noting that list appending is not going to be O(N*N), because
    it's going to allow room for expansion.

    ChrisA
    Chris Angelico, Jan 30, 2013
    #1
    1. Advertising

  2. On Thu, 31 Jan 2013 02:49:31 +1100, Chris Angelico wrote:

    > it's worth
    > noting that list appending is not going to be O(N*N), because it's going
    > to allow room for expansion.


    This is true for list.append, which is amortized constant time. But it is
    not true for list addition, alist + blist, which is O(N**2) and hence
    gets really, really slow:

    steve@runes:~$ python -m timeit "L = []" "for i in xrange(1000): L = L + [1]"
    100 loops, best of 3: 3.08 msec per loop
    steve@runes:~$ python -m timeit "L = []" "for i in xrange(5000): L = L + [1]"
    10 loops, best of 3: 71 msec per loop
    steve@runes:~$ python -m timeit "L = []" "for i in xrange(25000): L = L + [1]"
    10 loops, best of 3: 2.06 sec per loop


    Notice that as the number of list additions goes up by a factor of 5,
    the time taken goes up by a factor of 25.

    --
    Steven
    Steven D'Aprano, Jan 31, 2013
    #2
    1. Advertising

  3. Chris Angelico

    Roy Smith Guest

    In article <5109fe6b$0$11104$>,
    Steven D'Aprano <> wrote:

    > On Thu, 31 Jan 2013 02:49:31 +1100, Chris Angelico wrote:
    >
    > > it's worth
    > > noting that list appending is not going to be O(N*N), because it's going
    > > to allow room for expansion.

    >
    > This is true for list.append, which is amortized constant time. But it is
    > not true for list addition, alist + blist, which is O(N**2) and hence
    > gets really, really slow:
    >
    > steve@runes:~$ python -m timeit "L = []" "for i in xrange(1000): L = L + [1]"
    > 100 loops, best of 3: 3.08 msec per loop
    > steve@runes:~$ python -m timeit "L = []" "for i in xrange(5000): L = L + [1]"
    > 10 loops, best of 3: 71 msec per loop
    > steve@runes:~$ python -m timeit "L = []" "for i in xrange(25000): L = L + [1]"
    > 10 loops, best of 3: 2.06 sec per loop
    >
    >
    > Notice that as the number of list additions goes up by a factor of 5,
    > the time taken goes up by a factor of 25.


    It's not the addition, per-se, that's the problem. It's the creation of
    a new list each time. If you use +=, it's back to O(n):

    ~$ python -m timeit "L = []" "for i in xrange(1000): L += [1]"
    1000 loops, best of 3: 275 usec per loop

    ~$ python -m timeit "L = []" "for i in xrange(5000): L += [1]"
    1000 loops, best of 3: 1.34 msec per loop

    ~$ python -m timeit "L = []" "for i in xrange(25000): L += [1]"
    100 loops, best of 3: 6.91 msec per loop
    Roy Smith, Jan 31, 2013
    #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. Vedran Furac(
    Replies:
    4
    Views:
    312
    Marc 'BlackJack' Rintsch
    Dec 19, 2008
  2. Paul Butcher
    Replies:
    12
    Views:
    673
    Gary Wright
    Nov 28, 2007
  3. Terry Reedy
    Replies:
    14
    Views:
    293
    Tim Golden
    Aug 25, 2012
  4. Robin Becker

    looping versus comprehension

    Robin Becker, Jan 30, 2013, in forum: Python
    Replies:
    0
    Views:
    91
    Robin Becker
    Jan 30, 2013
  5. Robin Becker

    Re: looping versus comprehension

    Robin Becker, Jan 30, 2013, in forum: Python
    Replies:
    0
    Views:
    110
    Robin Becker
    Jan 30, 2013
Loading...

Share This Page