The only more declarative and thus Pythonic way that pops into my mind and that improves performance for large b
(and a
) is to use some sort of counter with decrement:
from collections import Counter
class DecrementCounter(Counter):
def decrement(self,x):
if self[x]:
self[x] -= 1
return True
return False
Now we can use list comprehension:
b_count = DecrementCounter(b)
complement = [x for x in a if not b_count.decrement(x)]
Here we thus keep track of the counts in b
, for each element in a
we look whether it is part of b_count
. If that is indeed the case we decrement the counter and ignore the element. Otherwise we add it to the complement
. Note that this only works, if we are sure such complement
exists.
After you have constructed the complement
, you can check if the complement exists with:
not bool(+b_count)
If this is False
, then such complement cannot be constructed (for instance a=[1]
and b=[1,3]
). So a full implementation could be:
b_count = DecrementCounter(b)
complement = [x for x in a if not b_count.decrement(x)]
if +b_count:
raise ValueError('complement cannot be constructed')
If dictionary lookup runs in O(1) (which it usually does, only in rare occasions it is O(n)), then this algorithm runs in O(|a|+|b|) (so the sum of the sizes of the lists). Whereas the remove
approach will usually run in O(|a|×|b|).
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…