Shift-to-Middle Array：比 `std::deque` 更快的替代方案？

Shift-to-Middle Array: A Faster Alternative to Std:Deque?

Source | HN Comments

Shift-To-Middle Array 是一种动态数组，旨在优化两端插入和删除操作，作为 `std::deque` 等数据结构的高性能替代方案。它通过连续内存存储、改善缓存局部性和支持并行处理来实现高效操作，尤其在两端插入和删除上具有均摊 O(1) 的时间复杂度。与 `std::deque` 相比，它在内存使用和缓存局部性方面更具优势。基准测试表明，其性能提升依赖于 CPU 和 GPU 的能力。该数据结构适用于高性能队列、游戏引擎、网络应用等场景。

Shift-To-Middle Array 是一种动态数组，旨在优化两端的插入和删除操作，为 std::deque、std::vector 和链表提供了一种高性能的替代方案。它通过保持连续的内存存储、改善缓存局部性并实现高效的并行处理来实现这一点。

🌟 特性

✅ 两端均摊 O(1) 时间复杂度的插入和删除 ✅ 快速随机访问 (O(1)) ✅ 比链表更好的缓存局部性 ✅ 支持 SIMD 和并行优化 ✅ 与 std::deque 相比，内存使用效率更高

📌 工作原理

与使用分段块结构的 std::deque 不同，Shift-To-Middle Array 动态重新分配空间以避免代价高昂的移位。在调整大小时，元素会向中间移动，从而确保两端的高效插入，而无需过多的复制。

🚀 时间复杂度比较

下表比较了 Shift-To-Middle Array 操作与其他常见数据结构的时间复杂度：

操作 | ArrayList (std::vector) | 链表 | Shift-To-Middle Array ---|---|---|--- 按索引访问 | O(1) | O(n) | O(1) 头部插入 | O(n) | O(1) | O(1) (均摊) 尾部插入 | O(1) (均摊) | O(1) | O(1) (均摊) 中间插入 | O(n) | O(n) | O(n) 头部删除 | O(n) | O(1) | O(1) (均摊) 尾部删除 | O(1) | O(1) | O(1) (均摊) 中间删除 | O(n) | O(n) | O(n) 缓存局部性 | 优秀 | 差 | 优秀

🏆 性能基准

Shift-To-Middle Array 与 std::deque、ExpandingRingBuffer 和 std::queue 的基准测试表明，性能改进取决于 CPU 和 GPU 的能力，例如多核并行、SIMD 优化和缓存效率。

这些基准测试是使用 GCC 编译器，并开启 -O3 优化标志进行编译的，确保了高性能执行。结果会因硬件规格和工作负载特性而异。

📂 安装与使用

要在您的项目中使用 Shift-To-Middle Array，请执行以下操作：

#include "ShiftToMiddleArray.h"
ShiftToMiddleArray<int> stmArray;
stmArray.insert_head(42);
stmArray.insert_tail(99);
int value = stmArray.get_head();
stmArray.remove_head();

🔬 何时使用

高性能队列结构
游戏引擎和实时应用
网络（数据包缓冲、事件队列）
计算几何与物理学中的动态序列

📖 文档

运行 Java 基准测试

要运行 Java 基准测试，请确保您已安装 Trove 库。使用以下命令编译并执行：

javac -cp trove-3.0.3.jar; ShiftToMiddleArrayBenchmarkTrove.java
java -cp trove-3.0.3.jar; ShiftToMiddleArrayBenchmarkTrove

完整的 API 参考和基准测试可在 Wiki 中找到!

📊 基准测试与结果

有关完整的基准测试详细信息，请查看基准测试报告。提供的 Python 脚本可用于可视化来自 CSV 基准测试结果的性能指标。

🏛 历史

Shift-To-Middle Array 的开发是为了创建一种更有效的列表和双端队列的实现策略。诸如 std::deque 和链表之类的传统数据结构存在缓存局部性差或内存分配分散的问题，导致效率低下。通过利用连续内存、动态中间移位和现代 CPU 优化，Shift-To-Middle Array 为插入、删除和访问性能提供了平衡的解决方案。

📜 许可

该项目已根据 MIT 许可证获得许可。

🤝 贡献

欢迎贡献！随意开启 issue 或 pull request。

🚀 立即尝试 Shift-To-Middle Array 并优化您的数据结构！

关于

一种用于实现列表和双端队列的创新数据结构。