[c#] स्ट्रिंग.Substring () इस कोड को बाधा लग रहा है



0 Answers

Question

परिचय

मेरे पास यह पसंदीदा एल्गोरिदम है जिसे मैंने कुछ समय पहले बनाया है जिसे मैं हमेशा नई प्रोग्रामिंग भाषाओं, प्लेटफार्मों आदि में कुछ प्रकार के बेंचमार्क के रूप में लिख रहा हूं और फिर से लिख रहा हूं। यद्यपि मेरी मुख्य प्रोग्रामिंग भाषा सी # है, मैंने बस सचमुच कोड को कॉपी-पेस्ट किया है और सिंटैक्स को थोड़ा बदल दिया है, इसे जावा में बनाया है और इसे 1000x तेज चलाने के लिए पाया है।

कोड

काफी कोड है लेकिन मैं केवल इस स्निपेट को प्रस्तुत करने जा रहा हूं जो मुख्य मुद्दा प्रतीत होता है:

for (int i = 0; i <= s1.Length; i++) 
{
    for (int j = i + 1; j <= s1.Length - i; j++)
    {
        string _s1 = s1.Substring(i, j);
        if (tree.hasLeaf(_s1))
         ...

आँकड़े

यह इंगित करना महत्वपूर्ण है कि इस विशेष परीक्षण में स्ट्रिंग एस 1 लंबाई 1 मिलियन वर्ण (1 एमबी) है।

माप

मैंने विजुअल स्टूडियो में अपना कोड निष्पादन प्रोफाइल किया है क्योंकि मैंने सोचा कि जिस तरह से मैं अपना पेड़ बनाता हूं या जिस तरह से मैं इसे पार करता हूं वह इष्टतम नहीं है। परिणामों की जांच करने के बाद ऐसा लगता है कि लाइन string _s1 = s1.Substring(i, j); निष्पादन समय के 90% से अधिक के लिए समायोजित कर रहा है!

अतिरिक्त अवलोकन

एक और अंतर जो मैंने देखा है वह यह है कि यद्यपि मेरा कोड सिंगल थ्रेडेड जावा सभी 8 कोर (100% सीपीयू उपयोग) का उपयोग करके इसे निष्पादित करने के लिए प्रबंधित करता है, जबकि समानांतर के साथ भी। () और बहु ​​थ्रेडिंग तकनीकें मेरा सी # कोड 35- सबसे अधिक 40%। चूंकि एल्गोरिदम स्केल (और आवृत्ति) की संख्या के साथ रैखिक रूप से स्केल करता है, इसलिए मैंने इसके लिए मुआवजा दिया है और फिर भी जावा में स्निपेट 100-1000x तीव्रता के क्रम को निष्पादित करता है।

विचार

मुझे लगता है कि ऐसा क्यों हो रहा है इस कारण से यह करना है कि सी # में तार अपरिवर्तनीय हैं इसलिए स्ट्रिंग। सब्स्ट्रिंग () को एक प्रतिलिपि बनाना है और चूंकि यह कई पुनरावृत्तियों के साथ लूप के लिए घोंसला में है, इसलिए मुझे बहुत प्रतिलिपि लगता है और कचरा संग्रहण जारी है, हालांकि, मुझे नहीं पता कि जावा में सबस्ट्रिंग कैसे कार्यान्वित किया जाता है।

सवाल

इस बिंदु पर मेरे विकल्प क्या हैं? सबस्ट्रिंग्स की संख्या और लंबाई के आसपास कोई रास्ता नहीं है (यह पहले से ही अधिकतम अनुकूलित है)। क्या कोई ऐसी विधि है जिसे मैं नहीं जानता (या शायद डेटा संरचना) जो मेरे लिए इस मुद्दे को हल कर सकती है?

अनुरोधित न्यूनतम कार्यान्वयन (टिप्पणियों से)

मैंने प्रत्यय वृक्ष के कार्यान्वयन को छोड़ दिया है जो निर्माण में ओ (एन) है और ओ (लॉग (एन)) ट्रैवर्सल में है

public static double compute(string s1, string s2)
{
    double score = 0.00;
    suffixTree stree = new suffixTree(s2);
    for (int i = 0; i <= s1.Length; i++) 
    {
        int longest = 0;
        for (int j = i + 1; j <= s1.Length - i; j++)
        {
            string _s1 = s1.Substring(i, j);
            if (stree.has(_s1))
            {
                score += j - i;
                longest = j - i;
            }
            else break;
         };

        i += longest;
    };
    return score;
}

प्रोफाइलर का स्क्रीनशॉट स्निपेट

नोट यह स्ट्रिंग एस 1 के साथ 300,000 वर्णों के आकार के साथ परीक्षण किया गया था। कुछ कारणों से 1 मिलियन वर्णों को जावा में रहते हुए सी # में कभी खत्म नहीं होता है, जबकि इसमें केवल 0.75 सेकेंड लगते हैं .. स्मृति की खपत और कचरा संग्रह की संख्या स्मृति समस्या को इंगित नहीं करती है। चोटी लगभग 400 एमबी थी लेकिन विशाल प्रत्यय पेड़ पर विचार करना यह सामान्य प्रतीत होता है। कोई अजीब कचरा इकट्ठा पैटर्न या तो देखा।




Related