ประสิทธิภาพต่ำของนิพจน์ทั่วไป?

โพสต์โดย Eyal Schneider เมื่อวันที่ 21 พฤษภาคม 2552 แพ็คเกจ java.util.regex ถูกเพิ่มใน Java ในเวอร์ชัน 1.4 มันเป็นเครื่องมือที่ทรงพลังมากและเราต้องเป็นผู้เชี่ยวชาญจึงจะใช้มันได้อย่างถูกต้อง แม้ว่านิพจน์ทั่วไปจะเป็นจริง แต่ก็อาจทำงานได้ช้ามากหากไม่ได้เขียนอย่างชาญฉลาด อ่านต่อหากคุณต้องการเข้าใจสาเหตุของปัญหา หรือเลื่อนไปที่ท้ายหน้าซึ่งคุณจะพบเคล็ดลับที่เป็นประโยชน์ 10 ข้อในการปรับปรุงประสิทธิภาพของนิพจน์ทั่วไปใน Java

มันช้าขนาดนั้นเลยเหรอ?

สมมติว่าเราต้องการเลือกเฉพาะบรรทัดที่มีลำดับอักขระ "a" และ "b" วิธีแก้ไขที่ถูกต้องอาจเป็น: (a*b*)* อย่างไรก็ตาม หากคุณเรียกใช้นิพจน์ด้วยสตริง เช่น “aaaaaaaaaaaaaaaaaaaaaaaaaaaax” จะใช้เวลาหลายนาทีก่อนที่จะเสร็จสิ้นและรายงานว่าไม่มีรายการที่ตรงกัน! แน่นอนว่า regex ที่ดีที่สุดในกรณีนี้คือ: (a|b)* ใช้เวลาน้อยกว่าหนึ่งมิลลิวินาทีในเครื่องของฉันที่มีสตริงเดียวกัน เห็นได้ชัดว่ามีปัญหาด้านประสิทธิภาพที่นี่

ทำไมสิ่งนี้ถึงเกิดขึ้น?

เช่นเดียวกับกลไก regexp ส่วนใหญ่ Java ใช้วิธีการ NFA (Non-Determistic Finite Automata) กลไกจะสแกนส่วนประกอบ regex ทีละรายการและเลื่อนผ่านสตริงอินพุตตามลำดับ และเขาสามารถกลับไปสู่จุดเริ่มต้นเพื่อค้นหาทางเลือกที่เหมาะสมได้หากเขาไปถึง "ทางตัน" ผลลัพธ์ทางเลือกจะได้มาจากการใช้โครงสร้างปกติ เช่น ปริมาณ ( *, +, ? ) และการสลับ (เช่น a|b|c|d ) เทคนิคการวิจัยนี้เรียกว่าการย้อนรอย ในตัวอย่างที่แย่มากข้างต้น เครื่องยนต์จะพิจารณาการสลายตัวของสัญลักษณ์ "a" ทั้งหมดในซีรีส์ทั้งหมดเป็นซีรีส์ย่อยๆ จนกระทั่งพบว่าไม่มีค่าที่ตรงกัน ตัวอย่างนี้แสดงให้เห็นว่าอัลกอริธึมการย้อนรอยสามารถส่งผลให้เกิดการประมาณเวลาแบบเอ็กซ์โปเนนเชียลได้อย่างไร (ขึ้นอยู่กับความยาวของสตริงอินพุต) นอกจากนี้ยังแสดงให้เห็นถึงคุณสมบัติที่สำคัญของ NFA: จะมีกรณีที่เลวร้ายที่สุดที่เกือบจะตรงกับรูปแบบเสมอ หากพบรายการที่ตรงกัน การค้นหาจะหยุดลง วิธีการหลักอีกวิธีหนึ่งสำหรับการใช้งานใน regex คือ DFA (Determistic Finite Automaton) ในแนวทางนี้ นิพจน์ทั่วไปจะสร้างหุ่นยนต์ที่ใช้ในการสำรวจอักขระสตริงอินพุตทีละอักขระโดยไม่ต้องย้อนรอย ซึ่งให้เวลาเชิงเส้นแก่อินพุตทั้งหมด โดยไม่คำนึงถึงความซับซ้อนของนิพจน์ทั่วไป แทนที่จะสแกนสตริงตามลำดับเพื่อหารายการที่ตรงกัน (เช่นใน NFA) DFA จะจำลองการสแกนแบบขนาน เหตุใด Java (และ. NET, Perl, Python, Ruby, PHP และอื่น ๆ ) จึงใช้ NKA ไม่ใช่ DKA ซึ่งมีพฤติกรรมที่ดีกว่ามาก เหตุผลก็คือ NKA มีข้อได้เปรียบที่สำคัญหลายประการ:

คอมไพล์เร็วขึ้นและใช้หน่วยความจำน้อยกว่ามาก
อนุญาตคุณสมบัติที่มีประโยชน์บางอย่าง (ดู รายละเอียด การสอนของ Sun ):

