Hi, I can very much recommend reading this list of blog posts by Russ Cox <https://swtch.com/~rsc/regexp/>. They explain the theory behind all of this. And AIUI, yes, compilation should also be linear. The cost, notably, is that the regexp package actually can only compile actual regular expressions which only recognize regular languages, by omitting features such as back-references. Other regexp-engines are more powerful, at the expense of no longer being able to have this linear runtime characteristic. So there is still a tradeoff (though I tend to agree with the one made by RE2 and thus the regexp-package).
On Wed, Jun 3, 2020 at 11:43 PM Ray Pereda <rayper...@gmail.com> wrote: > Typo fix, regexp#MatchString <https://golang.org/pkg/regexp/#MatchString> and > related Match functions are linear. That is an amazing guarantee and makes > regular > expressions 10x more useful than regexps in most other programming > languages. > > Question: Does the *compile* of regular expressions also guaranteed > linear runtime? I'm considering regular expressions with > 1000s of keywords; very long regexps. I looked at the source and it was > not obvious if that is the case. Intricate code. > > On Wednesday, June 3, 2020 at 10:07:12 AM UTC-7, Ray Pereda wrote: >> >> I believe that the complexity of regexp.MustCompile() >> <https://golang.org/pkg/regexp/#MustCompile> is linear based on this >> comment in the regexp package overview. >> <https://golang.org/pkg/regexp/#pkg-overview> >> >> "The regexp implementation provided by this package is guaranteed to run >> in time linear in the size of the input" >> >> >> What is the complexity of regexp.MustCompile() >> <https://golang.org/pkg/regexp/#MustCompile>? Is it linear in the length >> of the regular expression? >> >> -ray >> >> >> >> -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/golang-nuts/f51125e7-f66e-45e8-af3a-381f96071d9a%40googlegroups.com > <https://groups.google.com/d/msgid/golang-nuts/f51125e7-f66e-45e8-af3a-381f96071d9a%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAEkBMfHP3ymt%2BL63fdw%3Dob8%3Df-FfBtsC%3DGhaO1Q97N3eszvogQ%40mail.gmail.com.
