考虑对字符串的所有后缀进行排序的问题,其中后缀是从某个索引 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 中做类似的事情?
最佳答案
在我看来,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()
关于python - 是否可以使用类似缓冲区(基于指针)的字符串比较在 python 3 中进行排序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21272734/