Строка Python 'join' быстрее (?), Чем '+', но что здесь не так?

Question

Я спросил самый эффективный метод массовой динамической конкатенации строк в предыдущем посте, и мне предложили использовать метод 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 на 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 и это обеспечивает '+' как наиболее эффективный? Должен ли я использовать '+' в качестве альтернативы join ? Или я сделал что-то очень глупое? Или что? Пожалуйста, объясните ясно.

Answer 1

Некоторые из нас, приверженцев 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 не поднимает ваш запрос от вашего имени. так что вы должны делать свой подъем в тех редких случаях, когда важна каждая микросекунда.

Answer 2

Почему q намного медленнее: когда вы говорите

l += "a"

вы добавляете строку "a" в конец l, но когда вы говорите

l = l + ["a"]

вы создаете новый список с содержимым l и ["a"], а затем переназначаете результаты обратно на l. Таким образом, новые списки постоянно создаются.

Answer 3

Я предполагаю, что x () медленнее, потому что вы сначала строите массив, а затем присоединяетесь к нему. Таким образом, вы измеряете не только время, необходимое для объединения, но и время, которое вы тратите на создание массива.

В сценарии, где у вас уже есть массив и вы хотите создать строку из его элементов, объединение должно быть быстрее, чем итерация по массиву и построение строки шаг за шагом.

Answer 4

Я разобрался с ответом из ответов экспертов. Конкатенация строк 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

Подводя итог всем этим, я принял следующие решения для меня:

1. Если у вас есть список доступных строк, лучший метод для строки быстрый.
2. Если вы можете использовать понимание списка, Это самый простой и быстрый способ.
3. Если вам нужно объединение от 1 до 10 (среднее) длиной от 1 до 100, список append, '+', оба занимают одно и то же время (почти обратите внимание, что время масштабируется).
4. Оптимизированный список приложений выглядит очень хорошо в большинстве ситуаций.
5. Когда #concatenation или длина строки увеличивается, '+' начинает занимать значительно больше и больше времени. Обратите внимание, что на 10000 конкатенаций с 100'a 'мой компьютер завис!
6. Если вы используете список, добавьте и «присоединиться» всегда ты в безопасности все время (указал Алекс Мартелли).
7. Но в какой-то ситуации скажи, где ты нужно принять пользовательский ввод и распечатать «Привет, пользовательский мир!», Проще всего использовать «+». Я думаю, что составление списка и присоединиться для этого случая как x = input ("Введите имя пользователя:"), а затем x.join (["Hello", "'s world! "]) более уродлив, чем" Hello% s's world! "% x or" Привет "+ x +" мир "
8. улучшен Python 3.1 производительность конкатенации. Но в некоторая реализация как и Jython, «+» менее эффективен.
9. Преждевременная оптимизация является корнем всего зла (говорят эксперты). Наиболее времени вам не нужна оптимизация. Так что не тратьте время на стремление для оптимизации (если вы не пишете большой или вычислительный проект, где каждый микро / миллисекунда имеет значение.
10. Используйте эту информацию и пишите в как хочешь обстоятельства при рассмотрение.
11. Если вам действительно нужна оптимизация, используйте профилировщик, найдите узкие места и попытаться оптимизировать их.

Наконец, я пытаюсь изучить Python более глубоко. Так что нет ничего необычного в том, что в моих наблюдениях будут ошибки (ошибки). Итак, прокомментируйте это и предложите мне, если я выбрал неправильный маршрут Спасибо всем за участие.

Answer 5

Этот вопрос действительно о том, что вещи стоят. Мы будем играть немного быстро и без потерь, вычитая результаты в подобных случаях. Вы можете решить для себя, является ли это допустимым методом. Вот несколько базовых тестов:

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

Что касается вопроса ОП, то join () быстрый, но время создания базового списка, будь то с помощью примитивов списка или понимания списка, сравнимо с созданием строки с примитивами строки. Если у вас уже есть список, преобразуйте его в строку с помощью join () - это будет быстро.

Времена, представленные OP, указывают на то, что построение списков с использованием операторов сцепления происходит медленно. Напротив, использование списочных представлений быстро. Если вам нужно создать список, используйте понимание списка.

Наконец, давайте рассмотрим три из ближайших функций 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 Module of the Week Дуга Хеллмана, опубликовавшего на dis .

Answer 6

Здесь уже есть много хороших резюме, но только для большего доказательства.

Источник: я часами смотрел на исходный код 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

Если у вас есть что-то, кроме строк, используйте формат, потому что дух.

Надеюсь, это поможет!

Answer 7

Вы измеряете две различные операции: создание массива строк и объединение строк.

    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

Answer 8

Существует разница между + = и + со строками - если нет других ссылок на «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 и более ранних версиях.

Answer 9

В дополнение к тому, что сказали другие, 100 1-символьных строк действительно малы . (Я немного удивлен, что вы получаете разделение результатов вообще.) Это тот набор данных, который помещается в кэш вашего процессора. Вы не увидите асимптотику на микробенчмарке.

Answer 10

Интересно: я провел несколько тестов, в которых размер строки изменяется, и вот что я нашел:

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 - сумма длин всех соединяемых строк).