[Python-ideas] Complicate str methods

[Franklin? Lee]

On Feb 7, 2018 17:28, "Serhiy Storchaka" <storchaka at gmail.com> wrote:

04.02.18 00:04, Franklin? Lee пише:

Let s be a str. I propose to allow these existing str methods to take
> params in new forms.
>
> s.replace(old, new):
>      Allow passing in a collection of olds.
>      Allow passing in a single argument, a mapping of olds to news.
>      Allow the olds in the mapping to be tuples of strings.
>
> s.split(sep), s.rsplit, s.partition:
>      Allow sep to be a collection of separators.
>
> s.startswith, s.endswith:
>      Allow argument to be a collection of strings.
>
> s.find, s.index, s.count, x in s:
>      Similar.
>      These methods are also in `list`, which can't distinguish between
> items, subsequences, and subsets. However, `str` is already inconsistent
> with `list` here: list.M looks for an item, while str.M looks for a
> subsequence.
>
> s.[r|l]strip:
>      Sadly, these functions already interpret their str arguments as
> collections of characters.
>

The name of complicated str methods is regular expressions. For doing these
operations efficiently you need to convert arguments in special optimized
form. This is what re.compile() does. If make a compilation on every
invocation of a str method, this will add too large overhead and kill
performance.

Even for simple string search a regular expression can be more efficient
than a str method.

$ ./python -m timeit -s 'import re; p = re.compile("spam"); s =
"spa"*100+"m"' -- 'p.search(s)'
500000 loops, best of 5: 680 nsec per loop

$ ./python -m timeit -s 's = "spa"*100+"m"' -- 's.find("spam")'
200000 loops, best of 5: 1.09 usec per loop


That's an odd result. Python regexes use backtracking, not a DFA. I gave a
timing test earlier in the thread:
https://mail.python.org/pipermail/python-ideas/2018-February/048879.html
I compared using repeated .find()s against a precompiled regex, then
against a pure Python and unoptimized tree-based algorithm.

Could it be that re uses an optimization that can also be used in str?
CPython uses a modified Boyer-Moore for str.find:
https://github.com/python/cpython/blob/master/Objects/stringlib/fastsearch.h
http://effbot.org/zone/stringlib.htm
Maybe there's a minimum length after which it's better to precompute a
table.

In any case, once you have branches in the regex, which is necessary to
emulate these features, it will start to slow down because it has to travel
down both branches in the worst case.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20180208/1b37a917/attachment.html>