list IndexError

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

  1. Ishwor

    Ishwor Guest

    i am trying to remove an item 'e' from the list l but i keep getting IndexError.
    I know the size of the list l is changing in the for loop & its sort
    of trivial task but i found no other way than to suppress the
    IndexError by doing a pass. any other ways you guys can suggest? Also
    is this a good or bad habit in Python? someone may perhaps suggest a
    better way which i am unaware of?? the deletion could be invoked from
    user input (command line) as well so its not limited to 'e'( as in my
    code)

    >>> l

    ['a', 'b', 'c', 'e', 'm']
    >>> for i in range(0,len(l)):

    if l == 'e':
    l.pop(i);


    'e'

    Traceback (most recent call last):
    File "<pyshell#389>", line 2, in -toplevel-
    if l == 'e':
    IndexError: list index out of range
    >>> l

    ['a', 'b', 'c', 'm']


    ==Using suppressing technique( a bad one though :) )==
    >>> l

    ['a', 'b', 'c', 'm', 'd']
    >> for i in range(0,len(l)):

    try:
    if l == 'e':
    l.pop(i);
    except IndexError:
    pass;

    >>> l

    ['a', 'b', 'c', 'm', 'd']

    ==Using suppressing technique====

    Any type of code changing/improving ways is heartily welcomed ;-)

    --
    cheers,
    Ishwor Gurung
    Ishwor, Dec 22, 2004
    #1
    1. Advertising

  2. Ishwor wrote:
    > i am trying to remove an item 'e' from the list l


    I thought it might be helpful to code some of the alternatives you've
    been given and look at the timings to put things into perspective. The
    code:

    -------------------- remove.py --------------------
    def remove_lc(x, lst):
    lst[:] = [item for item in lst if item != x]

    def remove_list(x, lst):
    result = []
    for item in lst:
    if item != x:
    result.append(item)
    lst[:] = result

    def remove_filter(x, lst):
    lst[:] = filter(lambda item: item != x, lst)

    def remove_xrange(x, lst):
    for i in xrange(len(lst)-1, -1, -1):
    if lst == x:
    del lst

    def remove_remove(x, lst):
    while x in lst:
    lst.remove(x)

    def remove_try(x, lst):
    try:
    while True:
    lst.remove(x)
    except ValueError:
    pass

    def remove_ishwor(x, lst):
    for item in lst[:]:
    if item == x:
    lst.remove(x);
    --------------------------------------------------

    First, some timings when only 1 out of every 1000 elements needs to be
    removed. Timings were taken with Python 2.4 on a 2.26 Ghz Windows box
    using:
    $ python -m timeit -s "import remove; lst = [x % 1000 for x in
    xrange(10000)]" "remove.remove_<name>(500, lst)"

    remove_remove: 516 usec per loop
    remove_try: 604 usec per loop
    remove_ishwor: 1.61 msec per loop
    remove_xrange: 2.29 msec per loop
    remove_lc: 2.37 msec per loop
    remove_list: 5.3 msec per loop
    remove_filter: 5.65 msec per loop

    Now, some timings when 1 out of every 10 elements needs to be removed.
    Timings were taken using:
    $ python -m timeit -s "import remove; lst = [x % 10 for x in
    xrange(10000)]" "remove.remove_<name>(5, lst)"

    remove_lc: 2.03 msec per loop
    remove_xrange: 2.08 msec per loop
    remove_list: 4.72 msec per loop
    remove_filter: 5.17 msec per loop
    remove_try: 30.7 msec per loop
    remove_ishwor: 31.5 msec per loop
    remove_remove: 60.2 msec per loop



    The moral of the story here is that, if the items to be removed only
    make up a very small percentage of the list, an approach like
    remove_remove or remove_try might be okay. On the other hand, if you
    expect the items to be removed will make up even a moderate percentage
    of the list (e.g. 10%), then remove_lc or remove_xrange is a vastly
    better alternative.

    Steve
    Steven Bethard, Dec 22, 2004
    #2
    1. Advertising

  3. Ishwor

    Ishwor Guest

    On Wed, 22 Dec 2004 21:42:16 GMT, Steven Bethard
    <> wrote:
    > Ishwor wrote:
    > > i am trying to remove an item 'e' from the list l

    >
    > I thought it might be helpful to code some of the alternatives you've
    > been given and look at the timings to put things into perspective. The
    > code:
    >
    > -------------------- remove.py --------------------
    > def remove_lc(x, lst):
    > lst[:] = [item for item in lst if item != x]
    >
    > def remove_list(x, lst):
    > result = []
    > for item in lst:
    > if item != x:
    > result.append(item)
    > lst[:] = result
    >
    > def remove_filter(x, lst):
    > lst[:] = filter(lambda item: item != x, lst)
    >
    > def remove_xrange(x, lst):
    > for i in xrange(len(lst)-1, -1, -1):
    > if lst == x:
    > del lst
    >
    > def remove_remove(x, lst):
    > while x in lst:
    > lst.remove(x)
    >
    > def remove_try(x, lst):
    > try:
    > while True:
    > lst.remove(x)
    > except ValueError:
    > pass
    >
    > def remove_ishwor(x, lst):
    > for item in lst[:]:
    > if item == x:
    > lst.remove(x);
    > --------------------------------------------------
    >
    > First, some timings when only 1 out of every 1000 elements needs to be
    > removed. Timings were taken with Python 2.4 on a 2.26 Ghz Windows box
    > using:
    > $ python -m timeit -s "import remove; lst = [x % 1000 for x in
    > xrange(10000)]" "remove.remove_<name>(500, lst)"
    >
    > remove_remove: 516 usec per loop
    > remove_try: 604 usec per loop
    > remove_ishwor: 1.61 msec per loop
    > remove_xrange: 2.29 msec per loop
    > remove_lc: 2.37 msec per loop
    > remove_list: 5.3 msec per loop
    > remove_filter: 5.65 msec per loop
    >
    > Now, some timings when 1 out of every 10 elements needs to be removed.
    > Timings were taken using:
    > $ python -m timeit -s "import remove; lst = [x % 10 for x in
    > xrange(10000)]" "remove.remove_<name>(5, lst)"
    >
    > remove_lc: 2.03 msec per loop
    > remove_xrange: 2.08 msec per loop
    > remove_list: 4.72 msec per loop
    > remove_filter: 5.17 msec per loop
    > remove_try: 30.7 msec per loop
    > remove_ishwor: 31.5 msec per loop
    > remove_remove: 60.2 msec per loop
    >
    > The moral of the story here is that, if the items to be removed only
    > make up a very small percentage of the list, an approach like
    > remove_remove or remove_try might be okay. On the other hand, if you
    > expect the items to be removed will make up even a moderate percentage
    > of the list (e.g. 10%), then remove_lc or remove_xrange is a vastly
    > better alternative.
    >
    > Steve
    > --
    > http://mail.python.org/mailman/listinfo/python-list
    >

    umm... looks good.. i am running these task sets on my box as well
    slightly slower than yours 2.4Ghz... thanx Steve. :) now i'll sit
    back and dwell a bit deeper into it now.


    --
    cheers,
    Ishwor Gurung
    Ishwor, Dec 22, 2004
    #3
  4. Ishwor

    Peter Otten Guest

    Steven Bethard wrote:

    > I thought it might be helpful to code some of the alternatives you've
    > been given and look at the timings to put things into perspective. The
    > code:
    >
    > -------------------- remove.py --------------------
    > def remove_lc(x, lst):
    > lst[:] = [item for item in lst if item != x]


    [snip]

    > $ python -m timeit -s "import remove; lst = [x % 1000 for x in
    > xrange(10000)]" "remove.remove_<name>(500, lst)"


    I do not think it measures what you think it measures.

    A statement in the -s option is only run once, so you have to be careful
    with mutable data and pass a copy of your sample to the function about to
    be timed. The following example illustrates the problem:

    $ py24 -m timeit -n5 -r1 -s"r=[0]" -s"def f(r): print r; r[0] += 1" "f(r)"
    [0]
    [1]
    [2]
    [3]
    [4]
    5 loops, best of 1: 106 usec per loop

    Peter
    Peter Otten, Dec 23, 2004
    #4
  5. Ishwor

    Nick Coghlan Guest

    Steven Bethard wrote:
    > Ishwor wrote:
    >
    >> i am trying to remove an item 'e' from the list l

    >
    >
    > I thought it might be helpful to code some of the alternatives you've
    > been given and look at the timings to put things into perspective. The
    > code:
    >
    > -------------------- remove.py --------------------
    > def remove_lc(x, lst):
    > lst[:] = [item for item in lst if item != x]
    >
    > def remove_try(x, lst):
    > try:
    > while True:
    > lst.remove(x)
    > except ValueError:
    > pass
    >

    I'd suggest a slightly different definition for remove_try:

    def remove_try(x, lst):
    idx = 0
    try:
    while True:
    idx = lst.index(x, idx)
    del s[idx]
    except ValueError:
    pass

    This avoids the 'restart from the beginning' problem with the current approach.

    Anyway, pitting that against Steve's remove_lc on a 2.6 GHz hyperthreaded P4
    gives the following results for different percentages of removed values:

    ..1% lc: 2010 usec try: 467 usec
    10% lc: 1810 usec try: 427 usec
    50% lc: 1010 usec try: 273 usec
    90% lc: 214 usec try: 61 usec

    I know why the filtration version gets faster as the percentage increases (the
    resulting list is smaller), but I'm not sure why the in-place version is getting
    faster (as it makes more method calls and performs more deletions). One
    possibility is that as the list gets shorter due to the deletions, the whole
    thing gets pulled into the processor's cache and the operations start going
    blazingly fast.

    Cheers,
    Nick.

    P.S. These were the commands I timed:

    ..1%:
    python -m timeit -s "import remove; lst = [bool(x % 1000) for x in
    xrange(10000)]" "remove.remove_<name>(False, lst)"

    10%:
    python -m timeit -s "import remove; lst = [bool(x % 10) for x in xrange(10000)]"
    "remove.remove_<name>(False, lst)"

    50%:
    python -m timeit -s "import remove; lst = [bool(x % 2) for x in xrange(10000)]"
    "remove.remove_<name>(False, lst)"

    90%:
    python -m timeit -s "import remove; lst = [not bool(x % 10) for x in
    xrange(10000)]" "remove.remove_<name>(False, lst)"

    And just to prove they're both still doing the right thing in that last example:

    Py> import remove
    Py> lst = [not bool(x % 10) for x in xrange(10000)]
    Py> len(lst)
    10000
    Py> remove.remove_lc(False, lst)
    Py> len(lst)
    1000
    Py> lst = [not bool(x % 10) for x in xrange(10000)]
    Py> len(lst)
    10000
    Py> remove.remove_try(False, lst)
    Py> len(lst)
    1000

    --
    Nick Coghlan | | Brisbane, Australia
    ---------------------------------------------------------------
    http://boredomandlaziness.skystorm.net
    Nick Coghlan, Dec 23, 2004
    #5
  6. Ishwor

    Nick Coghlan Guest

    Peter Otten wrote:
    > I do not think it measures what you think it measures.


    Ah, good point. . . so we were actually measuring how long it takes to make zero
    replacements on the modified list, which explains the downward trend of the
    timings (as the modified list gets shorter).

    Adding the list copy (using lst[:] in the call to the remove() method) gives me
    these numbers:

    ..1% lc: 2410 usec try: 617 usec
    10% lc: 2020 usec try: 7340 usec
    50% lc: 1780 usec try: 34300 usec
    90% lc: 1450 usec try: 61000 usec

    Right, that's *far* more like the numbers I was expecting :)

    And now they demonstrate what they were meant to demonstrate - that there's a
    reason filtration is the recommended approach!

    Cheers,
    Nick.

    --
    Nick Coghlan | | Brisbane, Australia
    ---------------------------------------------------------------
    http://boredomandlaziness.skystorm.net
    Nick Coghlan, Dec 23, 2004
    #6
  7. Steven Bethard wrote:
    > Ishwor wrote:
    >
    >> i am trying to remove an item 'e' from the list l

    >
    >
    > I thought it might be helpful to code some of the alternatives you've
    > been given and look at the timings to put things into perspective.


    Corrected timings[1] using:

    $ python -m timeit -s "import remove" "remove.remove_<name>(500, [x %
    1000 for x in xrange(10000)])"

    remove_xrange: 5.46 msec per loop
    remove_lc: 5.48 msec per loop
    remove_try: 6.31 msec per loop
    remove_ishwor: 7.03 msec per loop
    remove_list: 8.38 msec per loop
    remove_filter: 9.08 msec per loop
    remove_remove: 9.98 msec per loop

    and using:

    $ python -m timeit -s "import remove" "remove.remove_<name>(50, [x % 100
    for x in xrange(10000)])"

    remove_lc: 5.12 msec per loop
    remove_xrange: 5.8 msec per loop
    remove_list: 7.9 msec per loop
    remove_filter: 8.29 msec per loop
    remove_try: 30.3 msec per loop
    remove_ishwor: 30.7 msec per loop
    remove_remove: 55.2 msec per loop

    So, when timed correctly =) list comprehensions and xrange are faster
    even when the items to be removed are only 0.1% of the data.

    Steve

    [1] Thanks Peter!

    P.S. For fun, I played around with the data to see if I could find a
    dataset on which one of the "slower" techniques is faster than remove_lc
    or remove_xrange. Here's one:

    $ python -m timeit -s "import remove" "remove.remove_<name>(25, [x % 50
    for x in xrange(100)])"

    remove_remove: 53.3 usec per loop
    remove_xrange: 57.7 usec per loop
    remove_try: 58.8 usec per loop
    remove_ishwor: 58.9 usec per loop
    remove_lc: 65.4 usec per loop
    remove_list: 93.7 usec per loop
    remove_filter: 95.8 usec per loop
    Steven Bethard, Dec 23, 2004
    #7
    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. Ishwor

    Re: list IndexError

    Ishwor, Dec 22, 2004, in forum: Python
    Replies:
    4
    Views:
    292
    Steve Holden
    Dec 23, 2004
  2. Mike C. Fletcher

    Re: list IndexError

    Mike C. Fletcher, Dec 23, 2004, in forum: Python
    Replies:
    5
    Views:
    287
    Jeff Shannon
    Dec 23, 2004
  3. Ishwor

    Re: list IndexError

    Ishwor, Dec 23, 2004, in forum: Python
    Replies:
    2
    Views:
    275
    Alex Martelli
    Dec 27, 2004
  4. Replies:
    5
    Views:
    663
    Steven Bethard
    Mar 31, 2005
  5. Replies:
    36
    Views:
    1,596
    MonkeeSage
    Oct 11, 2006
Loading...

Share This Page