Python 3 `str.__getitem__` 计算复杂度是多少？

Question

''' Set up '''
s= open("Bilion_of_UTF-8_chars.txt",encoding="UTF-8").read()

'''
The following doesn't look like a cheap operation
because Python3 `str`-s are UTF-8 encoded (EDIT: in some implementations only).
'''
my_char= s[453_452_345]

然而，很多人这样写循环：

for i in range(len(s)):
    do_something_with(s[i])

使用索引操作最多n次或更多。

Python3 如何解决这两个代码片段在字符串中索引 UTF-8 字符的问题？

• 它是否总是对第 n 个字符执行线性查找（这既简单又昂贵的解决方案）？
• 或者它可能存储一些额外的 C 指针来执行智能索引计算？

Answer 1

Python 3 的计算复杂度是多少str.__getitem__？

答：O(1)

Python 字符串内部不是 utf-8：在 Python 3 中，当从任何外部源获取文本时，文本会根据给定的编解码器进行解码。在大多数源/平台中，此文本解码默认为 utf-8，但会根据 SO 的默认值而变化 - 无论如何，所有相关的“文本导入”API（例如打开文件或连接到数据库）都允许您指定文本编码使用。

内部字符串根据文本字符串中“最宽”代码点的需要使用“Latin-1”、“UCS-2”或“UCS-4”之一。

这是从 Python 3.3 开始的新功能（在此之前，所有内部字符串表示形式都默认为 32 位 UCS-4，即使对于纯 ASCII 文本也是如此）。该规范记录在PEP-393中。

因此，Python 可以在给定索引的情况下将正确的字符归零。

作为一个轶事，Luciano Ramalho（Fluent Python 一书的作者）编写了Leanstr一个用于学习目的的字符串类实现，该字符串类将在内部保存 utf-8。当然，那么您对__getitem__复杂性的担忧也适用：https://github.com/ramalho/leanstr

不幸的是（或者幸运的是，在这种情况下），Python 的许多标准库和本机代码扩展都不会接受类似于 的类str，即使它继承str并单独保留其数据，重新实现所有 dunder 方法。但是，如果所有 str 方法都已到位，则任何处理字符串的纯 python 代码都应该接受一个LeanStr实例。

其他实现：Pypy

因此，内部如何使用文本是一个“实现细节”，并且从版本 7.1开始，Pypy 确实在内部使用 utf-8 字节字符串作为其文本对象。

然而，与上面 Ramalho 的天真“leanstr”不同，他们确实为每个 4 个 utf-8 字符保留一个索引，以便仍然可以在 O(1) 内进行按索引的字符访问。我没有找到任何有关它的文档，但创建索引的代码在这里。

我在推特上提到过这个问题，因为我是 Ramalho 的无罪释放者，最终 Pypy 开发者之一 Carl Friederich Bolz-Terich 回复了我：

这对我们来说真的非常有效！大多数 Unicode 字符串不需要这个索引，零拷贝 utf-8 解码非常酷。最烦人的实际上是 str.find，因为在那里你需要反向转换，从字节索引到字符索引。我们没有这方面的索引。

鸣叫