Increase efficiency of basic string compressor I was wondering what I can do to increase the performance of this program. The algorithm is pretty slow right now but I was wondering what I can do to increase the efficiency of this program.  I used lists instead of strings to avoid immutable string concatenation.

This program should compress strings by the number of characters within the string

Example:

aaabbbcc --&gt; a3b3c2


Code:

def compressBad(string):
    string = list(string)
    mystr = []
    last = string[0]
    count = 1
    for x in xrange(1,len(string)):
        if string[x] == last:
            count += 1
        else:
            mystr.append(last)
            mystr.append(str(count))
            last = string[x]
            count = 1
    # add the last character
    mystr.append(last)
    mystr.append(str(count))
    return ''.join(mystr)

print compressBad("abaabccc")


output:

a1b1a2b1c3
The following code performs twice as fast as your code does on my machine, both for short strings (e.g. your example) and longer strings.

def compressBetter(string):
    last = string[0]
    result = []
    count = 1
    for c in string[1:]:
        if c == last:
            count += 1
        else:
            result.append(last + `count`)
            count = 1
            last = c

    result.append(last + `count`)
    return ''.join(result)


The main two optimisations are


Using backticks instead of str() for int to str conversion (note that backticks are deprecated and have been removed in Python 3). Some discussion of why they are faster is given here.
Iterating over the string directly rather than indexing. I'm guessing this saves function calls, which have quite a lot of overhead in python.


I find that each optimisation accounts for about half of the performance increase. I am using cPython - the results would probably be very different if you used a different interpreter.