Xác định xem 2 danh sách có cùng các yếu tố, bất kể thứ tự không?

Question

Xin lỗi vì câu hỏi đơn giản, nhưng tôi đang gặp khó khăn khi tìm câu trả lời.

Khi tôi so sánh 2 danh sách, tôi muốn biết liệu chúng có "bằng nhau" ở chỗ chúng có cùng nội dung không, nhưng theo thứ tự khác nhau.

Ex:

x = ['a', 'b'] 
y = ['b', 'a'] 

Tôi muốn x == y để đánh giá để True.

Answer 1

Bạn chỉ có thể kiểm tra xem multisets với các yếu tố của x và y đều bình đẳng:

import collections 
collections.Counter(x) == collections.Counter(y) 

Điều này đòi hỏi các yếu tố để được hashable; thời gian chạy sẽ ở trong O(n), trong đó n là kích thước của danh sách.

Nếu các yếu tố này cũng là duy nhất, bạn cũng có thể chuyển đổi sang bộ (cùng thời gian chạy tiệm cận, có thể là một chút nhanh hơn trong thực tế):

set(x) == set(y) 

Nếu các yếu tố không hashable, nhưng có thể phân loại, khác thay thế (thời gian chạy theo số O(n log n)) là

sorted(x) == sorted(y) 

Nếu các phần tử không thể băm cũng không thể sắp xếp, bạn có thể sử dụng hàm trợ giúp sau. Lưu ý rằng nó sẽ được khá chậm (O(n²)) và thường nên không được sử dụng bên ngoài trường hợp bí truyền của các yếu tố không thể tháo rời và không thể loại bỏ.

def equal_ignore_order(a, b): 
    """ Use only when elements are neither hashable nor sortable! """ 
    unmatched = list(b) 
    for element in a: 
     try: 
      unmatched.remove(element) 
     except ValueError: 
      return False 
    return not unmatched 

Answer 2

Xác định nếu 2 danh sách có những yếu tố giống nhau, không phân biệt thứ tự?

Suy luận từ ví dụ của bạn:

x = ['a', 'b'] 
y = ['b', 'a'] 

rằng các phần tử của danh sách này sẽ không được lặp lại (họ là duy nhất) cũng như hashable (mà chuỗi và một số đối tượng python bất biến khác) , câu trả lời trực tiếp và hiệu quả nhất về tính toán sử dụng các bộ dựng sẵn của Python, (các ngữ nghĩa giống như các bộ toán học mà bạn có thể đã học được ở trường).

set(x) == set(y) # prefer this if elements are hashable 

Trong trường hợp đó, yếu tố này là hashable, nhưng không duy nhất, các collections.Counter cũng hoạt động ngữ nghĩa như một MultiSet, nhưng nó còn lâu mới chậm:

from collections import Counter 
Counter(x) == Counter(y) 

thích sử dụng sorted:

sorted(x) == sorted(y) 

nếu các phần tử có thể đặt hàng. Điều này sẽ giải thích cho các trường hợp không phải là duy nhất hoặc không có hàm băm, nhưng điều này có thể chậm hơn nhiều so với sử dụng tập hợp.

thực nghiệm Thử nghiệm

Một thí nghiệm thực nghiệm kết luận rằng người ta nên thích set, sau đó sorted. Chỉ chọn số Counter nếu bạn cần những thứ khác như đếm hoặc sử dụng thêm dưới dạng nhiều lần.

thiết lập đầu tiên:

import timeit 
import random 
from collections import Counter 

data = [str(random.randint(0, 100000)) for i in xrange(100)] 
data2 = data[:]  # copy the list into a new one 

def sets_equal(): 
    return set(data) == set(data2) 

def counters_equal(): 
    return Counter(data) == Counter(data2) 

def sorted_lists_equal(): 
    return sorted(data) == sorted(data2) 

Và thử nghiệm:

>>> min(timeit.repeat(sets_equal)) 
13.976069927215576 
>>> min(timeit.repeat(counters_equal)) 
73.17287588119507 
>>> min(timeit.repeat(sorted_lists_equal)) 
36.177085876464844 

Vì vậy, chúng ta thấy rằng so sánh bộ là giải pháp nhanh nhất, và đối chiếu danh mục được sắp xếp là nhanh thứ hai.

Answer 3

Điều này dường như hoạt động, mặc dù có thể cồng kềnh đối với các danh sách lớn.

>>> A = [0, 1] 
>>> B = [1, 0] 
>>> C = [0, 2] 
>>> not sum([not i in A for i in B]) 
True 
>>> not sum([not i in A for i in C]) 
False 
>>> 

Tuy nhiên, nếu mỗi danh sách phải chứa tất cả các yếu tố của khác thì mã trên là có vấn đề.

>>> A = [0, 1, 2] 
>>> not sum([not i in A for i in B]) 
True 

Sự cố phát sinh khi len(A) != len(B) và, trong ví dụ này, len(A) > len(B). Để tránh điều này, bạn có thể thêm một câu lệnh nữa.

>>> not sum([not i in A for i in B]) if len(A) == len(B) else False 
False 

Một điều nữa, tôi đã chấm điểm giải pháp của mình với timeit.repeat, trong cùng điều kiện được Aaron Hall sử dụng trong bài đăng của anh ấy. Theo nghi ngờ, kết quả là đáng thất vọng. Phương pháp của tôi là phương pháp cuối cùng. set(x) == set(y).

>>> def foocomprehend(): return not sum([not i in data for i in data2]) 
>>> min(timeit.repeat('fooset()', 'from __main__ import fooset, foocount, foocomprehend')) 
25.2893661496 
>>> min(timeit.repeat('foosort()', 'from __main__ import fooset, foocount, foocomprehend')) 
94.3974742993 
>>> min(timeit.repeat('foocomprehend()', 'from __main__ import fooset, foocount, foocomprehend')) 
187.224562545 

Answer 4

Như đã đề cập trong các nhận xét ở trên, trường hợp chung là một cơn đau. Nó là khá dễ dàng nếu tất cả các mục được hashable hoặc tất cả các mục có thể sắp xếp. Tuy nhiên, gần đây tôi đã phải cố gắng giải quyết trường hợp chung. Đây là giải pháp của tôi. Tôi nhận ra sau khi đăng bài rằng đây là một bản sao cho một giải pháp ở trên mà tôi bỏ lỡ trên vượt qua đầu tiên. Dù sao, nếu bạn sử dụng các lát thay vì list.remove(), bạn có thể so sánh các chuỗi bất biến.

def sequences_contain_same_items(a, b): 
    for item in a: 
     try: 
      i = b.index(item) 
     except ValueError: 
      return False 
     b = b[:i] + b[i+1:] 
    return not b