Быстрый способ удалить несколько элементов из списка / очереди
Это является следствием аналогичного вопроса, который задал наилучший способ написать
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, потому что он на самом деле работает медленнее.