परीक्षण अगर सूचियों में पाइथन

Question

में कोई आइटम साझा करते हैं तो मैं जांचना चाहता हूं कि किसी भी सूची में आइटमों में से किसी अन्य सूची में मौजूद हैं या नहीं। मैं बस नीचे दिए गए कोड के साथ ऐसा कर सकता हूं, लेकिन मुझे संदेह है कि ऐसा करने के लिए लाइब्रेरी फ़ंक्शन हो सकता है। यदि नहीं, तो क्या एक ही परिणाम प्राप्त करने की एक और पाइथोनिक विधि है।

In [78]: a = [1, 2, 3, 4, 5] 

In [79]: b = [8, 7, 6] 

In [80]: c = [8, 7, 6, 5] 

In [81]: def lists_overlap(a, b): 
    ....:  for i in a: 
    ....:   if i in b: 
    ....:    return True 
    ....:  return False 
    ....: 

In [82]: lists_overlap(a, b) 
Out[82]: False 

In [83]: lists_overlap(a, c) 
Out[83]: True 

In [84]: def lists_overlap2(a, b): 
    ....:  return len(set(a).intersection(set(b))) > 0 
    ....: 

Answer 1

लघु जवाब: not set(a).isdisjoint(b) उपयोग करते हैं, यह आम तौर पर सबसे तेजी से है।

परीक्षण करने के चार सामान्य तरीके हैं यदि दो सूचियां a और b किसी भी आइटम को साझा करती हैं। खोज उन्हें है O(1) (की जटिलता के बारे में अधिक जानकारी के लिए here देखते हैं, क्योंकि सेट पायथन में एक हैश तालिका का उपयोग कर जमा हो जाती है

bool(set(a) & set(b)) 

: पहला विकल्प सेट करने के लिए दोनों को बदलने और उनके चौराहे जाँच करने के लिए इस तरह के रूप है पायथन में ऑपरेटर)। सैद्धांतिक रूप से, n और m सूचियों में a और b में O(n+m) औसत पर O(n+m) है। लेकिन 1) इसे पहले सूचियों से सेट सेट करना होगा, जो एक गैर-नगण्य समय ले सकता है, और 2) यह मानता है कि आपके डेटा के बीच हैशिंग टकराव दुर्लभ हैं।

यह एक जनरेटर अभिव्यक्ति जैसे सूचियों, पर यात्रा प्रदर्शन उपयोग कर रहा है करने के लिए दूसरा तरीका:

any(i in a for i in b) 

यह इसलिए कोई नया स्मृति मध्यस्थ चर के लिए आवंटित किया जाता है, यथा-स्थान खोज करने के लिए अनुमति देता है। यह पहले खोज पर भी बाहर निकलता है। लेकिन in ऑपरेटर हमेशा O(n) सूचियों पर (here देखें)।

एक और प्रस्तावित विकल्प, सूची में से एक के माध्यम से एक hybridto पुनरावृति है इस सेट पर सदस्यता के लिए एक सेट में एक दूसरे को और परीक्षण कनवर्ट करते हैं, तो जैसे:

a = set(a); any(i in a for i in b) 

चौथा दृष्टिकोण का लाभ लेने के लिए है (जमे हुए) सेट (here देखें) की isdisjoint() विधि, उदाहरण के लिए:

not set(a).isdisjoint(b) 

तत्वों आप खोज एक सरणी की शुरुआत (उदाहरण के लिए यह क्रमबद्ध किया जाता है) के पास रखते हैं, जनरेटर अभिव्यक्ति के रूप में, इष्ट है सेट मुझे चौराहे मध्यस्थ चर के लिए नई स्मृति को आबंटित करने के लिए है Thod:

from timeit import timeit 
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=list(range(1000))", number=100000) 
26.077727576019242 
>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=list(range(1000))", number=100000) 
0.16220548999262974 

यहाँ सूची के आकार के समारोह में इस उदाहरण के लिए निष्पादन समय का ग्राफ है:

