Julia中理想的列表式数据结构是什么？
我想要一个具有常量时间追加操作的可索引，可增长的集合。
标准数据结构似乎是Array与push!操作。这是不变的时间吗？
正如哈伦所说，push!的摊销时间不变。有关参数的原因，请参阅C ++类似数据结构的描述：Amortized analysis of std::vector insertion
如果您想要一个合法的恒定时间数据结构，您可能希望实现一个链表。我已经看过很多样本实现，但没有任何可用于生产的内容。
反复调用push!不是恒定的时间，但它很快。它偶尔会对缓冲区进行指数式重新分配。请参阅附加到数组的C源：https://github.com/JuliaLang/julia/blob/master/src/array.c#L564
差异列表允许您在恒定时间内追加，前置和连接。我昨天推出了一个实施here。它实际上只是几行代码，但我通过添加对迭代和显示的支持使其变得更加漂亮。
您可以使用dl函数创建差异列表，如下所示：dl(1, 2, 3)或为可以使用todl(items)迭代的任何内容创建差异列表。
您可以使用concat函数在恒定时间内连接任意数量的差异列表，如下所示：concat(dl(1, 2), dl(3, 4))。
您可以使用pushfirst和push以恒定时间添加到开始和结束。
差异列表可以迭代，因此您可以在for循环和splats中使用它们，并轻松将它们转换为数组。
我正在等待它作为Julia包发布，但你可以直接使用the DifferenceLists.jl file。