[docs] [issue21667] Clarify status of O(1) indexing semantics of str objects
Guido van Rossum
report at bugs.python.org
Thu Jun 5 18:32:42 CEST 2014
Guido van Rossum added the comment:
I don't want the O(1) property explicitly denounced in the reference manual. It's fine if the manual is silent on this -- maybe someone can prove that it isn't a problem based on benchmarks of an alternate implementation, but until then, I'm skeptical -- after all we have a bunch of important APIs (indexing, slicing, find()/index(), the re module) that use integer indexes, and some important algorithms/patterns are based off this behavior.
E.g. searching a string for something, returning the position where it's found, and then continuing the search from that position. Even if the basic search uses find() or regex matching, there's still a position being returned and accepted, and if it took O(N) time to find that position in the representation, the whole algorithm could degenerate from O(N) to O(N**2).
I am fine with the changes related to code points.
For the pedants amongst us, surrogates are also code points. A surrogate pair is two code points that encode a single code point. Fortunately we don't have to deal with those any more outside codecs.
Python tracker <report at bugs.python.org>
More information about the docs