python-3.x - 什么是 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

What is Python 3 str.__getitem__ computional complexity?

一个:O(1)

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

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

这是 Python 3.3 之后的新功能(在此之前，所有内部字符串表示都默认为 32 位 UCS-4，即使对于纯 ASCII 文本也是如此)。该规范记录在 PEP-393 上.

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

作为轶事，Luciano Ramalho(《流利的 Python》一书的作者)编写了 Leanstr，这是一个以学习为目的的字符串类实现，它将在内部保存 utf-8。当然，您对 __getitem__ 复杂性的担忧适用:https://github.com/ramalho/leanstr

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

其他实现:Pypy

因此，碰巧内部如何使用文本是一个“实现细节”，而来自 version 7.1 的 Pypy onwards 确实在内部为其文本对象使用 utf-8 字节字符串。

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

我已经在推特上提到了这个问题，因为我是 Ramalho 的熟人，最终 Pypy 开发人员之一 Carl Friederich Bolz-Terich 回复了:

It's worked really quite well for us! Most Unicode strings don't need this index, and zero copy utf-8 decoding is quite cool. What's most annoying is actually str.find, because there you need the reverse conversion, from byte index to char index. we don't have an index for that.

Tweet