निर्धारित करें कि एक IEnumerable <T> एक और IEnumberable <T>

Question

की किसी भी वस्तु में शामिल मैं 2 IEnumerable<int>

IEnumerable<int> x; 
IEnumerable<int> y; 

निर्धारित करने के लिए y में किसी भी पूर्णांक एक्स में मौजूद है, तो सबसे अच्छा सबसे अच्छा तरीका क्या है?
वर्तमान में मैं उपयोग कर रहा हूँ:

return x.Intersect<int>(y).Count() > 0; 

यह काफी लूप करने के लिए तेजी से हो सकता है और प्रत्येक व्यक्तिगत रूप से परीक्षण होगा?

foreach (int i in x) 
{ 
    foreach (int j in y) 
    { 
     if (i == j) return true; 
    } 
} 
return false; 

सूचियों कि अगर विचार में मायने रखती है अपेक्षाकृत हल्के हैं, वाई में एक्स में 50 से अधिक नहीं ints और 4 के साथ।

Answer 1

यह Count method के बजाय Any method उपयोग करने के लिए सबसे तेजी से होगा:

return x.Intersect<int>(y).Any(); 

मतलब यह है कि IEnumerable<int> कार्यान्वयन भी ICollection<int> को लागू नहीं करता है। उस स्थिति में, Count (मामले में IEnumerable<T> लागू ICollection<T>) एक ओ (एन) ऑपरेशन है जबकि Anyहमेशा एक ओ (1) ऑपरेशन है। (क्योंकि यह केवल एकल तत्व के लिए जांचता है)। हालांकि, Count का व्यवहार एक कार्यान्वयन विवरण है, और आपको उस पर भरोसा नहीं करना चाहिए।

मैंने इस बारे में अधिक गहराई से in a blog post लिखा है जो Count() बनाम Any() का उपयोग करने के बारे में विस्तार से बताता है। सारांश में:

• अनुक्रम में तत्वों के होने की जाँच करने के लिए उपयोग Enumerable.Any विस्तार विधि करते हैं।
• नहीं उपयोग करते हैं, शून्य के खिलाफ तुलना में Enumerable.Count विस्तार विधि DO के रूप में निम्नलिखित अर्थ की दृष्टि से बराबर हैं:
  • sequence.Count() == 0
  • !sequence.Any()
• करते नहीं तुलना में Enumerable.Count विस्तार विधि का उपयोग "शून्य नहीं" स्थिति के विरुद्ध, जैसा कि निम्नलिखित अर्थात् समकक्ष हैं:
  • sequence.Count != 0
  • sequence.Any()

Answer 2

संपादित करें: नीचे मूल जवाब वास्तव में जटिलता के मामले में काम कर रहा है। यदि अनुक्रम काफी कम हैं, GetNext() के माध्यम से सभी कॉल, HashSet आदि का निर्माण वास्तव में Intersect(y).Any() का उपयोग करने से अधिक महंगा होगा। हालांकि, उस मामले में दोनों कॉल वास्तव में वैसे भी बहुत जल्दी हो जाएगा।के रूप में दो दृश्यों लंबे समय तक मिलता है

दूसरे शब्दों में, Intersect(y).Any() निश्चित रूप से बेहतर मापता है, लेकिन अगर आप पूरी तरह से यकीन कि दृश्यों कम हैं कर रहे हैं के लिए, नेस्टेड लूप समाधान तेजी से हो जाएगा।

मूल जवाब

नहीं है, Intersect() दो लूप समाधान की तुलना में तेजी होगा - लेकिन जैसा कि CasperOne लिखा था, Any()Count() की तुलना में तेजी है क्योंकि यह जैसे ही यह एक तत्व देखता है बाहर निकल जाएगा किया जाएगा।

लंबाई एन और एम की अनुक्रमित मानते हैं, इंटरसेक्ट O(N + M) होगा जबकि दो-लूप समाधान O(N * M) है।

इंटरसेक्ट "आंतरिक" अनुक्रम से एक HashSet बनाता है (इस O(M) जटिलता लेता है) और फिर बाहरी अनुक्रम (जो O(N) जटिलता लेता है) के माध्यम से लूप होता है, किसी भी तत्व जो सेट में है उपज। इन परिणामों को स्ट्रीम किया जाता है - आंतरिक अनुक्रम का मूल्यांकन किया जाएगा जब पहले तत्व से Intersect() से अनुरोध किया जाता है, लेकिन यह केवल पहले मैच (यदि कोई हो) ढूंढने तक जाता है। Any() का उपयोग करके यदि आपके पास कोई मिलान है तो आपके पास "प्रारंभिक" होगा, इसलिए जटिलता को पूरा करते समय हमें कुल मिलानों को ध्यान में रखना आवश्यक नहीं है।

LINQ चट्टानों से स्ट्रीमिंग परिणाम - यह आपके सिर के दौर (साथ ही स्थगित निष्पादन) प्राप्त करने के लायक है।

Answer 3

आप ऐसा करने का बेहतर कर रहे हैं: के रूप में यह एक भी मैच पाता है

return x.Intersect(y).Any(); 

यह रूप में जल्द ही रद्द कर देगा, और संग्रह के माध्यम से गणना बंद करो।

