Re: best way to compare contents of 2 lists?

Discussion in 'Python' started by Esmail, Apr 24, 2009.

1. EsmailGuest

Esmail wrote:
> What is the best way to compare the *contents* of two different
> lists regardless of their respective order? The lists will have
> the same number of items, and be of the same type.
>
> E.g. a trivial example (my lists will be larger),
>
> a=[1, 2, 3]
>
> b=[2, 3, 1]
>
> should yield true if a==b
>
> I suppose I could sort them and then compare them. I.e.,
>
> sorted(a)==sorted(b)
>
>
> I am wondering if there is a more efficient/preferred way to do so.

oh, I forgot to mention that each list may contain duplicates. So I
suppose this means I would have to sort the two lists and compare them
afterall, unless there's another way?

Esmail, Apr 24, 2009

2. Guest

Esmail:
> oh, I forgot to mention that each list may contain duplicates.

Comparing the sorted lists is a possible O(n ln n) solution:

a.sort()
b.sort()
a == b

Another solution is to use frequency dicts, O(n):

from itertools import defaultdict
d1 = defaultdict(int)
for el in a:
d1[el] += 1
d2 = defaultdict(int)
for el in b:
d2[el] += 1
d1 == d2

As the arrays (Python lists) become large the second solution may
become faster.

Bye,
bearophile

, Apr 24, 2009

3. Arnaud DelobelleGuest

On Apr 24, 7:12 am, wrote:
[...]
> Another solution is to use frequency dicts, O(n):
>
> from itertools import defaultdict
> d1 = defaultdict(int)
> for el in a:
>     d1[el] += 1
> d2 = defaultdict(int)
> for el in b:
>     d2[el] += 1
> d1 == d2

Thanks to the power of negative numbers, you only need one dict:

d = defaultdict(int)
for x in a:
d[x] += 1
for x in b:
d[x] -= 1
# a and b are equal if d[x]==0 for all x in d:
not any(d.itervalues())

--
Arnaud

Arnaud Delobelle, Apr 24, 2009
4. Guest

Arnaud Delobelle:
> Thanks to the power of negative numbers, you only need one dict:
>
> d = defaultdict(int)
> for x in a:
>     d[x] += 1
> for x in b:
>     d[x] -= 1
> # a and b are equal if d[x]==0 for all x in d:
> not any(d.itervalues())

Very nice, I'll keep this for future use.
Someday I'll have to study this new new kind of numbers that can
represent borrowed items too.

Bye,
bearophile

, Apr 24, 2009