सी

Question

में फास्ट स्ट्रिंग तुलना मैं वर्तमान में

while(1) 
{ 
    generate_string(&buffer); 

    for(int i = 0; i < filelines; i++) 
    { 
     if(strcmp(buffer,line[i]) == 0) 
     { 
      /* do something */ 
     } 
    } 
} 

मैं कुछ लाख तार (जो उम्मीद है कि कुछ समय जल्द ही आधे से कटौती किया जाना चाहिए) के साथ एक फ़ाइल है पाश इस तरह की है, इन सभी तार की संख्या है फाइललाइन

लाइन [i] मूल रूप से स्ट्रिंग को संग्रहीत किया जाता है।

वर्तमान में, इन मिलियन तारों की तुलना के कारण, उत्पन्न_स्ट्रिंग (बफर); प्रति सेकेंड 42 बार निष्पादित किया जाता है। सी में स्ट्रिंग तुलना करने का कोई तेज़ तरीका है?

Answer 1

strcmp आमतौर पर सभी विक्रेताओं द्वारा अनुकूलित किया जाता है। हालांकि, अगर आप इस से संतुष्ट नहीं हैं तो आप की कोशिश कर सकते हैं:

• लुक Burst Tries
• तेज स्ट्रिंग तुलना के लिए एक प्रत्यय पेड़ का प्रयोग करें - देख this लेख
• अपने आवेदन में तार के आकार के आधार पर आप एक कस्टम स्ट्रिंग तुलनित्र लिख सकते हैं। E.g: जीएनयू libc छोटे स्ट्रिंग्स के लिए यह अनुकूलन प्रयुक्त होता था जहां उन्होंने पांच बाइट्स से छोटे स्ट्रिंग का परीक्षण पूर्णांक के रूप में किया था। एमएस cl में छोटे-तारों के लिए कुछ अनुकूलन भी हैं (इसे देखें)।

लेकिन अधिक महत्वपूर्ण बात यह सुनिश्चित करें कि strcmp अपने असली टोंटी है या नहीं।

Answer 2

मैं उपलब्ध न हो strcmp बुला स्ट्रिंग तुलना करने के लिए की तुलना में एक तेज़ तरीका पता नहीं है, लेकिन आप शायद इतना strcmp बुला बच सकते हैं। अपने तारों को स्टोर करने के लिए हैश टेबल का उपयोग करें और फिर आप जांच सकते हैं कि buffer में स्ट्रिंग हैश तालिका में है या नहीं। यदि आप "कुछ करते हैं" पर हिट की अनुक्रमणिका महत्वपूर्ण होती है, तो तालिका स्ट्रिंग को इंडेक्स में मैप कर सकती है।

Answer 3

आप पहले चार के आधार पर स्क्रीनिंग जैसी कुछ 'सस्ता' कोशिश कर सकते हैं। यदि पहले अक्षर मेल नहीं खाते हैं, तो तार बराबर नहीं हो सकते हैं। यदि वे मेल खाते हैं, तो पूरी स्ट्रिंग की तुलना करने के लिए strcmp को कॉल करें। यदि आप अपनी स्थिति के लिए उपयुक्त हैं तो आप बेहतर एल्गोरिदम पर विचार करना चाहेंगे; उदाहरण फाइल/लाइनों को सॉर्ट करना और एक हैश टेबल या समान स्ट्रिंग टेबल तकनीकों का उपयोग करके बाइनरी खोज करना होगा।

Answer 4

आप इस मामले में बाइनरी तुलना के साथ प्राप्त करने में सक्षम हो सकते हैं क्योंकि आपका प्रोग्राम वास्तव में क्रमबद्ध नहीं है, लेकिन समानता के लिए तुलना करता है।

आप लंबाई की लंबाई निर्धारित करके तुलनात्मक गति में भी सुधार कर सकते हैं (बशर्ते वे पर्याप्त रूप से भिन्न हों)। जब लंबाई यहां मेल नहीं खाती है, do something नहीं होगा।

बेशक, हैशिंग यहां एक और विचार होगा कि आपने कितनी बार हैश मूल्य पढ़ा है।

Answer 5

