सूची करने के लिए तेज़ तरीका <T>Contains()

Question

मैं ऐसा करने की कोशिश कर रहा हूं जो मुझे लगता है कि "डी-इंटरेक्ट" है (मुझे यकीन नहीं है कि उचित नाम क्या है, लेकिन एपिकगेम्स के टिम स्वीनी ने इसे कहा पुराने UnrealEd में)

// foo and bar have some identical elements (given a case-insensitive match) 
List‹string› foo = GetFoo(); 
List‹string› bar = GetBar(); 

// remove non matches 
foo = foo.Where(x => bar.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList(); 
bar = bar.Where(x => foo.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList(); 

फिर बाद में, मैं एक और चीज करता हूं जहां मैं मूल से परिणाम घटाता हूं, यह देखने के लिए कि मैंने कौन से तत्व हटा दिए हैं। यह एक्स्सेप्ट() का उपयोग कर सुपर-फास्ट है, इसलिए वहां कोई परेशानी नहीं है।

ऐसा करने का एक तेज़ तरीका होना चाहिए, क्योंकि यह किसी भी सूची में ~ 30,000 तत्वों (स्ट्रिंग के) के साथ बहुत खराब प्रदर्शन कर रहा है। अधिमानतः, इस कदम को करने का एक तरीका और बाद में एक में गिरने से एक अच्छा हो जाएगा। मैंने बजाय .xists() का उपयोग करने की कोशिश की।(), लेकिन यह थोड़ा धीमा है। मुझे थोड़ा मोटा लगता है, लेकिन मुझे लगता है कि यह कुछ संयोजन के साथ संभव होना चाहिए() और .Intersect() और/या। यूनियन()।

Answer 1

के साथ एक दूसरे को काटना

इसे इस तरह से किया जाना होगा:

var matches = ((from f in foo 
       select f) 
       .Intersect(
        from b in bar 
        select b, StringComparer.InvariantCultureIgnoreCase)) 

Answer 2

इस ऑपरेशन को सममित अंतर कहा जा सकता है।

आपको हैश तालिका की तरह एक अलग डेटा संरचना की आवश्यकता है। दोनों सेटों के चौराहे को इसमें जोड़ें, फिर प्रत्येक सेट से चौराहे को अंतर करें।

अद्यतन:

मैं कोड में यह कोशिश करने के लिए समय का एक सा हो गया।

मूल: 79,499 एमएस

HashSet: 33 एमएस

BTW मैं निम्नलिखित परिणामों के साथ 50,000 तार के एक सेट के साथ HashSet<T> इस्तेमाल किया, 2 से 10 वर्ण लंबा से , हैशसेट पर SymmetricExceptWith नामक एक विधि है जिसे मैंने सोचा था कि मेरे लिए काम करेगा, लेकिन यह वास्तव में दोनों सेटों के सेट को सेट करने के लिए अलग-अलग तत्वों को जोड़ता है। शायद यह वही है जो आप चाहते हैं, शुरुआती दो सेटों को अनमोडिफाइड छोड़ने के बजाय, और कोड अधिक सुरुचिपूर्ण होगा।

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.Linq; 

class Program 
{ 
    static void Main(string[] args) 
    { 
     // foo and bar have some identical elements (given a case-insensitive match) 
     var foo = getRandomStrings(); 
     var bar = getRandomStrings(); 

     var timer = new Stopwatch(); 

     timer.Start(); 
     // remove non matches 
     var f = foo.Where(x => !bar.Contains(x)).ToList(); 
     var b = bar.Where(x => !foo.Contains(x)).ToList(); 
     timer.Stop(); 

     Debug.WriteLine(String.Format("Original: {0} ms", timer.ElapsedMilliseconds)); 

     timer.Reset(); 

     timer.Start(); 
     var intersect = new HashSet<String>(foo); 
     intersect.IntersectWith(bar); 

     var fSet = new HashSet<String>(foo); 
     var bSet = new HashSet<String>(bar); 

     fSet.ExceptWith(intersect); 
     bSet.ExceptWith(intersect); 
     timer.Stop(); 

     var fCheck = new HashSet<String>(f); 
     var bCheck = new HashSet<String>(b); 

     Debug.WriteLine(String.Format("Hashset: {0} ms", timer.ElapsedMilliseconds)); 

     Console.WriteLine("Sets equal? {0} {1}", fSet.SetEquals(fCheck), bSet.SetEquals(bCheck)); //bSet.SetEquals(set)); 
     Console.ReadKey(); 
    } 

    static Random _rnd = new Random(); 

    private const int Count = 50000; 

    private static List<string> getRandomStrings() 
    { 
     var strings = new List<String>(Count); 

     var chars = new Char[10]; 

     for (var i = 0; i < Count; i++) 
     { 
      var len = _rnd.Next(2, 10); 

      for (var j = 0; j < len; j++) 
      { 
       var c = (Char)_rnd.Next('a', 'z'); 
       chars[j] = c; 
      } 

      strings.Add(new String(chars, 0, len)); 
     } 

     return strings; 
    } 
} 

Answer 3

एक सूची पर तालिका रखती है हे (एन) ऑपरेशन है:

यहाँ कोड है। यदि आपके पास एक अलग डेटा संरचना थी, जैसे क्रमबद्ध सूची या शब्दकोश, तो आप नाटकीय रूप से अपना समय कम कर देंगे। एक क्रमबद्ध सूची में एक कुंजी तक पहुंच आमतौर पर ओ (लॉग एन) समय होता है, और हैश में आमतौर पर ओ (1) समय होता है।

Answer 4

तत्व एक सूची के भीतर अद्वितीय हैं, तो आप का उपयोग कर एक HashSet

HashSet (टी) वर्ग उच्च प्रदर्शन सेट आपरेशन प्रदान करता है पर विचार करना चाहिए। एक सेट संग्रह है जिसमें कोई डुप्लिकेट तत्व नहीं हैं, और जिनके तत्व विशेष क्रम में नहीं हैं।

Answer 5

क्रमबद्ध सूची के साथ, आप द्विआधारी खोज का उपयोग कर सकते हैं।