在Python中通过双端队列进行迭代的时间复杂度是多少?

毅力

从Python的collections库进行迭代(或更精确地说,通过双端队列进行每次迭代)的时间复杂度是多少?

一个例子是这样的:

elements = deque([1,2,3,4])
for element in elements:
  print(element)

每次迭代都是常数O(1)运算吗?还是执行线性O(n)运算以在每次迭代中到达元素?

有许多资源在线时间与所有其他deque的方法,如复杂性appendleftappendpopleftpop关于双端队列的迭代,似乎没有任何时间复杂度信息。

谢谢!

胡安帕·阿里维利亚加

如果您的构造是这样的:

elements = deque([1,2,3,4])
for i in range(len(elements)):
    print(elements[i])

没有遍历deque,而是遍历了range对象,然后索引到deque由于每个索引操作elements[i]均为O(n)因此这使得迭代多项式时间成为可能然而,实际上迭代deque是线性的时间。

for x in elements:
    print(x)

这是一个快速的经验检验:

import timeit
import pandas as pd
from collections import deque

def build_deque(n):
    return deque(range(n))

def iter_index(d):
    for i in range(len(d)):
        d[i]

def iter_it(d):
    for x in d:
        x

r = range(100, 10001, 100)

index_runs = [timeit.timeit('iter_index(d)', 'from __main__ import build_deque, iter_index, iter_it; d = build_deque({})'.format(n), number=1000) for n in r]
it_runs = [timeit.timeit('iter_it(d)', 'from __main__ import build_deque, iter_index, iter_it; d = build_deque({})'.format(n), number=1000) for n in r]

df = pd.DataFrame({'index':index_runs, 'iter':it_runs}, index=r)
df.plot()

和结果情节: 在此处输入图片说明

现在,我们实际上可以看到如何dequeCPython源代码中对象实现迭代器协议

首先,deque对象本身:

typedef struct BLOCK {
    struct BLOCK *leftlink;
    PyObject *data[BLOCKLEN];
    struct BLOCK *rightlink;
} block;

typedef struct {
    PyObject_VAR_HEAD
    block *leftblock;
    block *rightblock;
    Py_ssize_t leftindex;       /* 0 <= leftindex < BLOCKLEN */
    Py_ssize_t rightindex;      /* 0 <= rightindex < BLOCKLEN */
    size_t state;               /* incremented whenever the indices move */
    Py_ssize_t maxlen;
    PyObject *weakreflist;
} dequeobject;

因此,如评论中所述,adeque是“块”节点的双向链接列表,其中,块本质上是python对象指针的数组。现在使用迭代器协议:

typedef struct {
    PyObject_HEAD
    block *b;
    Py_ssize_t index;
    dequeobject *deque;
    size_t state;          /* state when the iterator is created */
    Py_ssize_t counter;    /* number of items remaining for iteration */
} dequeiterobject;

static PyTypeObject dequeiter_type;

static PyObject *
deque_iter(dequeobject *deque)
{
    dequeiterobject *it;

    it = PyObject_GC_New(dequeiterobject, &dequeiter_type);
    if (it == NULL)
        return NULL;
    it->b = deque->leftblock;
    it->index = deque->leftindex;
    Py_INCREF(deque);
    it->deque = deque;
    it->state = deque->state;
    it->counter = Py_SIZE(deque);
    PyObject_GC_Track(it);
    return (PyObject *)it;
}

...

static PyObject *
dequeiter_next(dequeiterobject *it)
{
    PyObject *item;

    if (it->deque->state != it->state) {
        it->counter = 0;
        PyErr_SetString(PyExc_RuntimeError,
                        "deque mutated during iteration");
        return NULL;
    }
    if (it->counter == 0)
        return NULL;
    assert (!(it->b == it->deque->rightblock &&
              it->index > it->deque->rightindex));

    item = it->b->data[it->index];
    it->index++;
    it->counter--;
    if (it->index == BLOCKLEN && it->counter > 0) {
        CHECK_NOT_END(it->b->rightlink);
        it->b = it->b->rightlink;
        it->index = 0;
    }
    Py_INCREF(item);
    return item;
}

正如您所看到的,迭代器本质上跟踪着队列索引,指向块的指针以及双端队列中所有项目的计数器。如果计数器达到零,它将停止迭代,否则计数器将停止获取当前索引处的元素,将索引递增,将计数器递减,然后检查是否要移至下一个块。换句话说,双端队列可以表示为Python中的列表列表,例如d = [[1,2,3],[4,5,6]],并进行迭代

for block in d:
    for x in block:
        ...

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章