删除 Python 字符串中的第一个字符的时间复杂度是多少？

Question

我有以下代码：

>>> s = "Whosebug"
>>> tmp = s[0]
>>> s = s[1:]
>>> s
'tackoverflow'

我正在重复执行这种“首先删除”的操作，并试图确定它如何影响性能。

单个切片操作是否像上面显示的那样 O(1)？如果不是 O(1)，有没有办法可以执行复杂度为 O(1) 的操作？

Answer 1

Python 的 str() 在 O(n) 时间内对 s[1:] 进行切片，因为 str() 是不可变的，任何切片操作都会创建全新的字符串并复制所有切片数据，所以对于长度为 N 的字符串，此操作为 O(N)。

要在 O(1) 时间内进行任何切片，您需要使用特殊的实现，例如 Numpy 的数组。 Numpy 数组保留指向已分配数组的指针以及三个额外字段 begin、end、stride.

在对具有 N 个元素的 Numpy 数组进行切片之前，将从 begin=0，end=N 开始。切片后，例如a[1:]，与 str() 不同，Numpy 数组不复制任何内存，而只是更改 begin/end/stride。内存指针和大小保持不变。因此在 a[1:] 之后我们将有 begin=1, end=N。再一个 a[1:] 之后，我们将有 begin=2, end=N.

对于字符串，您可以在程序开始时将它们一次转换为 uint32 元素的 Numpy 数组（因为 Unicode 代码点目前是 32 位）。然后只在 Numpy 数组中执行程序中的所有操作。 Numpy 还为其数组实现了许多 string operations。

您可以非常快速地进行切片和许多其他操作，比使用 Python 的 str() 快得多。并且所有切片操作都在 O(1) 时间内完成。完成 Numpy 操作后，您将转换回 Python 的 str()。

接下来是代码示例。它首先将 Python str() 转换为 numpy 数组。然后执行任何操作，包括切片（切片在 numpy 数组上以 O(1) 时间完成）。当我们完成后，numpy 数组被转换回 Python 的 str().

Try it online!

import numpy as np
s = 'abcde'
# Convert string to Numpy array
a = np.frombuffer(s.encode('utf-32-le'), dtype = np.uint32)
# Do any slicing operations in O(1) time
a = a[1:]
a = a[1:]
# Convert Numpy array to string
s = a.tobytes().decode('utf-32-le')
print(s)

输出：

cde

删除 Python 字符串中的第一个字符的时间复杂度是多少？

What is the time complexity of removing the first character in a Python string?

python

string

time-complexity