I was trying to implement the Burrows-Wheeler transform in Python. (This is one of the assignments in an online course, but I hope I have done some work to be qualified to ask for help.) The algorithm works as follows. Take a string which ends with a special character ($ in my case) and create all cyclic strings from this string. Sort all these strings alphabetically, having a special character always less then any other character. After this, get the last element of each string. This gave me a one-liner: ''.join([i[-1] for i in sorted([text[i:] + text[0:i] for i in xrange(len(text))])] Which is correct and reasonably fast for reasonably big strings (which is enough to solve the problem): 60 000 chars - 16 secs 40 000 chars - 07 secs 25 000 chars - 02 secs But when I tried to process a really huge string with few millions of characters, I failed (it takes too much time to process). I assume that the problem is with storing too many strings in the memory. Is there a way to overcome this? P.S.: I just want to point out that also this might look like a homework problem. My solution already passes the grader and I am just looking for a way to make it faster. Also, I am not spoiling the fun for other people, because if they would like to find a solution, the Wikipedia article has one which is similar to mine. I also checked this question which sounds similar, but answers a harder question, how to decode the string coded with this algorithm. Continue reading...
