धीमी रेगेक्स प्रदर्शन

Question

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

class Program 
{ 
    private static void StringMatch(string s) 
    { 
     // regex: quote, zero-or-more-(zero-or-more-non-backslash-quote, optional-backslash-anychar), quote 
     Match m = Regex.Match(s, "\"(([^\\\\\"]*)(\\\\.)?)*\""); 
     if (m.Success) 
      Trace.WriteLine(m.Value); 
     else 
      Trace.WriteLine("no match"); 
    } 

    public static void Main() 
    { 
     // this first string is unterminated (so the match fails), but it returns instantly 
     StringMatch("\"OK"); 

     // this string is terminated (the match succeeds) 
     StringMatch("\"This is a longer terminated string - it matches and returns instantly\""); 

     // this string is unterminated (so the match will fail), but it never returns 
     StringMatch("\"This is another unterminated string and takes FOREVER to match"); 
    } 
} 

मैं एक अलग रूप में regex refactor कर सकते हैं, लेकिन किसी को एक स्पष्टीकरण क्यों प्रदर्शन इतना बुरा है की पेशकश कर सकते हैं?

Answer 1

आप catastrophic backtracking:

में चला रहे हैं की एक बिट (भाग निकले उद्धरण चिह्नों के बिना और दूसरे वैकल्पिक समूह के बिना, क्योंकि अपनी टिप्पणी के रूप में, यह परीक्षण किया स्ट्रिंग्स के लिए अप्रासंगिक है) regex को आसान बनाने में करते हैं:

"(([^\\"]*))*" 

