2

Why does f work much faster than g?

def f(n):
    s = ''
    for i in range(n):
        s = s + 'x'
    return s

def g(n):
    s, t = '', ''
    for i in range(n // 2):
        s = t + 'x'
        t = s + 'x'
    return t

print(len(f(500000))) - 0.1s
print(len(g(500000))) - 7.684s

Return values are the same. Why f has linear complexity, but g quadratic?

Chris_Rands
  • 38,994
  • 14
  • 83
  • 119
indigo153
  • 1,021
  • 2
  • 10
  • 23
  • 7
    CPython has a special case optimization for the case of `x += y` or `x = x + y` where `x` and `y` are a `str` (`y` can be an expression that results in a `str`, e.g. `x += 'a' + 'bcd'`) and there are no other references to it; CPython mutates the `str` in place (technically against the rules, but with no other references, it's not breaking observed behaviors). – ShadowRanger Jun 22 '18 at 09:49
  • Yes ShadowRanger wrote an excellent related answer here https://stackoverflow.com/a/40996908/6260170 – Chris_Rands Jun 22 '18 at 11:22
  • Incidentally, the *time complexity* isn't changing I think, although the *computation time* is – Chris_Rands Jun 22 '18 at 11:23
  • @Chris_Rands: It really does change if the strings are overallocated for the purpose. – Davis Herring Jun 22 '18 at 21:17

0 Answers0