Понимание списка Python против +=
Сегодня я пытался найти метод, чтобы сделать некоторую обработку строк в Python. Более старший программист, чем я сказал, не использовать += но использовать ''.join() Я мог бы также прочитать это, например: http://wiki.python.org/moin/PythonSpeed/. Но я сам проверил это и нашел немного странные результаты (я не пытаюсь их угадать, но я хочу понять). Идея заключалась в том, если бы была строка "This is \"an example text\" содержащие пробелы "строка должна быть преобразована в Thisis"an example text"containingspaces Пробелы удаляются, но только за пределами кавычек.
Я измерил производительность двух разных версий моего алгоритма, используя ''.join(list) и один с помощью +=
import time
#uses '+=' operator
def strip_spaces ( s ):
ret_val = ""
quote_found = False
for i in s:
if i == '"':
quote_found = not quote_found
if i == ' ' and quote_found == True:
ret_val += i
if i != ' ':
ret_val += i
return ret_val
#uses "".join ()
def strip_spaces_join ( s ):
#ret_val = ""
ret_val = []
quote_found = False
for i in s:
if i == '"':
quote_found = not quote_found
if i == ' ' and quote_found == True:
#ret_val = ''.join( (ret_val, i) )
ret_val.append(i)
if i != ' ':
#ret_val = ''.join( (ret_val,i) )
ret_val.append(i)
return ''.join(ret_val)
def time_function ( function, data):
time1 = time.time();
function(data)
time2 = time.time()
print "it took about {0} seconds".format(time2-time1)
На моей машине это дало этот вывод с небольшим преимуществом для алгоритма, использующего +=
print '#using += yields ', timeit.timeit('f(string)', 'from __main__ import string, strip_spaces as f', number=1000)
print '#using \'\'.join() yields ', timeit.timeit('f(string)', 'from __main__ import string, strip_spaces_join as f', number=1000)
когда рассчитано время:
#using += yields 0.0130770206451
#using ''.join() yields 0.0108470916748
Разница действительно незначительная. Но почему ''.join() неясно выполняет функцию, которая использует +=, но, похоже, есть небольшое преимущество для версии '.join(). Я проверял это на Ubuntu 12.04 с python-2.7.3
4 ответа
Используйте правильную методологию при сравнении алгоритмов; использовать timeit модуль для устранения колебаний в загрузке процессора и подкачки.
С помощью timeit показывает, что есть небольшая разница между этими двумя подходами, но ''.join() немного быстрее:
>>> s = 1000 * string
>>> timeit.timeit('f(s)', 'from __main__ import s, strip_spaces as f', number=100)
1.3209099769592285
>>> timeit.timeit('f(s)', 'from __main__ import s, strip_spaces_join as f', number=100)
1.2893600463867188
>>> s = 10000 * string
>>> timeit.timeit('f(s)', 'from __main__ import s, strip_spaces as f', number=100)
14.545105934143066
>>> timeit.timeit('f(s)', 'from __main__ import s, strip_spaces_join as f', number=100)
14.43651008605957
Большая часть работы в ваших функциях - это циклическая обработка каждого символа и проверка кавычек и пробелов, а не сама конкатенация строк. Кроме того, ''.join() вариант делает больше работы; Сначала вы добавляете элементы в список (это заменяет += операции объединения строк), затем вы объединяете эти значения в конце, используя ''.join(), И этот метод все еще немного быстрее.
Вы можете отказаться от выполняемой работы, чтобы сравнить только часть конкатенации:
def inplace_add_concatenation(s):
res = ''
for c in s:
res += c
def str_join_concatenation(s):
''.join(s)
который показывает:
>>> s = list(1000 * string)
>>> timeit.timeit('f(s)', 'from __main__ import s, inplace_add_concatenation as f', number=1000)
6.113742113113403
>>> timeit.timeit('f(s)', 'from __main__ import s, str_join_concatenation as f', number=1000)
0.6616439819335938
Это показывает ''.join() конкатенация по-прежнему намного быстрее, чем +=, Разница в скорости лежит в петле; s это список в обоих случаях, но ''.join() перебирает значения в C, в то время как другая версия должна делать все это в Python. И в этом вся разница.
(Это может быть много деталей, о которых ОП уже знает, но полное рассмотрение проблемы может помочь другим, кто в конечном итоге ответит на этот вопрос)
Проблема в mystring += suffix является то, что строки являются неизменяемыми, так что это на самом деле эквивалентно mystring = mystring + suffix, Таким образом, реализация должна создать новый строковый объект, скопировать все символы из mystring к нему, а затем скопировать все символы из suffix после этого. Тогда mystring имя отскок, чтобы обратиться к новой строке; исходный строковый объект, на который ссылался mystring нетронутым
Само по себе это на самом деле не проблема. Любой метод объединения этих двух строк должен сделать это, в том числе ''.join([mystring, suffix]); на самом деле это еще хуже, потому что он должен сначала создать объект списка, а затем выполнить итерацию по нему, и в то время как нет фактической передачи данных при объединении пустой строки между mystring а также suffix это займет по крайней мере одну инструкцию, чтобы разобраться.
куда += становится проблемой, когда вы делаете это неоднократно. Что-то вроде этого:
mystring = ''
for c in 'abcdefg' * 1000000:
mystring += c
Помни что mystring += c эквивалентно mystring = mystring + c, Таким образом, на первой итерации цикла он оценивает '' + 'a' копирование всего 1 символа Далее это делает 'a' + 'b' копирование всего 2 символа. затем 'ab' + 'c' для 3 символов, затем 'abc' + 'd' на 4, и я думаю, вы можете видеть, куда это идет. Каждый последующий += повторяет всю работу предыдущей, а затем копирует новую строку. Это становится чрезвычайно расточительным.
''.join(...) Это лучше, потому что там вы ждете, пока не узнаете все строки, чтобы скопировать любую из них, а затем копируете каждую из них прямо на правильное место в конечном строковом объекте. Вопреки тому, что было сказано в некоторых комментариях и ответах, это сохраняется, даже если вам нужно изменить цикл, чтобы добавить строки в список строк, а затем join их после петли. Списки не являются неизменяемыми, поэтому добавление в список изменяет его на месте, и ему также нужно только добавить одну ссылку, а не копировать все символы в строке. Делать тысячи добавлений в список намного быстрее, чем тысячи строк += операции.
Повторная строка += теоретически проблема даже без циклов, если вы просто напишите свой исходный код примерно так:
s = 'foo'
s += 'bar'
s += 'baz'
...
Но на практике вы вряд ли будете писать достаточно длинную последовательность кода, подобную той, что написана от руки, если только строки не очень большие. Так что просто следите за += в циклах (или рекурсивных функциях).
Причина, по которой вы можете не увидеть этот результат, когда пытаетесь рассчитать время, заключается в том, что на самом деле есть оптимизация для строки += в интерпретаторе CPython. Давайте вернемся к моему глупому примеру цикла:
mystring = ''
for c in 'abcdefg' * 1000000:
mystring += c
Каждый раз, когда это делает mystring = mystring + c старая ценность mystring становится мусором и удаляется, а имя mystring заканчивается ссылкой на вновь созданную строку, которая начинается именно с содержимого старого объекта. Мы могли бы оптимизировать это, признав, что mystring вот-вот станет мусором, поэтому мы можем делать с ним все, что захотим, без посторонней помощи. Таким образом, даже если строки неизменны на уровне Python, на уровне реализации мы сделаем их динамически расширяемыми и реализуем target += source либо путем обычного выделения новой строки и метода копирования, либо путем расширения целевой строки и копирования только исходных символов, в зависимости от того, target будет сделан мусор.
Проблема этой оптимизации в том, что ее легко нарушить. Он прекрасно работает на небольших автономных циклах (которые проще всего преобразовать в использование join, Кстати). Но если вы делаете что-то более сложное и случайно сталкиваетесь с несколькими ссылками на строки, вдруг код может работать намного медленнее.
Скажем, у вас есть некоторые журналирующие вызовы в цикле, и система журналирования на некоторое время буферизует свои сообщения, чтобы распечатать их все сразу (должно быть безопасно; строки неизменяемы). Ссылки на ваши строки в системе регистрации могут остановить += оптимизация применима.
Скажем, вы написали свой цикл как рекурсивную функцию (что Python на самом деле не очень нравится, но все же), создавая строку с += по какой-то причине. Внешние кадры стека будут по-прежнему иметь ссылки на старые значения.
Или, может быть, то, что вы делаете со строками, генерирует серию объектов, поэтому вы передаете их классу; если класс хранит строку непосредственно в экземпляре, оптимизация прекращается, но если класс сначала манипулирует ими, тогда оптимизация все еще работает.
По сути, производительность того, что выглядит как действительно простая примитивная операция, либо нормальная, либо очень плохая, и зависит от другого кода, отличного от кода, использующего +=, В крайних случаях вы можете внести изменения в совершенно отдельный файл (может быть, даже в пакет стороннего производителя), что приведет к значительному снижению производительности в одном из ваших модулей, который не менялся долгое время!
Кроме того, я понимаю, что += оптимизацию легко реализовать на CPython, потому что она использует подсчет ссылок; вы можете легко определить, когда целевая строка является мусором, посмотрев на его счетчик ссылок, тогда как с более сложной сборкой мусора вы не сможете определить, пока не удалите ссылку и не дождетесь запуска сборщика мусора; слишком поздно, чтобы принять решение о том, как реализовать +=, Итак, опять же, действительно простой базовый код, который не должен иметь проблем с переносимостью между реализациями Python, может неожиданно запускаться слишком медленно, чтобы быть полезным, когда вы перемещаете его в другую реализацию.
И вот несколько сравнительных тестов, чтобы показать масштаб проблемы:
import timeit
def plus_equals(data):
s = ''
for c in data:
s += c
def simple_join(data):
s = ''.join(data)
def append_join(data):
l = []
for c in data:
l.append(c)
s = ''.join(l)
def plus_equals_non_garbage(data):
s = ''
for c in data:
dummy = s
s += c
def plus_equals_maybe_non_garbage(data):
s = ''
for i, c in enumerate(data):
if i % 1000 == 0:
dummy = s
s += c
def plus_equals_enumerate(data):
s = ''
for i, c in enumerate(data):
if i % 1000 == -1:
dummy = s
s += c
data = ['abcdefg'] * 1000000
for f in (
plus_equals,
simple_join,
append_join,
plus_equals_non_garbage,
plus_equals_maybe_non_garbage,
plus_equals_enumerate,
):
print '{:30}{:20.15f}'.format(f.__name__, timeit.timeit(
'm.{0.__name__}(m.data)'.format(f),
setup='import __main__ as m',
number=1
))
На моей системе это печатает:
plus_equals 0.066924095153809
simple_join 0.013648986816406
append_join 0.086287975311279
plus_equals_non_garbage 540.663727998733521
plus_equals_maybe_non_garbage 0.731688976287842
plus_equals_enumerate 0.156824111938477
Оптимизация += работает очень хорошо, когда работает (даже избивая тупого append_join версия немного). Мои цифры показывают, что вы можете оптимизировать код, заменив append + join с += в некоторых случаях, но выгода не стоит того, чтобы какое-то другое будущее изменение случайно получило выброс (и, скорее всего, оно было бы невероятно маленьким, если бы в цикле была какая-то другая фактическая работа; а если нет, то вы должны использовать что-то вроде simple_join версия).
Сравнивая plus_equals_maybe_non_garbage в plus_equals_enumerate Вы можете видеть, что даже если оптимизация не удалась только один на каждую тысячу += операций, все еще есть 5-кратная потеря производительности.
Оптимизация += на самом деле предназначен только для того, чтобы спасти людей, которые не являются опытными программистами на Python или просто быстро и лениво пишут какой-то рабочий код. Если вы думаете о том, что вы делаете, вы должны использовать join,
Резюме: Использование += хорошо для фиксированного небольшого числа конкатенаций. join всегда лучше использовать циклы для создания строк. На практике вы можете не увидеть огромное улучшение кода переноса из += в join, из-за += оптимизация. Вы все еще должны использовать join в любом случае, потому что оптимизация ненадежна и разница, когда она не срабатывает, может быть огромной.
Другой вариант - написать функцию, которая присоединяется с использованием генератора, а не добавляется в список каждый раз.
Например:
def strip_spaces_gen(s):
quote_found = False
for i in s:
if i == '"':
quote_found = not quote_found
if i == ' ' and quote_found == True:
# Note: you (c|sh)ould drop the == True, but I'll leave it here so as to not give an unfair advantage over the other functions
yield i
if i != ' ':
yield i
def strip_spaces_join_gen(ing):
return ''.join(strip_spaces_gen(ing))
Это выглядит примерно так же (как объединение) для более короткой строки:
In [20]: s = "This is \"an example text\" containing spaces"
In [21]: %timeit strip_spaces_join_gen(s)
10000 loops, best of 3: 22 us per loop
In [22]: %timeit strip_spaces(s)
100000 loops, best of 3: 13.8 us per loop
In [23]: %timeit strip_spaces_join(s)
10000 loops, best of 3: 23.1 us per loop
Но быстрее для больших строк.
In [24]: s = s * 1000
In [25]: %timeit strip_spaces_join_gen(s)
100 loops, best of 3: 12.9 ms per loop
In [26]: %timeit strip_spaces(s)
100 loops, best of 3: 17.1 ms per loop
In [27]: %timeit strip_spaces_join(s)
100 loops, best of 3: 17.5 ms per loop
Разница в производительности между += а также .join зависит от множества факторов:
Операционная система Выполнение этого для все более крупных строк в Unix-подобных системах или системах Windows может дать совершенно разные результаты. Как правило, вы увидите гораздо большее увеличение времени выполнения под Windows.
Реализация Python. По умолчанию мы говорим о CPython, но есть и другие реализации, такие как Jython или PyPy. Давайте посмотрим на PyPy. Используя исходный код из ответа выше:
CPython 2.7: python concat.py inplace_add_concatenation: 0.420897960663 str_join_concatenation: 0.061793088913 ratio: 6.81140833169 PyPy 1.9: pypy concat.py inplace_add_concatenation: 1.26573014259 str_join_concatenation: 0.0392870903015 ratio: 32.2174570038
Хотя PyPy славится своими ускорениями по сравнению с CPython, он медленнее += версия. Это было намеренное решение, не включающее оптимизацию `+='в версии PyPy по умолчанию.
Практическое правило, касающееся производительности: "Никогда не угадай, всегда измеряй".
Также чтение документов помогает:
6 Подробности реализации CPython: если s и t являются обеими строками, некоторые реализации Python, такие как CPython, обычно могут выполнять оптимизацию на месте для назначений вида s = s + t или s += t. Когда это применимо, эта оптимизация делает квадратичное время выполнения гораздо менее вероятным. Эта оптимизация зависит как от версии, так и от реализации. Для чувствительного к производительности кода предпочтительно использовать метод str.join(), который обеспечивает согласованную производительность линейной конкатенации между версиями и реализациями."""