Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fast way to remove a few items from a list/queue

This is a follow up to a similar question which asked the best way to write

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

and it seems the consensus was on something like

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

However, I think if you are only removing a few items, most of the items are being copied into the same object, and perhaps that is slow. In an answer to another related question, someone suggests:

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

However, here the list.remove will search for the item, which is O(N) in the length of the list. May be we are limited in that the list is represented as an array, rather than a linked list, so removing items will need to move everything after it. However, it is suggested here that collections.dequeue is represented as a doubly linked list. It should then be possible to remove in O(1) while iterating. How would we actually accomplish this?

Update: I did some time testing as well, with the following code:

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)

and got:

list comp =  4.01255393028
filtering =  3.59962391853
like image 660
highBandWidth Avatar asked Apr 21 '11 14:04

highBandWidth


People also ask

How do I remove a specific item from a Queue?

To remove an element from a Queue, use the remove() method.

How do I remove multiple data from a list?

To remove an element by its index value we can use the del keyword. It supports positive, negative, and a range of indexes (for slicing). Now to remove multiple elements from a list we can use the del keyword with a range of indexes with loop. The above code is using del keyword to remove multiple elements from a list.

How do I remove an item from a Queue in Python?

Removing an item from a queue in Python: To remove items from a queue in Python, we will be using the “get function”. See the Python Queue example given below. To make sure that our queue is empty, we can use the empty function which will return Boolean values.


1 Answers

The list comprehension is the asymptotically optimal solution:

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

It only makes one pass over the list, so runs in O(n) time. Since you need to call determine() on each object, any algorithm will require at least O(n) operations. The list comprehension does have to do some copying, but it's only copying references to the objects not copying the objects themselves.

Removing items from a list in Python is O(n), so anything with a remove, pop, or del inside the loop will be O(n**2).

Also, in CPython list comprehensions are faster than for loops.

like image 135
Daniel Stutzbach Avatar answered Sep 18 '22 15:09

Daniel Stutzbach