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
1
420
正規表現改善報告する回 / 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
Make Regexp#match much faster
makenowjust
1
2.3k
ReDoS 検出の最先端 recheck の紹介 / State of the Art of ReDoS Detection
makenowjust
9
3.1k
ReDoS 検出プログラム recheck の開発 / recheck: ReDoS check program
makenowjust
0
98
Integrated Shrinking による 高階関数の自動生成 / PRO-2020-4 Generating Higher-Order Functions by Integrated Shrinking
makenowjust
0
110
ハイブリッド型ReDoS検出プログラムの実装 / PROSYM62 - A Hybrid Approach to Detect ReDoS
makenowjust
1
510
SpannerのSQL解析ライブラリ "memefish" の紹介/gcpug-memefish-introduction
makenowjust
3
1.1k
dali introduction
makenowjust
1
150
memefish the Spanner SQL parser and analyzer
makenowjust
0
2.9k
«le noir que j'ai créé»
makenowjust
0
860
Other Decks in Programming
See All in Programming
はてなにおける CSS Modules、及び CSS Modules に足りないもの / CSS Modules in Hatena, and CSS Modules missing parts
mizdra
7
950
dbtのドメイン分割による データ基盤の改善とDigdagとの連携
sakama
0
390
禅の心を手に入れよ
eltociear
1
200
Komplexe Oberflächen mit SVG und der Web Animation API
joergneumann
0
680
CDKコントリビュートの最初の壁を越えよう! -簡単issueの見つけ方-
badmintoncryer
2
130
GitHub Actionsで泣かないためにやっておきたい設定 / Recommended GHA settings to avoid crying
pinkumohikan
3
550
Build Apps for iOS, Android & Desktop in 100% Kotlin With Compose Multiplatform (mDevCamp 2024)
zsmb
0
380
初心者のためのRubyKaigi入門/RubyKaigi Introduction
a_matsuda
7
1.1k
デフォルトにして至高、RubyMineの大好きな所
ruzia
0
520
大規模Reactアプリのリアーキテクチャ~8万行のTanStack Query移行の軌跡~
kj455
4
980
Scalable Customer Journey Orchestration (CJO)
lewuathe
0
370
Polars入門
daikikatsuragawa
1
110
Featured
See All Featured
A Tale of Four Properties
chriscoyier
152
22k
Creatively Recalculating Your Daily Design Routine
revolveconf
211
11k
Put a Button on it: Removing Barriers to Going Fast.
kastner
58
3.1k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
352
28k
A designer walks into a library…
pauljervisheath
201
23k
RailsConf & Balkan Ruby 2019: The Past, Present, and Future of Rails at GitHub
eileencodes
126
32k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
11
8.3k
Fantastic passwords and where to find them - at NoRuKo
philnash
38
2.5k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
155
14k
BBQ
matthewcrist
80
8.8k
Code Review Best Practice
trishagee
56
15k
Embracing the Ebb and Flow
colly
80
4.2k
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νϟϯωϧʹͯ