how to remove 50000 elements from a 100000 list?

[Jack Orenstein]

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