在Python中高效地双向迭代deque

Question

在Python中高效地双向迭代deque

6

我有一个双端队列，我们称其为deq。我需要从两端迭代它，并且在这些迭代过程中不会修改它。

自然地，我不想创建另一个双端队列。我已经考虑过使用reversed，但我不知道它是否实际上会创建任何副本。例如，如果我写：

reversed_deq = reversed(deq)

它是否会引用完全相同的内存位置，只是以相反的方式迭代，而不使用更多的内存/时间？

这似乎是双端队列的逻辑方式，但我想确保我没有漏掉任何东西。

我找不到deque的代码（通常它们有一个这些东西的“Python等效物”，但我找不到它），并且由于某种原因-无论我运行什么-timeit总是给我15到16 ns之间的结果（对于我尝试计时的所有内容，而不仅仅是这个）

- user1999728

1

在Python中，您可以使用列表来实现双端队列，不需要其他任何东西。此外，如果您想要高效地完成某些任务，就不应该使用Python。 - Hannes Karppila

@HannesKarppila 很不幸，我别无选择，只能使用Python，所以我正在尽力克服困难。而且没有理由使用列表，因为 A. 我会不断地向deque添加元素，而列表每次都会重新分配空间， B. 我只需要访问前几个元素，最多只需要访问最后3个元素。 - user1999728

collections.deque有一个内置的reverse()方法。当你说要从两端遍历它，你是指先沿一个方向迭代一次，然后再沿另一个方向迭代一次吗？ - csunday95

@csunday95 是的。我已经阅读了文档，它说“原地”-这意味着不需要重新分配内存。我只想验证它们是否也会迭代整个deque并反转顺序（因为从我理解的实现来看，每个元素都指向下一个和上一个元素）。正如我所提到的，我找不到deque的实际代码，而我的timeit函数似乎无法正常工作。 - user1999728

你想在两个方向上进行什么操作？ - csunday95

显示剩余4条评论

2个回答

1

Python 2和3文档说明reversed()内置函数“返回一个反向的迭代器”。严格来说，这并不阻止collections.deque.__reversed__()的实现进行复制。实际上，没有理由进行复制，因为双端队列在两个方向上都是可迭代的。

- Witiko

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- csunday95 · Accepted Answer

从C源代码中可以看到，reversed([deque])返回一个反向迭代器，不会进行复制或内存分配。使用[deque].reverse()可以原地反转。