通常在 Python 中创建字符串切片时,需要 O(n) 空间:
s = "hello world"
s[1:] # O(n)
当您循环遍历字符串切片时,它也需要 O(n) 空间是有意义的:
s = "hello_world"
for c in s[1:]: # O(n)?
...
但是我们可以通过索引实现相同的循环,由于我们使用范围,因此应该占用 O(1) 空间:
s = "hello_world"
for i in range(1, len(s)): # O(1)
...
如果这一切都是真的,那么循环遍历字符串切片总是会恶化索引的空间复杂度。
如果我们因此而不能使用像
for c in s[1:]:
这样的好语法,那就太糟糕了。
我的感觉是解释器只是以相同的方式处理这两种情况,并且由于它是一个 for 循环,因此 s[1:] 不一定返回字符串,而是返回迭代器。然而,我根本没有这方面的具体证据。
循环字符串切片的空间复杂度是多少?
理想情况下,我希望直接从文档中获得解释,但我还没有找到任何明确的解释。
我不知道如何跟踪 python 脚本中使用的内存/空间量,所以我不确定如何在现实世界中测试它。
Python 不会检查切片操作的上下文来对其进行优化。无论您循环结果、将其存储在变量中、将其传递给函数,甚至只是丢弃输出,切片检索都将执行相同的操作。
for c in s[1:]
具有 O(n) 空间复杂度。
对于跳过字符串第一项的特定情况,您可以执行类似的操作
it = iter(s)
next(it)
for c in it:
...
它检索迭代器并显式跳过第一个元素,或者
import itertools
for c in itertools.islice(s, 1):
...
它使用 itertools 做几乎相同的事情。
请注意,
itertools.islice
不是是生成任意序列的任意基于迭代器的切片的有效方法。它通过迭代器协议而不是通过索引进行操作,因此它无法有效地跳转到您传递给它的序列的任意索引。如果您尝试使用 s[1000000:]
复制 itertools.islice
,它将必须迭代 s
的前 1000000 个字符,然后才能产生任何输出。