03｜双端队列：并行计算中的工作窃取算法如何实现？
该思维导图由 AI 生成，仅供参考
队列
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文深入介绍了双端队列在并行计算中的工作窃取算法的实现。首先，文章详细讲解了STL中双端队列的实现，包括内存布局和迭代器的实现。双端队列的内存布局具有list和vector的特点，通过一段段连续的空间和map的管理实现了高效的插入和删除操作。接着，文章探讨了双端队列的基本操作，包括push和pop的实现原理。文章还分析了C++选择基于map分段存储的双端队列的原因，以及与vector和list的比较。最后，文章引出了工作窃取算法需要用到双端队列的思路，并留下了课后作业，鼓励读者深入探讨队列的实现方式。整体而言，本文对于想要深入了解并行计算中的工作窃取算法的读者具有很高的参考价值。
《业务开发算法 50 讲》，新⼈⾸单¥59
全部留言(9)
- 最新
- 精选
SevenHemap如果只是用于维护block的索引，本身更新的频率比较低，似乎list比vector更适合，为何不直接使用链表呢？这样不需要考虑扩容和缩容的问题了作者回复: 这个问题非常好！看得出来你是有思考的同学～ 我个人的理解，也不一定正确，可能主要是因为 stl::deque 支持了 at 方法；用数组就可以比较快速的取到特定的元素； 这点我在专栏里可能没有说明，之后会调整一下。 至于为什么deque要支持at方法，我还不是特别清楚。
2021-12-2211- Paul ShanDeque的实现分了两层，第一层是不定长的循环对列管理数据块指针，第二层是定长的数据块，管理实际元素的存取。 和链表相比，这种实现因为有了定长的数据块，可以减少添加和删除内存的数目，也省去了每个节点的指针。有了第一层不定长的循环队列，对于插入和删除元素都能做到O(1)的均摊复杂度，这里使用的指针数目是使用双向链表1/2m，（m是块的大小）
作者回复: 嗯嗯 说的很对
2021-12-168 
丶双端队列的两种实现：链表和数组 https://github.com/hzq-qqq/-1。能力有限，有错误的地方，希望指正作者回复: 很认真呀；感觉问题不是很大；晚些我仔细看一下。 可以加我vx：constant_variation 一起讨论
2021-12-25
灵茶山艾府🎈有一种双端队列的实现方法是用两个 queue，头对头，这样也可以做到类似 deque 的效果。但是为什么 STL 不采用这种实现方式呢，疑惑。作者回复: 哈哈哈 能稍微展开讲解一下吗 我还不是很确定具体的做法
2021-12-163
那时刻请问老师，如果 map 使用率已经超过一半，我们就可以重新申请更大的空间，把老的 map 上的数据拷贝到新的区域。 请问什么这么做呢？ 如果不重新申请大的内存，而是增加一个block，如此岂不是节省了拷贝的开销？作者回复: 增加一个block没法保证数据是连续存储的哈 和vector扩容的时候不原地扩容是一个道理
2021-12-16
友还有一点 这个玩意我感觉和go的gmp 一样一样的作者回复: 嗯嗯 GMP好像确实用了工作窃取算法 具体的细节我也不是很确定了；欢迎补充 可以+V: constant_variation 和我交流
2021-12-162- 友简单的总结: 看了下老师的文字描述，感觉这个deque在我的理解上就是 map是一个不定长数组了 然后里面的每个元素就是一段连续的空间(也是节点数组) 这样就可以拼接起来实现双端队列。 然后对于扩容操作 如果发现某一个端点在map层用完了 那么判断是否超过总容量的百分之五十 如果没有超过证明某一段比较数据集中，另外一点数据较少可以移动到中间来 无需扩容，反之扩容 在map层 其他的主要就是维护其他指针了 保证push pop对应的位置 主要是看不明白cpp代码 准备去用go实现一下 以上是小总结如果有错误希望大家指正
作者回复: 说的非常正确；欢迎用golang实现；可以另外提一份PR到我的仓库 https://github.com/wfnuser/Algorithms 哦
2021-12-162 
徐晓桐你好 老师 我不太明白 STL 为啥不直接用双链表实现双端队列 ?2022-10-21归属地：上海- Geek_ef214b老师你好，我想请问多线程环境下双端队列和FIFO队列在工作窃取算法中有什么区别？线程对队列进行Push或Pop不都要上锁吗？对效率的提升有什么帮助？2022-03-26
