Конкатенация строк в цикле: почему профайлер показывает квадратичный рост
Два способа собрать строку из n кусков:
# A
def build_a(parts):
s = ""
for p in parts:
s += p
return s
# B
def build_b(parts):
return "".join(parts)
На списке из 300 000 коротких строк вариант A иногда работает почти линейно, а иногда — катастрофически медленно (например, если в цикле результат ещё куда-то сохраняется: acc.append(s)). Какое объяснение верно?
- Разницы по сложности нет: `join` — тот же цикл конкатенации, просто написанный на C, поэтому отличается только константа, а порядок роста одинаков
- Строки неизменяемы: `s += p` копирует весь накопленный результат, поэтому A в общем случае квадратичен, а B копирует каждый кусок ровно один раз; линейность A держится на необязательной оптимизации CPython
- A всегда быстрее B на коротких кусках: `join` сначала обходит весь список ради подсчёта суммарной длины, и этот лишний проход дороже самой конкатенации
- A медленнее из-за сборщика мусора: промежуточные строки копятся до конца цикла и освобождаются разом, из-за чего пик памяти растёт и запускается сборка