Как итеративное применение оператора `+=` к строковой переменной позволяет избежать квадратичной сложности? ⇐ Python

[Anonymous]

Я немного запутался. Я был уверен, что из-за неизменности операции str, такой как s += "abc", необходимо скопировать все содержимое s в другое место в памяти, поэтому эффективное добавление символа в очень длинную строку будет потреблять много времени.
Я написал фрагмент, чтобы доказать свою теорию:

Код: Выделить всё

import timeit

def foo(i):
res = ""
for _ in range(i):
res += "a"
return res

def foo2(i):
res = []
for _ in range(i):
res.append("a")
return "".join(res)

iterations = 100000
print(timeit.timeit('foo(iterations)', globals=globals(), number=100))
print(timeit.timeit('foo2(iterations)', globals=globals(), number=100))

Как это выглядит

• Код: Выделить всё

  foo

  время выполнения растет линейно в зависимости от итераций

• Код: Выделить всё

  foo2

  едва ли в два раза быстрее, чем foo

Я пытался проверить байт-код в поисках скрытых оптимизаций. Я попытался изменить константную строку на случайную строку подходящей длины, чтобы также запретить интернирование, но не смог найти никакого объяснения этому поведению.
Ошибся ли я тогда? Зависит ли += от длины строки или нет? Если да, то как я могу это доказать?

Подробнее здесь: https://stackoverflow.com/questions/776 ... e-manage-t