([^\\"]*) उद्धरण या बैकस्लेश को छोड़कर किसी भी स्ट्रिंग से मेल खाता है। यह फिर से एक वैकल्पिक समूह में संलग्न है जो कई बार दोहरा सकता है।

• ",, ABC
• ", ABC, <empty string>
• ", AB, C
• ":

  अब स्ट्रिंग "ABC के लिए, regex इंजन निम्नलिखित क्रमपरिवर्तन की कोशिश करने की जरूरत है AB, C, <empty string>

• ", AB, <empty string>, C
• ", AB, <empty string>, C, <empty string>
• ", <empty string>, AB, C
• ", <empty string>, AB, C, <empty string>
• ", <empty string>, AB, <empty string>, C, <empty string>
• ", <empty string>, AB, <empty string>, C
• ", A, BC
• ", A, BC, <empty string>
• ", A, <empty string> , BC
• ", <empty string>, A, BC
• आदि
• ", A, B, C
• ", A, B, C, <empty string>
• ", A, B, <empty string>, C
• आदि आदि

जिनमें से प्रत्येक तब विफल रहता है क्योंकि कोई फॉलो नहीं है एनजी "।

इसके अलावा, आप केवल संपूर्ण स्ट्रिंग से मेल खाने के लिए रेगेक्स को मजबूर करने के बजाय सबस्ट्रिंग के लिए परीक्षण कर रहे हैं। और आप आम तौर पर बैकस्लाश की संख्या पर कटौती करने के लिए रेगेक्स के लिए वर्बैटिम तारों का उपयोग करना चाहते हैं। कैसे इस बारे में:

foundMatch = Regex.IsMatch(subjectString, 
    @"\A  # Start of the string 
    ""  # Match a quote 
    (?:  # Either match... 
    \\.  # an escaped character 
    |  # or 
    [^\\""] # any character except backslash or quote 
    )*  # any number of times 
    ""  # Match a quote 
    \Z  # End of the string", 
    RegexOptions.IgnorePatternWhitespace); 

Answer 2

Match m = Regex.Match(s, @"'.*?(?<=[^\\](\\\\)*)'".Replace("'", "\"")); 

यह प्रयास करें "समझदारी से" \ की भी संख्या पर ध्यान नहीं देगा। इसका कारण यह है " एक स्ट्रिंग बंद कर देता है, \" नहीं है, \\" करता है (क्योंकि पहले बैकस्लैश दूसरा एक निकल जाता है), \\\" नहीं है ...

.*? एक आलसी परिमाणक है। आप मानक .* क्वांटिफ़ायर का भी उपयोग कर सकते हैं। मैं कहूंगा कि शायद आपको ^ और $ के साथ अपने रेगेक्स को एंकर करना चाहिए।

मैं बदलें क्योंकि बचने दोहरे उद्धरण चिह्नों मुझे दिया उपयोग कर रहा हूँ :-)

मैं एक 4k पाठ अपने कंप्यूटर पर यह तात्कालिक साथ कि जोड़ देंगे, दोनों मैच में और मेल नहीं खाते सिर दर्द।

एक विकल्प के रूप:

Match m = Regex.Match(s, @"^'(?>([^'\\]|\\.)*)'$".Replace("'", "\"")); 

स्पष्टीकरण:

(?>) disables backtracking 

^ begin of the string 

तो आप एक वैकल्पिक निर्माण (0 या अधिक बार, *) होना:

[^'\\] any non-quote and non backslash 

\\. or a backslash followed by another character (that is escaped) 

$ end of the string 

यह भी है बहुत तेज़, और इसे पढ़ने में काफी आसान है।

Answer 3

संपादित

ये रहा: "\"([^\\\\\"]|\\\\.)*\""

व्याख्या करने के लिए, के बाद सी # स्ट्रिंग बच निकला है तो आप इस regex मिलती है: "([^\\"]|\\.)*"

अर्थ:

"    #start with a quote 
(
    [^\\"]  #match a non backslash or quote 
    |   #or 
    \\.   #backslash something 
)     
*    #And repeat 
"    #end with a quote 

तक अपने घोंसले को नहीं घूमते * आपको एक्सपोन नहीं मिलता है ntial या अनंत लूप, और यह तुरंत मेरे लिए लौटता है।

Answer 4

मुझे लगता है कि @ टिम पिट्ज़कर ने बैकट्रैकिंग के बारे में सबसे अच्छा स्पष्टीकरण दिया।

विभिन्न मानक के माध्यम से चारों ओर (अपने ही शामिल है) इन तेजी से तरीके हैं:

विधि 1, unrolling

" [^"\\]* (?: \\. [^"\\]*)* " 

विधि 2, प्रत्यावर्तन

" (?: \\. | [^"\\]+)* " 

विधि 1, मात कर सकते हैं पर्याप्त मार्जिन द्वारा 2।

जानकारी

मुझे लगता है कि आपत्तिजनक बैक ट्रैकिंग समझाने के लिए अपने वास्तव में कड़ी मेहनत। यहां तक ​​कि यह पहचानना कभी-कभी कठिन होता है जब तक कि यह भी स्पष्ट नहीं होता है। फिर, समय-महत्वपूर्ण अनुप्रयोगों में कभी-कभी कुछ मानक करने के लिए फायदेमंद होता है।

इस उद्धरण विषय पर, मैं यह देखने के लिए बेंचमार्क टेम्पलेटेड पर्ल (5.10 इंजन) स्क्रिप्ट में नए दृष्टिकोण जोड़ना चाहता हूं। प्रत्येक इंजन थोड़ा अलग है। यदि आप परवाह करते हैं, तो यहां एक नमूना है।

भारी मात्रा में उद्धृत और बच निकलने वाली स्ट्रिंग का उपयोग करते हुए रेगेक्स नमूने बनाम समय
प्रत्येक 100,000 बार इटरेट किया गया।

(?x-ism:" ((?: \\?.)*?) ")
कोड लिया: 14.7031 wallclock सेकेंड (14.58 usr + 0.00 sys = 14.58 सीपीयू)

(?x-ism:" (.*? (?<!\\) (?:\\{2})*) ")
कोड लिया: 12.8435 wallclock सेकेंड (12.75 usr + 0.00 sys = 12.75 सीपीयू)

(?x-ism:" ((?: [^\\"] | \\.)*) ")
कोड लिया: 10.3123 wallclock सेकेंड (10.27 usr + 0.00 sys = 10.27 सीपीयू)

