c# - String.Substring() इस कोड को टोंटी लगता है



performance (1)

परिचय

मेरे पास यह पसंदीदा एल्गोरिदम है जो मैंने कुछ समय पहले बनाया है जो मैं हमेशा नई प्रोग्रामिंग भाषाओं, प्लेटफार्मों आदि में लिख रहा हूं और कुछ प्रकार के बेंचमार्क के रूप में लिख रहा हूं। यद्यपि मेरी मुख्य प्रोग्रामिंग भाषा C # है, मैंने कोड को सचमुच कॉपी-पेस्ट किया है और सिंटैक्स को थोड़ा बदल दिया है, इसे जावा में बनाया है और इसे 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))
         ...

आँकड़े

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

माप

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

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

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

विचार

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

सवाल

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

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

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

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;
}

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

ध्यान दें कि यह स्ट्रिंग s1 के साथ 300.000 वर्णों के आकार का परीक्षण किया गया था। किसी कारण से 1 मिलिट्री कैरेक्टर सिर्फ C # में कभी खत्म नहीं होते हैं जबकि जावा में केवल 0.75 सेकेंड लगते हैं। मेमोरी मेमोरी और कूड़े के संग्रह की संख्या एक मेमोरी इश्यू को इंगित नहीं करती है। चोटी लगभग 400 एमबी की थी लेकिन विशाल प्रत्यय के पेड़ को देखते हुए यह सामान्य प्रतीत होता है। कोई भी अजीब कचरा इकट्ठा करने वाला पैटर्न नहीं देखा गया है।


अंक उत्पत्ति

एक शानदार लड़ाई होने के बाद जो दो दिन और तीन रात तक चली (और टिप्पणियों से अद्भुत विचार और विचार) आखिरकार मैं इस मुद्दे को ठीक करने में कामयाब रहा!

मैं ऐसे ही मुद्दों पर चलने वाले किसी भी व्यक्ति के लिए एक उत्तर पोस्ट करना चाहूंगा जहां string.Substring(i, j) फ़ंक्शन स्ट्रिंग का स्थान प्राप्त करने के लिए एक स्वीकार्य समाधान नहीं है क्योंकि स्ट्रिंग या तो बहुत बड़ी है और आप बर्दाश्त नहीं कर सकते। string.Substring(i, j) द्वारा किया गया string.Substring(i, j) (इसे एक copy बनाना होता है क्योंकि C # strings अपरिवर्तनीय हैं, इसके आस-पास कोई रास्ता नहीं है) या string.Substring(i, j) को कई बार भारी संख्या में कहा जाता है एक ही तार (जैसे मेरे छोरों के लिए नेस्टेड) ​​कचरा कलेक्टर को एक कठिन समय दे रहा है, या मेरे मामले में दोनों के रूप में!

प्रयास

मैंने कई सुझाई गई चीज़ों की कोशिश की है जैसे कि StringBuilder , Streams , unmanaged मेमोरी एलोकेशन का उपयोग करके Intptr और Mars का उपयोग unsafe{} ब्लॉक के भीतर और यहाँ तक कि एक IEnumerable और उपज बनाने के लिए दिए गए पदों के भीतर संदर्भ द्वारा वर्ण वापस करें। ये सभी प्रयास अल्टिमेटली विफल हो गए क्योंकि डेटा के जुड़ने का कुछ रूप ऐसा होना था क्योंकि प्रदर्शन को खतरे में डाले बिना चरित्र द्वारा मेरे पेड़ के चरित्र को टटोलना मेरे लिए कोई आसान रास्ता नहीं था। यदि केवल एक बार में एक सरणी के भीतर कई मेमोरी पतों पर स्पैन करने का एक तरीका था जैसे कि आप कुछ सूचक अंकगणित के साथ C ++ में सक्षम होंगे .. को छोड़कर .. (क्रेडिट @ इवान स्टोव की टिप्पणी के लिए)

समाधान

समाधान System.ReadOnlySpan<T> ( System.Span<T> अपरिवर्तनीय होने के कारण स्ट्रिंग नहीं हो सकता) का उपयोग कर रहा था, जो कि, अन्य चीजों के अलावा, हमें प्रतियों को बनाए बिना किसी मौजूदा सरणी के भीतर मेमोरी एड्रेस के उप सरणियों को पढ़ने की अनुमति देता है।

इस कोड का टुकड़ा पोस्ट किया गया:

string _s1 = s1.Substring(i, j);
if (stree.has(_s1))
{
    score += j - i;
    longest = j - i;
}

निम्नलिखित में बदल गया था:

if (stree.has(i, j))
{
    score += j - i;
    longest = j - i;
}

जहाँ stree.has() अब दो पूर्णांक (स्थिति और स्थान की लंबाई stree.has() लगते हैं:

ReadOnlySpan<char> substr = s1.AsSpan(i, j);

ध्यान दें कि मूल चर वस्तुतः प्रारंभिक s1 सरणी के वर्णों के सबसेट का संदर्भ है और प्रतिलिपि नहीं है! (इस फ़ंक्शन से s1 चर को सुलभ बनाया गया था)

ध्यान दें कि यह लिखने के समय मैं C # 7.2 और .NET फ्रेमवर्क 4.6.1 का उपयोग कर रहा हूं, जिसका अर्थ है कि स्पैन फीचर प्राप्त करने के लिए मुझे प्रोजेक्ट> प्रबंधित NuGet पैकेज पर जाना होगा, जिसमें "प्रीलेयरेज़ शामिल करें" चेकबॉक्स पर टिक करें और सिस्टम के लिए ब्राउज़ करें .Memory और इसे स्थापित करें।

प्रारंभिक परीक्षण को फिर से चलाना (लंबाई 1 मिलिअन वर्ण (1 एमबी) के स्ट्रिंग्स पर) गति 2+ मिनट से बढ़ गई (मैंने 2 मिनट के बाद इंतजार करना छोड़ दिया) ~ 86 मिलिसकॉन्ड !!





substring