Fast way to remove a few items from a list/queue
Solution 1
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.
Solution 2
If you need to remove item in O(1) you can use HashMaps
Solution 3
Since list.remove
is equivalent to del list[list.index(x)]
, you could do:
for idx, item in enumerate(somelist):
if determine(item):
del somelist[idx]
But: you should not modify the list while iterating over it. It will bite you, sooner or later. Use filter
or list comprehension first, and optimise later.
Solution 4
A deque is optimized for head and tail removal, not for arbitrary removal in the middle. The removal itself is fast, but you still have to traverse the list to the removal point. If you're iterating through the entire length, then the only difference between filtering a deque and filtering a list (using filter
or a comprehension) is the overhead of copying, which at worst is a constant multiple; it's still a O(n) operation. Also, note that the objects in the list aren't being copied -- just the references to them. So it's not that much overhead.
It's possible that you could avoid copying like so, but I have no particular reason to believe this is faster than a straightforward list comprehension -- it's probably not:
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:]
Solution 5
I took a stab at this. My solution is slower, but requires less memory overhead (i.e. doesn't create a new array). It might even be faster in some circumstances!
This code has been edited since its first posting
I had problems with timeit, I might be doing this wrong.
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)
And here are the results
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
I must be doing something wrong with psyco, because it is actually running slower.
Related videos on Youtube
highBandWidth
Updated on July 09, 2022Comments
-
highBandWidth almost 2 years
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
-
user1066101 about 13 yearsWithout a specific performance objective, and without this being the only bottleneck in your program, this is a fair amount of hand-wringing over very little. What are the
timeit
measurements for these operations? -
Praveen Gollakota about 13 yearsI retested with your code using
timeit
instead ofcProfile
. I was able to replicate your results.filter
worked fastest. I need to dig deeper and figure out why cProfile showed filter was fastest. I deleted my answer because based on the differences between cProfile vs. timeit will only add to the confusion for future knowledge-seekers ;) The only conclusion that can be drawn with certainty is thatlist.remove
sucks. -
Daniel Stutzbach about 13 yearsIf you want to compare apples to apples, you should make the list comp use "c = ..." or make the filter use "c[:] = ...".
-
jfs about 13 years@Daniel Stutzbach:
c = [x for x in b if tokeep(x)]
takes the same time that is strange. -
nakedfanatic about 9 yearsI ran this same test in Python 3.4.1 and got the following result:list comp = 3.207311153242804 filtering = 0.0023201516740933847
-
jfs over 8 years@nakedfanatic:
filter()
returns an iterator on Python 3. Call list() on the result, to get items.
-
-
highBandWidth about 13 yearsYou're right, and I might have to fall back on that, but hashmaps are overkill since I don't need O(1) removing for random items, just O(1) removal while iterating over that item, which is possible for linked lists.
-
highBandWidth about 13 yearsThat's what the second code snippet I mentioned does, with
reversed
solving the problem of safety. But remove or del somelist[idx] is still O(N), isn't it? -
highBandWidth about 13 yearsYou're right this is asymptotically the fastest. I still wonder if there is a way to remove the linear overhead of copying.
-
user1066101 about 13 years@highBandWidth:
reversed
does not solve the "safety" problem. Nothing does except making an actual copy. -
Daniel Stutzbach about 13 years@highBandWidth: The copy is cache-friendly and will be very, very fast. You'd be better off trying to make sure determine() is fast.
-
Kevin about 13 yearsCan you point to next item? for example if you have someting like this: item1 , item2 , item3 and you have to remove item2 you can do something like this: item1->next=item3. I hope that now I understood correct
-
senderle about 13 years@S.Lott -- doesn't it though? I would have thought it would ensure that all
del
side-effects occur to portions of the list that have already been traversed. (Of course one still shouldn't do it that way -- scales badly.) -
user1066101 about 13 years@senderle: (1) Try it. (2) Try to avoid assuming this kind of thing. Measurements are more valuable and useful that "would have thought".
-
senderle about 13 years@S.Lott, I completely agree with you, so I'll rephrase: I have tried it before and it seemed to work. Perhaps there was a test-case that I missed.
-
highBandWidth about 13 yearsYou are doing the setup steps (making the b array), all over again, and timing it. I was only timing the actual filter/delete steps. What is the difference between forfilter and forfiltCheating?
-
highBandWidth about 13 yearsOhh I get it, in *Cheating, you use the literal rather than the function object, and it seems to be faster!
-
Garrett Berg about 13 yearsApparently the timeit module does not re-run the initialization steps. Since I am changing the array itself, it has be be included in the timing. I've never used timit before, I was kind of just trying to get some results.
-
Garrett Berg about 13 yearsI am so confused by this code... why isn't it: somelist = [x for x in somelist if not determine(x)]
-
jfs about 13 years@Garrett Berg: Indeed.
somelist[:] =
triggerslist_ass_slice()
that does a lot of work. -
krenerd about 3 yearsIt is sort of annoying why the default
remove
orpop
isn'tm implemented this way. -
Elias Hasle almost 3 years@krenerd The default
remove
andpop
mutate the list, whereas a list comprehension creates a new one.