हैशसेट प्रदर्शन मौजूदा तत्वों के लिए बनाम बनाम

Question

किसी कारण से, HashSet पर Add ऑपरेशन Contains ऑपरेशन से धीमा है जब तत्व पहले से ही HashSet में मौजूद है।

Stopwatch watch = new Stopwatch(); 
    int size = 10000; 
    int iterations = 10000; 


    var s = new HashSet<int>(); 
    for (int i = 0; i < size; i++) { 
     s.Add(i); 
    } 

    Console.WriteLine(watch.Time(() => 
    { 
     for (int i = 0; i < size; i++) { 
      s.Add(i); 
     } 
    }, iterations)); 

    s = new HashSet<int>(); 
    for (int i = 0; i < size; i++) { 
     s.Add(i); 
    } 

    // outputs: 47,074,764 

    Console.WriteLine(watch.Time(() => 
    { 
     for (int i = 0; i < size; i++) { 
      if (!s.Contains(i)) 
       s.Add(i); 
     } 
    }, iterations)); 

    // outputs: 41,125,219 

क्यों Contains तेजी Add से पहले ही से मौजूद तत्वों के लिए है:

यहाँ सबूत है?

नोट: मैं इस Stopwatch एक्सटेंशन को किसी अन्य SO प्रश्न से उपयोग कर रहा हूं।

public static long Time(this Stopwatch sw, Action action, int iterations) { 
     sw.Reset(); 
     sw.Start(); 
     for (int i = 0; i < iterations; i++) { 
      action(); 
     } 
     sw.Stop(); 

     return sw.ElapsedTicks; 
    } 

अद्यतन: आंतरिक परीक्षण से पता चला है कि बड़े प्रदर्शन अंतर केवल .NET ढांचे का x64 संस्करण पर होता है। फ्रेमवर्क के 32 बिट संस्करण के साथ समान गति पर चलाने के लिए लगता है (वास्तव में ऐसा लगता है कि इसमें शामिल संस्करण के साथ कुछ परीक्षण रनों में धीमी गति से चलती है) फ्रेमवर्क के एक्स 64 संस्करणों पर, इसमें वाला संस्करण लगता है लगभग 15% तेजी से चलाएं।

Answer 1

AddIfNotPresent एक अतिरिक्त विभाजन होता है कि प्रदर्शन नहीं करता है।आईएल के लिए आईएल पर एक नज़र डालें:

IL_000a: call  instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0) 
    IL_000f: stloc.0 
    IL_0010: ldarg.0 
    IL_0011: ldfld  int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets 
    IL_0016: ldloc.0 
    IL_0017: ldarg.0 
    IL_0018: ldfld  int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets 
    IL_001d: ldlen 
    IL_001e: conv.i4 
    IL_001f: rem 
    IL_0020: ldelem.i4 
    IL_0021: ldc.i4.1 
    IL_0022: sub 
    IL_0023: stloc.1 

यह हैश कोड के लिए बाल्टी स्थान की गणना कर रहा है। परिणाम स्थानीय स्मृति स्थान पर सहेजा गया है 1.

AddIfNotPresent कुछ समान करता है, लेकिन यह स्थान 2 पर गणना मूल्य भी बचाता है, ताकि आइटम उस स्थिति में हैश तालिका में सम्मिलित कर सके यदि आइटम नहीं करता है मौजूद। यह सहेजता है क्योंकि बाद में किसी स्थान को उस लूप में संशोधित किया जाता है जो आइटम की तलाश में जाता है। वैसे भी, यहाँ AddIfNotPresent के लिए प्रासंगिक कोड है: वैसे भी

IL_0011: call  instance int32 class System.Collections.Generic.HashSet`1<!T>::InternalGetHashCode(!0) 
    IL_0016: stloc.0 
    IL_0017: ldloc.0 
    IL_0018: ldarg.0 
    IL_0019: ldfld  int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets 
    IL_001e: ldlen 
    IL_001f: conv.i4 
    IL_0020: rem 
    IL_0021: stloc.1 
    IL_0022: ldarg.0 
    IL_0023: ldfld  int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets 
    IL_0028: ldloc.0 
    IL_0029: ldarg.0 
    IL_002a: ldfld  int32[] class System.Collections.Generic.HashSet`1<!T>::m_buckets 
    IL_002f: ldlen 
    IL_0030: conv.i4 
    IL_0031: rem 
    IL_0032: ldelem.i4 
    IL_0033: ldc.i4.1 
    IL_0034: sub 
    IL_0035: stloc.2 

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

Answer 2

दिलचस्प, मेरी मशीन (डेल अक्षांश डी 630, ड्यूल-कोर 2.2 गीगा) पर, मुझे परीक्षणों से पहले null कार्रवाई के विरुद्ध स्टॉपवॉच चलाने तक दोनों परीक्षणों के लिए लगभग समान परिणाम मिल रहे हैं। उदाहरण के लिए:

Without Contains(): 8205794 
With Contains(): 8207596 

अगर मैं इस तरह से कोड को संशोधित:

के बाद:

Stopwatch watch = new Stopwatch(); 
int size = 10000; 
int iterations = 10000; 

मैं सटीक कोड है कि विचाराधीन दे दिया है के साथ परीक्षण चला

जोड़ें:

watch.Time(null, 0); 

मेरे परिणाम हो:

Without Contains(): 8019129 
With Contains(): 8275771 

इस तरह कुछ अजीब Stopwatch कि ये उतार-चढ़ाव खड़ी कर रहा है के अंदर चल रहा है मुझे लगता है।

Answer 3

मेरा अनुमान है कि आपने विजुअल स्टूडियो से अपना परीक्षण चलाया है जिसके कारण AddIfNotPresent को Add में दबाने के लिए इनलाइनिंग हुई है, इसलिए आप विधि कॉल में अतिरिक्त स्तर के संकेत के परिणाम देख रहे हैं।

अगर मैं संकलन और किसी भी प्रवंचना वी.एस. दूर करने के लिए कमांड लाइन से चलाने ...

> csc /o+ /t:exe Program.cs 
> Program.exe 

... तो कोई प्रदर्शन अंतर है।

नमूना आउटपुट (परीक्षण की एक बड़ी संख्या के प्रतिनिधि):

35036174 
35153818 

35225763 
34862330 

35047377 
35033323