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




performance (2)

परिचय

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


Answers

समस्या उत्पत्ति

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

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

प्रयास

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

समाधान

समाधान 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);

ध्यान दें कि substr वैरिएबल सचमुच प्रारंभिक s1 सरणी के अक्षरों के सबसेट का संदर्भ है, न कि प्रतिलिपि! ( s1 चर को इस समारोह से सुलभ बनाया गया था)

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

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


जॉन की असेंबली दिखाती है कि दो संस्करणों के बीच का अंतर यह है कि तेज़ संस्करण स्थानीय चरों में से एक को स्टोर करने के लिए रजिस्टरों ( esi,edi ) की एक जोड़ी का उपयोग करता है जहां धीमी संस्करण नहीं है।

जेआईटी कंपाइलर कोड के लिए रजिस्टर उपयोग के संबंध में अलग-अलग धारणाएं बनाता है जिसमें एक कोशिश-पकड़ ब्लॉक बनाम कोड होता है जो नहीं करता है। इससे अलग पंजीकरण आवंटन विकल्प अलग-अलग होते हैं। इस मामले में, यह कोशिश-पकड़ ब्लॉक के साथ कोड का पक्ष लेता है। अलग-अलग कोड विपरीत प्रभाव का कारण बन सकते हैं, इसलिए मैं इसे सामान्य उद्देश्य वाली गति-अप तकनीक के रूप में नहीं मानूंगा।

अंत में, यह बताने में बहुत मुश्किल है कि कौन सा कोड सबसे तेज़ चल रहा है। पंजीकरण आवंटन की तरह कुछ और इसे प्रभावित करने वाले कारक ऐसे निम्न स्तर के कार्यान्वयन विवरण हैं जो मुझे नहीं लगता कि कोई विशिष्ट तकनीक विश्वसनीय रूप से तेज़ कोड कैसे उत्पन्न कर सकती है।

उदाहरण के लिए, निम्नलिखित दो विधियों पर विचार करें। वे वास्तविक जीवन उदाहरण से अनुकूलित किए गए थे:

interface IIndexed { int this[int index] { get; set; } }
struct StructArray : IIndexed { 
    public int[] Array;
    public int this[int index] {
        get { return Array[index]; }
        set { Array[index] = value; }
    }
}

static int Generic<T>(int length, T a, T b) where T : IIndexed {
    int sum = 0;
    for (int i = 0; i < length; i++)
        sum += a[i] * b[i];
    return sum;
}
static int Specialized(int length, StructArray a, StructArray b) {
    int sum = 0;
    for (int i = 0; i < length; i++)
        sum += a[i] * b[i];
    return sum;
}

एक दूसरे का एक सामान्य संस्करण है। सामान्य प्रकार को StructArray साथ StructArray विधियों को समान बना देगा। चूंकि StructArray एक मान प्रकार है, इसलिए इसे सामान्य विधि का अपना संकलित संस्करण मिलता है। फिर भी वास्तविक चलने का समय विशेष विधि की तुलना में काफी लंबा है, लेकिन केवल x86 के लिए। X64 के लिए, समय काफी समान हैं। अन्य मामलों में, मैंने x64 के लिए अंतर भी देखा है।





c# performance substring