@ gnosis, остерегайтесь всех благонамеренных респондентов, говорящих, что вы должны измерить время: да, вы должны (потому что инстинкты программистов часто не основаны на производительности), , но измеряют один случай как и во всех приведенных выше timeit примерах, пропущен важный момент: big-O .
Ваши инстинкты верны: в общем (с очень немногими особыми случаями, когда недавние выпуски Python могут немного оптимизировать вещи, но они не слишком сильно растягиваются), создавая строку с помощью цикла += над частями (или reduce и т. Д.) Должно быть O(N**2) из-за большого количества промежуточных распределений объектов и неизбежного повторного копирования содержимого этого объекта; объединение, регулярные выражения и третий вариант, который не был упомянут в вышеприведенных ответах (write метод cStringIO.StringIO экземпляров), являются решениями O(N) и, следовательно, единственными, которые стоит рассмотреть, если только вы не знаете точно, что строки, с которыми вы будете работать, имеют скромные верхние границы своей длины.
Так, каковы, если таковые имеются, верхние границы длины строк, которые вы обрабатываете? Если вы можете дать нам идею, тесты могут быть выполнены на репрезентативных диапазонах интересующих длин (например, скажем, «чаще всего менее 100 символов, но в некоторых% случаев может быть пара тысяч символов») было бы отличной спецификацией для этой оценки производительности: IOW, она не должна быть очень точной, просто указывающей на ваше проблемное пространство).
Я также замечаю, что никто не следит за одним критическим и трудным моментом в ваших спецификациях: строки представляют собой многобайтовые символы Python 2.5, кодируются в кодировке UTF-8, str с, и вставки должны выполняться только после каждого "завершенного символа" не после каждого байта . Кажется, что все "зацикливаются на строке", которые дают каждый байт, а не каждый символ , как вы четко указали.
На самом деле нет хорошего, быстрого способа "перебрать символы" в многобайтовом кодированном байте str; лучшее, что можно сделать, - это .decode('utf-8'), предоставляющий объект Unicode - обработать объект Unicode (где циклы do правильно перебирают символы!), затем .encode его обратно в конце. Безусловно, лучший подход в общем случае состоит в том, чтобы использовать исключительно юникодные объекты, , а не , закодированные str s, по всему сердцу вашего кода; кодировать и декодировать в / из байтовых строк только при вводе / выводе (если и когда это необходимо, потому что вам нужно взаимодействовать с подсистемами, которые поддерживают только байтовые строки и не используют надлежащий Unicode).
Поэтому я настоятельно рекомендую вам рассмотреть этот «наилучший подход» и соответствующим образом реструктурировать свой код: юникод везде, кроме тех границ, где он может быть закодирован / декодирован только в случае необходимости. Что касается «обработки», вы будете НАМНОГО счастливее с объектами Unicode, чем та, что тащили бы за блокированные многобайтовые строки! -)
Редактировать : забыл прокомментировать возможный подход, о котором вы упомянули - array.array. Это действительно O (N) , если , вы только добавляете к концу нового массива, который вы строите (некоторые добавления приведут к росту массива сверх ранее выделенной емкости и, следовательно, требуют перераспределение и копирование данных, , но , как и для списка, стратегия средне экспоненциального перераспределения позволяет append быть амортизированным O (1), и, следовательно, N добавляется к O ( N)).
Однако, чтобы построить массив (опять же, как список) с помощью повторяющихся insert операций в середине его, это O(N**2), потому что каждая из вставок O (N) должна сдвигать все O (N) следующие элементы (при условии, что количество ранее существующих элементов и количество вновь вставленных элементов пропорционально друг другу, что, как представляется, соответствует вашим конкретным требованиям).
Итак, array.array('u'), с повторяющимися append с ( не insert с! -), является четвертым O (N) подходом, который может решить вашу проблему (в дополнение к трем, которые я уже упомянул: join, re и cStringIO) - эти - те, которые стоит сравнить, когда вы уточните диапазоны длин, которые представляют интерес, как я упоминал выше .