Быстрый способ удаления нескольких элементов из списка / очереди

Это продолжение аналогичного вопроса , в котором задавался лучший способ написания

for item in somelist:
    if determine(item):
         code_to_remove_item

, и кажется, что консенсус был о чем-то вроде

somelist[:] = [x for x in somelist if not determine(x)]

. Однако я думаю, что если вы удаляете только несколько элементов, большинство элементов копируются в один и тот же объект, и, возможно, это медленно. В ответе на другой связанный вопрос кто-то предлагает:

for item in reversed(somelist):
    if determine(item):
        somelist.remove(item)

Однако здесь list.remove будет искать элемент, что составляет O (N) по длине списка. Возможно, мы ограничены тем, что список представлен как массив, а не как связанный список, поэтому при удалении элементов нужно будет переместить все, что находится после него. Однако предлагается здесь , что collections.dequeue представлен в виде двусвязного списка. Тогда должно быть возможно удалить в O (1) во время итерации. Как мы на самом деле этого добьемся?

Обновление : Я также провел некоторое время, используя следующий код:

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]>.45) and (x[1]<.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)

и получил:

list comp =  4.01255393028
filtering =  3.59962391853