> Both of these techniques are O(n^2). You can reduce it to O(n log n) > by using sets: > >>>> set2 = set(list2) >>>> [x for x in list1 if x not in set2] > > Checking to see if an item is in a set is much more efficient than a > list.
Is the set-lookup reliably O(log n)? I was under the impression that it is hash-based, and this should be O(1) usually, but couldbve O(n) worst-case (hash the same for _all_ entries). Regards, Diez -- http://mail.python.org/mailman/listinfo/python-list