3 ms·
Notable pitfalls: - s[i:j] is O(j - i) because it creates a copy instead of a view - max(range(n)) is O(n) - substring search is O(n), which is good, but rfi
by gpugreg 1mo ago
Notable pitfalls:
- s[i:j] is O(j - i) because it creates a copy instead of a view
- max(range(n)) is O(n)
- substring search is O(n), which is good, but rfind is O(n m)
- iterative string concatenation (for c in ...: s += c) can be O(n^2) due to string immutability according to footnote 10, although it is O(n) in most cases due to an implementation detail of CPython: https://stackoverflow.com/a/34008199 https://stackoverflow.com/a/34008199
- chronial 1mo agoNote the footnote for rfind: > This is the worst case. Reverse searches are O(n) on typical input.
- gpugreg 1mo agoI could have used more precise terminology. rfind is average case O(n + m), worst case O(n * m). Imho the worst case performance is more important than the average case performance, since it tells us whether there is any risk for attacks like Hash DoS, which is the reason why Python's dict hashing had to be changed. https://peps.python.org/pep-0456/ https://peps.python.org/pep-0456/
- speedstyle 1mo agorealloc is frequently O(n), ie CPython can avoid copying and immediately collecting the object but still copy the bytes. It's the same as calling reserve in a loop