title: Fast way to remove a few items from a list/queue
body: <p>This is a follow up to a similar <a href="https://stackoverflow.com/questions/1207406/remove-items-from-a-list-while-iterating-in-python/1207461#comment-6561137">question</a> which asked the best way to write</p>
  
  <pre><code>for item in somelist:
      if determine(item):
           code_to_remove_item
  </code></pre>
  
  <p>and it seems the consensus was on something like</p>
  
  <pre><code>somelist[:] = [x for x in somelist if not determine(x)]
  </code></pre>
  
  <p>However, I think if you are only removing a few items, most of the items are being copied into the same object, and perhaps that is slow. In an <a href="https://stackoverflow.com/questions/18418/elegant-way-to-remove-items-from-sequence-in-python/181062#181062">answer</a> to another related <a href="https://stackoverflow.com/questions/18418/elegant-way-to-remove-items-from-sequence-in-python">question</a>, someone suggests:</p>
  
  <pre><code>for item in reversed(somelist):
      if determine(item):
          somelist.remove(item)
  </code></pre>
  
  <p>However, here the <code>list.remove</code> will search for the item, which is O(N) in the length of the list. May be we are limited in that the list is represented as an array, rather than a linked list, so removing items will need to move everything after it. However, it is suggested <a href="http://wiki.python.org/moin/TimeComplexity" rel="noreferrer">here</a> that collections.dequeue is represented as a doubly linked list. It should then be possible to remove in O(1) while iterating. How would we actually accomplish this?</p>
  
  <p><strong>Update</strong>:
  I did some time testing as well, with the following code:</p>
  
  <pre><code>import timeit
  setup = """
  import random
  random.seed(1)
  b = [(random.random(),random.random()) for i in xrange(1000)]
  c = []
  def tokeep(x):
          return (x[1]&gt;.45) and (x[1]&lt;.5)
  """
  listcomp = """
  c[:] = [x for x in b if tokeep(x)]
  """
  filt = """
  c = filter(tokeep, b)
  """
  print "list comp = ", timeit.timeit(listcomp,setup, number = 10000)
  print "filtering = ", timeit.timeit(filt,setup, number = 10000)
  </code></pre>
  
  <p>and got:</p>
  
  <pre><code>list comp =  4.01255393028
  filtering =  3.59962391853
  </code></pre>