Предположим, что у нас есть список строк, и мы хотим создать строку путем объединения всех элементов в этом списке.Примерно так:
def foo(str_lst):
result = ''
for element in str_lst:
result += element
return result
Поскольку строки являются неизменяемыми объектами, я ожидаю, что python создает новый объект str и копирует содержимое результата и элемента на каждой итерации.Это усложняет O(M * N^2) время, M - длину каждого элемента, а N - размер списка.
Однако мой эксперимент показывает, что он выполняется за линейное время.
N = 1000000 # 1 million
str_lst = ['a' for _ in range(N)]
foo(str_lst) # It takes around 0.5 seconds
N = 2000000 # 2 million
str_lst = ['a' for _ in range(N)]
foo(str_lst) # It takes around 1.0 seconds
N = 10000000 # 10 million
str_lst = ['a' for _ in range(N)]
foo(str_lst) # It takes around 5.3 seconds
Я подозреваю, что python использует что-то вроде stringbuffer под капотом.Таким образом, он не создает новый объект на каждой итерации.
Теперь рассмотрим немного другую реализацию.Разница лишь в одном дополнительном назначении.
def foo2(str_lst):
result = ''
for element in str_lst:
result += element
temp = result # new added line
return result
Я знаю, что строка temp = result не создает новый объект.temp просто указывает на тот же объект.Таким образом, это небольшое изменение не должно сильно повлиять на производительность.
N = 1000000 # 1 million
str_lst = ['a' for _ in range(N)]
foo(str_lst) # It takes around 0.5 seconds
foo2(str_lst) # It takes around 30 seconds
N = 2000000 # 2 million
str_lst = ['a' for _ in range(N)]
foo(str_lst) # It takes around 1 seconds
foo2(str_lst) # It takes around 129 seconds
Однако есть огромная разница.И похоже, что функция foo2 - это O (N ^ 2), а функция foo - это O (N).
Мой вопрос: как python достигает линейного времени в конкатенации строк, не нарушая другие языковые компоненты, такие как неизменяемое присвоение объектов?и как эта дополнительная строка так сильно влияет на производительность?Я немного искал в реализации cpython, но не смог найти точное местоположение.
Обновление
Вот результаты профилирования линии.
результат для функции foo
Total time: 0.545577 s
File: <ipython-input-38-b9bb169e8fe0>
Function: foo at line 1
Line # Hits Time Per Hit % Time Line Contents
==============================================================
1 def foo(str_lst):
2 1 2.0 2.0 0.0 result = ''
3 1000001 238820.0 0.2 43.8 for element in str_lst:
4 1000000 306755.0 0.3 56.2 result += element
5 1 0.0 0.0 0.0 return result
результат для функции foo2
Total time: 30.6663 s
File: <ipython-input-40-34dd53670dd9>
Function: foo2 at line 1
Line # Hits Time Per Hit % Time Line Contents
==============================================================
1 def foo2(str_lst):
2 1 2.0 2.0 0.0 result = ''
3 1000001 299122.0 0.3 1.0 for element in str_lst:
4 1000000 30033127.0 30.0 97.7 result += element
5 1000000 413283.0 0.4 1.3 temp = result
6 1 0.0 0.0 0.0 return result
Каким-то образом строка temp = result влияет на производительность линии result += element.