comparing lists
Alex Martelli
aleax at aleax.it
Thu May 9 02:37:31 EDT 2002
Mark McEahern wrote:
> Suppose I want to do a boolean comparison (equal or not equal) of two
> lists case-insensitively and I don't care about order. I can do this:
"Don't care about order" -> use dictionaries. O(N) operation rather than:
> 1. Create temporary copies that are lowercased and use the in operator:
O(N**2)
> 2. Sort temporary copies, then then compare them.
O(N logN)
Here's a O(N) solution:
def compare_via_dicts(L, M):
def makebag(L):
dL = {}
for x in L:
x = x.lower()
dL[x] = 1 + dL.get(x, 0)
return makebag(L) == makebag(M)
Note we use a 'bag' (x -> #instances of x in list), not a set, to take care
of repetitions so ['a', 'A'] will not appear equal to ['a', 'A', 'A'], &c.
Alex
More information about the Python-list
mailing list