python - 有效地从字符串末尾弹出子字符串

Question

假设我有一个长度为 n 的 big_string，并且我想从其末尾删除长度为 k 的子字符串

我们可以用big_string[:-k]来实现，但这将是O(n-k)，我们可以做得比这更好吗，比如O(k)？

Answer 1

如果你的字符串是 py2 unicode 或 py3 str，@MyNameIsCaleb 指向的 memoryview 想法将不起作用，而切片将起作用确实进行复制，时间复杂度为 O(n)。

对于可变类型(del m[-k:])，修剪末尾很快，但只有字符串类型(不可变)支持诸如 find() 之类的字符串操作>、in 和正则表达式。

如果修剪结尾是一个非常频繁的操作，并且很少使用字符串操作或者只能限制到字符串的一小部分，那么将字符串一次转换为字符列表可能是值得的:

chars = [c 代表 big_string 中的 c]

要对有界部分使用字符串操作，您可以将切片转换为字符串。例如，要确定“foo”是否出现在最后 1000 个字符中:

''.join(chars[-1000:]) 中的'foo'