Встроенная оптимизация добавления символов в строку.
Люблю делать мини-эксперименты на Питоне. Попробую оформлять их постами, посмотрю, как пойдёт.
Суть проблемы.
Недавно опять всплыл в обсуждении тот неочевидный факт, что современный Питон оптимизирует добавление символов в строку и не всегда создаёт новые строки при этом. Хотя на собеседованиях мы и говорим, что строки в Питоне иммутабельны, и если мы хотим поменять строку, то Питон нам создаёт новую строку, а старую строку мы изменить не можем... Но при этом существует оптимизация, противоречащая этому очевидному знанию.
В общем, давайте проверим, сохраняется ли строка на том же самом месте памяти. Это мы проверим по id объекта. Сохранился id - это тот же объект (хотя и, возможно, изменённый) в том же месте памяти. Поменялся id - это уже другой объект в другом месте, Питон потратил ресурсы на то, чтобы скопировать исходный объект в новое место.
def test_str():
string = ''
old_id = id(string)
print(0, 0, old_id)
old_i = 0
for i in range(1, 20000):
string += '-'
new_id = id(string)
if new_id != old_id:
print(i, i - old_i, new_id)
old_i = i
old_id = new_id
test_str()Запустим (часть строк я сократил для наглядности):
|"№|Шаг|Id|
|:---|:---|:---|
|0|0|2160689512496|
|1|1|2160690869616|
|2|1|2160740037552|
|16|14|2160761306960|
|32|16|2160761158704|
|48|16|2160738952768|
|64|16|2160760928688|
|...|...|...|
|448|16|2160739774000|
|464|16|2160724879344|
|465|1|2160724880928|
|...|...|...|
|1016|1|2160635636480|
|2176|1160|2160726063040|
|3200|1024|2160724362096|
|4128|928|2160688590304|
|4576|448|2160635890208|
|4736|160|2160724769808|
|5056|320|2160744468544|
|8096|3040|2160745279680|
|12064|3968|2160703847904|
|13072|1008|2160724677104|
|14592|1520|2160745337504|
|15600|1008|2160724821296|
|16288|688|2160726148256|Как интересно. Получается такая картина:
Первое прибавление. Питон честно выделяет новую строку.
Второе прибавление. Питон кажется что-то подозревает и выделяет сразу место под следующие прибавления - по 16 ячеек (но в первый раз чуть меньше).
Прибавление 464. Питон почему-то вдруг обратно переключается на копирование строки каждый раз.
Прибавление 1016 (тут цифры разные при разных запусках). Питон вдруг вспоминает про оптимизацию и начинает выделять под строку большие куски памяти, довольно неравномерные. Возможно, он выделяет просто те сплошные куски, которые у него есть в куче и поэтому такое отсутствие системы? Тут уже нужно будет смотреть исходники.
В целом картина получается интересная. Кстати, Питон умный и если заменить код на такой, то ничего не изменится, оптимизация сохранится:
string = string + '-'Оптимизация пропадёт только если сохранять результат в другую переменную.
Почему это важно.
Если бы не было этой оптимизации, то при каждом добавлении символа или строки в нашу строку происходило бы копирование старой строки в новое место, где достаточно памяти под новую строку. Такой процесс имел бы асимптотику O(n2) при добавлении n символов в строку по одному и это было бы очень долго и нерационально. Вместо этого обычно рекомендуют добавлять части строки в список и в самом конце собирать итоговую строку с помощью метода join, что-то типа ''.join(lst). Но, благодаря описываемой тут оптимизации мы видим, что такие добавления можно делать и к строке и производительность при этом должна не сильно страдать. Но конкретика будет зависеть от длины добавляемых фрагментов строки.
"А теперь - слайды!"
Люблю проверять всё "руками", благо Питон это легко и удобно позволяет. Планирую постепенно публиковать и другие эксперименты с Питоном. Спасибо за чтение.
P.S. Таблица в markdown похоже не получилась, подскажите, плиз, как поправить!
P.P.S. Пишут, что начиная с CPython 3.11 эту оптимизацию потеряли. ( Формирование строк через объединение списка вновь актуально.