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

Question

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

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) в длине списка.Возможно, мы ограничены в том, что список представлен в виде массива, а не связанного списка, поэтому при удалении элементов нужно будет перемещать все после него.Тем не менее, здесь предлагается представить коллекцию в виде двусвязного списка.Затем должно быть возможно удалить в 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

Answer 1

Понимание списка является асимптотически оптимальным решением:

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

Он делает только один проход по списку, поэтому выполняется за O (n) времени.Так как вам нужно вызывать define () для каждого объекта, любой алгоритм потребует как минимум O (n) операций.Понимание списка действительно требует некоторого копирования, но это только копирование ссылок на объекты, а не копирование самих объектов.

Удаление элементов из списка в Python - это O (n), так что все, что с помощью remove, popили del внутри цикла будет O (n ** 2).

Кроме того, в списке CPython понимание происходит быстрее, чем для циклов.

Answer 2

Deque оптимизирован для удаления головы и хвоста, а не для произвольного удаления в середине. Само удаление выполняется быстро, но вам все равно придется пройти список до точки удаления. Если вы выполняете итерацию по всей длине, то единственная разница между фильтрацией deque и фильтрацией списка (используя filter или понимание) - это издержки копирования, которые в худшем случае являются постоянным кратным; это все еще операция O (n). Также обратите внимание, что объекты в списке не копируются - только ссылки на них. Так что это не так много накладных расходов.

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

write_i = 0
for read_i in range(len(L)):
    L[write_i] = L[read_i]
    if L[read_i] not in ['a', 'c']:
         write_i += 1
del L[write_i:]

Answer 3

Поскольку list.remove эквивалентно del list[list.index(x)], вы можете сделать:

for idx, item in enumerate(somelist):
    if determine(item):
        del somelist[idx]

Но: вы должны не изменять список, перебирая его. Это укусит вас рано или поздно. Сначала используйте filter или составьте список, а потом оптимизируйте.

Answer 4

Если вам нужно удалить элемент в O (1), вы можете использовать HashMaps

Answer 5

Я сделал удар в этом.Мое решение медленнее, но требует меньших затрат памяти (т.е. не создает новый массив).В некоторых случаях это может быть даже быстрее!

Этот код был отредактирован с момента его первой публикации

У меня были проблемы с timeit, возможно, я поступаю неправильно1007 *

import timeit
setup = """

import random
random.seed(1)
global b
setup_b = [(random.random(), random.random()) for i in xrange(1000)]
c = []
def tokeep(x):
        return (x[1]>.45) and (x[1]<.5)


# define and call to turn into psyco bytecode (if using psyco)
b = setup_b[:]
def listcomp():
   c[:] = [x for x in b if tokeep(x)]
listcomp()

b = setup_b[:]
def filt():
   c = filter(tokeep, b)
filt()

b = setup_b[:]
def forfilt():
   marked = (i for i, x in enumerate(b) if tokeep(x))
   shift = 0
   for n in marked:
      del b[n - shift]
      shift += 1
forfilt()

b = setup_b[:]
def forfiltCheating():
   marked = (i for i, x in enumerate(b) if (x[1] > .45) and (x[1] < .5))

   shift = 0
   for n in marked:
      del b[n - shift]
      shift += 1
forfiltCheating()

"""

listcomp = """
b = setup_b[:]

listcomp()
"""

filt = """
b = setup_b[:]

filt()
"""

forfilt = """
b = setup_b[:]

forfilt()
"""

forfiltCheating = '''
b = setup_b[:]

forfiltCheating()
'''

psycosetup = '''

import psyco
psyco.full()


'''

print "list comp = ", timeit.timeit(listcomp, setup, number = 10000)
print "filtering = ", timeit.timeit(filt, setup, number = 10000)
print 'forfilter = ', timeit.timeit(forfilt, setup, number = 10000)
print 'forfiltCheating = ', timeit.timeit(forfiltCheating, setup, number = 10000)


print '\nnow with psyco \n'
print "list comp = ", timeit.timeit(listcomp, psycosetup + setup, number = 10000)
print "filtering = ", timeit.timeit(filt, psycosetup + setup, number = 10000)
print 'forfilter = ', timeit.timeit(forfilt, psycosetup + setup, number = 10000)
print 'forfiltCheating = ', timeit.timeit(forfiltCheating, psycosetup + setup, number = 10000)

И вот результаты

list comp =  6.56407690048
filtering =  5.64738512039
forfilter =  7.31555104256
forfiltCheating =  4.8994679451

now with psyco 

list comp =  8.0485959053
filtering =  7.79016900063
forfilter =  9.00477004051
forfiltCheating =  4.90830993652

Я, должно быть, что-то не так делаю с психом, потому что на самом деле он работает медленнее.