2013-01-14 9 views
7

मेरे पास एक ऐसा एप्लिकेशन है जिसे इनपुट पैरामीटर के रूप में कई मिलियन char * में लेना आवश्यक है (आमतौर पर 512 वर्णों (यूनिकोड में) से कम स्ट्रिंग्स), और उन्हें रूपांतरित और संग्रहित करें। नेट स्ट्रिंग्सस्ट्रिंग रूपांतरणों के लिए कई मिलियन char * अनुकूलित करना

यह मेरे आवेदन के प्रदर्शन में एक वास्तविक बाधा बन गया है। मैं सोच रहा हूं कि क्या कुछ डिजाइन पैटर्न या विचार इसे अधिक प्रभावशाली बनाने के लिए हैं।

एक महत्वपूर्ण हिस्सा है जो मुझे महसूस करता है कि इसे बेहतर किया जा सकता है: बहुत सारे डुप्लिकेट हैं। कहें कि 1 मिलियन ऑब्जेक्ट्स आ रहे हैं, वहां केवल 50 अद्वितीय चार * पैटर्न हो सकते हैं।

रिकॉर्ड के लिए, यहाँ एल्गोरिथ्म मैं (इस एल्गोरिथ्म सी ++ में है, लेकिन परियोजना के बाकी सी # में है)

String ^StringTools::MbCharToStr (const char *Source) 
{ 
    String ^str; 

    if((Source == NULL) || (Source[0] == '\0')) 
    { 
     str = gcnew String(""); 
    } 
    else 
    { 
     // Find the number of UTF-16 characters needed to hold the 
     // converted UTF-8 string, and allocate a buffer for them. 
     const size_t max_strsize = 2048; 

     int wstr_size = MultiByteToWideChar (CP_UTF8, 0L, Source, -1, NULL, 0); 
     if (wstr_size < max_strsize) 
     { 
     // Save the malloc/free overhead if it's a reasonable size. 
     // Plus, KJN was having fits with exceptions within exception logging due 
     // to a corrupted heap. 

     wchar_t wstr[max_strsize]; 

     (void) MultiByteToWideChar (CP_UTF8, 0L, Source, -1, wstr, (int) wstr_size); 
     str = gcnew String (wstr); 
     } 
     else 
     { 
     wchar_t *wstr = (wchar_t *)calloc (wstr_size, sizeof(wchar_t)); 
     if (wstr == NULL) 
      throw gcnew PCSException (__FILE__, __LINE__, PCS_INSUF_MEMORY, MSG_SEVERE); 

     // Convert the UTF-8 string into the UTF-16 buffer, construct the 
     // result String from the UTF-16 buffer, and then free the buffer. 

     (void) MultiByteToWideChar (CP_UTF8, 0L, Source, -1, wstr, (int) wstr_size); 
     str = gcnew String (wstr); 
     free (wstr); 
     } 
    } 
    return str; 
} 
+4

यह सी ++/सीएलआई या सी ++/सीएक्स की तरह सी ++ की तरह दिखता है। मैं केवल टैग नहीं बदल रहा हूं क्योंकि मुझे नहीं पता कि कौन सा है। – bames53

+0

तो आप केवल अपने 50 या तो सी # स्ट्रिंग्स और दस लाख संदर्भों के साथ समाप्त करना चाहते हैं? –

+0

इसकी सी ++/सीएलआई, और हाँ, मेरे पास 1 मिलियन संदर्भ हो सकते हैं, यह समय के साथ परीक्षणों का संग्रह हो सकता है। – greggorob64

उत्तर

5

आप trie संरचना को खिलाने के लिए इनपुट स्ट्रिंग से प्रत्येक वर्ण का उपयोग कर सकते हैं। पत्तियों पर, एक एकल .NET स्ट्रिंग ऑब्जेक्ट है। फिर, जब char* उसमें आता है जिसे आपने पहले देखा है, तो आप किसी भी स्मृति को आवंटित किए बिना मौजूदा .NET संस्करण को तुरंत पा सकते हैं।

छद्म कोड:

  • एक खाली trie के साथ शुरू,
  • प्रक्रिया एक चार * trie खोज जब तक आप आगे कोई
  • अपने पूरे चार तक नोड्स जोड़ने के लिए जा सकते हैं द्वारा * इनकोडिंग कर दिया गया है पत्ती में नोड्स के रूप में
  • , एक वास्तविक नेट स्ट्रिंग

इस दूसरे अतः सवाल का जवाब देते हैं आप starte मिलना चाहिए डी: How to create a trie in c#

+0

मुझे लगता है कि यह एक ठोस कार्यान्वयन होगा जो अच्छी तरह से काम करना चाहिए। – greggorob64

1

मैं शायद का प्रयोग करेंगे स्ट्रिंग के लिए चार * कन्वर्ट करने के लिए उपयोग कर रहा हूँ है एक टर्नरी पेड़ संरचना, या इसी तरह के आधार पर एक कैश, और यह देखने के लिए इनपुट स्ट्रिंग को देखें कि यह पहले से ही एक वर्ण को .NET प्रतिनिधित्व में परिवर्तित करने से पहले परिवर्तित हो गया है या नहीं।

3

एक महत्वपूर्ण हिस्सा है जो मुझे महसूस करता है कि इसे बेहतर किया जा सकता है: बहुत सारे डुप्लिकेट हैं। कहें कि 1 मिलियन ऑब्जेक्ट्स आ रहे हैं, वहां केवल 50 अद्वितीय चार * पैटर्न हो सकते हैं।

यदि यह मामला है, तो आप एक नक्शे के भीतर "मिला" पैटर्न के भंडारण (जैसे एक std::map<const char*, gcroot<String^>> का उपयोग कर [हालांकि आप const char* के लिए एक comparer की आवश्यकता होगी के रूप में) पर विचार करें, और वापसी के लिए उपयोग करें कि कर सकते हैं पहले परिवर्तित मूल्य।

मानचित्र को संग्रहीत करने, तुलना करने आदि के लिए एक ओवरहेड है। हालांकि, नाटकीय रूप से कम स्मृति उपयोग (आप प्रबंधित स्ट्रिंग उदाहरणों का पुन: उपयोग कर सकते हैं) के साथ-साथ स्मृति आवंटन (कॉलोक) को सहेज सकते हैं। /मुक्त)। इसके अलावा, के बजाय malloc का उपयोग करना संभवतः एक बहुत छोटा सुधार होगा, क्योंकि आपको MultiByteToWideChar पर कॉल करने से पहले स्मृति को शून्य करने की आवश्यकता नहीं है।

+0

मैं निश्चित रूप से मॉलोक से कॉलोक पर स्विच कर दूंगा। मैपिंग पेड़ कार्यान्वयन के समान ही लगता है, लेकिन चूंकि मेरे पास .NET डेटाटाइप तक पहुंच है (सी ++ मेरा मतलब सी ++ था। नेट, मानक सी ++ नहीं), मैं अपने मानचित्र प्रकारों का उपयोग करने में सक्षम हो सकता हूं। – greggorob64

+0

@ greggorob64 आप देशी प्रकार के साथ कुंजी के रूप में आसानी से .NET संग्रह के साथ काम करने में सक्षम नहीं होंगे। 'Gdroot 'मान के साथ' std :: map' का उपयोग करके कस्टम निर्मित प्रकार के बिना काम करेगा, और आपको एक ही' लॉग (एन) 'पहुंच समय को ट्राई के रूप में देगा। ;) –

