strcmp for python或如何在构建后缀数组时有效地对子字符串进行排序(无需复制)

Question

这是从python中的字符串构建后缀数组的一种非常简单的方法:

def sort_offsets(a, b):
    return cmp(content[a:], content[b:])

content = "foobar baz foo"
suffix_array.sort(cmp=sort_offsets)
print suffix_array
[6, 10, 4, 8, 3, 7, 11, 0, 13, 2, 12, 1, 5, 9]

但是,"content [a:]"会制作内容的副本,当内容变大时,内容会变得非常低效.所以我想知道是否有办法比较两个子串而不必复制它们.我试过使用buffer-builtin,但它没有用.

Answer 1

该缓冲功能不会复制整个字符串,而是创建一个对象,只有引用源字符串.使用interjay的建议,那将是:

suffix_array.sort(key=lambda a: buffer(content, a))

Answer 2

我不知道是否有一种比较子串的快速方法,但您可以通过使用key而不是cmp:使代码更快(更简单):

suffix_array.sort(key=lambda a: content[a:])

这将为a的每个值创建一次子字符串.

编辑:可能的缺点是它需要O(n ^ 2)内存用于子字符串.