Answer 4

Intersect ठीक है, लेकिन जैसा कि अन्य ने कहा है कि मैं परिणाम पर .Count() पर कॉल नहीं करूंगा।

कारण यह है कि अंतर दो सूचियों का चौराहे बनाता है। यह बनाता है जो को छेड़छाड़ करने वाला है, लेकिन यह वास्तव में उन परिणामों को वास्तव में गणना नहीं करता है। अधिकांश काम उस समय तक स्थगित कर दिया जाता है जब आप अंततः इस गणना पर फिर से शुरू होते हैं।

Count के साथ समस्या यह है कि यह पूरे गणना पर फिर से शुरू होता है। इसलिए न केवल यह हमेशा सभी परिणामों की गणना करता है, बल्कि यह उन परिणामों को कंप्यूटिंग करने में शामिल सभी कार्यों का भी कारण बनता है।

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

यह इन दो स्निपेट के बीच अंतर की तरह है:

int count = 0; 
foreach (int i in x) 
{ 
    foreach (int j in y) 
    { 
     if (i==j) count++; 
    } 
} 
return (count > 0); 

।

// this one should look familiar 
foreach (int i in x) 
{ 
    foreach (int j in y) 
    { 
     if (i==j) return true; 
    } 
} 
return false; 

स्पष्ट रूप से दूसरा औसत पर बहुत तेज है। Any() का प्रदर्शन समान (जैसा कि हैशसेट के लिए धन्यवाद नहीं) दूसरा स्निपेट होगा, जबकि Count() पहले के समान होगा।

Answer 5

यह प्रश्न और अंतिम उत्तर मेरे उत्तर के रूप में 1 वर्ष से अधिक पुराना है; हालांकि, मेरे निष्कर्ष स्वीकृत उत्तर से अलग हैं। मुझे लगता है कि लूपिंग Intersect.Any() का उपयोग करने से काफी तेज है। शायद मेरा बेंचमार्क कोड सही नहीं है?

यहां कोड है जो मैं इंटरसेक्ट, नेस्टेड लूप और इंडेक्सऑफ के साथ एक लूप के बीच प्रति सेकंड पुनरावृत्तियों की संख्या को खोजने के लिए उपयोग करता हूं। कृपया वीबी क्षमा करें। ;)

Dim ArrayLength As Integer = 50 
Dim doesContain As Boolean = False 
Dim counter As Integer = 0 
Dim sw As New System.Diagnostics.Stopwatch() 
Dim BigArray1 As String() = New String(ArrayLength) {} 
Dim BigArray2 As String() = New String(ArrayLength) {} 
Dim rand As New Random(DateTime.Now.Millisecond) 
For i As Integer = 0 To ArrayLength 
    BigArray1(i) = Convert.ToChar(rand.Next(0, 255)).ToString() 
    BigArray2(i) = Convert.ToChar(rand.Next(0, 255)).ToString() 
Next 
Dim AnEnumerable1 As IEnumerable(Of String) = BigArray1 
Dim AnEnumerable2 As IEnumerable(Of String) = BigArray2 

counter = 0 
sw.Restart() 
Do 
    doesContain = False 
    For Each x As String In AnEnumerable1 
     For Each y As String In AnEnumerable2 
      If x.Equals(y) Then 
       doesContain = True 
       Exit For 
      End If 
     Next 
     If doesContain Then Exit For 
    Next 
    counter += 1 
Loop While sw.ElapsedMilliseconds < 1000 
Console.WriteLine("InnerLoop iterated: " & counter.ToString() & " times in " & sw.ElapsedMilliseconds.ToString() & "ms.") 

counter = 0 
sw.Restart() 
Do 
    doesContain = AnEnumerable1.Intersect(AnEnumerable2).Any() 
    counter += 1 
Loop While sw.ElapsedMilliseconds < 1000 
Console.WriteLine("Intersect iterated: " & counter.ToString() & " times in " & sw.ElapsedMilliseconds.ToString() & "ms.") 

counter = 0 
sw.Restart() 
Do 
    For Each x As String In AnEnumerable1 
     If Array.IndexOf(Of String)(BigArray2, x) <> -1 Then 
      Exit For 
     End If 
    Next 
    counter += 1 
Loop While sw.ElapsedMilliseconds < 1000 
Console.WriteLine("IndexOf iterated: " & counter.ToString() & " times in " & sw.ElapsedMilliseconds.ToString() & "ms.") 

मेरे परिणाम दो 5,000,000 आइटम सरणी से अधिक हैं। उच्च पुनरावृत्तियों बेहतर हैं:

• इनरलूप पुनरावृत्त: 1000ms में 2 9 74553 बार।
• पुनरावृत्त छेड़छाड़: ​​1168ms में 4 बार।
• इंडेक्स अगर पुन: 1000ms में 41 9 4423 बार।

मेरे परिणाम दो 50 आइटम सरणी से अधिक हैं। उच्च पुनरावृत्तियों बेहतर हैं:

• इनरलूप पुनरावृत्त: 100057 में 375712 बार।
• पुन: छेड़छाड़: ​​1000ms में 203721 बार।
• इंडेक्स द्वारा पुन: 1000000 में 668421 बार।