On May 5, 2006, at 9:36 AM, Ju Hui wrote: >>> a=range(100000) >>> b=range(50000) >>> for x in b: > ... a.remove(x) > ... > it will very slowly. Shall I change to another data structure and choos > a better arithmetic? > any suggestion is welcome.
If removal is an O(n) operation, then removing 1/2 the list will take O(n**2), which you don't want. You'd be better off with the contents of "a" being in a hash table (O(1) removal in practice) or a balanced tree (O(log n) removal). Another possibility: If the a and b lists are ordered in the same way, then you could walk through the lists in order using a merge procedure, generating a new list as you go. After ruling out slow data structures and algorithms, you'll almost certainly be better off using something built in to Python rather than coding your own data structure in Python. Jack Orenstein -- http://mail.python.org/mailman/listinfo/python-list
