Reducing complexity of following code

What I wanted to do was to search in a list and remove a value .

So I wrote the following code

for x in range(10):
   if x in list1:
      list1.remove(x)

Does this function of order ~ (n^2) since first it looks for the value and then it deletes and pushes the rest of the values backwards ??

Also is there a way to turn this in开发者_StackOverflow社区 order n by using try/except

try:
  for x in range(10):
    list1.remove(x)
except ValueError:
  # make it go back to next iteration 

Use:

L = [x for x in L if x not in removal_list]

removal_list can be any container, but if you use a set() or a frozenset() you will achieve O(n) (with n = len(L)).

This sounds like a job for filter():

>>> filter(lambda x: not x in (4, 5, 7), xrange(10))
[0, 1, 2, 3, 6, 8, 9]

Update: one more example where I construct a list using list comprehension:

>>> filter(lambda x: not x[0] in (4, 5, 7), [[a] for a in xrange(10)])
[[0], [1], [2], [3], [6], [8], [9]]

Slice replacement:

a[:] = ( l for l in a if l not in set(list_of_removable))

Pythons not my area, but some things spring to mind. First, how big is the list, because you are going to iterate over it a number of times. If it's large it might be a better idea to flip things around so you only iterate over it once.

Second, if Python is like Java, then there is a rule for good code - Do not use exceptions for process flow. This rules out your second suggestion. It's also likely that it will perform badly.

Like Giovanni Bajo suggests, list comprehension is cool, but assuming you'll use the result only once, generators are even better:

l = [1,23,2,24,3,26,1]
(x for x in l if x not in xrange(10))

xrange() is a generator as well and is faster than range() If you want to use the result more than once I'd go for:

[x for x in l if x not in xrange(10)]

To answer the original question: There is no getting around the fact that you will have to compare each element of the list-to-remove-elements-from to each element of the list-containing-removable-elements. So in that sense, every version of this code is O(N^2) (assuming we can have arbitrarily many elements in each list). You can hide the loops by using a variety of constructs (and in many cases it will be faster, because the looping can be done "internally" in the C code of the interpreter rather than by interpreting more bytecode), but the loops are still there (and remember that constant factors are ignored by big-O analysis).