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

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

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

5 Solutions collect form web for “Быстрый способ удалить несколько элементов из списка / очереди”

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

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

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

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

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

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

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

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

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

Дека оптимизирована для удаления головы и хвоста, а не для произвольного удаления посередине. Само удаление происходит быстро, но вам все равно придется перемещать список в точку удаления. Если вы выполняете итерацию по всей длине, то единственная разница между фильтрацией 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:] 

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

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

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

 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, потому что он на самом деле работает медленнее.

 
Interesting Posts for Van-Lav

python все возможные пары из 2 элементов списка и получение индекса этой пары

Опубликовать в API Django rest framework, но всегда получать ошибку «Это поле обязательно»

Cython: использование импортированного класса в объявлении типа

как получить endianess в Java или python?

Удалите один фрейм данных из другого с помощью Pandas

python bisect, можно работать с нисходящими отсортированными списками?

Bash: рекурсивно записывать строку в файл из максимального столбца

Не удалось выполнить проверку CSRF. Запрос прерван

python asyncio, как создавать и отменять задачи из другого потока

подпроцесс Popen блокирует PyQt GUI

Итератор Python пуст после выполнения некоторых действий на нем

Вычисление площади под кривой, заданной набором координат, не зная функции

Как разместить и выровнять легенду фигуры matplotlib?

Я встретил ошибку, когда я использую функции преобразования hive

Запуск скрипта Python за пределами Django

Python - лучший язык программирования в мире.