python - 是否可以使用类似缓冲区(基于指针)的字符串比较在 python 3 中进行排序？

Question

考虑对字符串的所有后缀进行排序的问题，其中后缀是从某个索引 i 到字符串末尾的子字符串。我们可以创建与排序后缀的起点对应的索引列表，而不是创建已排序后缀的列表。然后我们可以这样做:

text = ... some text string ...
sortedIndices = sorted([i for i in range(len(text))], 
                       key = lambda i: text[i:])  

这适用于短字符串，但如果字符串足够长，我们将耗尽内存，因为键函数会生成后缀的副本，并且所有键都是在开始时生成的。在 python 2.7 中有一个巧妙的方法来解决这个问题，即 buffer() 函数:

sortedIndices = sorted([i for i in range(len(text))], 
                       key = lambda i: buffer(text, i))  

在这种情况下，键只是指向文本字符串的指针，因此所需的总内存要少得多(O(n) vs O(n*n))。因此，它将适用于更长的字符串。这在 2.7 中工作得很好，但在 3.x 中，buffer() 函数已被删除以支持 memoryview，这与 buffer 不同——据我所知——不支持基于指针的字符串比较(即，不使用 tobytes 方法，这会创建字符串的副本)。我的问题是:有没有办法在 python 3.x 中做类似的事情？

Answer 1

在我看来，memoryview 不会那样做。这实际上可能是一件好事。

你仍然可以用一个类来做到这一点，无论如何它更面向对象:

#!/usr/local/cpython-3.3/bin/python

import sys
import functools

@functools.total_ordering
class Suffix_comparison:
    def __init__(self, string, starting_position):
        self.string = string
        self.starting_position = starting_position

    def __lt__(self, other):
        if self.string[self.starting_position:] < other.string[other.starting_position]:
            return True
        else:
            return False

    def __eq__(self, other):
        if self.string[self.starting_position:] == other.string[other.starting_position]:
            return True
        else:
            return False

    def __str__(self):
        return self.string

    __repr__ = __str__

def main():
    list_ = []
    for line in sys.stdin:
        stripped_line = line.rstrip('\n')
        list_.append(Suffix_comparison(stripped_line, 5))

    list_.sort()

    for line in list_:
        print(line)

main()