Re: best way to compare contents of 2 lists?

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

  1. Esmail

    Esmail Guest

    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
    #1
    1. Advertising

  2. Esmail

    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
    #2
    1. Advertising

  3. 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
    #3
  4. Esmail

    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
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Robin Siebler
    Replies:
    6
    Views:
    5,488
    Raymond Hettinger
    Sep 15, 2004
  2. Esmail
    Replies:
    0
    Views:
    270
    Esmail
    Apr 24, 2009
  3. Esmail
    Replies:
    6
    Views:
    266
    Terry Reedy
    Apr 24, 2009
  4. norseman
    Replies:
    3
    Views:
    1,048
    ajaksu
    Apr 24, 2009
  5. Zachary Dziura
    Replies:
    12
    Views:
    462
    Chris Angelico
    Jun 13, 2011
Loading...

Share This Page