ध्यान दें कि दोनों अक्ष लघुगणक हैं। यह जनरेटर अभिव्यक्ति के लिए सबसे अच्छा मामला दर्शाता है। जैसा कि देखा जा सकता है, isdisjoint() विधि बहुत छोटी सूची आकारों के लिए बेहतर है, जबकि जेनरेटर अभिव्यक्ति बड़ी सूची आकारों के लिए बेहतर है।

दूसरी तरफ, खोज हाइब्रिड और जनरेटर अभिव्यक्ति की शुरुआत के साथ शुरू होती है, यदि साझा तत्व सरणी के अंत में व्यवस्थित रूप से प्रारंभ होता है (या दोनों सूचियां किसी भी मान को साझा नहीं करती हैं), विवाद और सेट चौराहे के दृष्टिकोण जेनरेटर अभिव्यक्ति और हाइब्रिड दृष्टिकोण से तेज़ तरीके से होते हैं।

>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000)) 
13.739536046981812 
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000)) 
0.08102107048034668 

यह ध्यान रखें कि जनरेटर अभिव्यक्ति तरीका बड़ा सूची आकार के लिए धीमी है दिलचस्प है। यह पिछले आंकड़े के लिए 100000 की बजाय 1000 पुनरावृत्ति के लिए है। यह सेटअप तब भी अनुमानित होता है जब कोई तत्व साझा नहीं किया जाता है, और विवाद और सेट चौराहे के दृष्टिकोण के लिए सबसे अच्छा मामला है। साझा करने के

उच्च मौका:

यहाँ यादृच्छिक संख्या का उपयोग कर (बजाय हेराफेरी सेटअप एक तकनीक या किसी अन्य के पक्ष में) दो विश्लेषण कर रहे हैं तत्वों बेतरतीब ढंग से [1, 2*len(a)] से लिया जाता है। साझा करने का कम मौका: तत्वों को यादृच्छिक रूप से [1, 1000*len(a)] से लिया जाता है।

अब तक, यह विश्लेषण माना जाता है कि दोनों सूचियां एक ही आकार के हैं।अन्यथा प्रदर्शन कम हो जाती है

सुनिश्चित करें कि a सूची छोटी है बनाओ,: विभिन्न आकारों की दो सूचियों के मामले में, उदाहरण के लिए a बहुत छोटा है, isdisjoint() हमेशा तेज है। इस प्रयोग में, a सूची आकार 5 पर स्थिर सेट किया गया था।

सारांश में:

• सूचियों बहुत छोटे (< 10 तत्वों) कर रहे हैं, not set(a).isdisjoint(b) हमेशा सबसे तेज है।
• यदि सूचियों में तत्वों को क्रमबद्ध किया गया है या नियमित संरचना है जिसका आप लाभ उठा सकते हैं, जेनरेटर अभिव्यक्ति any(i in a for i in b) बड़ी सूची आकारों में सबसे तेज़ है;
• not set(a).isdisjoint(b) के साथ सेट चौराहे का परीक्षण करें, जो bool(set(a) & set(b)) से हमेशा तेज़ है।
• हाइब्रिड "सूची के माध्यम से पुनरावृत्ति, सेट पर परीक्षण" a = set(a); any(i in a for i in b) आमतौर पर अन्य विधियों की तुलना में धीमी है।
• जनरेटर अभिव्यक्ति और हाइब्रिड तत्वों को साझा किए बिना सूचियों की बात करते समय दो अन्य दृष्टिकोणों की तुलना में बहुत धीमी हैं।

ज्यादातर मामलों में, isdisjoint() विधि का उपयोग कर जनरेटर अभिव्यक्ति के रूप में सबसे अच्छा तरीका बहुत लंबे समय तक ले, निष्पादित करने के लिए होगा के रूप में यह बहुत अक्षम है जब कोई तत्व साझा कर रहे हैं।

Answer 2

def lists_overlap3(a, b): 
    return bool(set(a) & set(b)) 

ध्यान दें: ऊपर मानता है कि आप जवाब के रूप में एक बूलियन चाहते हैं। यदि आप सभी की जरूरत एक if बयान में उपयोग करने के लिए एक अभिव्यक्ति है, बस if set(a) & set(b):

Answer 3

तुम भी any सूची समझ के साथ इस्तेमाल कर सकते हैं का उपयोग करें:

any([item in a for item in b]) 