การจับภาพกลุ่มและลิงก์ย้อนกลับ
การตรวจสอบตำแหน่ง
Extended Quantifiers (โลภและขี้เกียจ)

สิ่งสำคัญคือต้องทราบว่าคำศัพท์ยอดนิยม NKA และ DKA นั้นไม่ชัดเจนเมื่อใช้ในบริบทของนิพจน์ทั่วไป ตามทฤษฎีแล้ว ทั้งสองโมเดลนี้มีพลังการประมวลผลเท่ากัน ซึ่งหมายความว่าคุณไม่สามารถเขียนนิพจน์ทั่วไปในโมเดลออโตมาตะหนึ่งซึ่งเป็นไปไม่ได้ที่จะแสดงในอีกโมเดลหนึ่ง ในทางปฏิบัติ มีความจำเป็นต้องมีความสามารถเพิ่มเติมเพื่อให้การใช้งานทั้งสองประเภทแตกต่างกันในความหมาย เอ็นจิ้น NKA ให้ความยืดหยุ่นมากกว่า ทำให้เหนือกว่า DKA ในด้านพลังการประมวลผล เนื่องจากความเร็วของ DFA และคุณลักษณะเฉพาะของ NFA จึงมีวิธี "สำเร็จรูป" อีก 2 วิธีในการใช้นิพจน์ทั่วไป การใช้งานบางอย่างใช้ทั้งสองประเภท (เช่น GNU egrep ซึ่งเลือกกลไกเฉพาะขณะรันไทม์) และบางประเภทก็สามารถจัดการการใช้งานเวอร์ชันไฮบริดอย่างแท้จริง (เช่น Tcl regexps) พร้อมคุณประโยชน์ทั้งหมด

คำแนะนำ

ต่อไปนี้เป็นเคล็ดลับบางประการเกี่ยวกับวิธีหลีกเลี่ยงปัญหาประสิทธิภาพ regex ใน Java หลายแห่งมีเป้าหมายเพื่อลดผลตอบแทน

1) การรวบรวมล่วงหน้า

ซ้ำซากแต่ก็คุ้มค่าที่จะกล่าวถึง หากคุณใช้ regexp มากกว่าหนึ่งครั้ง อย่าลืมคอมไพล์ไว้ล่วงหน้า:

// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);

2) Lazy Quantifiers กับGreedy Quantifiers

ตามค่าเริ่มต้น ปริมาณ ( * + ? ) ถือเป็นความละโมบ ซึ่งหมายความว่าพวกมันจะเริ่มจับคู่กับลำดับที่ยาวที่สุดเท่าที่จะเป็นไปได้ จากนั้นจะค่อยๆ ทำงานกลับหากจำเป็น หากคุณรู้ล่วงหน้าว่าการแข่งขันมักจะสั้น คุณควรใช้ตัวระบุปริมาณแบบขี้เกียจ พวกเขาเริ่มต้นด้วยการแข่งขันที่เล็กที่สุดและเดินหน้าต่อไปหากจำเป็น สมมติว่าเราต้องการค้นหาเฉพาะบรรทัดที่ตรงกับลำดับ "สวัสดี" .*hello.*ปกติจะทำทุกอย่างถูกต้อง แต่หากเรารู้ว่า "hello" มักจะปรากฏใกล้กับจุดเริ่มต้นของข้อความ .*?hello.*จะทำงานเร็วขึ้นโดยเฉลี่ย

3) ใช้ ตัวระบุปริมาณ ที่โลภมากหากเป็นไปได้

แตกต่างจากการหาปริมาณแบบขี้เกียจซึ่งส่งผลต่อประสิทธิภาพแต่ไม่ส่งผลต่อพฤติกรรมปกติ แต่ปริมาณที่โลภมากสามารถเปลี่ยนความหมายของนิพจน์ทั่วไปได้ เมื่อ ใช้ *+แทน *นัดแรกจะโลภมาก (นั่นคือ ใหญ่ที่สุดที่เป็นไปได้ราวกับว่าเป็นแค่ *) แต่จะไม่มีทางถอยกลับหากล้มเหลว แม้ว่าจะทำให้การค้นหาทั้งหมดล้มเหลวก็ตาม สิ่งนี้จะมีประโยชน์เมื่อใด สมมติว่าเราจำเป็นต้องค้นหาข้อความในเครื่องหมายคำพูด \"[^\"]*\"แบบปกติจะใช้ได้ผลดี อย่างไรก็ตาม มันจะทำการเยื้องโดยไม่จำเป็นในกรณีเชิงลบ (เช่น “bla bla bla) การใช้ \"[^\"]*+\"จะกำจัด การย้อนกลับโดยไม่เปลี่ยนความหมายของการแสดงออก การจัดกลุ่มอย่างอิสระให้ผลลัพธ์เดียวกันและให้การควบคุมที่มากยิ่งขึ้น (ดู บทช่วยสอนของ Sun )

4) หลีกเลี่ยงการจับกลุ่ม

