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.
