newbie : removing recurring element from lists

Alex Martelli aleax at aleax.it
Fri Oct 11 15:00:44 EDT 2002


Andrew Koenig wrote:
        ...
> Mark> Its probably a bit cleaner to phrase that as
> 
> Mark> while yourValue in aList:
> Mark>     aList.remove(yourValue)
> 
> But that's worst-case quadratic in the length of the list.
> Instead, how about
> 
>         aList = filter(lambda x: x != yourValue, aList)
> 
> or use a list comprehension as suggested earlier.
> 
> I know about the evils of premature optimization, but I think there is
> a difference between optimizing prematurely (which is rarely necessary)
> and avoiding premature pessimization (which can make a huge difference).

As one of the paladins of avoiding premature optimization, I entirely
concur with you.  Knowingly using an O(N squared) solution where
an O(N) one of comparable code complexity is available may perhaps
be defensible only when there are known, provable, strict bounds on
N, or some other spot in the program is known to have unavoidably
even-worse O() behavior.  Overall, IMHO, the best approach is to "almost
forget" the existence of the bad-big-O idioms and have the good-big-O 
ones become nearly automatic habits.

Just one nit: _premature_ optimization is NOT "rarely necessary", but
"never" -- otherwise, it wouldn't be premature, by definition:-).


Alex





More information about the Python-list mailing list