Строка Python Конкатенация в длинные строки цикла

Question

Я уже слышал пару раз, что вы не должны выполнять конкатенацию строк в цикле for, поскольку строки неизменяемы и поэтому вычисляют конкатенацию как новый экземпляр строки, а затем переназначают идентификатор. Таким образом, если результат имеет п символов временная сложность будет O (N^2)

Bad: работает в O (N^2)

letters = "" 
for c in document: 
    if c.isalpha(): 
     letters += c 

Хорошо: работает в O (п)

document = "" 
temp = [] 
for c in document: 
    if c.isalpha(): 
     temp.append(c) 
letters = "".join(temp) 

в то же время я читал, что

«Некоторые более поздние реализации функций Python-интерпретатор разработал оптимизацию, позволяющую завершить такой код в линейном времени ... »

Итак, первое решение должно быть прекрасным? Это оптимизация, которая находится в последних версиях python?

Answer 1

Сначала вы должны написать для себя наиболее читаемый код; только если у вас есть проблемы со средой выполнения, вы должны думать об оптимизации:

letters = "".join(c for c in document if c.isalpha()) 

Для текущей реализации CPython join быстрее, чем «+».

>>> def test(): 
... s = "" 
... for x in range(1000): 
...  s += 'x' 
... 
>>> timeit.timeit(test) 
157.9563412159987 
>>> def test(): 
... s = [] 
... for x in range(1000): 
...  s.append('x') 
... s = ''.join(s) 
... 
>>> timeit.timeit(test) 
147.74276081599965 

Answer 2

str неизменны, но list нет. Лучший способ добиться было бы:

my_list = [] 
for c in my_string: 
    if c.isalpha(): 
     my_list.append(c) 

Однако .append() очень дорогостоящая операция по времени (так как вы говорите сложности здесь). Проверьте: HERE сравнение, которое я сделал для другого ответа. Лучший способ будет:

my_list = [c for c in my_string if c.isalpha()] 

Теперь вы можете преобразовать это list в string как:

''.join(my_list) 

Answer 3

Ключ некоторые реализации. Не все. Если вы хотите, чтобы ваш код работал быстро на всех реализациях python, используйте str.join. В зависимости от размера вашего документа разные подходы будут быстрее. Однако "".join(...) очень pythonic, и люди будут быстрее понимать ваши намерения. Таким образом, если у вас нет лотов из small документы палкой с str.join.

Однако, чтобы получить 10-кратное увеличение скорости на str.join и +=, используйте str.translate. Однако это решение особенно важно для удаления отдельных символов.

from string import digits 
translation_table = str.maketrans("", "", digits) 
# first two args about translating characters, third is for removing characters 
letters = document.translate(translation_table) 

Причина этого увеличения скорости заключается в том, что python необходимо создать новую строку для каждого символа в документе. str.translate не нужно делать это, и это намного быстрее.