I think that regexp/syntax.patchlist.append refers to line 42 here https://golang.org/src/regexp/syntax/compile.go
Using a singly linked list with a pointer to the tail pointer would give constant time append Ray On Thu, Jun 11, 2020 at 5:40 PM Andy Balholm <andybalh...@gmail.com> wrote: > Right. That’s why I left the double bar in my example. > > Basically all the time is spent appending to a linked list in > regexp/syntax.patchlist.append. Which makes sense, because appending to a > linked list when you only have a head pointer is O(n) in the length of the > list. So building the whole list that way is O(n^2). > > Andy > > On Jun 11, 2020, at 4:47 PM, Kurtis Rader <kra...@skepticism.us> wrote: > > On Thu, Jun 11, 2020 at 2:57 PM 'Axel Wagner' via golang-nuts < > golang-nuts@googlegroups.com> wrote: > >> The Graph is clearly not linear. Another way to see this is to print out >> the ratio of time taken and i. If the cost is linear, you'd expect that >> ratio to be constant. When I run this code >> https://play.golang.org/p/v1JVQkOXnEH on my machine I get... >> > > The poor scalability of the example provided by Andy is due to the empty > alternation. Using "D|" repeated as many times as you desire results in > linear time and a constant number of memory allocations to compile > the sequence. Changing the segment to "D||" causes two allocations for > every "||" instance. While "D||D" is legal it's also somewhat silly since > it matches anything. Inserting a repetition between the two "|" (e.g., " > D|d*|"), or a fixed length expression that is a different length (e.g., " > D|xy|") results in the same behavior. Putting a fixed length expression > between the two "|" that is the same length as the expression on the > other side results in linear time even if the expression is a char class; > e.g., "D|[xy]|". This doesn't surprise me given the research papers > linked to earlier in this thread. Whether the pathological alternation case > can be optimized to reduce the number of allocations is an open question. > > -- > Kurtis Rader > Caretaker of the exceptional canines Junior and Hank > > -- > 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/CABx2%3DD-ciPs%3DRa9GAO9SqXqFM_AFRV6TR6h3n3g-_DSpnzu%3DBg%40mail.gmail.com > <https://groups.google.com/d/msgid/golang-nuts/CABx2%3DD-ciPs%3DRa9GAO9SqXqFM_AFRV6TR6h3n3g-_DSpnzu%3DBg%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > > > -- > You received this message because you are subscribed to a topic in the > Google Groups "golang-nuts" group. > To unsubscribe from this topic, visit > https://groups.google.com/d/topic/golang-nuts/8M-qVbRKIWA/unsubscribe. > To unsubscribe from this group and all its topics, 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/C52F7F0C-1DCA-44B6-ACE8-2F96066D62CD%40gmail.com > <https://groups.google.com/d/msgid/golang-nuts/C52F7F0C-1DCA-44B6-ACE8-2F96066D62CD%40gmail.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/CANZUSA%2BVObY_21%3DEc7C4VEaKDrO2fS4eNtSrQuG0u059cc3fsw%40mail.gmail.com.
