Сложность алгоритма добавления к строке в цикле

#python #time_complexity

Достаточно распространённая gotcha, что

r = ""
for c in s:
  r += c


может быть сложностью O(len(s)**2) в Python, но так ли это на самом деле, и если
да (или нет), то почему?
    

Ответы

Ответ 1

Рассмотрим этот вопрос в целом для разных языков.

Случай первый. Строки изменяемые, строка представляет собой указатель на некий массив
(или иную структуру данных) символов (+ возможно обёртка с функциями). Примеры языков
- С (char *) и С++ (string). 

В этом случае код из вопроса по сути вырождается в обычное добавление элемента в
массив. И если это не низкокачественная лаба самописная реализация то сложность добавления
(аммортизированная) будет не больше чем длина того что добавляется.

Тогда очевидно сложность на 1 итерацию будет O(1) а суммарно O(len).

Плюсы данного подхода - скорость работы (добавление, возможность замены символов,
быстрое создание подстрок).
Минусы - нужно быть очень внимательным что и как меняется в строке, особенно в многопоточных
реализациях.

И 2 случай - строки неизменяемые. Т.е. объект строка создаётся 1 раз и не может прямым
или косвенным образом изменять своё состояние. Это характерно например для Java. 

В этом случае происходит каждый раз создание временного объекта, в который копируется
вся старая строка + то что нужно добавить. Т.е. грубо говоря (псевдокод)

@s - string
r[0] = ''
for i =1: i <= s.length(); i++ 
   r[i] = String.gen(r[i-1] , s[i-1]);


И мы создаём Len строк, длинной от 0 до Len включительно, несложно заметить что их
суммарная длина  будет Len*(Len+1)/2 ~ O(Len^2). 

Кстати при отсутствии нормального сборщика мусора (но обычно он есть в таких языках)
можно весьма просесть по памяти.

Плюсы и минусы можно сказать обратные, работать проще но медленнее.

Но в каждом таком языке есть механизм которые позволяют создавать подобное не теряя
в производительности. Это может быть конструктор строки из коллекции или специальные
утилитарные классы (StringBuiled и подобное). Использование их позволяет существенно
ускорить процесс и достичь в данном примере асимптотики  O(len).

Умный компилятор, если может доказать эквивалентность кода (а в такой простой ситуации
это несложно) может заменить прямую конкатенацию строк на утилитарную, обеспечив выигрыш
в скорости. Именно это и произошло в Питоне в примере http://ideone.com/wqfd8C. 

Однако полагаться на это опасно. Цитаты из комментариев.


  Попробуйте к примеру на Jython запустить. Вот подробное описание от создателя языка.
CPython (после 2.5) иногда может оптимизировать (в качестве специального случая) код
типа r +=. Так как тяжело новичкам объяснять, что всегда следует ''.join использовать
вместо s+=. Вот хороший ответ от Alex Martelli на связанный вопрос.


(Ссылка на вопрос - https://stackoverflow.com/a/1350289/4279)


  чтобы осознать хрупкость оптимизации, сравните: python -mtimeit -s 's="a"*1000000'
$'r = ""\nfor c in s:\n r += c' и python -mtimeit -s 's="a"*1000000' $'r = ""\nfor
c in s:\n r += c\n t=r'


В этом случае компилятору не хватает "сообразительности" и он реализовывает что написано
в "лоб", что значительно медленнее. Поэтому повторюсь, нужно использовать специальные
 конструкции языка и упрощать жизнь компилятору.