Наиболее эффективная буферизация строк

Question

Я выполнил требование в моем текущем проекте, что привело меня к необходимости метода буферизации для последовательности символов Юникода с минимальными временными затратами.Основные операции для такого буфера:

• Чтение его значения в виде строки Unicode
• Добавление символа к концу буфера
• Очистка буфера

Поэтому я протестировал несколько подходов, чтобы найти тот, у которого минимальные накладные расходы по времени, но я все еще не уверен, получил ли я самый быстрый.Я попробовал следующие алгоритмы (перечислены из наиболее эффективных):

1. A list символов
2. io.StringIO object
3. Хранение наивной строки
4. Предварительно выделено array.array

Может кто-нибудь дать мне подсказку о лучшем подходе к этому вызову?Интерпретатор проекта - CPython 2.7.MCVE для моего теста:

# -*- coding: utf-8 -*-

import timeit
import io
import array
import abc


class BaseBuffer:
    """A base abstract class for all buffers below"""
    __metaclass__ = abc.ABCMeta

    def __init__(self):
        pass

    def clear(self):
        old_val = self.value()
        self.__init__()
        return old_val

    @abc.abstractmethod
    def value(self):
        return self

    @abc.abstractmethod
    def write(self, symbol):
        pass


class ListBuffer(BaseBuffer):
    """Use lists as a storage"""
    def __init__(self):
        BaseBuffer.__init__(self)
        self.__io = []

    def value(self):
        return u"".join(self.__io)

    def write(self, symbol):
        self.__io.append(symbol)


class StringBuffer(BaseBuffer):
    """Simply append to the stored string. Obviously unefficient due to strings immutability"""
    def __init__(self):
        BaseBuffer.__init__(self)
        self.__io = u""

    def value(self):
        return self.__io

    def write(self, symbol):
        self.__io += symbol


class StringIoBuffer(BaseBuffer):
    """Use the io.StringIO object"""
    def __init__(self):
        BaseBuffer.__init__(self)
        self.__io = io.StringIO()

    def value(self):
        return self.__io.getvalue()

    def write(self, symbol):
        self.__io.write(symbol)


class ArrayBuffer(BaseBuffer):
    """Preallocate an array"""
    def __init__(self):
        BaseBuffer.__init__(self)
        self.__io = array.array("u", (u"\u0000" for _ in xrange(1000000)))
        self.__caret = 0

    def clear(self):
        val = self.value()
        self.__caret = 0
        return val

    def value(self):
        return u"".join(self.__io[n] for n in xrange(self.__caret))

    def write(self, symbol):
        self.__io[self.__caret] = symbol
        self.__caret += 1


def time_test():
    # Test distinct buffer data length
    for i in xrange(1000):
        for j in xrange(i):
            buffer_object.write(unicode(i % 10))
        buffer_object.clear()


if __name__ == '__main__':

    number_of_runs = 10
    for buffer_object in (ListBuffer(), StringIoBuffer(), StringBuffer(), ArrayBuffer()):
        print("Class {klass}: {elapsed:.2f}s per {number_of_runs} runs".format(
            klass=buffer_object.__class__.__name__,
            elapsed=timeit.timeit(stmt=time_test, number=number_of_runs),
            number_of_runs=number_of_runs,
        ))

... и результаты, которые я получил за этот прогон:

Class ListBuffer: 1.88s per 10 runs
Class StringIoBuffer: 2.04s per 10 runs
Class StringBuffer: 2.40s per 10 runs
Class ArrayBuffer: 3.10s per 10 runs

Answer 1

Я попробовал пару альтернатив (см. Ниже), но я не смог превзойти реализацию ListBuffer.Вот что я пробовал:

Массив без предварительного выделения

class ArrayBufferNoPreallocate(BaseBuffer):
    """array buffer"""
    def __init__(self):
        BaseBuffer.__init__(self)
        self.__io = array.array("u")

    def value(self):
        return self.__io.tounicode()

    def write(self, symbol):
        self.__io.append(symbol)

Numpy

class NumpyBuffer(BaseBuffer):
    """numpy array with pre-allocation"""
    def __init__(self):
        BaseBuffer.__init__(self)
        self.__io = np.zeros((1000000,), dtype=np.unicode_)
        self.__cursor = 0

    def clear(self):
        val = self.value()
        self.__cursor = 0
        return val

    def value(self):
        return np.char.join(u"", (self.__io[i] for i in xrange(self.__cursor)))

    def write(self, symbol):
        self.__io[self.__cursor] = symbol
        self.__cursor += 1

Результаты

Class ListBuffer: 3.40s per 10 runs
Class StringIoBuffer: 4.44s per 10 runs
Class StringBuffer: 4.58s per 10 runs
Class ArrayBuffer: 4.65s per 10 runs
Class ArrayBufferNoPreallocate: 3.94s per 10 runs
Class NumpyBuffer: 5.73s per 10 runs

Если вы действительноЕсли вы хотите существенно повысить скорость, вам может потребоваться написать расширение c или использовать что-то вроде cython .

Если вы можете оптимизировать свою проблему так, чтобы она не требовалавызов функции для каждого персонажа, вы также можете получить некоторую производительность.