Скорость конкатенации строки Python

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

import cProfile count = 20000000 def profileWrapper(f): def wrapper(*args, **argv): pr = cProfile.Profile() pr.enable() string = f(*args, **argv) pr.create_stats() pr.print_stats() return string return wrapper @profileWrapper def naiveConcat(): global count string = '' for i in xrange(count): string += `i` return string @profileWrapper def improvedConcat(): global count string = [] for i in xrange(count): string.append(`i`) return ''.join(string) @profileWrapper def fastestConcat(): global count return ''.join([`i` for i in xrange(count)]) print 15 * "=", "naiveConcat", 15 * "=" naiveConcat() print 15 * "=", "improvedConcat", 15 * "=" improvedConcat() print 15 * "=", "fastestConcat", 15 * "=" fastestConcat() 

Я ожидаю, что улучшенный метод будет быстрее, чем наивный, и он не должен «быть намного медленнее, чем самый быстрый метод, но результат не выглядит так:

 =============== naiveConcat =============== 3 function calls in 3.951 seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 0.000 0.000 cProfile.py:90(create_stats) 1 3.951 3.951 3.951 3.951 str_concat.py:18(naiveConcat) 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} =============== improvedConcat =============== 20000004 function calls in 6.990 seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 0.000 0.000 cProfile.py:90(create_stats) 1 5.196 5.196 6.990 6.990 str_concat.py:26(improvedConcat) 20000000 1.322 0.000 1.322 0.000 {method 'append' of 'list' objects} 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 1 0.473 0.473 0.473 0.473 {method 'join' of 'str' objects} =============== fastestConcat =============== 4 function calls in 3.043 seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function) 1 0.000 0.000 0.000 0.000 cProfile.py:90(create_stats) 1 2.539 2.539 3.043 3.043 str_concat.py:34(fastestConcat) 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 1 0.504 0.504 0.504 0.504 {method 'join' of 'str' objects} 

Улучшенный метод оказался намного медленнее, чем наивный метод!

Это не имеет смысла, поскольку наивный метод создает новую привязку и копирует предыдущую строку вместе с символом конкатенированной строки символом ON EACH ITERATION, этот метод должен принимать O (n ^ 2), который должен быть намного медленнее, чем другой методы, которые представляют собой O (n).

Итак, что делает улучшенный метод настолько медленным? Единственная причина, по которой я могу думать, это метод append, но в соответствии с этой статьей метод append принимает O (1), поэтому это определенно не причина. Тогда что занимает так много времени в улучшенииConcat ()? Спасибо.

Столбец ncalls улучшенногоConcat показывает, что вы сделали 20000004 вызовов функций, по сравнению с несколькими другими для других алгоритмов. Вызов функций не слишком дешев в Python, поэтому старайтесь держать их ограниченными. Чтобы продемонстрировать, я сделал новый тест после вашего шаблона nop, который просто вызывает пустое определение функции:

 def foo(): pass @profileWrapper def nop(): for i in xrange(count): foo() return '' 

Я получаю аналогичные результаты синхронизации к вашему другому тесту, и этот результат NOP (без операции) приводит к

 =============== nop =============== 20000003 function calls in 4.386 seconds 

Таким образом, у вас есть 4,4 накладных вызова функций.