Increase efficiency of basic string compressor

Question

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 --> 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

Answer 1

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

1. 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.

2. 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.

Answer 2

Bugs:

• This currently crashes when the string is empty. It should either check for that, or (better) avoid treating the first character specially.
• When there's a run of more than 9 characters, the output is ill-formed: rleCompress('aaaaaaaaaa') ⇒ 'a10'. You could avoid this by limiting runs to length 9, giving 'a9a1' instead.

Simplifications and optimizations:

• There's no need to convert the string to a list. You can subscript strings too.
• The only thing you do with x is string[x], so the loop can be simplified to for c in string[1:]:, or just for c in string: if you don't treat the first character specially.
• It might be faster to collect the output in a buffer rather than a list of strings, but Python doesn't have a good way to do this. You could try StringIO, but probably isn't significantly faster.

Names:

• This compression scheme is called run-length encoding, so the function's name should indicate that: rleCompress? compressRuns?
• mystr is the compressed result, so it should be called something like compressed.

You should probably write rleDecompress too, so you can use them to test each other:

assert rleDecompress(rleCompress(x)) == x