Почему это так медленно при назначении объединенной строки переменной в Python? - PullRequest
Новая
       15

Почему это так медленно при назначении объединенной строки переменной в Python?

15 голосов
/ 11 мая 2019

Если это только конкатенация строк следующим образом, она немедленно завершается. 

test_str = "abcdefghijklmn123456789"
str1 = ""
str2 = ""

start = time.time()
for i in range(1, 100001):

    str1 = str1 + test_str
    str2 = str2 + test_str

    if i % 20000 == 0:
        print("time(sec) => {}".format(time.time() - start))
        start = time.time()

Постоянное время обработки 

time(sec) => 0.013324975967407227
time(sec) => 0.020363807678222656
time(sec) => 0.009979963302612305
time(sec) => 0.01744699478149414
time(sec) => 0.0227658748626709

Необъяснимо, что присвоение объединенной строки другой переменной делает процесс все медленнее и медленнее. 

test_str = "abcdefghijklmn123456789"
str1 = ""
str2 = ""

start = time.time()
for i in range(1, 100001):

    str1 = str1 + test_str
    # str2 = str2 + test_str
    # ↓
    str2 = str1

    if i % 20000 == 0:
        print("time(sec) => {}".format(time.time() - start))
        start = time.time()

Время обработки будет отложено. 

time(sec) => 0.36466407775878906
time(sec) => 1.105351209640503
time(sec) => 2.6467738151550293
time(sec) => 5.891657829284668
time(sec) => 9.266698360443115

И python2, и python3 дают одинаковый результат.

1 Ответ

21 голосов
/ 11 мая 2019

В целом, стандарт языка Python здесь не дает никаких гарантий; на самом деле, как определено, строки неизменяемы, и то, что вы делаете , должно кусать вас в любом случае, так как вы написали форму Алгоритм Шлемьеля-живописца .

Но в первом случае, как деталь реализации, CPython (справочный интерпретатор) поможет вам и объединит строку на месте (технически нарушая гарантию неизменности) при некоторых довольно специфических условиях, которые позволяют ему придерживаться дух правил неизменности. Наиболее важным условием является то, что на соединяемую строку следует ссылаться только в одном месте (если это не так, другая ссылка изменится на месте, нарушив видимость неизменности str). Присваивая str2 = str1 после каждой конкатенации, вы гарантируете, что при конкатенации будет две ссылки, поэтому при каждой конкатенации должен быть сделан новый str , чтобы сохранить кажущуюся неизменность строк , Это означает больше выделения и освобождения памяти, большее (и постепенно увеличивающееся) количество копий памяти и т. Д.

Обратите внимание, что полагаться на эту оптимизацию явно не рекомендуется в PEP 8, руководстве по стилю Python :

  • Код должен быть написан так, чтобы не мешать другим реализациям Python (PyPy, Jython, IronPython, Cython, Psyco и т. Д.).

    Например, не полагайтесь на эффективную реализацию CPython конкатенации строк на месте для операторов в форме a += b или a = a + b. Эта оптимизация хрупка даже в CPython (она работает только для некоторых типов) и совсем не присутствует в реализациях, которые не используют пересчет. В чувствительных к производительности частях библиотеки следует использовать форму ''.join(). Это гарантирует, что объединение происходит в линейное время в разных реализациях.

Важное замечание о "работает только для некоторых типов". Эта оптимизация относится только к str; в Python 2 он не работает на unicode (хотя * Python 3 str основан на реализации unicode в Python 2), а в Python 3 он не работает на bytes (которые похожи на Python 2 str под капотом).

...