On Wed, Oct 14, 2020 at 7:45 PM Steven D'Aprano email@example.com wrote:
Perhaps this is a silly suggestion, but could we offer this as an external function in the stdlib rather than a string method?
That feels unworkable to me.
For one thing, the 'in' operator hits this same issue, doesn't it? But for another, the example initially posted where the current code did or didn't hit that quadratic breakdown was just one extra character in a long string. I cannot imagine end users knowing in advance whether their exact search will hit that unlucky circumstance that is very data dependent.
If it was a case of "in certain circumstances, this other function might be twice as fast" I can see that being useful. But here we get a big-O explosion that went from milliseconds to hours on ostensibly similar operations.
That said, I do recognize that the `re` module also has pathological cases, and the standard library documentation explicitly says "maybe you want to try the third-party `regex` implementation." That is sort of precedent for this approach.