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

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

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

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

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

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

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

Однако здесь list.remove будет искать элемент, который является O (N) в длине списка. Может быть, мы ограничены тем, что список представлен как массив, а не связанный список, поэтому для удаления элементов необходимо будет переместить все после него. Тем не менее, предлагается здесь, что collection.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

Ответы

Ответ 1

Понимание списка - это асимптотически оптимальное решение:

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

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

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

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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:]

Ответ 5

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

Этот код был отредактирован с момента его первого размещения

У меня были проблемы с timeit, я мог бы сделать это неправильно.

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

Я должен делать что-то неправильно с psyco, потому что он на самом деле работает медленнее.