什么是 Python 3 `str.__getitem__` 计算复杂度？
What is Python 3 `str.__getitem__` computional complexity?
''' 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(s.len()):
do_something_with(s[i])
使用索引操作最多n次或更多次。
Python3如何解决两个代码片段的字符串中的 UTF-8 字符索引问题？
- 它是否总是对第 n 个字符执行线性查找（这是既简单又昂贵的解决方案）？
- 或者它存储了一些额外的 C 指针来执行智能索引计算？
What is Python 3 str.__getitem__ computional complexity?
答：O(1)
Python 字符串在内部不是 utf-8：在 Python 3 中，当从任何外部源获取文本时，文本会根据给定的编解码器进行解码。此文本解码在大多数 sources/platforms 中默认为 utf-8，但根据 S.O 的默认值有所不同 - 无论如何，所有相关的“文本导入”API，如打开文件或连接到DB，允许您指定要使用的文本编码。
内部字符串根据文本字符串中“最宽”代码点的需要使用“Latin-1”、“UCS-2”或“UCS-4”之一。
这是 Python 3.3 之后的新功能（在此之前，所有内部字符串表示都默认为 32 位 UCS-4，即使是 ASCII-only 文本）。该规范记录在 PEP-393.
因此，Python 只能 zero-in 给定索引的正确字符。
作为轶事，Luciano Ramalho（Fluent Python 一书的作者）写了 Leanstr，一个 learning-purpose 字符串 class 的实现，它将包含 utf- 8 内部。当然，那么您对 __getitem__ 复杂性的担忧适用：https://github.com/ramalho/leanstr
不幸的是，（或者幸运的是，在这种情况下），Python 的许多标准库和本机代码扩展不会接受类似于 str 的 class，甚至如果它继承自 str 并单独保留其数据，则 re-implementing 所有 dunder 方法。但是，如果所有 str 方法都已到位，任何处理字符串的 pure-python 代码都应该接受一个 LeanStr 实例。
其他实现：Pypy
因此，文本在内部的使用方式恰好是一个“实现细节”，并且从 version 7.1 开始的 Pypy 确实在其文本对象内部使用 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.
''' 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(s.len()):
do_something_with(s[i])
使用索引操作最多n次或更多次。
Python3如何解决两个代码片段的字符串中的 UTF-8 字符索引问题？
- 它是否总是对第 n 个字符执行线性查找（这是既简单又昂贵的解决方案）？
- 或者它存储了一些额外的 C 指针来执行智能索引计算？
What is Python 3
str.__getitem__computional complexity?
答：O(1)
Python 字符串在内部不是 utf-8：在 Python 3 中，当从任何外部源获取文本时，文本会根据给定的编解码器进行解码。此文本解码在大多数 sources/platforms 中默认为 utf-8，但根据 S.O 的默认值有所不同 - 无论如何，所有相关的“文本导入”API，如打开文件或连接到DB，允许您指定要使用的文本编码。
内部字符串根据文本字符串中“最宽”代码点的需要使用“Latin-1”、“UCS-2”或“UCS-4”之一。
这是 Python 3.3 之后的新功能（在此之前，所有内部字符串表示都默认为 32 位 UCS-4，即使是 ASCII-only 文本）。该规范记录在 PEP-393.
因此，Python 只能 zero-in 给定索引的正确字符。
作为轶事，Luciano Ramalho（Fluent Python 一书的作者）写了 Leanstr，一个 learning-purpose 字符串 class 的实现，它将包含 utf- 8 内部。当然，那么您对 __getitem__ 复杂性的担忧适用：https://github.com/ramalho/leanstr
不幸的是，（或者幸运的是，在这种情况下），Python 的许多标准库和本机代码扩展不会接受类似于 str 的 class，甚至如果它继承自 str 并单独保留其数据，则 re-implementing 所有 dunder 方法。但是，如果所有 str 方法都已到位，任何处理字符串的 pure-python 代码都应该接受一个 LeanStr 实例。
其他实现：Pypy
因此，文本在内部的使用方式恰好是一个“实现细节”，并且从 version 7.1 开始的 Pypy 确实在其文本对象内部使用 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.