निर्धारित करें कि ऑर्डर के बावजूद 2 सूचियों में समान तत्व हैं या नहीं?

Question

सरल प्रश्न के लिए खेद है, लेकिन मुझे जवाब खोजने में कठिनाई हो रही है।

जब मैं 2 सूचियों की तुलना करता हूं, तो मैं जानना चाहता हूं कि वे "बराबर" हैं, उनके पास समान सामग्री है, लेकिन अलग-अलग क्रम में।

पूर्व:

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

मैं x == yTrue का मूल्यांकन करना चाहते हैं।

Answer 1

आप बस देख सकते हैं कि x और y के तत्वों के साथ multisets बराबर हैं:

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

यह hashable होने के लिए तत्वों की आवश्यकता है; रनटाइम O(n) में होगा, जहां n सूचियों का आकार है।

तत्वों को भी अद्वितीय हैं, तो आप भी सेट करने के लिए परिवर्तित कर सकते हैं (एक ही asymptotic क्रम, एक छोटा सा व्यवहार में तेजी से हो सकता है):

set(x) == set(y) 

तत्वों hashable नहीं कर रहे हैं, लेकिन sortable, एक और विकल्प (O(n log n) में क्रम)

sorted(x) == sorted(y) 

है तत्व न hashable हैं और न ही sortable आप निम्नलिखित सहायक समारोह का उपयोग कर सकते हैं। ध्यान दें कि यह काफी धीमा होगा (O(n²)) और आम तौर पर को अनावश्यक और अयोग्य तत्वों के गूढ़ मामले के बाहर उपयोग किया जाना चाहिए।

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

निर्धारित करें यदि 2 सूचियों आदेश की परवाह किए बिना, एक ही तत्व है?

अपने उदाहरण से निष्कर्ष निकालते:

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

कि सूचियों के तत्वों को दोहराया नहीं किए जाएंगे (उन्हें अद्वितीय हैं) और साथ ही hashable (जो तार और अन्य कुछ अपरिवर्तनीय अजगर वस्तुओं रहे हैं) , सबसे प्रत्यक्ष और कम्प्यूटेशनल रूप से कुशल उत्तर पायथन के बिल्टिन सेट का उपयोग करता है, (जो कि सैद्धांतिक रूप से गणितीय सेटों की तरह हैं जिन्हें आपने स्कूल में सीखा होगा)।

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

मामले है कि तत्वों hashable हैं, लेकिन गैर-अद्वितीय, collections.Counter भी एक मल्टीसेट के रूप में अर्थ की दृष्टि से काम करता है, लेकिन यह कहीं धीमी है:

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

sorted उपयोग करने के लिए पसंद करते हैं:

sorted(x) == sorted(y) 

यदि तत्व ऑर्डर करने योग्य हैं। यह गैर-अद्वितीय या गैर-हानिकारक परिस्थितियों के लिए जिम्मेदार होगा, लेकिन यह सेट का उपयोग करने से बहुत धीमा हो सकता है।

अनुभवजन्य प्रयोग

एक अनुभवजन्य प्रयोग का निष्कर्ष है कि एक set को प्राथमिकता देनी चाहिए, तो sorted। केवल Counter का चयन करें यदि आपको मल्टीसेट के रूप में अन्य चीजों की गणना या आगे उपयोग की आवश्यकता है।

पहले स्थापना:

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) 

और परीक्षण:

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

तो हम देखते हैं कि सेट की तुलना में सबसे तेजी से समाधान है, और हल कर सूचियों की तुलना दूसरी सबसे तेज है।

Answer 3

यह काम करता प्रतीत होता है, हालांकि संभवतः बड़ी सूचियों के लिए बोझिल है।

>>> 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 
>>> 

हालांकि, अगर प्रत्येक सूची चाहिए अन्य के सभी तत्व होते हैं तो ऊपर दिए गए कोड समस्याग्रस्त है।

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

समस्या पैदा होती है जब len(A) != len(B) और इस उदाहरण, len(A) > len(B) में,। इससे बचने के लिए, आप एक और कथन जोड़ सकते हैं।

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

एक और बात, मैं timeit.repeat के साथ अपने समाधान बेंचमार्क, अपनी पोस्ट में हारून हॉल द्वारा प्रयोग किया जाता इन्हीं परिस्थितियों में। संदिग्ध के रूप में, परिणाम निराशाजनक हैं। मेरी विधि आखिरी है। 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

जैसा ऊपर बताया गया है, सामान्य मामला दर्द है। यह सभी आसान है अगर सभी आइटम हैंशबल हैं या सभी आइटम क्रमबद्ध हैं। हालांकि मुझे हाल ही में सामान्य मामले को हल करने की कोशिश करनी है। मेरा समाधान यहाँ है। मुझे यह पोस्ट करने के बाद एहसास हुआ कि यह उपरोक्त समाधान के लिए एक डुप्लिकेट है जिसे मैंने पहले पास पर याद किया था। वैसे भी, यदि आप list.remove() के बजाय स्लाइस का उपयोग करते हैं तो आप अपरिवर्तनीय अनुक्रमों की तुलना कर सकते हैं।

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