Python 3字符串索引查找为O（1）？

Question

短篇故事：

Python 3 Unicode字符串查找是O（1）还是O（n）？

很长的故事：

C字符数组中字符的索引查找是恒定时间O（1），因为我们可以确定地跳转到连续的内存位置：

const char* mystring = "abcdef";
char its_d = mystring[3];

就像说：

char its_d = *(mystring + 3);

因为我们知道sizeof(char)C99是1，并且由于ASCII而一个字符适合一个字节。

现在，在Python 3中，字符串文字是unicode字符串，我们具有以下内容：

>>> mystring = 'ab€cd'
>>> len(mystring)
5
>>> mybytes = mystring.encode('utf-8')
>>> len(mybytes)
7
>>> mybytes
b'ab\xe2\x82\xaccd'
>>> mystring[2]
'€'
>>> mybytes[2]
226
>> ord(mystring[2])
8364

由于采用UTF-8编码，字节2> 127，因此对字符3使用多字节表示形式。

我只能得出结论，因为字符的多字节表示形式，所以Python字符串中的索引查找不能为O（1）吗？这就是说mystring[2]是O（n），并且为了找到索引处的字符，正在以某种方式对存储阵列进行即时解释？如果是这样，我是否错过了一些相关文档说明这一点？

我做了一些非常基本的基准测试，但我无法推断出O（n）行为：https : //gist.github.com/carlos-jenkins/e3084a07402ccc25dfd0038c9fe284b5

$ python3 lookups.py
Allocating memory...
Go!
String lookup: 0.513942 ms
Bytes lookup : 0.486462 ms

编辑：更新了更好的例子。

Answer 1

UTF-8是Python 的默认源编码。 的内部表示使用固定大小的每字符要素在两个Python 2和Python 3的结果之一是，通过指数在Python（Unicode）的字符串对象访问字符具有O（1）成本。

您提供的代码和结果没有其他说明。您将转换string为UTF-8编码的字节序列，我们都知道UTF-8使用变长代码序列，但是这些都没有说明原始的内部表示string。