迭代的时间复杂度是多少,或者更准确地说,通过 Python 中的集合库中的双端队列进行的每次迭代是多少?
一个例子是这样的:
elements = deque([1,2,3,4])
for element in elements:
print(element)
每次迭代都是常数 O(1) 操作吗?还是在每次迭代中执行线性 O(n) 操作来获取元素?
有很多关于时间复杂度的在线资源以及所有其他双端队列方法,例如
appendleft
, append
, popleft
, pop
.似乎没有关于双端队列迭代的任何时间复杂度信息。谢谢!
最佳答案
如果您的构造类似于:
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()
以及由此产生的情节:现在,我们实际上可以看到
deque
的迭代器协议(protocol)是如何实现的。 CPython source code 中的对象:一、
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;
因此,如评论中所述,deque
是“ block ”节点的双向链表,其中 block 本质上是 python 对象指针的数组。现在对于迭代器协议(protocol):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;
}
如您所见,迭代器本质上跟踪 block 索引、指向 block 的指针和双端队列中总项目的计数器。如果计数器达到零,它会停止迭代,如果不是,它会抓取当前索引处的元素,递增索引,递减计数器,并负责检查是否移动到下一个 block 。换句话说,双端队列可以表示为 Python 中的列表列表,例如d = [[1,2,3],[4,5,6]]
, 并且迭代for block in d:
for x in block:
...
关于python - 在 Python 中遍历双端队列的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47338547/