带有for in的python字符串迭代的时间复杂度

它是O（n），但是索引查找参数是一个红色鲱鱼。

迭代如何工作

如果这样做，索引查找速度将很重要：

for index in range(len(mystring)):
    char = mystring[index]
    ...

但是您没有使用索引。您正在使用迭代器，更确切地说是字符串迭代器：

>>> iter('test')
<str_iterator object at 0x03569820>

该迭代器会记住它在字符串中的位置（它喜欢的任何方式都不需要是“索引”）。并且可以反复询问下一个字符：

>>> it = iter('test')
>>> next(it)
't'
>>> next(it)
'e'
>>> next(it)
's'
>>> next(it)
't'
>>> next(it)
Traceback (most recent call last):
  File "<pyshell#200>", line 1, in <module>
    next(it)
StopIteration

这就是for-loop的作用。它创建该迭代器，然后反复要求它提供下一个值，直到迭代器告诉它停止为止。并且它从迭代器获得的每个值都将其命名为变量，并提供给您的代码。换句话说，for-loop实际上只是迭代器和循环体内代码之间的中间人。

与字符串相反，想象一个简单的链表。链表中的索引查找需要O（n），因为每次查找都需要从链表的开始到所需的节点。但是您仍然可以轻松地在O（n）中进行完整的迭代，对吗？并且迭代器对象将保留对下一个节点的引用，因此它将在O（1）时间内提供给它（然后将其引用向前移动）。因此，对于链表，for使用索引的-loop将使用O（n ²），但是普通的pythonic for-loop（隐式使用链表迭代器）将是O（n）。

您甚至可以for使用while-loop和您自己处理的显式迭代器来模仿-loop，而不是让for-loop为您处理。代替

for char in 'test':
    print(char)

做这个：

it = iter('test')
while True:
    try:
        char = next(it)
    except StopIteration:
        break
    print(char)

打印：

t
e
s
t

字符串迭代的时间复杂度

让我们看一下源代码。我对它不是很熟悉，但是我会描述一下我所相信的。还记得str_iterator吗？什么是str在Python 3被称为unicode在Python 2，这仍然在Python 3做的C源代码的名称unicodeobject.c，我们找到字符串"str_iterator"，并且它的“统一迭代器”部分。摘录：

/********************* Unicode Iterator **************************/

typedef struct {
    ...
    Py_ssize_t it_index;
    PyObject *it_seq;    /* Set to NULL when iterator is exhausted */
} unicodeiterobject;
...
unicodeiter_next(unicodeiterobject *it)
{
    ...
    seq = it->it_seq;
      ...
        void *data = PyUnicode_DATA(seq);
        Py_UCS4 chr = PyUnicode_READ(kind, data, it->it_index);
        item = PyUnicode_FromOrdinal(chr);
        if (item != NULL)
            ++it->it_index;
        return item;
    ...
}
...
PyTypeObject PyUnicodeIter_Type = {
    ...
    "str_iterator",         /* tp_name */
   ...
};

因此，它unicodeiterobject带有一个指向it_seq要迭代的字符串的指针和一个索引it_index。它的next功能使用它们来获取下一个字符，增加索引并返回该字符。好的，事实证明迭代器确实在内部使用索引。但是，与使用Python的使用以下unicode_getitem函数的索引相比，该索引的内部层次较低，更直接：

static PyObject *
unicode_getitem(PyObject *self, Py_ssize_t index)
{
    void *data;
    enum PyUnicode_Kind kind;
    Py_UCS4 ch;
    ...
    if (index < 0 || index >= PyUnicode_GET_LENGTH(self)) {
        PyErr_SetString(PyExc_IndexError, "string index out of range");
        return NULL;
    }
    kind = PyUnicode_KIND(self);
    data = PyUnicode_DATA(self);
    ch = PyUnicode_READ(kind, data, index);
    return unicode_char(ch);
}

两者看起来很相似，最终都可以使用PyUnicode_READ(kind, data, index)。我找不到那个，但是它应该相当简单，为O（1），使得整个迭代为O（n）。

还有一件事：@NickParsons上面指出的答案/问题使用可变大小的多字节字符表示法处理了Python的烦恼，这可能使索引查找为O（n）而不是O（1）。即使是这种情况，也只会影响unicode_getitem功能。不是str_iterator迭代器。因为迭代器绝对肯定不会使用朴素的“字符串索引”，而是指向下一个字符的第一个字节的指针，以便它可以在O（1）中读取并前进。因此，它的整个迭代仍然是O（n）。