Btukfyl

I met a requirement in my current project, which led me to the necessity of a buffering method for a unicode symbols sequence with minimal time cost.
Basic operations for such buffer are:

• Reading its value as a unicode string


• Appending a symbol to the tail of the buffer


• Flushing the buffer

Therefore, I tested a few approaches to find the one with the minimal timing overhead, but I'm still not sure if I got the fastest one. I tried the following algorithms (listed from the most efficient):

1. A list of symbols


2. 
   io.StringIO object


3. Naive string storing


4. Preallocated array.array
   

Can anyone give me a hint on a better approach for this challenge?
The project interpreter is CPython 2.7. The MCVE for my test is:

# -*- 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,

        ))

... and the results I've got for this run are:

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

I tried a couple of alternatives (see below), but I wasn't able to outperform the ListBuffer implementation. Things I've tried:

Non-pre-allocated array

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

Results

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

If you really want substantial speed improvements, you might have to write a c extension or use something like cython.

If you can optimize your problem so that it doesn't require a function call for each character, you could gain some performance as well.