Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
正規表現改善報告する回 / Regexp memoization progress report
Search
TSUYUSATO Kitsune
August 19, 2023
Programming
2
640
正規表現改善報告する回 / Regexp memoization progress report
RubyKaigi 2023 follow up(
https://rhc.connpass.com/event/288535/
) での発表資料です。
TSUYUSATO Kitsune
August 19, 2023
Tweet
Share
More Decks by TSUYUSATO Kitsune
See All by TSUYUSATO Kitsune
最近の研究とか、RubyへのContributionとか / Recent My Study and Ruby Contributions
makenowjust
2
220
Make Parsers Compatible Using Automata Learning
makenowjust
3
11k
YAPC::Japan::Online 2022で発表して WEB+DB PRESSに記事を寄稿した話
makenowjust
0
40
Regular Expressions, REXML, Automata Learning
makenowjust
0
390
オートマトン学習しろ / Do automata learning
makenowjust
3
400
#kaigieffect LT 2024 - rexml-css_selector: A REXML extension for supporting CSS selector
makenowjust
1
410
RubyKaigi 2024 - Make Your Own Regex Engine!
makenowjust
1
1.9k
Make Regexp#match much faster
makenowjust
1
2.8k
ReDoS 検出の最先端 recheck の紹介 / State of the Art of ReDoS Detection
makenowjust
10
3.7k
Other Decks in Programming
See All in Programming
株式会社 Sun terras カンパニーデック
sunterras
0
210
Le côté obscur des IA génératives
pascallemerrer
0
120
エンジニアとして高みを目指す、 利益を生み出す設計の考え方 / design-for-profit
minodriven
23
12k
Breaking Up with Big ViewModels — Without Breaking Your Architecture (droidcon Berlin 2025)
steliosf
PRO
1
300
dynamic!
moro
9
6.3k
CSC509 Lecture 03
javiergs
PRO
0
330
メモリ不足との戦い〜大量データを扱うアプリでの実践例〜
kwzr
1
820
階層構造を表現するデータ構造とリファクタリング 〜1年で10倍成長したプロダクトの変化と課題〜
yuhisatoxxx
3
900
実践AIチャットボットUI実装入門
syumai
7
2.4k
Advance Your Career with Open Source
ivargrimstad
0
310
大規模アプリのDIフレームワーク刷新戦略 ~過去最大規模の並行開発を止めずにアプリ全体に導入するまで~
mot_techtalk
0
370
Serena MCPのすすめ
wadakatu
4
880
Featured
See All Featured
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
358
30k
The Invisible Side of Design
smashingmag
301
51k
jQuery: Nuts, Bolts and Bling
dougneiner
64
7.9k
The Psychology of Web Performance [Beyond Tellerrand 2023]
tammyeverts
49
3.1k
Product Roadmaps are Hard
iamctodd
PRO
54
11k
Learning to Love Humans: Emotional Interface Design
aarron
274
40k
Fireside Chat
paigeccino
40
3.7k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
132
19k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
140
34k
It's Worth the Effort
3n
187
28k
Code Review Best Practice
trishagee
72
19k
Put a Button on it: Removing Barriers to Going Fast.
kastner
60
4k
Transcript
౻࿘େ !NBLF@OPX@KVTU !3VCZ,BJHJGPMMPXVQ ਖ਼نදݱվળใࠂ͢Δճ
લճͷ͋Β͢͡ IUUQTSVCZLBJHJPSHQSFTFOUBUJPOTNBLFOPXKVTUIUNMEBZ
લճͷ͋Β͢͡ ਖ਼نදݱϚονϯάΛΊͬͪΌͨ͘͠
લճͷ͋Β͢͡ ͔͠͠ɺਖ਼نදݱ͕͘ͳΔͨΊʹ੍͍͔͕ͭ͘
લճͷ͋Β͢͡ ੍ϑϦʔͳੈքΛΊͯ͟͠ ό Ϧ Ξ
੍#FGPSF w ͜ΕΒͷػೳΛ͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)ʮΞτϛοΫάϧʔϓʯ(?>foo) ʮ݅ذʯ(?(<x>)yes|no)ʮඇแؚԋࢉࢠʯ(?~foo) ʮޙํࢀরʯ(foo)\1
ʮ෦ࣜͷݺͼग़͠ʯ(?<x>foo)\g<x> w ͦͷଞɺಾͷ੍ͨͪ ճࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍(fo{1,23}){42} ۭจࣈྻʹϚον͢Δ͔͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍
w ͜ΕΒͷػೳΛ͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)ʮΞτϛοΫάϧʔϓʯ(?>foo) ʮ݅ذʯ(?(<x>)yes|no)ʮඇแؚԋࢉࢠʯ(?~foo) ʮޙํࢀরʯ(foo)\1 ʮ෦ࣜͷݺͼग़͠ʯ(?<x>foo)\g<x>
w ͦͷଞɺಾͷ੍ͨͪ ճࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍(fo{1,23}){42} ۭจࣈྻʹϚον͢Δ͔͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍ ੍"GUFS
w ͜ΕΒͷػೳΛ͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)ʮΞτϛοΫάϧʔϓʯ(?>foo) ʮ݅ذʯ(?(<x>)yes|no)ʮඇแؚԋࢉࢠʯ(?~foo) ʮޙํࢀরʯ(foo)\1 ʮ෦ࣜͷݺͼग़͠ʯ(?<x>foo)\g<x>
w ͦͷଞɺಾͷ੍ͨͪ ճࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍(fo{1,23}){42} ۭจࣈྻʹϚον͢Δ͔͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍ ੍"GUFS ඍົʁ
w ͜ΕΒͷػೳΛ͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)ʮΞτϛοΫάϧʔϓʯ(?>foo) ʮ݅ذʯ(?(<x>)yes|no)ʮඇแؚԋࢉࢠʯ(?~foo) ʮޙํࢀরʯ(foo)\1 ʮ෦ࣜͷݺͼग़͠ʯ(?<x>foo)\g<x>
w ͦͷଞɺಾͷ੍ͨͪ ճࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍(fo{1,23}){42} ۭจࣈྻʹϚον͢Δ͔͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍ ੍"GUFS ཧతʹແཧ ͋·ΓΘΕͯͳ͍
w ͜ΕΒͷػೳΛ͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)ʮΞτϛοΫάϧʔϓʯ(?>foo) ʮ݅ذʯ(?(<x>)yes|no)ʮඇแؚԋࢉࢠʯ(?~foo) ʮޙํࢀরʯ(foo)\1 ʮ෦ࣜͷݺͼग़͠ʯ(?<x>foo)\g<x>
w ͦͷଞɺಾͷ੍ͨͪ ճࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍(fo{1,23}){42} ۭจࣈྻʹϚον͢Δ͔͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍ ੍"GUFS ཧతʹແཧ ͋·ΓΘΕͯͳ͍ ͦΜͳʹ ѱ͘ͳ͍ʁ
͜Ε·ͰͷϝϞԽ w ී௨ͷਖ਼نදݱͷ߹ɺ ʮ͋Δঢ়ଶʹ͋ΔҐஔ͔ΒͷϚονͰࣦഊͨ͠ʯͱ͍͏ใΛه͢Ε0, w ϝϞԽςʔϒϧͷܕ memo: (State,
Int) -> (NoMemo | Failure) w ઌಡΈɾޙಡΈ͕͋Δ߹ɺΞτϛοΫάϧʔϓ͕͋Δ߹ʁ
ઌಡΈɾޙಡΈͷϝϞԽ w ઌಡΈɾޙಡΈ෦Ϛονϯάࣦഊ͍ͯ͠ͳͯ͘ɺ ʮ͋Δঢ়ଶɾ͋ΔҐஔʯʹ͏Ұ౸ୡ͢ΔՄೳੑ͕͋Δ ྫ/a*?(?=a*)z/ w ʮઌಡΈɾޙಡΈ෦ͷϚονϯάʹޭͨ͠ʯͱ͍͏ใΛ
ϝϞԽςʔϒϧʹه͢Δඞཁ͕͋Δ w ϝϞԽςʔϒϧͷܕ memo: (State, Int) -> (NoMemo | Success | Failure)
ΞτϛοΫά ϧʔϓͷϝϞԽ w ΞτϛοΫά ϧʔϓͷ߹ɺ ΞτϛοΫά ϧʔϓͷதͰͷࣦഊͱɺ֎ଆͰͷࣦഊΛ۠ผ͠ͳ͚Ε͍͚ͳ͍ ֎ଆͰࣦഊͨ͠߹ɺΞτϛοΫά ϧʔϓͷதͷόοΫτϥοΫ
লུ͠ͳ͚Ε͍͚ͳ͍ w ϝϞԽςʔϒϧͷܕ memo: (State, Int) -> (NoMemo | Success | AtomicFailure | Failure)
࣮ͷमਖ਼ w ࣮ࡍͷϝϞԽςʔϒϧCJUྻͳͷͰɺ ઌಡΈɾޙಡΈɾΞτϛοΫά ϧʔϓͷঢ়ଶʹରͯ͠ CJUͬͯϝϞԽ͢ΔΑ͏ʹͨ͠ w ͜Ε·Ͱʮ͋Δঢ়ଶʹ͋ΔҐஔͰ౸ୡͨ͠ʯͱ͍͏ใΛه͍͕ͯͨ͠ɺ
ʮ͋Δঢ়ଶʹ͋ΔҐஔ͔ΒͷϚονʹࣦഊͨ͠ʯͱ͍͏ใʹ͢ΔͨΊɺ όοΫτϥοΫதʹϝϞԽςʔϒϧΛߋ৽͢ΔΑ͏ʹͨ͠ IUUQTHJUIVCDPNSVCZSVCZQVMM
ݱࡏͷ੍ w ͜ΕΒͷػೳΛ͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ ʮ݅ذʯ(?(<x>)yes|no)ʮඇแؚԋࢉࢠʯ(?~foo) ʮޙํࢀরʯ(foo)\1 ʮ෦ࣜͷݺͼग़͠ʯ(?<x>foo)\g<x> w ͦͷଞɺಾͷ੍ͨͪ
ճࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍(fo{1,23}){42} ઌಡΈɾޙಡΈͱΞτϛοΫά ϧʔϓ͕ωετͰ͖ͳ͍ ઌಡΈɾޙಡΈɾΞτϛοΫά ϧʔϓͷதͰΩϟϓνϟ͑ͳ͍
ΏΔ΅ w ੍ʹ͔͔Βͳ͍͔Ͳ͏͔ΛRegexp.linear_time?ͰνΣοΫͰ͖·͢ w ͜ΕΛͬͯɺϓϩάϥϜதͷਖ਼نදݱ੍͕ʹ͔͔Βͳ͍͔νΣοΫ͢Δ 3VCPDPQϓϥάΠϯΛ࡞ͬͯɺϝϯςφϯεͯ͘͠ΕΔਓΛืू͍ͯ͠·͢ SVCZKQ4MBDLͷSFHFYQνϟϯωϧʹͯ