+0

@Reed: तारों की संख्या के संबंध में 'ओ (1) 'की कोशिश की जाती है, न कि' ओ (एलजी एन)'। –

2

मुझे लगता है कि आप जो पहला ऑप्टिमाइज़ेशन कर सकते हैं, वह आपके पहले प्रयास को MultiByteToWideChar को एक नल पॉइंटर के बजाय बफर से शुरू करना होगा। क्योंकि आपने CP_UTF8 निर्दिष्ट किया है, MultiByteToWideChar अपेक्षित लंबाई निर्धारित करने के लिए पूरी स्ट्रिंग पर चलना चाहिए।यदि कुछ लंबाई है जो आपके तारों के विशाल बहुमत से अधिक लंबी है, तो आप ढेर पर उस आकार के बफर को आवंटित रूप से आवंटित करने पर विचार कर सकते हैं; और यदि वह विफल रहता है, तो गतिशील आवंटन पर जा रहा है। यही है, अगर if/elseif/else के बाहर ब्लॉक करें तो पहली शाखा को स्थानांतरित करें।

आप स्रोत स्ट्रिंग की लंबाई की गणना करके और इसे स्पष्ट रूप से पारित करके कुछ समय बचा सकते हैं - इस तरह मल्टीबाइट टॉवाइड कैर को हर बार जब आप इसे कॉल करते हैं तो strlen नहीं करना पड़ता है।

ऐसा कहा गया है, ऐसा लगता है कि आपकी बाकी परियोजना सी # है, तो आपको कनवर्ट करने के एकमात्र उद्देश्य के लिए सी ++/सीएलआई में साइड असेंबली के पक्ष में होने के बजाय इसे करने के लिए डिज़ाइन की गई .NET बीसीएल कक्षा पुस्तकालयों का उपयोग करना चाहिए। तार। यही System.Text.Encoding है।

मुझे संदेह है कि आप किसी भी तरह की कैशिंग डेटा संरचना का उपयोग कर सकते हैं जिसका उपयोग आप यहां कर सकते हैं।

ओह, और MultiByteToWideChar के परिणाम को अनदेखा न करें - न केवल आपको void पर कुछ भी डालना चाहिए, आपको MultiByteToWideChar ईवेंट में अपरिभाषित व्यवहार नहीं मिला है।

+0

मैं system.text.encoding नामस्थानों में देखूंगा। जब हमने पहली बार .NET का उपयोग शुरू किया, तो हमने मानक स्ट्रिंग contstuctor का उपयोग किया: नई स्ट्रिंग (char * इनपुट)। यह व्यापक वर्णों के साथ जल्दी से बाहर निकल गया, यही कारण है कि ऊपर वर्णित कार्यान्वयन पाया गया और इसका इस्तेमाल किया गया। सही समाधान निश्चित रूप से लाइब्रेरी givent आटा का उपयोग कर रहा है। – greggorob64

संबंधित मुद्दे