在python文档中,我可以看到deque是一个特别的集合,高度优化从左侧或右侧弹出/添加项目.例如文件说:
Deques是堆栈和队列的概括(名称发音为"deck",是"双端队列"的缩写).Deques支持线程安全,内存有效的附加和从双端队列的弹出,在任一方向上具有大致相同的O(1)性能.
尽管列表对象支持类似的操作,但它们针对快速固定长度操作进行了优化,并导致pop(0)和insert(0,v)操作的O(n)内存移动成本,这些操作改变了底层数据表示的大小和位置.
我决定使用ipython进行一些比较.谁能解释一下我在这里做错了什么:
In [31]: %timeit range(1, 10000).pop(0)
10000 loops, best of 3: 114 us per loop
In [32]: %timeit deque(xrange(1, 10000)).pop()
10000 loops, best of 3: 181 us per loop
In [33]: %timeit deque(range(1, 10000)).pop()
1000 loops, best of 3: 243 us per loop
我已经读过按位置索引访问元素可以在STL双端队列中以恒定时间完成.据我所知,双端队列中的元素可能存储在几个非连续的位置,从而消除了通过指针算法的安全访问.例如:
ABC-> defghi-> jkl-> MNOP
上面的双端队列元素由一个字符组成.一组中的字符集表示它被分配在连续的存储器中(例如,abc在单个存储器块中,defhi位于另一个存储器块中,等等).任何人都可以解释如何通过位置索引进行访问可以在恒定时间内完成,特别是如果要访问的元素在第二个块中？或者双端队列是否有指向这组块的指针？
更新:或者deque还有其他常见的实现吗？
目前我从我的存储中获取"列表"数据,"解除"它以使用该数据.在处理获取的数据后,我必须将它们放回存储器中.只要我没有强迫(至少我认为如此)使用python的标准"list"对象来保存这些数据,这就不会有问题了.
存储服务:Google Appengine.
我的解决方法是:
dequeObj = deque(myData)
my_list= list()
for obj in dequeObj:
my_list.append(obj)
但这似乎不是很理想.
我一直在考虑如何将deque(即双端队列)实现为不可变数据结构.
似乎有不同的方法来做到这一点.AFAIK,不可变数据结构通常是分层的,因此在修改诸如插入或删除项之类的操作之后,可以重用它的主要部分.
Eric Lippert 在他的博客上有两篇 关于这个主题的文章,以及C#中的示例实现.
他的两个实现都让我觉得比实际需要更精细.难道deques只能被实现为二叉树,其中元素只能在树的"左"(前)和非"右"(后面)插入或删除？
o
/ \
… …
/ \
… …
/ \ / \
front --> L … … R <-- back
此外,树将与旋转保持合理平衡:
在我看来,Eric Lippert是一个非常聪明的人,我非常尊重他,但他显然没有考虑这种方法.因此我想知道,这是有充分理由的吗？我建议的实施dequesnaïve的方法吗？
他们之间有什么区别？我知道
队列设计为在队列末尾插入元素,并从队列的开头删除元素.Dequeue表示一个队列,您可以在其中插入和删除队列两端的元素.
但哪个效率更高？
加上他们两个有什么区别？因为我对它们有一些了解,我上面说过,但我想了解更多关于它们的信息.我们将不胜感激.
正如标题所要求的那样.
我对双端队列的理解是它分配了"块".我没有看到如何分配更多的空间使迭代器无效,如果有的话,人们会认为deque的迭代器比矢量更有保证,而不是更少.
如果我有两个向量并想将它们组合成一个,我可以通过以下方式实现:
std::vector<T> a(100); // just some random size here
std::vector<T> b(100);
a.insert(std::end(a), std::begin(b), std::end(b));
这涉及复制,但我想避免.有没有办法使用move-semantics将它们组合在一起？
我非常怀疑它,因为vector它应该是连续的.但是有什么方法可以做到deque吗？
我已经改变了一些使用列表来使用双端队列的代码.当我收到错误时,我无法再切入它:
TypeError:序列索引必须是整数,而不是'slice'
这是一个显示问题的REPL.
>>> import collections
>>> d = collections.deque()
>>> for i in range(3):
... d.append(i)
...
>>> d
deque([0, 1, 2])
>>> d[2:]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: sequence index must be integer, not 'slice'
那么,有没有一种解决方法来支持在Python中切割成deques？
我几乎可以肯定这应该是重复但我搜索了一段时间,但找不到答案.我应该在C#中使用,以取代C++向量和deque 有效.也就是说,我需要一种能够高效地支持直接索引的结构,并且还支持以有效的方式从一端或两端(取决于向量或双端情况)进行删除.
在java中,我通常使用ArrayList至少用于向量,但对于C#,我发现这个源表明:
ArrayList resizes dynamically. As elements are added, it grows in capacity to accommodate them. It is most often used in older C# programs..那么新的方法是什么？我又如何为deque案件做些什么呢？
如果我错了,请纠正我.谢谢!
insert并且erase将重新定位元素,但是在插入/擦除发生的位置之前的元素不会重新定位,因此它们的迭代器保持有效.
push_back并且pop_back不要使任何迭代器无效.
push_front和pop_front无效所有迭代器.
swap 不会重新定位元素,但不知何故,我认为它应该使迭代器无效.