How to improve lambda expression in python suffix array

Question

There is a code that uses lambda expression

def ComputeArray(text):
    # text is ended with $
    if text[-1] != "$":
        text += "$"
    sarray  = sorted(range(len(text)), key = lambda i: text[i:])
    print ", ".join([str(x) for x in sarray])

if __name__ == "__main__":
    ComputeArray("AACGATAGCGGTAAACGATAGCGGTAGA$")

it correctly outputs desired array

28, 27, 12, 0, 13, 1, 14, 25, 6, 19, 4, 17, 2, 15, 8, 21, 26, 3, 16, 7, 20, 9, 22, 10, 23, 11, 24, 5, 18 

How could I improve line

sarray  = sorted(range(len(text)), key = lambda i: text[i:])

so when increasing length of text I do not use lots of memory on a lambda expression?

Traceback (most recent call last):
  File "C:\Array.py", line 23, in <module>
    ComputeArray(text)
  File "C:\Array.py", line 11, in ComputeArray
    sarray  = sorted(range(len(text)), key = lambda i: text[i:])
  File "C:\Array.py", line 11, in <lambda>
    sarray  = sorted(range(len(text)), key = lambda i: text[i:])
MemoryError

UPDATE

There is other code like:

sarray=[]
for i in range(len(text)):
  sarray.append(text[i:])
order=[i[0] for i in sorted(enumerate(sarray), key=lambda x:x[1])]
print ", ".join([str(x) for x in order])

However is taking so much memory,

Also I tried solution using library available on https://code.google.com/p/pysuffix/

s = 'AACGATAGCGGTAGA'
s = unicode(s,'utf-8','replace') 
n = len(s) 
sa = tks.simple_kark_sort(s) 
lcp = tks.LCP(s,sa) 
print n print sa 

although it solves the problem, it takes too much time with larger strings, ... do you know other library or a method to improve suffix?

Answer 1

Looks like you're trying to build a suffix array. Luckily, there are already Python implementations of this algorithm: https://code.google.com/p/pysuffix/

If you must implement it yourself, think about what your code is doing:

1. Make a list of integers the same length as your text with range.
2. Apply the key function to each element of the list and store the result in a new list.
3. Sort the new list
4. Return the original integer associated with each element of the new list.

(This is also known as the Schwartzian Transform, which a pretty neat idea.)

The point is, you're making a slice of your (presumably large) text for each offset in the text, and storing it in a new list. You'll want to use a more specialized suffix array construction algorithm to avoid this cost.

Finally, to address your original question: the lambda expression isn't the culprit here. You're simply running into an algorithmic wall.

EDIT

Here's a good resource for fast SA algorithms: What's the current state-of-the-art suffix array construction algorithm?

Answer 2

How could I improve line … so when increasing length of text I do not use lots of memory on a lambda expression?

That lambda expression creates a simple function. Most likely the bytecode for that function is around 8 bytes, and the cost of the code and function objects that get wrapped around it are maybe 80-128 bytes depending on your platform. Only one such function exists at a time, so your total memory cost is 8 bytes in the module, and another 128 bytes while this function runs.

So… do nothing.

To reduce memory usage, you have to find the part of your code that actually is using a lot of memory, and reduce that. In particular, it's most likely that you're creating an list of N numbers (with range), and then another list of N numbers (with sorted). You're also creating N strings of N/2 length transiently, which you don't need if you make your comparison a little more subtle. And so on. Don't do that.

• Using an xrange to replace the first list.
• Rewrite your algorithm so it doesn't need to build a whole sorted list, and instead generates the elements one by one in the first place.
• If that's not possible, consider using an array.array or a NumPy ndarray, which will at least eliminate the 24-48 bytes of "boxing" overhead for each number.
• You can write a cleverer key function that doesn't need to actually hold onto the suffix in its result object; instead, it holds onto i and to text, and has custom comparison operators that reference text[i:] as needed. Then at worst two of these suffixes will exist at the same time.
• If you're generating the values one by one, you can't use str.join (because it will create a list behind your back), so you will need a different alternative, like writing them to a StringIO. Or, in your case, since you're not actually returning anything, just dumping it to stdout, just print them one by one in a loop.