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