एस/^ \ s + | \ s + $ // g क्यों है; दो अलग-अलग प्रतिस्थापन से बहुत धीमी है?

Question

पर्ल सामान्य प्रश्न प्रविष्टि How do I strip blank space from the beginning/end of a string? कहा गया है कि

s/^\s+|\s+$//g; 

का उपयोग कर दो चरणों में यह कर की तुलना में धीमी:

s/^\s+//; 
s/\s+$//; 

क्यों इस संयुक्त बयान काफ़ी अलग लोगों की तुलना में धीमी (किसी भी इनपुट स्ट्रिंग के लिए) है ?

Answer 1

पर्ल रेगेक्स रनटाइम 'फिक्स्ड' या 'एंकर' सबस्ट्रिंग्स के बजाय 'फिक्स्ड' सबस्ट्रिंग्स के बजाय काम करते समय बहुत तेज़ चलता है। एक सबस्ट्रिंग तय की जाती है जब आप इसे स्रोत स्ट्रिंग में किसी निश्चित स्थान पर लॉक कर सकते हैं। '^' और '$' दोनों एंकरिंग प्रदान करते हैं। हालांकि, जब आप alternation '|' का उपयोग करते हैं, तो कंपाइलर विकल्पों को निश्चित रूप से पहचान नहीं करता है, इसलिए यह संपूर्ण स्ट्रिंग को स्कैन करने के लिए कम अनुकूलित कोड का उपयोग करता है। और प्रक्रिया के अंत में, दो बार निश्चित तारों की तलाश करना एक बार एक फ़्लोटिंग स्ट्रिंग की तलाश में बहुत तेज़ है। संबंधित नोट पर, पर्ल के regcomp.c को पढ़ने से आप अंधे हो जाएंगे।

अद्यतन: यहां कुछ अतिरिक्त विवरण दिए गए हैं। यदि आप इसे डीबगिंग समर्थन के साथ संकलित करते हैं तो आप '-Dr' ध्वज के साथ पर्ल चला सकते हैं और यह रेगेक्स संकलन डेटा को डंप कर देगा। शब्द पहले डंप में 'लंगर'

~# debugperl -Dr -e 's/^\s+//g' 
Compiling REx `^\s+' 
size 4 Got 36 bytes for offset annotations. 
first at 2 
synthetic stclass "ANYOF[\11\12\14\15 {unicode_all}]". 
    1: BOL(2) 
    2: PLUS(4) 
    3: SPACE(0) 
    4: END(0) 
stclass "ANYOF[\11\12\14\15 {unicode_all}]" anchored(BOL) minlen 1 

---

# debugperl -Dr -e 's/^\s+|\s+$//g' 
Compiling REx `^\s+|\s+$' 
size 9 Got 76 bytes for offset annotations. 

    1: BRANCH(5) 
    2: BOL(3) 
    3: PLUS(9) 
    4:  SPACE(0) 
    5: BRANCH(9) 
    6: PLUS(8) 
    7:  SPACE(0) 
    8: EOL(9) 
    9: END(0) 
minlen 1 

नोट: यहाँ आप क्या मिलता है।

Answer 2

यदि यह वास्तव में मामला है, तो ऐसा इसलिए होगा क्योंकि रेगेक्स इंजन संयुक्त के मुकाबले व्यक्तिगत regexes के लिए बेहतर अनुकूलित करने में सक्षम है।

"उल्लेखनीय धीमी" से आपका क्या मतलब है?

Answer 3

चूंकि दोनों विधियां तार्किक रूप से समकक्ष हैं, इसलिए मूल्यांकन प्रदर्शन में उनके लिए कोई अंतर्निहित कारण नहीं है। अभ्यास में, हालांकि, कुछ इंजन अधिक जटिल regexes में अनुकूलन स्पॉट करने में सक्षम नहीं होंगे।

इस मामले में, एक पूरे के रूप में संयुक्त regex unanchored, तो यह संभावित स्ट्रिंग में किसी भी बिंदु पर मेल खा सकते हैं, जबकि ^\s+ शुरू में लंगर डाले है है, इसलिए यह मैच के लिए तुच्छ है, और \s+$ पर लंगर डाले है अंत, और प्रत्येक चरित्र के लिए पीछे की तरफ से एक चरित्र चरित्र प्रदान करता है - एक अच्छी तरह से अनुकूलित इंजन उस तथ्य को पहचान लेगा और रिवर्स में मिल जाएगा, जो इनपुट के विपरीत पर ^\s+ मैच के रूप में छोटा हो जाता है।

Answer 4

अन्य उत्तरों ने संकेत दिया है कि पूरी तरह से लंगर वाले रेगेक्स इंजन को खोज प्रक्रिया को अनुकूलित करने की अनुमति देते हैं, केवल शुरुआत या अंत या स्ट्रिंग पर ध्यान केंद्रित करते हैं। ऐसा प्रतीत होता है कि आप विभिन्न लम्बाई के तारों का उपयोग करके दो दृष्टिकोणों के गति अंतर की तुलना करके इस अनुकूलन के प्रभाव को देख सकते हैं। जैसे-जैसे स्ट्रिंग अधिक हो जाती है, "फ़्लोटिंग" रेगेक्स (वैकल्पिकता का उपयोग करके) अधिक से अधिक पीड़ित होता है।

use strict; 
use warnings; 
use Benchmark qw(cmpthese); 

my $ws = " \t\t\n"; 

for my $sz (1, 10, 100, 1000){ 
    my $str = $ws . ('Z' x $sz) . $ws; 
    cmpthese(-2, { 
     "alt_$sz" => sub { $_ = $str; s/^\s+|\s+$//g }, 
     "sep_$sz" => sub { $_ = $str; s/^\s+//; s/\s+$// }, 
    }); 
} 

      Rate alt_1 sep_1 
alt_1 870578/s -- -16% 
sep_1 1032017/s 19% -- 

      Rate alt_10 sep_10 
alt_10 384391/s  -- -62% 
sep_10 1010017/s 163%  -- 

      Rate alt_100 sep_100 
alt_100 61179/s  -- -92% 
sep_100 806840/s 1219%  -- 

      Rate alt_1000 sep_1000 
alt_1000 6612/s  --  -97% 
sep_1000 261102/s 3849%  --