นิพจน์ใดๆ ในวงเล็บจะถือเป็นกลุ่มตามค่าเริ่มต้น สิ่งนี้มีผลกระทบเล็กน้อยต่อประสิทธิภาพ ทำให้กลุ่มของคุณ "uncapturable" ทุกครั้งที่เป็นไปได้โดยเริ่มต้นด้วย (?:แทน ( .

5) ใช้การสลับอย่างชาญฉลาด

เมื่อใช้การแทรกสลับ (เช่น Paul|Jane|Chris ) ลำดับที่เครื่องยนต์พยายามจับคู่ตัวเลือกจะเหมือนกับลำดับที่ปรากฏ คุณสามารถใช้ประโยชน์จากคุณสมบัตินี้และวางตัวเลือกที่พบบ่อยที่สุดให้ใกล้กับจุดเริ่มต้นมากขึ้น สิ่งนี้จะปรับปรุงเวลาตอบสนองเชิงบวกโดยเฉลี่ย

6) หลีกเลี่ยงความคลุมเครือ

เขียน regexps ในลักษณะที่จะลดจำนวนการจับคู่ที่แตกต่างกันในสตริงอินพุตให้เหลือน้อยที่สุด ตัวอย่างเช่น: นิพจน์ทั่วไป (a*b*)*ที่ให้ไว้ตอนต้นของบทความทำให้สตริง "aabb" สามารถตีความได้หลายวิธีเกินไป ในทางกลับกัน (a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… Regexp (a|b)* จะตีความเฉพาะที่ไม่ซ้ำกันเท่านั้น การรวมกันในเชิงบวก นี่เป็นสิ่งสำคัญมากในการลดผลตอบแทนในกรณี ที่ใกล้ เคียงกัน

7) ดูตัวอย่าง

การแสดงตัวอย่างช่วยให้คุณสามารถเพิ่มข้อจำกัดเกี่ยวกับลำดับทางด้านซ้าย/ขวาของตำแหน่งปัจจุบันได้ โดยเฉพาะอย่างยิ่ง หากใช้ lookahead เชิงลบ คุณสามารถค้นหาบรรทัดที่ไม่มีลำดับบางอย่างได้ (เราจะทำอย่างไรหากไม่มีสิ่งนี้!) สิ่งนี้จะช่วยเพิ่มผลผลิตได้อย่างไร? สมมติว่าเราต้องการนำ URL จากแท็กลิงก์ พิจารณา regexp ต่อไปนี้: a .* href=(\S*).*/ สำหรับแท็กทั่วไป นิพจน์นี้จะจับคู่ที่อยู่หากข้อความมีแอตทริบิวต์ "href" เท่านั้น (\S ใช้สำหรับอักขระทั้งหมดยกเว้นตัวคั่น) แต่สำหรับแท็กที่ผิดปกติบางแท็ก การย้อนกลับจะเกิดขึ้น ตัวอย่างเช่น: “a href= href=href=…. href=บางสิ่งบางอย่าง” regexp ต่อไปนี้จะป้องกันไม่ให้สิ่งนี้เกิดขึ้นเมื่อแทนที่ “.*” ในนิพจน์ด้วยสิ่งที่ไม่ตรงกับ “href”: a ((?!href).)* href=(\S*)((?!href).)*/

8) ระบุความยาว

Java มีเครื่องมือเพิ่มประสิทธิภาพ regexp ที่ตรวจสอบความยาวของสตริงอินพุตกับความยาวต่ำสุดและสูงสุดที่ได้รับจากนิพจน์ทั่วไป ซึ่งจะทำให้คุณสามารถหยุดการค้นหาได้ทันทีในบางกรณี เพื่อช่วยกลไกนี้ ควรระบุจำนวนการซ้ำทุกครั้งที่เป็นไปได้ (เช่น [01]{6}จะจับคู่สตริงไบนารี่ทั้งหมดที่มีความยาวหกอักขระ)

9) เลือกเส้นที่เหมือนกัน

บางครั้งสตริงที่เหมือนกันจะถูกซ่อนอยู่ภายในกลุ่มหรือทางเลือกอื่น: (hello|hell|heel) นิพจน์นี้สามารถทำให้ง่ายขึ้นเป็น: he(llo|ll|el) โดยการทำเช่นนี้ เราจะให้ข้อมูลเพิ่มเติมแก่เครื่องมือเพิ่มประสิทธิภาพ regexp

10) ทดสอบ regexp ของคุณ

อาจเป็นการดีที่จะทดสอบนิพจน์ทั่วไปก่อนเมื่อจะใช้ในแอปพลิเคชันที่เน้นประสิทธิภาพการทำงาน เขียนเกณฑ์มาตรฐานขนาดเล็กเพื่อทดสอบการแสดงออกของคุณกับข้อมูลอินพุตต่างๆ อย่าลืมทดสอบข้อมูลที่มีความยาวต่างกัน และข้อมูลที่ใกล้เคียงกับตัวอย่างของคุณมากที่สุด

ลิงค์:

http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/RegularExpressions/RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -ของ-การแสดงออก-การประมวลผล/