c# - हशसेट<पॉइंट> हशसेट<string> से इतना धीमा क्यों है?




.net performance (2)

मैं डुप्लिकेट की अनुमति के बिना कुछ पिक्सेल स्थानों को संग्रहीत करना चाहता था, इसलिए पहली बात दिमाग में आती है HashSet<Point> या इसी तरह की कक्षाएं। हालाँकि यह HashSet<string> जैसी किसी चीज़ की तुलना में बहुत धीमा प्रतीत होता है।

उदाहरण के लिए, यह कोड:

HashSet<Point> points = new HashSet<Point>();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x < img.Width; x++)
    {
        for (int y = 0; y < img.Height; y++)
        {
            points.Add(new Point(x, y));
        }
    }
}

लगभग 22.5 सेकंड लगते हैं।

जबकि निम्नलिखित कोड (जो स्पष्ट कारणों के लिए एक अच्छा विकल्प नहीं है) केवल 1.6 सेकंड लेता है:

HashSet<string> points = new HashSet<string>();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x < img.Width; x++)
    {
        for (int y = 0; y < img.Height; y++)
        {
            points.Add(x + "," + y);
        }
    }
}

तो, मेरे सवाल हैं:

  • क्या इसका कोई कारण है? मैंने इस उत्तर की जाँच की, लेकिन उस उत्तर में दर्शाई गई संख्या से 22.5 सेकंड अधिक है।
  • क्या डुप्लिकेट के बिना अंक स्टोर करने का एक बेहतर तरीका है?

प्रदर्शन ड्रॉप का मुख्य कारण सभी मुक्केबाजी चल रहा है (जैसा कि पहले ही हंस पसंत के जवाब में बताया गया है)।

इसके अलावा, हैश कोड एल्गोरिथ्म समस्या को बदतर करता है, क्योंकि यह Equals(object obj) को अधिक कॉल करता है जिससे बॉक्सिंग रूपांतरण की मात्रा बढ़ जाती है।

यह भी ध्यान दें कि Point का हैश कोड x ^ y द्वारा गणना की जाती है। यह आपके डेटा रेंज में बहुत कम फैलाव पैदा करता है, और इसलिए HashSet की बाल्टियाँ HashSet हैं - कुछ ऐसा जो string साथ नहीं होता है, जहाँ हैश का फैलाव बहुत बड़ा होता है।

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

(x << 16) ^ y

कुछ अच्छी सलाह के लिए जब हैश कोड की बात आती है, तो विषय पर एरिक लिपर्ट के ब्लॉग पोस्ट को पढ़ें।


बिंदु संरचना द्वारा प्रेरित दो पूर्ण समस्याएं हैं। जब आप Console.WriteLine(GC.CollectionCount(0)); जोड़ते हैं, तो आप कुछ देख सकते हैं Console.WriteLine(GC.CollectionCount(0)); परीक्षण कोड के लिए। आप देखेंगे कि प्वाइंट टेस्ट के लिए ~ 3720 संग्रह की आवश्यकता है लेकिन स्ट्रिंग टेस्ट को केवल ~ 18 संग्रह की आवश्यकता है। मुक्त करने के लिए नहीं। जब आप एक मूल्य प्रकार इतने सारे संग्रहों को देखते हैं तो आपको "उह-ओह, बहुत अधिक मुक्केबाजी" निष्कर्ष निकालने की आवश्यकता है।

इस मुद्दे पर कि IEqualityComparer<T> को अपना काम करवाने के लिए IEqualityComparer<T> आवश्यकता है। चूंकि आपने एक प्रदान नहीं किया था, इसलिए इसे EqualityComparer.Default<T>() द्वारा वापस लौटाया जाना चाहिए। यह विधि स्ट्रिंग के लिए एक अच्छा काम कर सकती है, यह IEquatable को लागू करती है। लेकिन प्वाइंट के लिए नहीं, यह एक प्रकार है जो .NET 1.0 से परेशान है और इसे कभी भी जेनरिक प्यार नहीं मिला। सभी यह कर सकते हैं वस्तु विधियों का उपयोग करें।

दूसरा मुद्दा यह है कि Point.GetHashCode () इस परीक्षण में बहुत अधिक टकराव नहीं करता है, इसलिए यह Object.Equals () को बहुत भारी बनाता है। स्ट्रिंग में एक उत्कृष्ट GetHashCode कार्यान्वयन है।

आप एक अच्छी तुलना के साथ HashSet प्रदान करके दोनों समस्याओं को हल कर सकते हैं। इस तरह:

class PointComparer : IEqualityComparer<Point> {
    public bool Equals(Point x, Point y) {
        return x.X == y.X && x.Y == y.Y;
    }

    public int GetHashCode(Point obj) {
        // Perfect hash for practical bitmaps, their width/height is never >= 65536
        return (obj.Y << 16) ^ obj.X;
    }
}

और इसका उपयोग करें:

HashSet<Point> list = new HashSet<Point>(new PointComparer());

और यह अब लगभग 150 गुना तेज है, आसानी से स्ट्रिंग परीक्षण को हरा देता है।






hashset