(?x-ism: " ((?: [^"\\]+ | (?:\\.)+)*) ")
कोड लिया: ८.३९०६३ wallclock सेकेंड (8.39 usr + 0.00 sys = 8.39 सीपीयू)

(?x-ism: " ((?: [^"\\]+ | \\.)*) ")
कोड लिया: 8.7498 wallclock सेकेंड (8.75 usr + 0.00 sys = 8.75 सीपीयू)

(?x-ism: " ((?: \\. | [^"\\]+)*) ")
कोड लिया: 8.5623 wallclock सेकेंड (8.44 usr + 0.00 sys = 8.44 सीपीयू)

(?x-ism: " ([^"\\]* (?: \\. [^"\\]*)*) ")
कोड लिया: ७.७९६६१ wallclock सेकेंड (7.80 usr + 0.00 sys = 7.80 सीपीयू)

(?x-ism: (?> " ((?: [^"\\] | \\.)* ")))
कोड लिया: 10.5156 wallclock सेकेंड (10.52 usr + 0.00 sys = 10.52 सीपीयू)

Answer 5

यहाँ मैं क्या उपयोग करेगी:

"[^\n"\\]*(?:\\.[^\n"\\]*)*" 

@sln unrolled- के बारे में सही है लूप दृष्टिकोण सबसे तेज़ है, लेकिन मैं लाइनफ़ीड्स को छोड़कर इसे थोड़ा और परिशोधित कर दूंगा, जिसे पुरानी शैली वाली स्ट्रिंग अक्षरों में अनुमति नहीं है।\\. हिस्सा ठीक है, लेकिन [^"\\] को [^\n"\\] पर बदला जाना आवश्यक है। इसके अलावा, अगर हम स्ट्रिंग अक्षरों को निकालने के बारे में बात कर रहे हैं, तो हम \A और \Z के साथ रेगेक्स एंकर नहीं कर सकते हैं।

मैंने रेगेक्सबड्डी का इस्तेमाल आपके रेगेक्स के प्रदर्शन की तुलना करने के लिए किया था, टिम के रेगेक्स एंकरों के बिना, और यह एक। मैं अपने नमूना तार में से प्रत्येक में उद्घाटन बोली से पहले कर्सर रखा जाता है और "डीबग यहाँ" का इस्तेमाल किया है, और इन परिणामों हैं:

original regex  : "(([^\\"\n]*)(\\.)?)*" 

"OK     : failed in 101 steps 

"This is a longer... : matched in 12 steps 

"This is another... : gave up after 1,000,000 steps 



Tim's regex   : "(?:\\.|[^\\"\n])*" 

"OK     : failed in 17 steps 

"This is a longer... : matched in 211 steps 

"This is another... : failed in 253 steps 


unrolled loop   : "[^\\"\n]*(?:\\.[^\\"\n]*)*" 

"OK     : failed in 5 steps 

"This is a longer... : matched in 5 steps 

"This is another... : failed in 5 steps 

Plugging कि एक शब्दशः स्ट्रिंग के रूप में अपने कोड में, आप मिल जाएगा:

Match m = Regex.Match(s, @"""[^\n""\\]*(?:\\.[^\n""\\]*)*"""); 

संपादित करें: वैसे, मैं तुम्हें चाहिए उपयोग इस regex यह नहीं कह रहा हूँ यह तेजी से है, क्योंकि; अन्य समाधान लगभग निश्चित रूप से पर्याप्त तेज़ हैं। लेकिन अगर आपको अधिकतम प्रदर्शन की आवश्यकता है (अभी भी रेगेक्स का उपयोग करते हुए), तो शायद यह हासिल करने का तरीका है। यह इतना तेज़ बनाता है कि रेगेक्स हमेशा आगे बढ़ता है: कोई बैकरेरेंस नहीं, कोई लुक नहीं, और सबसे महत्वपूर्ण बात, कोई बैकट्रैकिंग नहीं।