it-swarm-id.com

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.

119
johndir

O (n) : Metode Counter () yang terbaik (jika objek Anda dapat hashable):

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

O (n log n) : The diurutkan () metode terbaik berikutnya ( jika objek Anda dapat dipesan):

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

O (n * n) : Jika objek tidak hashable, juga tidak dapat dipesan, 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
205

Anda dapat mengurutkan keduanya:

sorted(a) == sorted(b)

A menghitung sort juga bisa lebih efisien (tetapi membutuhkan objek yang bisa di-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
14
Mark Byers

Jika Anda tahu item selalu hashable, Anda dapat menggunakan Counter() yang merupakan O (n)
Jika Anda tahu item selalu dapat diurutkan, Anda dapat menggunakan sorted() yang merupakan 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)
11
John La Rooy

Cara terbaik untuk melakukan ini adalah dengan menyortir daftar dan membandingkannya. (Menggunakan Counter tidak akan berfungsi dengan objek yang tidak dapat di hashable.) Ini sangat mudah untuk integer:

sorted(a) == sorted(b)

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

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

(Dalam Python 2.x Anda sebenarnya tidak memerlukan parameter key=, Karena Anda dapat membandingkan objek apa pun dengan objek apa pun. Pemesanannya arbitrer tetapi stabil, jadi ia berfungsi baik untuk tujuan ini; tidak masalah urutan objek apa yang ada, hanya urutannya sama untuk kedua daftar. Dalam Python 3, meskipun, membandingkan objek dari tipe yang berbeda tidak diperbolehkan dalam banyak keadaan - misalnya, Anda tidak dapat membandingkan string dengan bilangan bulat - jadi jika Anda akan memiliki objek dari berbagai jenis, lebih baik 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 yang berubah-ubah adalah dengan mengurutkan berdasarkan mereka repr(). Tentu saja, ini bisa membuang banyak waktu tambahan dan pembangunan memori repr() string untuk daftar besar dan seterusnya.

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

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

5
kindall

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

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

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.

2
jarekwg

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 mereka tidak melakukannya, 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

2
cleder

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.

1
Umur Kontacı

Saya harap kode di bawah ini bisa digunakan untuk 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 adalah sama, terlepas dari apakah mereka berada dalam urutan yang sama atau tidak.

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

1
Pabitra Pati