Bagaimana cara membandingkan secara efisien dua daftar tidak berurutan (bukan set) dengan Python?

a = [1, 2, 3, 1, 2, 3]
b = [3, 2, 1, 3, 2, 1]

a & b harus dianggap sama, karena mereka memiliki elemen yang persis sama, hanya dalam urutan yang berbeda.

Masalahnya, daftar aktual saya akan terdiri dari objek (instance kelas saya), bukan bilangan bulat.

O (n) : Metode Penghitung () adalah yang terbaik (jika objek Anda hashable):

def compare(s, t):
    return Counter(s) == Counter(t)

O (n log n) : Metode diurutkan () adalah yang terbaik berikutnya (jika objek Anda dapat dipesan):

def compare(s, t):
    return sorted(s) == sorted(t)

O (n * n) : Jika objek tidak hashable atau orderable, Anda dapat menggunakan persamaan:

def compare(s, t):
    t = list(t)   # make a mutable copy
    try:
        for elem in s:
            t.remove(elem)
    except ValueError:
        return False
    return not t

Anda dapat mengurutkan keduanya:

sorted(a) == sorted(b)

Sebuah penghitungan semacam juga bisa menjadi lebih efisien (tetapi membutuhkan objek menjadi hashable).

>>> from collections import Counter
>>> a = [1, 2, 3, 1, 2, 3]
>>> b = [3, 2, 1, 3, 2, 1]
>>> print (Counter(a) == Counter(b))
True

Jika Anda tahu item selalu hashable, Anda dapat menggunakan Counter()yang O (n)
Jika Anda tahu item selalu diurutkan, Anda dapat menggunakan sorted()yang O (n log n)

Dalam kasus umum, Anda tidak dapat mengandalkan kemampuan untuk menyortir, atau memiliki elemen, sehingga Anda perlu mundur seperti ini, yang sayangnya O (n ^ 2)

len(a)==len(b) and all(a.count(i)==b.count(i) for i in a)

Cara terbaik untuk melakukan ini adalah dengan menyortir daftar dan membandingkannya. (Menggunakan Countertidak akan bekerja dengan objek yang tidak hash.) Ini mudah untuk integer:

sorted(a) == sorted(b)

Itu menjadi sedikit rumit dengan benda-benda sewenang-wenang. Jika Anda peduli tentang identitas objek, yaitu apakah objek yang sama ada di kedua daftar, Anda dapat menggunakan id()fungsi sebagai kunci pengurutan.

sorted(a, key=id) == sorted(b, key==id)

(Dalam Python 2.x Anda sebenarnya tidak memerlukannya key= parameter, karena Anda dapat membandingkan objek apa pun dengan objek apa pun. Urutannya arbitrer tetapi stabil, sehingga berfungsi dengan baik untuk tujuan ini; tidak masalah apa pun urutan objeknya di, hanya bahwa urutannya sama untuk kedua daftar. Dalam Python 3, meskipun, membandingkan objek dari berbagai jenis tidak diizinkan dalam banyak keadaan - misalnya, Anda tidak dapat membandingkan string dengan bilangan bulat - jadi jika Anda akan memiliki objek dari berbagai jenis, terbaik untuk secara eksplisit menggunakan ID objek.)

Jika Anda ingin membandingkan objek dalam daftar dengan nilai, di sisi lain, pertama-tama Anda perlu mendefinisikan apa arti "nilai" untuk objek. Maka Anda akan memerlukan beberapa cara untuk menyediakannya sebagai kunci (dan untuk Python 3, sebagai jenis yang konsisten). Salah satu cara potensial yang akan bekerja untuk banyak objek sewenang-wenang adalah mengurutkannya repr(). Tentu saja, ini bisa membuang banyak waktu ekstra dan repr()string pembangun memori untuk daftar besar dan sebagainya.

sorted(a, key=repr) == sorted(b, key==repr)

Jika objek adalah semua tipe Anda sendiri, Anda bisa mendefinisikannya __lt__()agar objek tahu bagaimana membandingkan dirinya dengan orang lain. Maka Anda bisa menyortirnya dan tidak khawatir tentang key=parameternya. Tentu saja Anda juga bisa mendefinisikan __hash__()dan menggunakan Counter, yang akan lebih cepat.

https://docs.python.org/3.5/library/unittest.html#unittest.TestCase.assertCountEqual

assertCountEqual (pertama, kedua, msg = Tidak Ada)

Uji bahwa urutan pertama mengandung elemen yang sama dengan yang kedua, terlepas dari urutannya. Ketika tidak, pesan kesalahan yang mencantumkan perbedaan antara urutan akan dihasilkan.

Elemen duplikat tidak diabaikan ketika membandingkan pertama dan kedua. Itu memverifikasi apakah setiap elemen memiliki jumlah yang sama di kedua urutan. Setara dengan: assertEqual (Penghitung (daftar (pertama)), Penghitung (daftar (kedua))) tetapi bekerja dengan urutan objek yang tidak dapat dihancurkan juga.

Baru dalam versi 3.2.

atau di 2.7: https://docs.python.org/2.7/library/unittest.html#unittest.TestCase.assertItemsEqual

Jika daftar berisi item yang tidak hashable (seperti daftar objek), Anda mungkin dapat menggunakan kelas penghitung dan fungsi id () seperti:

from collections import Counter
...
if Counter(map(id,a)) == Counter(map(id,b)):
    print("Lists a and b contain the same objects")

Saya harap potongan kode di bawah ini dapat berfungsi dalam kasus Anda: -

if ((len(a) == len(b)) and
   (all(i in a for i in b))):
    print 'True'
else:
    print 'False'

Ini akan memastikan bahwa semua elemen dalam daftar a&b sama, terlepas dari apakah mereka berada dalam urutan yang sama atau tidak.

Untuk pemahaman yang lebih baik, lihat jawaban saya di pertanyaan ini

Jika perbandingan akan dilakukan dalam konteks pengujian, gunakan assertCountEqual(a, b)( py>=3.2) dan assertItemsEqual(a, b)(2.7<=py<3.2 ).

Berfungsi pada urutan objek yang tidak dapat dihancurkan juga.

Biarkan a, b daftar

def ass_equal(a,b):
try:
    map(lambda x: a.pop(a.index(x)), b) # try to remove all the elements of b from a, on fail, throw exception
    if len(a) == 0: # if a is empty, means that b has removed them all
        return True 
except:
    return False # b failed to remove some items from a

Tidak perlu membuatnya hashable atau mengurutkannya.

Menggunakan unittestmodul memberi Anda pendekatan yang bersih dan standar.

import unittest

test_object = unittest.TestCase()
test_object.assertCountEqual(a, b)