julia - Julia中推荐的数据结构以实现高效附加

Question

Julia 中理想的类似列表的数据结构是什么？

我想要一个具有恒定时间追加操作的可索引、可增长的集合。

标准数据结构似乎Array与push!操作有关。这是恒定的时间吗？

Answer 1

正如哈伦所说，push!是摊销常数时间。请参阅 C++ 的类似数据结构的描述，了解原因：Amortized analysis of std::vector injection

如果你想要一个合法的恒定时间数据结构，你可能想要实现一个链表。我已经看到了很多示例实现，但没有任何东西可以用于生产。

Answer 2

反复调用push!不是恒定的时间，但它非常快。它偶尔对缓冲区进行指数重新分配。请参阅 C 源以附加到数组：https ://github.com/JuliaLang/julia/blob/master/src/array.c#L564

Answer 3

差异列表允许您在恒定时间内追加、前置和连接。我昨天在这里推送了一个实现。它实际上只是几行代码，但我通过添加对迭代和显示的支持使它变得更漂亮。

您可以使用该函数创建一个差异列表dl，如下所示：dl(1, 2, 3)或者为您可以迭代的任何内容创建一个差异列表todl(items)。

concat您可以使用该函数在恒定时间内连接任意数量的差异列表，如下所示concat(dl(1, 2), dl(3, 4))：

您可以使用pushfirstandpush以恒定时间添加到开始和结束。

差异列表可以迭代，因此您可以在 for 循环和 splats 中使用它们，并轻松地将它们转换为数组。

我正在等待它作为 Julia 包发布，但您可以直接使用DifferenceLists.jl 文件。