Временная сложность python итерации строки с в течение - PullRequest
Новая
       19

Временная сложность python итерации строки с в течение

0 голосов
/ 11 января 2020

Какова временная сложность Python for in построения итерации со строкой?

Например, 

for s in 'test':
   ...  # s = 't', 'e', 's', 't'

Каково общее время выполнения l oop?

Редактировать : Я вижу, что путал поиск фрагмента строки Python с итерацией строки. Его поиск по индексу - O (1), и он повторяется в O (1), поэтому итоговое значение l oop должно быть равно O (n), так же как и список.

Ответы [ 2 ]

2 голосов
/ 11 января 2020

Это O (n), но аргумент поиска индекса - красная сельдь.

Как работает итерация

Скорость поиска индекса будет иметь значение, если вы сделаете это: 

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

Но вы не используете индексы. Вы используете итератор , точнее string итератор: 

>>> 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 -l oop. Он создает этот итератор и затем неоднократно запрашивает его для следующего значения, пока итератор не скажет ему остановиться. И каждое значение, которое он получает от итератора, он передает вашему коду в названной вами переменной. Другими словами, for -l oop - это просто посредник между итератором и вашим кодом в теле l oop.

В отличие от строк, представьте простой связанный список , Поиск индекса в связанном списке занимает O (n), поскольку каждый поиск требует перехода от начала связанного списка к нужному узлу. Но вы все равно можете легко выполнить полную итерацию в O (n), верно? И объект итератора будет хранить ссылку на следующий узел, поэтому он предоставит его за O (1) времени (и затем переместит свою ссылку вперед). Таким образом, для связанного списка, for -l oop с использованием индексов будет принимать O (n 2 ), но обычный pythoni c for -l oop (неявно используя связанный итератор списка) будет O (n).

Вы можете даже mimi c a for -l oop с while -l oop и явным итератором, который вы обрабатываете сами вместо этого позволить for -l oop справиться с этим за вас. Вместо 

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, и это все еще имя в C исходном коде Python 3. Так что в 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).

2 голосов
/ 11 января 2020

O (n) является ответом. проверьте этот сайт, чтобы узнать больше о timeComplexity python сложность времени

...