Answer 4

आप उपयोग कर सकते हैं किसी भी समारोह/वा जनरेटर अभिव्यक्ति में बनाया गया:

def list_overlap(a,b): 
    return any(i for i in a if i in b) 

के रूप में जॉन और झूठ बताया है यह गलत परिणाम देता है जब हर के लिए मैं दो सूचियों bool (i) == झूठी द्वारा साझा की है। यह होना चाहिए:

return any(i in b for i in a) 

Answer 5

def lists_overlap(a, b): 
    sb = set(b) 
    return any(el in sb for el in a) 

यह asymptotically इष्टतम है (सबसे खराब स्थिति ओ (n + m)), और चौराहे दृष्टिकोण की वजह से any के शॉर्ट सर्किट की तुलना में बेहतर हो सकता है।

उदाहरण के लिए: के रूप में यह करने के लिए हो जाता है 3 in sb

संपादित

lists_overlap([3,4,5], [1,2,3]) 

ही सच है वापस आ जाएगी: (डेव किर्बी के लिए धन्यवाद के साथ) एक और भिन्नता:

def lists_overlap(a, b): 
    sb = set(b) 
    return any(itertools.imap(sb.__contains__, a)) 

यह imap पर निर्भर करता है जेनरेटर समझ के बजाए, सी में लागू किया गया है। यह मैपिंग फ़ंक्शन के रूप में sb.__contains__ का भी उपयोग करता है। मुझे नहीं पता कि यह कितना प्रदर्शन अंतर बनाता है। यह अभी भी शॉर्ट-सर्किट होगा।

Answer 6

अजगर 2.6 में या बाद में आप कर सकते हैं:

return not frozenset(a).isdisjoint(frozenset(b)) 

Answer 7

यह प्रश्न बहुत पुराना है, लेकिन मैंने देखा कि जब लोग सेट बनाम सूचियों पर बहस कर रहे थे, तो कोई भी उन्हें एक साथ उपयोग करने का विचार नहीं करता था। Soravux के उदाहरण के बाद,

सूचियों के लिए सबसे खराब मामला:

>>> timeit('bool(set(a) & set(b))', setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000) 
100.91506409645081 
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000) 
19.746716022491455 
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=[x+9999 for x in range(10000)]", number=100000) 
0.092626094818115234 

और सूचियों के लिए सबसे अच्छा मामले:

>>> timeit('bool(set(a) & set(b))', setup="a=list(range(10000)); b=list(range(10000))", number=100000) 
154.69790101051331 
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=list(range(10000))", number=100000) 
0.082653045654296875 
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=list(range(10000))", number=100000) 
0.08434605598449707 

तो भी तेजी से दो सूचियों के माध्यम से पुनरावृत्ति से पुनरावृत्ति है, हालांकि एक सूची देखने के लिए यह एक सेट में है, जो यह जांचने के बाद समझ में आता है कि एक सेट में कोई संख्या स्थिर समय लेती है, जबकि सूची के माध्यम से पुनरावृत्ति की जांच करके सूची की लंबाई के लिए आनुपातिक समय लगता है।

इस प्रकार, मेरा निष्कर्ष यह है कि एक सूची के माध्यम से पुनरावृत्त है, और जांचें कि यह पर सेट है या नहीं।

Answer 8

यदि आपको परवाह नहीं है कि ओवरलैपिंग तत्व क्या हो सकता है, तो आप एक सेट के रूप में संयुक्त सूची बनाम संयुक्त सूची के len को आसानी से देख सकते हैं। यदि ओवरलैपिंग तत्व हैं, तो सेट छोटा होगा:

len(set(a+b+c))==len(a+b+c) कोई ओवरलैप नहीं होने पर सत्य लौटाता है।

Answer 9

मैं एक कार्यात्मक प्रोग्रामिंग शैली के साथ में एक और एक फेंक देंगे:

any(map(lambda x: x in a, b)) 

स्पष्टीकरण:

map(lambda x: x in a, b) 

बूलियन्स जहां b के तत्वों a में पाए जाते हैं की एक सूची देता है। उस सूची को any पर भेज दिया जाता है, जो True देता है यदि कोई तत्व True है।