प्रसंग:एक शब्द पार्सर का अनुकूलन
मैं तुलना में मैं अनुकूलन करने के लिए कोशिश कर रहा हूँ एक कोड/पाठ संपादक है। वर्तमान में, कार्यक्रम की बाधा सभी कीवर्ड स्कैन करने की तुलना में भाषा पार्सर है (एक से अधिक है, लेकिन वे आम तौर पर समान रूप से लिखे जाते हैं)।
मेरे कंप्यूटर पर, संपादक 1,000,000 कोड की रेखाओं के आसपास फ़ाइलों पर देरी करता है। रास्पबेरी पीई जैसे निचले अंत कंप्यूटर पर, देरी बहुत जल्द हो रही है (मुझे बिल्कुल याद नहीं है, लेकिन मुझे लगता है कि कोड के बारे में 10,000 लाइनें)। और यद्यपि मैंने कभी भी कोड की 1,000,000 लाइनों से बड़े दस्तावेज़ों को कभी नहीं देखा है, मुझे यकीन है कि वे वहां हैं और मैं चाहता हूं कि मेरा प्रोग्राम उन्हें संपादित करने में सक्षम हो।
प्रश्न:
यह मैं सवाल की ओर जाता है: बड़े, गतिशील स्ट्रिंग के भीतर शब्दों की एक सूची के लिए स्कैन करने का सबसे तेज़ तरीका क्या है?
यहाँ कुछ जानकारी है कि एल्गोरिथ्म के डिजाइन को प्रभावित कर सकता है:
- कीवर्ड
- योग्यता पात्रों एक कीवर्ड का हिस्सा बनने के लिए अनुमति दी, (मैं उन्हें क्वालिफायर कहते हैं)
- बड़े स्ट्रिंग
टोंटी-समाधान:
यह (लगभग) है विधि मैं वर्तमान में तार पार्स करने के लिए उपयोग कर रहा हूँ:
// this is just an example, not an excerpt
// I haven't compiled this, I'm just writing it to
// illustrate how I'm currently parsing strings
struct tokens * scantokens (char * string, char ** tokens, int tcount){
int result = 0;
struct tokens * tks = tokens_init();
for (int i = 0; string[i]; i++){
// qualifiers for C are: a-z, A-Z, 0-9, and underscore
// if it isn't a qualifier, skip it
while (isnotqualifier (string[i])) i++;
for (int j = 0; j < tcount; j++){
// returns 0 for no match
// returns the length of the keyword if they match
result = string_compare (&string[i], tokens[j]);
if (result > 0){ // if the string matches
token_push (tks, i, i + result); // add the token
// token_push (data_struct, where_it_begins, where_it_ends)
break;
}
}
if (result > 0){
i += result;
} else {
// skip to the next non-qualifier
// then skip to the beginning of the next qualifier
/* ie, go from:
'some_id + sizeof (int)'
^
to here:
'some_id + sizeof (int)'
^
*/
}
}
if (!tks->len){
free (tks);
return 0;
} else return tks;
}
संभव समाधान:
प्रासंगिक समाधान:
मैं निम्नलिखित पर विचार कर रहा हूं:
एक बार बड़ी स्ट्रिंग स्कैन करें, और प्रत्येक बार उपयोगकर्ता इनपुट (पूरे दस्तावेज़ को फिर से स्कैन करने के बजाय) टोकन मार्करों का मूल्यांकन/समायोजन करने के लिए एक फ़ंक्शन जोड़ें। मुझे उम्मीद है कि इससे बाधा ठीक हो जाएगी क्योंकि बहुत कम पार्सिंग शामिल है। लेकिन, यह प्रोग्राम को पूरी तरह से ठीक नहीं करता है, क्योंकि प्रारंभिक स्कैन अभी भी वास्तव में लंबे समय तक ले सकता है।
अनुकूलन टोकन स्कैनिंग एल्गोरिथ्म (नीचे देखें)
मैं भी विचार किया गया है, लेकिन अस्वीकार कर दिया है, इन अनुकूलन:
- कोड केवल स्क्रीन पर है कि स्कैनिंग।हालांकि यह बाधा को ठीक करेगा, यह उपयोगकर्ता द्वारा परिभाषित टोकन (यानी परिवर्तनीय नाम, फ़ंक्शन नाम, मैक्रोज़) को खोजने की क्षमता को सीमित करेगा जो पहले स्क्रीन पर शुरू होने से पहले दिखाई देता है।
- एक मोनोलिथिक सरणी के बजाय टेक्स्ट को एक लिंक्ड सूची (प्रति पंक्ति एक नोड) में स्विच करना। यह वास्तव में बाधा की मदद नहीं करता है। हालांकि सम्मिलन/हटाना तेज हो जाएगा, अनुक्रमित पहुंच का नुकसान पार्सर को धीमा कर देता है। मुझे लगता है कि, एक मोनोलिथिक सरणी टूटी हुई सूची की तुलना में कैश होने की अधिक संभावना है।
- प्रत्येक भाषा के लिए स्कैन-टोकन फ़ंक्शन हार्ड कोडिंग। हालांकि यह प्रदर्शन के लिए सबसे अच्छा अनुकूलन हो सकता है, यह सॉफ्टवेयर विकास बिंदु में व्यावहारिक प्रतीत नहीं होता है।
वास्तु समाधान:
विधानसभा भाषा, इन तार पार्स करने के लिए रजिस्टरों में पात्रों लोड और उन्हें एक बार में 4 या 8 बाइट्स तुलना करने के लिए किया जाएगा एक तेज तरीका है। कुछ अतिरिक्त उपाय और सावधानियां हैं जिन्हें ध्यान में रखना होगा, जैसे:
- क्या आर्किटेक्चर असीमित स्मृति पहुंच का समर्थन करता है?
- सभी श्रृंखलाएं पढ़ने उल्लंघन
- दूसरों को रोकने के लिए आकार
s, जहांs % word-size == 0का हो सकता है, के लिए होता है?
लेकिन ये समस्याएं प्रतीत होती हैं जैसे उन्हें आसानी से ठीक किया जा सकता है। एकमात्र समस्या (असेंबली भाषा में लिखने वाले सामान्य लोगों के अलावा) यह है कि यह एक एल्गोरिदमिक समाधान नहीं है क्योंकि यह एक हार्डवेयर समाधान है।
एल्गोरिथम समाधान:
अब तक, मैं इस कार्यक्रम होने पर विचार किया है एक द्विआधारी खोज एल्गोरिथ्म एक छोटे से अधिक संभव बनाने के लिए कीवर्ड की सूची को पुनर्व्यवस्थित।
एक तरीका मैंने उनको पुनर्व्यवस्थित करने के बारे में सोचा है, यह कीवर्ड की सूची के आयामों को स्विच करके है।
// some keywords for the C language
auto // keywords[0]
break // keywords[1]
case char const continue // keywords[2], keywords[3], keywords[4]
default do double
else enum extern
float for
goto
if int
long
register return
short signed sizeof static struct switch
typedef
union unsigned
void volatile
while
/* keywords[i] refers to the i-th keyword in the list
*
*/
दो आयामी सरणी के आयाम स्विचिंग यह इस तरह दिखना होगा:: यहाँ C में इस बात का एक उदाहरण है
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
-----------------------------------------------------------------
1 | a b c c c c d d d e e e f f g i i l r r s s s s s s t u u v v w
2 | u r a h o o e o o l n x l o o f n o e e h i i t t w y n n o o h
3 | t e s a n n f u s u t o r t t n g t o g z a r i p i s i l i
4 | o a e r s t a b e m e a o g i u r n e t u t e o i d a l
5 | k i u l r t s r t e o i c c d n g t e
6 | n l e n t n d f c t h e n i
7 | u t e f e l
8 | e r d e
// note that, now, keywords[0] refers to the string "abccccdddeeefffiilrr"
यह इसे एक द्विआधारी खोज एल्गोरिथ्म का उपयोग करने के कुशल बनाता है (या यहां तक कि एक सादा ब्रूट फोर्स एल्गोरिदम)। लेकिन यह केवल प्रत्येक कीवर्ड में पहले वर्णों के लिए शब्द है, इसके बाद कुछ भी 'क्रमबद्ध' नहीं माना जा सकता है। यह प्रोग्रामिंग भाषा जैसे शब्दों के छोटे सेटों में मदद कर सकता है, लेकिन यह शब्दों के बड़े सेट (जैसे पूरी अंग्रेजी भाषा में) के लिए पर्याप्त नहीं होगा।
क्या इस एल्गोरिदम को बेहतर बनाने के लिए किया जा सकता है?
क्या प्रदर्शन बढ़ाने के लिए कोई अन्य दृष्टिकोण लिया जा सकता है?
नोट्स:
This question अतः से मेरी मदद नहीं करता है। बॉयर-मूर-हॉर्सपूल एल्गोरिदम (जैसा कि मैं इसे समझता हूं) एक स्ट्रिंग के भीतर उप-स्ट्रिंग खोजने के लिए एक एल्गोरिदम है।चूंकि मैं एकाधिक तारों के लिए पार्सिंग कर रहा हूं, मुझे लगता है कि अनुकूलन के लिए और अधिक जगह है।
यदि आप इसे तेजी से करना चाहते हैं तो आप एक स्ट्रिंग तुलना और स्ट्रिंग की एक सूची के साथ लूप नहीं करते हैं, लेकिन किसी कीवर्ड को मिलने पर ट्रिगर होने वाले सभी स्ट्रिंग्स के प्रत्येक वर्ण के आधार पर एक सीमित राज्य मशीन बनाएं। लेक्स उपयोगिता यह करता है। – Jiminion