如何改进python后缀数组中的lambda表达式

Question

有一个代码使用lambda表达式

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$")

它正确输出所需的数组

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 

我怎么能提高线路

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

所以当增加文本长度时,我不会在lambda表达式上使用大量内存？

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

还有其他代码,如:

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

然而,记忆如此之多,

我还尝试使用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 

虽然它解决了这个问题,但是使用较大的字符串需要花费太多时间,...你知道其他库或改进后缀的方法吗？

Answer 1

看起来你正在尝试构建一个后缀数组.幸运的是,这个算法已经有Python实现:https://code.google.com/p/pysuffix/

如果您必须自己实现它,请考虑您的代码正在做什么:

1. 创建与文本长度相同的整数列表range.
2. 将key函数应用于列表的每个元素,并将结果存储在新列表中.
3. 对新列表进行排序
4. 返回与新列表的每个元素关联的原始整数.

(这也被称为Schwartzian变换,这是一个非常巧妙的想法.)

关键是,您正在为文本中的每个偏移量创建一个(可能是大的)文本片段,并将其存储在新列表中.您将需要使用更专业的后缀数组构造算法来避免此成本.

最后,为了解决你原来的问题:lambda表达式不是罪魁祸首.你只是碰上算法墙.

编辑

这是快速SA算法的一个很好的资源: 当前最先进的后缀数组构造算法是什么？

Answer 2

我怎么能改进行......所以当增加文本长度时我不会在lambda表达式上使用大量内存？

lambda表达式创建了一个简单的函数.最有可能的该功能的字节码大约是8字节,而成本code和function那得到缠着对象是根据您的平台也许80-128字节.一次只存在一个这样的函数,因此模块中的总内存开销为8个字节,而此函数运行时则为128个字节.

所以......什么都不做.

为了减少内存使用,你必须找到实际的代码的一部分是使用大量的内存,并减少.特别是,您最有可能创建一个N个数字列表(带range),然后是另一个N个数字列表(带有sorted).您还可以瞬时创建N个N/2长度的字符串,如果您使比较更加微妙,则不需要这些字符串.等等.不要那样做.

• 使用an xrange替换第一个列表.
• 重写您的算法,因此它不需要构建整个排序列表,而是首先逐个生成元素.
• 如果那是不可能的,考虑使用一个array.array或一个NumPy ndarray,这将至少消除每个数字的24-48字节的"装箱"开销.
• 您可以编写一个更聪明的键函数,它不需要在其结果对象中实际保留后缀; 相反,它保持i和text,并具有自定义比较运算符,text[i:]根据需要引用.然后在最坏的情况下,这些后缀中的两个将同时存在.
• 如果你逐个生成这些值,你就无法使用str.join(因为它会在你背后创建一个列表),所以你需要一个不同的选择,比如把它们写成一个StringIO.或者,在你的情况下,因为你实际上没有返回任何东西,只需将它转储到stdout,只需将print它们逐个循环.