Performance comparison of different string concatenation methods in Python

results.txt

Results: 5 for tree height, 40 for max branching (seems reasonable for current db)

Naive execution 5.043222
Mutable_string execution 38.200823
Char_array execution 7.517328
List execution 5.424522
Stringio execution 7.733451
List_comprehension execution 6.065958

Naive execution 7.540310
Mutable_string execution 55.285637
Char_array execution 11.127192
List execution 8.018250
Stringio execution 11.883038
List_comprehension execution 9.155894

Naive execution 5.394257
Mutable_string execution 40.364614
Char_array execution 7.945603
List execution 5.843919
Stringio execution 8.500603
List_comprehension execution 6.705491

test_concat.py

from UserString import MutableString
from array import array
from cStringIO import StringIO
import string
from random import (choice, random, randint)
from timeit import Timer


class Node():

    def __init__(self, name):
        self._name = name
        self._children = []

    def has_children(self):
        return self._children is not []

    def get_children(self):
        return self._children

    def get_name(self):
        return self._name

    def add_child(self, child):
        self._children.append(child)

    def has_protection(self):
        return random() < 0.5

    def __repr__(self):
        return self._name


def generate_name(size=6, chars=string.ascii_letters):
    return ''.join(choice(chars) for x in range(size))

def generate_data(lvl, size):
    root = Node(generate_name(randint(20, 50)))
    if lvl > 0:
        for _ in xrange(size):
            if random() < 0.8:
                root.add_child(generate_data(lvl-1, randint(0, size)))
    return root

def test_naive(node):
    buf = ''
    if len(node.get_children()) > 0:
        buf += "<ul>"
        for snode in node.get_children():
            buf += "<li><a href='%s'>%s</a>" % (snode.get_name()*2, snode.get_name())
            if snode.has_protection():
                buf += """&nbsp;<span style="font-size: 0.8em; color: gray;">(%s)</span>"""% "protected"
            buf += test_naive(snode)
        buf += "</ul>"
    return buf

def test_mutable_string(node):
    buf = MutableString()
    if len(node.get_children()) > 0:
        buf += "<ul>"
        for snode in node.get_children():
            buf += "<li><a href='%s'>%s</a>" % (snode.get_name()*2, snode.get_name())
            if snode.has_protection():
                buf += """&nbsp;<span style="font-size: 0.8em; color: gray;">(%s)</span>"""% "protected"
            buf += test_mutable_string(snode)
        buf += "</ul>"
    return buf

def test_char_array(node):
    buf = array('c')
    if len(node.get_children()) > 0:
        buf.fromstring("<ul>")
        for snode in node.get_children():
            buf.fromstring("<li><a href='%s'>%s</a>" % (snode.get_name()*2, snode.get_name()))
            if snode.has_protection():
                buf.fromstring("""&nbsp;<span style="font-size: 0.8em; color: gray;">(%s)</span>"""% "protected")
            buf.fromstring(test_char_array(snode))
        buf.fromstring("</ul>")
    return buf.tostring()

def test_list(node):
    buf = []
    if len(node.get_children()) > 0:
        buf.append("<ul>")
        for snode in node.get_children():
            buf.append("<li><a href='%s'>%s</a>"% (snode.get_name()*2, snode.get_name()))
            if snode.has_protection():
                buf.append("""&nbsp;<span style="font-size: 0.8em; color: gray;">(%s)</span>""" % "protected")
            buf.append(test_list(snode))
        buf.append("</ul>")
    return "".join(buf)

def test_stringio(node):
    buf = StringIO()
    if len(node.get_children()) > 0:
        buf.write("<ul>")
        for snode in node.get_children():
            buf.write("<li><a href='%s'>%s</a>" % (snode.get_name()*2, snode.get_name()))
            if snode.has_protection():
                buf.write("""&nbsp;<span style="font-size: 0.8em; color: gray;">(%s)</span>"""% "protected")
            buf.write(test_stringio(snode))
        buf.write("</ul>")
    return buf.getvalue()

def test_list_comprehension(node):
    buf = ["<li><a href='%s'>%s</a>%s%s" % (snode.get_name()*2, snode.get_name(),
          ("", """&nbsp;<span style="font-size: 0.8em; color: gray;">(%s)</span>"""
          % "protected")[node.has_protection()], test_list_comprehension(snode))
          for snode in node.get_children()]
    if buf:
        buf = ["<ul>"] + buf + ["</ul>"]
    return "".join(buf)

def print_node(node, prefix='  '):
    print "%s%s" % (prefix, node.get_name())
    for child in node.get_children():
        print_node(child, prefix + '  ')

if __name__ == '__main__':
    for _ in xrange(3):
        root = generate_data(5, 40)
        # print_node(root, '')
        for method in ['naive', 'mutable_string', 'char_array', 'list', 'stringio', 'list_comprehension']:
            print "%s execution %f" % (method.capitalize(), Timer(lambda: eval('test_' + method + '(root)')).timeit(3))
        print