Строка Python 'join' быстрее (?), Чем '+', но что здесь не так?
В более раннем посте я спросил наиболее эффективный метод массовой динамической конкатенации строк, и мне предложили использовать метод объединения, лучший, самый простой и быстрый способ сделать это (как все говорили). Но пока я играл с конкатенацией строк, я обнаружил некоторые странные (?) Результаты. Я уверен, что что-то происходит, но я не могу этого не понять. Вот что я сделал:
Я определил эти функции:
import timeit
def x():
s=[]
for i in range(100):
# Other codes here...
s.append("abcdefg"[i%7])
return ''.join(s)
def y():
s=''
for i in range(100):
# Other codes here...
s+="abcdefg"[i%7]
return s
def z():
s=''
for i in range(100):
# Other codes here...
s=s+"abcdefg"[i%7]
return s
def p():
s=[]
for i in range(100):
# Other codes here...
s+="abcdefg"[i%7]
return ''.join(s)
def q():
s=[]
for i in range(100):
# Other codes here...
s = s + ["abcdefg"[i%7]]
return ''.join(s)
Я пытался сохранить другие вещи (кроме конкатенации) почти одинаковыми во всех функциях. Затем я проверил следующее с результатами в комментарии (используя Python 3.1.1 IDLE на 32-битной машине Windows):
timeit.timeit(x) # 31.54912480500002
timeit.timeit(y) # 23.533029429999942
timeit.timeit(z) # 22.116181330000018
timeit.timeit(p) # 37.718607439999914
timeit.timeit(q) # 108.60377576499991
Это означает, что это показывает, что strng = strng + dyn_strng является самым быстрым. Хотя разница во времени не так существенна (кроме последней), но я хочу знать, почему это происходит. Это потому, что я использую Python 3.1.1, и это обеспечивает '+' как наиболее эффективный? Должен ли я использовать "+" в качестве альтернативы, чтобы присоединиться? Или я сделал что-то очень глупое? Или что? Пожалуйста, объясните четко.
11 ответов
Я разобрался с ответом из ответов экспертов. Конкатенация строк Python (и измерения времени) зависит от них (насколько я видел):
- Количество конкатенаций
- Средняя длина струн
- Количество вызовов функций
Я построил новый код, который связывает это. Спасибо Peter S Magnusson, sepp2k, hughdbrown, David Wolever и другим за указание важных моментов, которые я пропустил ранее. Кроме того, в этом коде я мог что-то пропустить. Поэтому я очень ценю любые ответы, указывающие на наши ошибки, предложения, критику и т. Д. В конце концов, я здесь для изучения. Вот мой новый код:
from timeit import timeit
noc = 100
tocat = "a"
def f_call():
pass
def loop_only():
for i in range(noc):
pass
def concat_method():
s = ''
for i in range(noc):
s = s + tocat
def list_append():
s=[]
for i in range(noc):
s.append(tocat)
''.join(s)
def list_append_opt():
s = []
zap = s.append
for i in range(noc):
zap(tocat)
''.join(s)
def list_comp():
''.join(tocat for i in range(noc))
def concat_method_buildup():
s=''
def list_append_buildup():
s=[]
def list_append_opt_buildup():
s=[]
zap = s.append
def function_time(f):
return timeit(f,number=1000)*1000
f_callt = function_time(f_call)
def measure(ftuple,n,tc):
global noc,tocat
noc = n
tocat = tc
loopt = function_time(loop_only) - f_callt
buildup_time = function_time(ftuple[1]) -f_callt if ftuple[1] else 0
total_time = function_time(ftuple[0])
return total_time, total_time - f_callt - buildup_time - loopt*ftuple[2]
functions ={'Concat Method\t\t':(concat_method,concat_method_buildup,True),
'List append\t\t\t':(list_append,list_append_buildup,True),
'Optimized list append':(list_append_opt,list_append_opt_buildup,True),
'List comp\t\t\t':(list_comp,0,False)}
for i in range(5):
print("\n\n%d concatenation\t\t\t\t10'a'\t\t\t\t 100'a'\t\t\t1000'a'"%10**i)
print('-'*80)
for (f,ft) in functions.items():
print(f,"\t|",end="\t")
for j in range(3):
t = measure(ft,10**i,'a'*10**j)
print("%.3f %.3f |" % t,end="\t")
print()
И вот что я получил. [В столбце времени показаны два (в масштабе) времени: первый - общее время выполнения функции, а второй - фактическое (?) Время объединения. Я вычел время вызова функции, время создания функции (время инициализации) и время итерации. Здесь я рассматриваю случай, когда это не может быть сделано без цикла (скажем, больше внутри).]
1 concatenation 1'a' 10'a' 100'a'
------------------- ---------------------- ------------------- ----------------
List comp | 2.310 2.168 | 2.298 2.156 | 2.304 2.162
Optimized list append | 1.069 0.439 | 1.098 0.456 | 1.071 0.413
Concat Method | 0.552 0.034 | 0.541 0.025 | 0.565 0.048
List append | 1.099 0.557 | 1.099 0.552 | 1.094 0.552
10 concatenations 1'a' 10'a' 100'a'
------------------- ---------------------- ------------------- ----------------
List comp | 3.366 3.224 | 3.473 3.331 | 4.058 3.916
Optimized list append | 2.778 2.003 | 2.956 2.186 | 3.417 2.639
Concat Method | 1.602 0.943 | 1.910 1.259 | 3.381 2.724
List append | 3.290 2.612 | 3.378 2.699 | 3.959 3.282
100 concatenations 1'a' 10'a' 100'a'
------------------- ---------------------- ------------------- ----------------
List comp | 15.900 15.758 | 17.086 16.944 | 20.260 20.118
Optimized list append | 15.178 12.585 | 16.203 13.527 | 19.336 16.703
Concat Method | 10.937 8.482 | 25.731 23.263 | 29.390 26.934
List append | 20.515 18.031 | 21.599 19.115 | 24.487 22.003
1000 concatenations 1'a' 10'a' 100'a'
------------------- ---------------------- ------------------- ----------------
List comp | 134.507 134.365 | 143.913 143.771 | 201.062 200.920
Optimized list append | 112.018 77.525 | 121.487 87.419 | 151.063 117.059
Concat Method | 214.329 180.093 | 290.380 256.515 | 324.572 290.720
List append | 167.625 133.619 | 176.241 142.267 | 205.259 171.313
10000 concatenations 1'a' 10'a' 100'a'
------------------- ---------------------- ------------------- ----------------
List comp | 1309.702 1309.560 | 1404.191 1404.049 | 2912.483 2912.341
Optimized list append | 1042.271 668.696 | 1134.404 761.036 | 2628.882 2255.804
Concat Method | 2310.204 1941.096 | 2923.805 2550.803 | STUCK STUCK
List append | 1624.795 1251.589 | 1717.501 1345.137 | 3182.347 2809.233
Подводя итог всем этим, я принял следующие решения для меня:
- Если у вас есть доступный список строк, метод 'join' будет лучшим и быстрым.
- Если вы можете использовать понимание списка, это также самый простой и быстрый способ.
- Если вам нужно объединение от 1 до 10 (среднее) длиной от 1 до 100, добавьте в список, "+" оба требуют одинакового (почти, обратите внимание, что время масштабируется) времени.
- Оптимизированное добавление в список в большинстве случаев выглядит очень хорошо.
- Когда #concatenation или длина строки увеличивается, "+" начинает занимать значительно больше и больше времени. Обратите внимание, что на 10000 конкатенаций с 100'a'мой компьютер завис!
- Если вы всегда используете list append и 'join', вы все время в безопасности (указывает Алекс Мартелли).
- Но в некоторых ситуациях, скажем, где вам нужно взять ввод пользователя и напечатать "Hello user world!", Проще всего использовать "+". Я думаю, что создание списка и присоединение для этого случая, например, x = input("Enter user name:"), а затем x.join(["Hello ","'s world!"]) Уродливее, чем"Hello % s world! "% x or" Hello "+ x + "'s world"
- Python 3.1 улучшил производительность конкатенации. Но в некоторых реализациях, таких как Jython, "+" менее эффективен.
- Преждевременная оптимизация - корень всего зла (говорят эксперты). Большую часть времени вам не нужна оптимизация. Так что не тратьте время на стремление к оптимизации (если только вы не пишете большой или вычислительный проект, в котором учитывается каждая микро / миллисекунда).
- Используйте эту информацию и пишите так, как вам нравится, учитывая обстоятельства.
- Если вам действительно нужна оптимизация, используйте профилировщик, найдите узкие места и попытайтесь их оптимизировать.
Наконец, я пытаюсь изучить Python более глубоко. Так что нет ничего необычного в том, что в моих наблюдениях будут ошибки (ошибки). Итак, прокомментируйте это и предложите мне, если я иду по неправильному маршруту. Спасибо всем за участие.
Некоторые из нас, приверженцев Python, я полагаю, в основном Rigo и Hettinger, старались изо всех сил (на пути к 2.5, я полагаю) оптимизировать некоторые особые случаи, увы, слишком распространенные s += something упадок, утверждая, что было доказано, что новички никогда не будут убеждены, что ''.join правильный путь и ужасная медлительность += может дать Python плохое имя. Другие из нас не были такими горячими, потому что они просто не могли оптимизировать каждый случай (или даже большинство из них) для достойной производительности; но мы не чувствовали себя достаточно остро в этом вопросе, чтобы попытаться активно их заблокировать.
Я считаю, что эта тема доказывает, что мы должны были противостоять им более строго. Как и сейчас, они оптимизированы += в некотором трудно предсказуемом подмножестве случаев, где это может быть, возможно, на 20% быстрее для конкретных глупых случаев, чем надлежащим образом (который все еще ''.join) - просто идеальный способ заманить новичков в погоню за несущественными 20% -ными выигрышами, используя неправильную идиому... по цене, время от времени и от их POV из ниоткуда, поражения с потерей производительности 200% (или больше, поскольку нелинейное поведение все еще скрывается за пределами углов, которые Хеттингер и Риго намазывают и кладут цветы;-) - тот, который имеет значение, тот, который сделает их несчастными. Это идет вразрез с "идеальным единственным очевидным способом сделать это" в Python, и мне кажется, что мы все вместе попали в ловушку для новичков - тоже самое лучшее... тех, кто не просто принимает что им говорят их "лучшие", но с любопытством иди и спрашивай и исследуй.
Ах, хорошо - я сдаюсь. OP, @mshsayem, продолжайте, используйте += везде, наслаждайтесь своими неуместными ускорениями на 20% в тривиальных, крошечных, не относящихся к делу случаях, и вам лучше наслаждаться ими до предела - потому что однажды, когда вы не сможете этого увидеть Приходя в ВАЖНУЮ, БОЛЬШУЮ операцию, вы столкнетесь с ударом по животу приближающегося грузовика с прицепом с замедлением на 200% (если вам не повезло, и это 2000%;-). Просто помните: если вы когда-нибудь почувствуете, что "Питон ужасно медленный", ПОМНИТЕ, скорее всего, это одна из ваших любимых петель += оборачиваясь и кусая руку, которая его кормит.
Для остальных из нас - тех, кто понимает, что значит говорить, мы должны забыть о малой эффективности, скажем, в 97% случаев, я буду искренне рекомендовать ''.joinТаким образом, мы все можем спать в полном спокойствии и ЗНАТЬ, что мы не столкнемся с суперлинейным замедлением, когда мы меньше всего ожидаем и меньше всего можем себе позволить. Но для вас, Армин Риго и Рэймонд Хеттингер (последние два, мои дорогие личные друзья, кстати, не просто соавторы;-) - пусть ваши += будь спокоен и твои биг-о никогда не хуже чем N!-)
Итак, для остальных из нас, вот более значимый и интересный набор измерений:
$ python -mtimeit -s'r=[str(x)*99 for x in xrange(100,1000)]' 's="".join(r)'
1000 loops, best of 3: 319 usec per loop
900 строк по 297 символов в каждой, присоединение к списку напрямую, конечно же, происходит быстрее всего, но ОП боится, что придется делать добавления до этого. Но:
$ python -mtimeit -s'r=[str(x)*99 for x in xrange(100,1000)]' 's=""' 'for x in r: s+=x'
1000 loops, best of 3: 779 usec per loop
$ python -mtimeit -s'r=[str(x)*99 for x in xrange(100,1000)]' 'z=[]' 'for x in r: z.append(x)' '"".join(z)'
1000 loops, best of 3: 538 usec per loop
... с небольшим количеством данных (всего несколько сотен килобайт - потребляемая измеряемая доля миллисекунды в разные стороны), даже просто старое доброе .append уже превосходят Кроме того, это очевидно и тривиально легко оптимизировать:
$ python -mtimeit -s'r=[str(x)*99 for x in xrange(100,1000)]' 'z=[]; zap=z.append' 'for x in r: zap(x)' '"".join(z)'
1000 loops, best of 3: 438 usec per loop
брить еще десятые доли миллисекунды в течение среднего времени цикла. Все (по крайней мере, все, кто полностью помешан на высокой производительности), очевидно, знают, что HOISTING (извлекающий из внутреннего цикла повторяющиеся вычисления, которые в противном случае выполнялись бы снова и снова) - это ключевой прием в оптимизации - Python не поднимает от вашего имени Таким образом, вы должны сделать свой собственный подъем в тех редких случаях, когда важна каждая микросекунда.
Что касается почему q намного медленнее: когда вы говорите
l += "a"
вы добавляете строку "a" до конца l, но когда вы говорите
l = l + ["a"]
вы создаете новый список с содержанием l а также ["a"] а затем переназначение результатов обратно l, Таким образом, новые списки постоянно создаются.
Этот вопрос действительно о том, что вещи стоят. Здесь мы будем играть немного быстро и свободно, вычитая результаты в подобных случаях. Вы можете решить для себя, является ли это допустимым методом. Вот несколько основных тестовых случаев:
import timeit
def append_to_list_with_join():
s=[]
for i in xrange(100):
s.append("abcdefg"[i%7])
return ''.join(s)
def append_to_list_with_join_opt():
s=[]
x = s.append
for i in xrange(100):
x("abcdefg"[i%7])
return ''.join(s)
def plus_equals_string():
s=''
for i in xrange(100):
s+="abcdefg"[i%7]
return s
def plus_assign_string():
s=''
for i in xrange(100):
s=s+"abcdefg"[i%7]
return s
def list_comp_join():
return ''.join(["abcdefg"[i%7] for i in xrange(100)])
def list_comp():
return ["abcdefg"[i%7] for i in xrange(100)]
def empty_loop():
for i in xrange(100):
pass
def loop_mod():
for i in xrange(100):
a = "abcdefg"[i%7]
def fast_list_join():
return "".join(["0"] * 100)
for f in [append_to_list_with_join, append_to_list_with_join_opt, plus_equals_string,plus_assign_string,list_comp_join, list_comp, empty_loop,loop_mod, fast_list_join]:
print f.func_name, timeit.timeit(f)
И вот что они стоят:
append_to_list_with_join 25.4540209021
append_to_list_with_join_opt 19.9999782794
plus_equals_string 16.7842428996
plus_assign_string 14.8312124167
list_comp_join 16.329590353
list_comp 14.6934344309
empty_loop 2.3819276612
loop_mod 10.1424356308
fast_list_join 2.58149394686
Во-первых, у многих вещей есть неожиданные затраты в Python. Приложение append_to_list_with_join против append_to_list_with_join_opt показывает, что даже поиск метода на объекте имеет немаловажную стоимость. В этом случае поиск s.append занимает четверть времени.
Далее, list_comp_join против list_comp показывает, что join() работает довольно быстро: это занимает около 1,7 или только 10% времени list_comp_join.
loop_mod показывает, что большая часть этого теста на самом деле в настройке данных, независимо от того, какой метод построения строки используется. Согласно выводу, время, необходимое для "string = string + ", "string += " и понимания списка:
plus_equals_string = 16.78 - 10.14 = 6.64
plus_assign_string = 14.83 - 10.14 = 4.69
list_comp = 14.69 - 10.14 = 4.55
Что касается вопроса OP, join() быстрый, но время создания базового списка, будь то с помощью примитивов списка или понимания списка, сравнимо с созданием строки с строковыми примитивами. Если у вас уже есть список, преобразуйте его в строку с помощью join() - это будет быстро.
Времена, представленные OP, указывают на то, что построение списков с использованием операторов сцепления происходит медленно. Напротив, использование списочных представлений быстро. Если вам нужно создать список, используйте понимание списка.
Наконец, давайте рассмотрим три из ближайших функций ОП: в чем разница между x, p и q? Давайте немного упростим:
import timeit
def x():
s=[]
for i in range(100):
s.append("c")
def p():
s=[]
for i in range(100):
s += "c"
def q():
s=[]
for i in range(100):
s = s + ["c"]
for f in [x,p,q]:
print f.func_name, timeit.timeit(f)
Вот результаты:
x 16.0757342064
p 87.1533697719
q 85.0999698984
А вот и разборка:
>>> import dis
>>> dis.dis(x)
2 0 BUILD_LIST 0
3 STORE_FAST 0 (s)
3 6 SETUP_LOOP 33 (to 42)
9 LOAD_GLOBAL 0 (range)
12 LOAD_CONST 1 (100)
15 CALL_FUNCTION 1
18 GET_ITER
>> 19 FOR_ITER 19 (to 41)
22 STORE_FAST 1 (i)
4 25 LOAD_FAST 0 (s)
28 LOAD_ATTR 1 (append)
31 LOAD_CONST 2 ('c')
34 CALL_FUNCTION 1
37 POP_TOP
38 JUMP_ABSOLUTE 19
>> 41 POP_BLOCK
>> 42 LOAD_CONST 0 (None)
45 RETURN_VALUE
>>> dis.dis(p)
2 0 BUILD_LIST 0
3 STORE_FAST 0 (s)
3 6 SETUP_LOOP 30 (to 39)
9 LOAD_GLOBAL 0 (range)
12 LOAD_CONST 1 (100)
15 CALL_FUNCTION 1
18 GET_ITER
>> 19 FOR_ITER 16 (to 38)
22 STORE_FAST 1 (i)
4 25 LOAD_FAST 0 (s)
28 LOAD_CONST 2 ('c')
31 INPLACE_ADD
32 STORE_FAST 0 (s)
35 JUMP_ABSOLUTE 19
>> 38 POP_BLOCK
>> 39 LOAD_CONST 0 (None)
42 RETURN_VALUE
>>> dis.dis(q)
2 0 BUILD_LIST 0
3 STORE_FAST 0 (s)
3 6 SETUP_LOOP 33 (to 42)
9 LOAD_GLOBAL 0 (range)
12 LOAD_CONST 1 (100)
15 CALL_FUNCTION 1
18 GET_ITER
>> 19 FOR_ITER 19 (to 41)
22 STORE_FAST 1 (i)
4 25 LOAD_FAST 0 (s)
28 LOAD_CONST 2 ('c')
31 BUILD_LIST 1
34 BINARY_ADD
35 STORE_FAST 0 (s)
38 JUMP_ABSOLUTE 19
>> 41 POP_BLOCK
>> 42 LOAD_CONST 0 (None)
45 RETURN_VALUE
Петли почти идентичны. Сравнение составляет CALL_FUNCTION+POP_TOP против INPLACE_ADD+STORE_FAST против BUILD_LIST+BINARY_ADD+STORE_FAST. Однако я не могу дать более низкое объяснение, чем это - я просто не могу найти стоимость байт-кодов python в сети. Тем не менее, вы можете получить некоторое вдохновение, посмотрев на Даг Хеллманн "Модуль недели Python", опубликованный на дис.
Я предполагаю, что x() медленнее, потому что вы сначала строите массив, а затем присоединяетесь к нему. Таким образом, вы измеряете не только время, которое занимает соединение, но и время, которое вы тратите на создание массива.
В сценарии, где у вас уже есть массив и вы хотите создать строку из его элементов, соединение должно быть быстрее, чем итерация по массиву и создание строки шаг за шагом.
Здесь уже есть много хороших резюме, но только для большего доказательства.
Источник: я смотрел на исходный код Python в течение часа и рассчитал сложности!
Мои выводы.
Для 2 струн. (Предположим, что n - длина обеих строк)
Concat (+) - O(n)
Join - O(n+k) effectively O(n)
Format - O(2n+k) effectively O(n)
Для более чем 2 строк. (Предположим, что n - длина всех строк)
Concat (+) - O(n^2)
Join - O(n+k) effectively O(n)
Format - O(2n+k) effectively O(n)
РЕЗУЛЬТАТ:
Если у вас есть две строки, технически конкатенация (+) лучше, эффективнее, хотя она точно такая же, как соединение и формат.
Если у вас более двух строк, concat становится ужасным, а объединение и форматирование практически одинаковы, хотя технически объединение немного лучше.
РЕЗЮМЕ:
Если вы не заботитесь об эффективности, используйте любой из вышеперечисленных. (Хотя, так как вы задали вопрос, я полагаю, что вы заботитесь
Следовательно -
Если у вас есть 2 строки, используйте concat (когда не в цикле!)
Если у вас более двух строк (все строки) (или в цикле), используйте join
Если у вас есть что-то не строки, используйте формат, потому что дух.
Надеюсь это поможет!
Вы измеряете две разные операции: создание массива строк и конкатенацию строк.
import timeit
def x():
s = []
for i in range(100):
s.append("abcdefg"[i%7])
return ''.join(s)
def y():
s = ''
for i in range(100):
s += "abcdefgh"[i%7]
# timeit.timeit(x) returns about 32s
# timeit.timeit(y) returns about 23s
Из вышесказанного действительно может показаться, что "+" является более быстрой операцией, чем соединение. Но учтите:
src = []
def c():
global src
s = []
for i in range(100):
s.append("abcdefg"[i%7])
src = s
def x2():
return ''.join(src)
def y2():
s = ''
for i in range(len(src)):
s += src[i]
return s
# timeit.timeit(c) returns about 30s
# timeit.timeit(x2) returns about 1.5s
# timeit.timeit(y2) returns about 14s
Другими словами, из-за синхронизации x() и y() ваш результат загрязняется конструкцией исходного массива. Если вы сломаете это, вы обнаружите, что объединение происходит быстрее.
Кроме того, вы работаете с небольшими массивами, и ваши временные числа просто совпадают. Если вы значительно увеличите размер массива и длину каждой строки, различия станут более очевидными:
def c2():
global src
s = []
for i in range(10000):
s.append("abcdefghijklmnopqrstuvwxyz0123456789"
src = s
# timeit.timeit(x2, number=10000) returns about 1s
# timeit.timeit(y2, number=10000) returns about 80s
Есть разница между += и + со строками - если нет других ссылок на "x", x+=y может просто добавить x, вместо того, чтобы брать копию строки для добавления - что тоже самое вы получаете выгоду от использования "".join().
Основное преимущество "".join () перед + или += состоит в том, что join () всегда должен давать линейную производительность, в то время как во многих случаях +/+= дает квадратичную производительность (т. Е. Когда вы удваиваете объем текста, вы в четыре раза больше времени). Но это будет иметь значение только с большим количеством текста, а не только с 100 байтами, и я думаю, что это не сработает, если у вас будет только одна ссылка на строку, к которой вы добавляете.
В деталях:
Лучшая производительность для конкатенации строк - один раз просмотреть каждый символ в последней строке. "".join() делает это естественно - он имеет всю необходимую информацию с самого начала.
Однако a+=b может работать двумя способами, он может либо просто добавить "b" к существующей строке, в этом случае ему нужно только взглянуть на символы в "b", либо он может взглянуть на символы в " "тоже.
В C strcat() всегда просматривает все символы в обеих строках, поэтому всегда работает плохо. Однако в Python длина строки сохраняется, поэтому строка может быть расширена до тех пор, пока на нее нет ссылок в другом месте - и вы получите хорошую производительность, только копируя символы в "b". Если на него ссылаются в другом месте, python сначала сделает копию "a", а затем добавит "b" в конец, что даст вам плохую производительность. Если вы добавляете пять строк таким образом, ваше время будет:
ab = a+b # Time is a + b
abc = ab+c # Time is (a+b) + c
abcd = abc+d # Time is (a+b+c) + d
abcde = abcd+e # Time is (a+b+c+d) + e
который, если a, b, c, d, e имеют примерно одинаковый размер, скажем, n, равен n*(n-1)/2-1 операциям или, по существу, n-квадрат.
Чтобы получить плохое поведение для x+=y, попробуйте:
def a(n=100):
res = ""
for k in xrange(n):
v=res
res += "foobar"
return res
Хотя v на самом деле не используется, достаточно запустить медленный путь для += и получить плохое поведение, которое беспокоит людей.
Я считаю, что += не был представлен до Python 2.0, поэтому было невозможно эффективно добавить его, не используя что-то вроде "".join () в Python 1.6 и более ранних версиях.
В дополнение к тому, что сказали другие, 100 строк из 1 символа действительно малы. (Я немного удивлен, что вы получаете разделение результатов вообще.) Это тот набор данных, который помещается в кэш вашего процессора. Вы не увидите асимптотических показателей на микробенчмарке.
Интересно: я провел несколько тестов, где размер строки изменяется, и вот что я нашел:
def x():
x = "a" * 100
s=[]
for i in range(100):
# Other codes here...
s.append(x)
return ''.join(s)
def z():
x = "a" * 100
s=''
for i in xrange(100):
# Other codes here...
s=s+x
return s
from timeit import timeit
print "x:", timeit(x, number=1000000)
print "z:", timeit(z, number=1000000)
Для струн длиной 1 (x = "a" * 1):
x: 27.2318270206
z: 14.4046051502
Для струн длиной 100:
x: 30.0796670914
z: 21.5891489983
И для строк длиной 1000, время выполнения составляет 100 000 раз вместо 1 000 000
x: 14.1769361496
z: 31.4864079952
Который, если мое чтение Objects/stringobject.c правильно, имеет смысл.
При первом прочтении кажется, что алгоритм String.join (за исключением крайних случаев):
def join(sep, sequence):
size = 0
for string in sequence:
size += len(string) + len(sep)
result = malloc(size)
for string in sequence:
copy string into result
copy sep into result
return result
Так что это потребует более или менее O(S) шаги (где S является суммой длин всех соединяемых строк).
Конкатенация строк была намного медленнее, чем в Python 2.5, когда он по-прежнему создавал новую копию для каждой конкатенации строк, а не добавлял к оригиналу, в результате чего метод join() стал популярным обходным путем.
Вот старый тест, демонстрирующий старую проблему: http://www.skymind.com/~ocrow/python_string/