Python 中循环字符串切片时的空间复杂度

问题描述 投票:0回答:1

通常在 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 string loops big-o space-complexity
1个回答
0
投票

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 个字符,然后才能产生任何输出。

© www.soinside.com 2019 - 2024. All rights reserved.