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

Что касается того, почему q намного медленнее: когда вы говорите

l += "a"

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

l = l + ["a"]

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

Преобразуйте его в формат, который принимает NSDate, а затем выполните обратное преобразование.

В качестве альтернативы, в зависимости от того, на какой NSDate вы ссылаетесь (!) InitWithString должен охватывать международные стандартные даты.

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

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

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 показывает, что большая часть этого теста на самом деле заключается в настройке данных, независимо от того, какой метод построения строки используется. По заключению, время, затраченное на «строка = строка +», «строка + =» и понимание списка:

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» на дис .

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

    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 () vs 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 () over + или + = означает, что join () всегда должен давать линейную производительность, в то время как во многих случаях + / + = дает квадратичную производительность (т. е. когда вы удваиваете количество текста, вы в четыре раза увеличиваете количество затрачиваемого времени). Но это будет иметь значение только для большого количества текста, а не только для 100 байт, и я думаю он не сработает, если у вас будет только одна ссылка на строку, к которой вы добавляете.

В деталь:

Ваш лучший результат для конкатенации строк - это один раз просмотреть каждый символ в последней строке. "" .join () делает это естественным образом - у него с самого начала есть вся необходимая информация.

Однако a + = b может работать двумя способами: он может либо просто добавить «b» к существующей строке, и в этом случае ему нужно будет смотреть только на символы в «b», либо он может взглянуть на символы в "a" тоже.

В C strcat () всегда просматривает все символы в обеих строках, поэтому всегда работает плохо. В Python, однако, длина строки сохраняется, поэтому строка может быть расширена до тех пор, пока на нее нет ссылок в другом месте - и вы получаете хорошую производительность, копируя только символы из «b». Если на него есть ссылка в другом месте, python сначала сделает копию "a", а затем добавит "

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

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 , имеет смысл.

Похоже,

Конкатенация строк была намного медленнее до Python 2.5, когда он по-прежнему создавал новую копию для каждой конкатенации строк, а не добавлялся к оригиналу, что привело к тому, что join () стал популярным обходным решением.

Вот старый тест, демонстрирующий старую проблему: http://www.skymind.com/~ocrow/python_string/

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

Некоторые из нас, коммиттеров Python, я полагаю, в основном, Риго и Хеттингер, изо всех сил старались изо всех сил (я полагаю, на пути к 2.5), чтобы оптимизировать некоторые особые случаи, когда, увы, слишком-слишком common s + = something blight , утверждая, что было доказано, что новичков никогда не убедят, что ''. join - правильный путь и ужасная медлительность + = может поставить Python в плохую репутацию. Другие из нас не были такими уж горячими, потому что они просто не могли оптимизировать каждое событие (или даже большинство из них) до достойной производительности; но мы не были достаточно горячими по этому поводу, чтобы попытаться активно заблокировать их.

Я считаю, что эта цепочка доказывает, что мы должны были противостоять им более жестко. Как сейчас, они оптимизировали + = в определенном трудно предсказуемом подмножестве случаев, где это может быть, возможно, на 20% быстрее для определенных глупых случаев, чем правильный способ (который по-прежнему ''. join ) - просто идеальный способ заманить новичков в ловушку и заставить их преследовать эти несущественные 20% прироста, используя неправильную идиому ... за счет, время от времени и из их POV неожиданно, попадания в игру потеря 200% (или больше, поскольку нелинейное поведение все еще таится за пределами углов, которые Хеттингер и Риго приукрашивали и укладывали цветами ;-) - то, что ВАЖНО, то, что БУДЕТ делать их несчастными. Это идет вразрез с сутью Python «в идеале только один очевидный способ сделать это», и мне кажется, что мы, все вместе, заложили ловушку для новичков - лучших тоже ... тех, кто этого не делает. просто принять то, что им говорят их «лучшие», но с любопытством идти, спрашивать и исследовать.

А, хорошо, я сдаюсь. OP, @mshsayem, продолжайте, используйте + = везде, наслаждайтесь своими несущественными 20% ускорениями в тривиальных, крошечных, не относящихся к делу случаях, и вам лучше наслаждаться ими полностью - потому что однажды, когда вы этого не увидите Приближаясь, во время ВАЖНОЙ, БОЛЬШОЙ операции вы получите удар в живот от встречного грузовика с прицепом из-за замедления 200% (если только вам не повезет, а это 2000% ;-). Просто помните: если вы когда-нибудь почувствуете, что «Python ужасно медленный», ПОМНИТЕ, скорее всего, это один из ваших любимых циклов + = , который поворачивается и кусает руку, которая его кормит.

Для остальных из нас - тех, кто понимает, что значит сказать Мы должны забыть о небольшой эффективности, скажем, примерно в 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 символов в каждой, присоединение к списку напрямую, конечно, быстрее всего, но OP боится, что до этого придется делать добавления. Но:

$ 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

сокращает еще десятые доли миллисекунды за среднее время цикла. Все (по крайней мере, все, кто полностью одержим большой производительностью), очевидно, знают, что ПОДЪЕМ (вывод из внутреннего цикла повторяющихся вычислений, которые в противном случае выполнялись бы снова и снова) является важным методом оптимизации - Python не поднимает от вашего имени , поэтому в тех редких случаях, когда важна каждая микросекунда, вам придется выполнять подъем самостоятельно.

$ 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

сокращает еще десятые доли миллисекунды за среднее время цикла. Все (по крайней мере, все, кто полностью одержим большой производительностью), очевидно, знают, что ПОДЪЕМ (вывод из внутреннего цикла повторяющихся вычислений, которые в противном случае выполнялись бы снова и снова) является важным методом оптимизации - Python не поднимает от вашего имени , поэтому в тех редких случаях, когда важна каждая микросекунда, вам придется выполнять подъем самостоятельно.

$ 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

сокращает еще десятые доли миллисекунды за среднее время цикла. Все (по крайней мере, все, кто полностью одержим большой производительностью), очевидно, знают, что ПОДЪЕМ (вывод из внутреннего цикла повторяющихся вычислений, которые в противном случае выполнялись бы снова и снова) является важным методом оптимизации - Python не поднимает от вашего имени , поэтому в тех редких случаях, когда важна каждая микросекунда, вам придется выполнять подъем самостоятельно.