यदि मुझे आपका प्रश्न सही तरीके से मिलता है, तो आपको यह जांचना होगा कि अब तक सभी पंक्तियों के साथ एक स्ट्रिंग है या नहीं। मैं फ़ाइल लाइनों से एक ट्राई या Patricia tree को बेहतर तरीके से उपयोग करने का प्रस्ताव दूंगा।इस तरह सभी लाइनों पर जाने की बजाय आप रैखिक रूप से जांच सकते हैं यदि आपकी स्ट्रिंग मौजूद है (और थोड़ा और प्रयास - जहां)।

Answer 6

आप पहले ही अनुकूलन के साथ संकलित कर रहे हैं, है ना?

यदि आपके पास जगह के चारों ओर स्थित एक ट्री या हैशटेबल डेटा संरचना है, तो उपयोग करने के लिए तैयार है, तो आपको चाहिए।

यह विफल होने के कारण, संभवत: चीजों को गति देने के लिए एक आसान परिवर्तन जो आपके सरणी line को सॉर्ट करने के लिए है, इससे पहले कि आप स्ट्रिंग्स को खोजना शुरू करें। फिर क्रमबद्ध सरणी में buffer के लिए बाइनरी खोज। यह आसान है क्योंकि आपको आवश्यक दो कार्य मानक हैं - qsort और bsearch।

एक क्रमबद्ध सरणी में एक बाइनरी खोज केवल फाइललाइनों के बजाय लॉग (फ़ाइललाइन) स्ट्रिंग तुलना के बारे में करने की आवश्यकता है। तो आपके मामले में 20 मिलियन की बजाय कुछ-स्ट्रिंग तुलना generate_string पर है। आपके द्वारा दिए गए आंकड़ों से, मुझे लगता है कि आप उचित रूप से 20-25 गुना तेजी से जाने की उम्मीद कर सकते हैं, हालांकि मैं कुछ भी वादा नहीं करता हूं।

Answer 7

मैं आपको आश्वस्त कर सकता हूं, फ़ंक्शन strcmp असीमित रूप से बाधा नहीं है। आमतौर पर, strcmp अच्छी तरह अनुकूलित है और आर्किटेक्चर के आधार पर 4/8 बाइट्स से अधिक तारों के लिए 32 या 64 बिट तुलना कर सकता है। न्यूलिब और जीएनयू लिबिक दोनों यह करते हैं। लेकिन यहां तक ​​कि यदि आप 20 बार दोनों तारों में प्रत्येक बाइट को देखना चाहते थे, तो इससे कोई फर्क नहीं पड़ता कि अल्गो & डेटा संरचना विकल्प यहां किए गए हैं।

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

यहां मेरे साथ भालू - गणित का बहुत कुछ अनुसरण करता है। लेकिन मुझे लगता है कि यह स्पष्ट करने का एक अच्छा अवसर है कि क्यों एल्गोरिदम & डेटा संरचना की पसंद स्ट्रिंग तुलना की विधि से FAR अधिक महत्वपूर्ण होती है। स्टीव इस पर छूता है, लेकिन मैं इसे थोड़ा और गहराई में समझा देना चाहता था।

एन = 1e6 के साथ, लॉग (1e6, 2) = 1 9.9, तो आदर्श डेटा संरचना पर 20 तुलनाओं तक गोल करें।

वर्तमान में आप ओ (एन), या 1e6 संचालन का सबसे खराब मामला खोज कर रहे हैं।

तो कहें कि आप ओ (लॉग एन) सम्मिलन समय के साथ एक लाल-काले पेड़ का निर्माण करते हैं, और आप एन आइटम डालते हैं, यह पेड़ बनाने के लिए ओ (एन लॉग एन) समय है। तो यह आपके पेड़ के निर्माण के लिए आवश्यक 1e6 x 20 या 20e6 संचालन है।

