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 <mailto: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 > <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 > <mailto: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 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/C52F7F0C-1DCA-44B6-ACE8-2F96066D62CD%40gmail.com.
