2

I have a python function defined as follows which i use to delete from list1 the items which are already in list2. I am using python 2.6.2 on windows XP

def compareLists(list1, list2):
    curIndex = 0
    while curIndex < len(list1):
        if list1[curIndex] in list2:
            list1.pop(curIndex)
        else:
            curIndex += 1

Here, list1 and list2 are a list of lists

list1 = [ ['a', 11221, '2232'], ['b', 1321, '22342'] .. ]

# list2 has a similar format.

I tried this function with list1 with 38,000 elements and list2 with 150,000 elements. If i put in a print statement to print the current iteration, I find that the function slows down with each iterations. At first, it processes around 1000 or more items in a second and then after a while it reduces to around 20-50 a second. Why can that be happening?

EDIT: In the case with my data, the curIndex remains 0 or very close to 0 so the pop operation on list1 is almost always on the first item.

If possible, can someone also suggest a better way of doing the same thing in a different way?

4
  • 6
    compareLists(l1,l2) is probably a bad name for a function that destructively modifies one of the inputs. How about removeDupes(l1,l2)? Nov 12, 2009 at 16:35
  • You have several good solutions here. Your best bet at this point is to try each method and time them all and figure out which would be the most efficient. It really depends on where the actual bottle neck is. Nov 12, 2009 at 16:38
  • How deeply nested is list2? Is it just a list of lists or is the structure more recursive? Nov 12, 2009 at 16:43
  • List2 has the exact same structure as list1. Only a list of lists. no recursive structure there. Nov 12, 2009 at 16:44

6 Answers 6

12

Try a more pythonic approach to the filtering, something like

[x for x in list1 if x not in set(list2)]

Converting both lists to sets is unnessescary, and will be very slow and memory hungry on large amounts of data.

Since your data is a list of lists, you need to do something in order to hash it. Try out

list2_set = set([tuple(x) for x in list2])
diff = [x for x in list1 if tuple(x) not in list2_set]

I tested out your original function, and my approach, using the following test data:

list1 = [[x+1, x*2] for x in range(38000)]
list2 = [[x+1, x*2] for x in range(10000, 160000)]

Timings - not scientific, but still:

 #Original function
 real    2m16.780s
 user    2m16.744s
 sys     0m0.017s

 #My function
 real    0m0.433s
 user    0m0.423s
 sys     0m0.007s
10
  • set(list2) doesn't work since Python can't hash lists: set([['a',1]]) -> TypeError: list objects are unhashable. Didn't expect that either ... Nov 12, 2009 at 16:41
  • this line gives me an error TypeError: unhashable type: 'list' Nov 12, 2009 at 16:41
  • It works with tuples, though (set([('a',1),])). Is there a fast way to convert the lists in list2 into tuples? Nov 12, 2009 at 16:42
  • 1
    I didn't read close enough to discover the data in question was lists of lists. Converting the inner level of lists to tuples allows us to use sets. See new example
    – gnud
    Nov 12, 2009 at 16:42
  • @gnud: Not to give you a hard time or anything, but the question was full of the word "list" :^)
    – Jed Smith
    Nov 12, 2009 at 16:46
3

There are 2 issues that cause your algorithm to scale poorly:

  1. x in list is an O(n) operation.
  2. pop(n) where n is in the middle of the array is an O(n) operation.

Both situations cause it to scale poorly O(n^2) for large amounts of data. gnud's implementation would probably be the best solution since it solves both problems without changing the order of elements or removing potential duplicates.

2

If we rule the data structure itself out, look at your memory usage next. If you end up asking the OS to swap in for you (i.e., the list takes up more memory than you have), Python's going to sit in iowait waiting on the OS to get the pages from disk, which makes sense given your description.

Is Python sitting in a jacuzzi of iowait when this slowdown happens? Anything else going on in the environment?

(If you're not sure, update with your platform and one of us will tell you how to tell.)

4
  • You can see that on linux by doing top and looking at the percent of time it's waiting on io. It's the wa portion of the percentages. They're probably thrashing do the how much editing the poping is doing. Nov 12, 2009 at 16:33
  • How can I find that out? I am running it on windows XP. Nov 12, 2009 at 16:33
  • 1
    On XP, you're going to have to use a third-party toy to accomplish that. Have a look at technet.microsoft.com/en-us/sysinternals/bb896653.aspx -- I've used Process Explorer in the past, and it'll tell you everything Python is doing. Can't tell you exactly how to look for Windows using Virtual Memory though (that's what it calls swap).
    – Jed Smith
    Nov 12, 2009 at 16:37
  • 1
    Task manager -> Processes -> PF delta column (you may have to turn it on first in View > Select column) It shows the number of page faults, which is a good indication of swapping.
    – Wim
    Nov 12, 2009 at 16:39
2

The only reason why the code can become slower is that you have big elements in both lists which share a lot of common elements (so the list1[curIndex] in list2 takes more time).

Here are a couple of ways to fix this:

  • If you don't care about the order, convert both lists into sets and use set1.difference(set2)

  • If the order in list1 is important, then at least convert list2 into a set because in is much faster with a set.

  • Lastly, try a filter: filter(list1, lambda x: x not in set2)

[EDIT] Since set() doesn't work on recursive lists (didn't expect that), try:

result = filter(list1, lambda x: x not in list2)

It should still be much faster than your version. If it isn't, then your last option is to make sure that there can't be duplicate elements in either list. That would allow you to remove items from both lists (and therefore making the compare ever cheaper as you find elements from list2).

1

EDIT: I've updated my answer to account for lists being unhashable, as well as some other feedback. This one is even tested.

It probably relates to the cost of poping an item out of a middle of a list.

Alternatively have you tried using sets to handle this?

def difference(list1, list2):
    return [x for x in list1 if tuple(x) in set(tuple(y) for y in list2)]

You can then set list one to the resulting list if that is your intention by doing

list1 = difference(list1, list2)
10
  • Sets are pure joy. Good alternative.
    – Jed Smith
    Nov 12, 2009 at 16:32
  • In the case with my data, the curIndex remains 0 or very close to 0 so the pop operation on list1 is almost always on the first item Nov 12, 2009 at 16:33
  • Ya you're paying for the cost of resizing the array, try with the methods I'm posting and see. I imagine it'll result in a faster operation overall as most of the processing will happen C side instead of inside your loop. Nov 12, 2009 at 16:35
  • Then probbaly the first few thousend iterations it is actually the first item being popped of, which seems to be implemented pretty efficiently (could be done by just incrementing the list pointer). But once you have an element that stays on the list, it's no longer removing the first element, but one in the middle which can't be implemented as quickly.
    – Wim
    Nov 12, 2009 at 16:36
  • If i try that, python throws an error saying 'TypeError: unhashable type: 'list'' for the line unique_items = set(list1).difference(set(list2)) Nov 12, 2009 at 16:37
0

The often suggested set wont work here, because the two lists contain lists, which are unhashable. You need to change your data structure first.

You can

  • convert the sublists into tuples or class instances to make them hashable, then use sets.
  • Keep both lists sorted, then you just have to compare the lists' heads.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.