आपके वर्तमान दृष्टिकोण में, डेटा संरचना का निर्माण ओ (एन), या 1e6 संचालन है, लेकिन आपका सबसे खराब केस खोज समय ओ (एन) भी है। तो जब तक आप फ़ाइल पढ़ते हैं और केवल 20 खोज ऑपरेशन करते हैं, तो आप 21,000,000 परिचालनों के सैद्धांतिक सबसे खराब मामले तक पहुंच जाते हैं। तुलनात्मक रूप से, लाल-काले पेड़ और 20 खोजों के साथ आपका सबसे खराब मामला 20,000,400 ऑपरेशंस है, या 99 (9) ऑपरेशन बेल्टर की तुलना में एक अनारक्षित सरणी पर है। तो 20 खोजों पर, आप पहले बिंदु पर हैं जहां एक अधिक परिष्कृत डेटा संरचना वास्तव में भुगतान करती है। लेकिन 1000 खोजों पर क्या होता है:

अनसुलझा सरणी = प्रारंभिक + 1000 x खोज समय = ओ (एन) + 1000 * ओ (एन) = 1,000,000 + 2,000,000,000 = 2,001,000,000 संचालन।

लाल-काला = प्रारंभिकरण + 1000 x खोज समय = ओ (एन लॉग एन) + 1000 * ओ (लॉग एन) = 20,000,000 + 20,000 = 20,020,000 संचालन।

2,001,000,000/20,020,000 ~ = 100x ओ (एन) खोज के लिए कई संचालन के रूप में।

1E6 खोज में है कि (1E6 + 1E6 * 1E6) है/(20e6 + 1E6 * 20) = 25,000x कई आपरेशनों के रूप में।

मान लें कि आपका कंप्यूटर 40e6 'ऑपरेशंस' को संभाल सकता है जो लॉग एन को 1 मिनट में करता है। आपके वर्तमान एल्गोरिदम के साथ एक ही काम करने में 25,000 मिनट या 17 दिन लगेंगे। या देखने का एक और तरीका यह है कि ओ (एन) खोज एल्गोरिदम केवल ओ (लॉग एन) एल्गोरिदम 1,000,000 कर सकता है जब 39 खोजों को संभाल सकता है। और जितनी अधिक खोज आप करते हैं, वह उलझन में आता है।

डेटा संरचनाओं के कई बेहतर विकल्पों के लिए स्टीव और dirkgently से प्रतिक्रिया देखें & एल्गोरिदम। मेरी केवल अतिरिक्त सावधानी होगा कि qsort() स्टीव ने सुझाव दिया पराक्रम हे की बुरी से बुरी हालत जटिलता (एन * एन) है, जो दूर है, अब तक, हे (एन लॉग ऑन एन) यदि आप एक heapsort या विभिन्न साथ मिल से भी बदतर है वृक्ष की तरह संरचनाएं।

Answer 8

Optimization of Computer Programs in C

आप कॉल करने से पहले प्रश्न में तार का पहला वर्ण की जाँच करके एक छोटे से समय की बचत कर सकते हैं। जाहिर है, यदि पहले अक्षर भिन्न हैं, तो बाकी की जांच करने के लिए strcmp को कॉल करने का कोई कारण नहीं है। प्राकृतिक भाषाओं में अक्षरों के गैर-समान वितरण के कारण, भुगतान 26: 1 नहीं है लेकिन अपरकेस डेटा के लिए 15: 1 की तरह अधिक है।

#define QUICKIE_STRCMP(a, b) (*(a) != *(b) ? \ 
    (int) ((unsigned char) *(a) - \ 
     (unsigned char) *(b)) : \ 
    strcmp((a), (b))) 

तो शब्दों का प्रयोग कर रहे के शब्दकोश में अच्छी तरह से परिभाषित कर रहे हैं (अर्थात आपका कोई आपत्ति नहीं है वापसी मान प्रपत्र strcmp लेकिन 0 == बराबर), उदाहरण के लिए, आदेश पंक्ति तर्क का एक सेट है कि शुरू होता है टीसीपी-स्वीकार करते हैं, टीसीपी-अस्वीकार की तुलना में आप मैक्रो पुनर्लेखन कर सकते हैं और 1 एक लेकिन वां चार नहीं तुलना करने के लिए कुछ सूचक अंकगणित करते हैं, इस मामले में, 4 चार, उदाहरण के लिए::

#define QUICKIE_STRCMP(a, b, offset) \ 
      (*(a+offset) != *(b+offset))\ ? -1 : strcmp((a), (b))) 

एक ही उपसर्ग, पूर्व के साथ