Python: remove lots of items from a list

Question

I am in the final stretch of a project I have been working on. Everything is running smoothly but I have a bottleneck that I am having trouble working around.

I have a list of tuples. The list ranges in length from say 40,000 - 1,000,000 records. Now I have a dictionary where each and every (value, key) is a tuple in the list.

So, I might have

myList = [(20000, 11), (16000, 4), (14000, 9)...]
myDict = {11:20000, 9:14000, ...}

I want to remove each (v, k) tuple from the list.

Currently I am doing:

for k, v in myDict.iteritems():
    myList.remove((v, k))

Removing 838 tuples from the list containing 20,000 tuples takes anywhere from 3 - 4 seconds. I will most likely be removing more like 10,000 tuples from a list of 1,000,000 so I need this to be faster.

Is there a better way to do this?

I can provide code used to test, plus pickled data from the actual application if needed.

Answer 1

The problem looks to me to be the fact you are using a list as the container you are trying to remove from, and it is a totally unordered type. So to find each item in the list is a linear operation (O(n)), it has to iterate over the whole list until it finds a match.

If you could swap the list for some other container (set?) which uses a hash() of each item to order them, then each match could be performed much quicker.

The following code shows how you could do this using a combination of ideas offered by myself and Nick on this thread:

list_set = set(original_list)
dict_set = set(zip(original_dict.values(), original_dict.keys()))
difference_set = list(list_set - dict_set)
final_list = []
for item in original_list:
    if item in difference_set:
        final_list.append(item)

Answer 2

Every time you call myList.remove, Python has to scan over the entire list to search for that item and remove it. In the worst case scenario, every item you look for would be at the end of the list each time.

Have you tried doing the "inverse" operation of:

newMyList = [(v,k) for (v,k) in myList if not k in myDict]

But I'm really not sure how well that would scale, either, since you would be making a copy of the original list -- could potentially be a lot of memory usage there.

Probably the best alternative here is to wait for Alex Martelli to post some mind-blowingly intuitive, simple, and efficient approach.

Answer 3

You'll have to measure, but I can imagine this to be more performant:

myList = filter(lambda x: myDict.get(x[1], None) != x[0], myList)

because the lookup happens in the dict, which is more suited for this kind of thing. Note, though, that this will create a new list before removing the old one; so there's a memory tradeoff. If that's an issue, rethinking your container type as jkp suggest might be in order.

Edit: Be careful, though, if None is actually in your list -- you'd have to use a different "placeholder."

Answer 4

[(i, j) for i, j in myList if myDict.get(j) != i]

Answer 5

Try something like this:

myListSet = set(myList)
myDictSet = set(zip(myDict.values(), myDict.keys()))
myList = list(myListSet - myDictSet)

This will convert myList to a set, will swap the keys/values in myDict and put them into a set, and will then find the difference, turn it back into a list, and assign it back to myList. :)

Answer 6

[i for i in myList if i not in list(zip(myDict.values(), myDict.keys()))]

Answer 7

A list containing a million 2-tuples is not large on most machines running Python. However if you absolutely must do the removal in situ, here is a clean way of doing it properly:

def filter_by_dict(my_list, my_dict):
    sentinel = object()
    for i in xrange(len(my_list) - 1, -1, -1):
        key = my_list[i][1]
        if my_dict.get(key, sentinel) is not sentinel:
            del my_list[i]

Update Actually each del costs O(n) shuffling the list pointers down using C's memmove(), so if there are d dels, it's O(n*d) not O(n**2). Note that (1) the OP suggests that d approx == 0.01 * n and (2) the O(n*d) effort is copying one pointer to somewhere else in memory ... so this method could in fact be somewhat faster than a quick glance would indicate. Benchmarks, anyone?

What are you going to do with the list after you have removed the items that are in the dict? Is it possible to piggy-back the dict-filtering onto the next step?

Answer 8

To remove about 10,000 tuples from a list of about 1,000,000, if the values are hashable, the fastest approach should be:

totoss = set((v,k) for (k,v) in myDict.iteritems())
myList[:] = [x for x in myList if x not in totoss]

The preparation of the set is a small one-time cost, wich saves doing tuple unpacking and repacking, or tuple indexing, a lot of times. Assignign to myList[:] instead of assigning to myList is also semantically important (in case there are any other references to myList around, it's not enough to rebind just the name -- you really want to rebind the contents!-).

I don't have your test-data around to do the time measurement myself, alas!, but, let me know how it plays our on your test data!

If the values are not hashable (e.g. they're sub-lists, for example), fastest is probably:

sentinel = object()
myList[:] = [x for x in myList if myDict.get(x[0], sentinel) != x[1]]

or maybe (shouldn't make a big difference either way, but I suspect the previous one is better -- indexing is cheaper than unpacking and repacking):

sentinel = object()
myList[:] = [(a,b) for (a,b) in myList if myDict.get(a, sentinel) != b]

In these two variants the sentinel idiom is used to ward against values of None (which is not a problem for the preferred set-based approach -- if values are hashable!) as it's going to be way cheaper than if a not in myDict or myDict[a] != b (which requires two indexings into myDict).