Julia中的推薦數據結構用於高效追加

Question

Julia中理想的類列表數據結構是什麼？

我想要一個具有恆定時間附加操作的可索引，可增長的集合。

標準數據結構似乎是Array而push!操作。這是恆定的時間嗎？

Answer 1

反覆調用push!不是固定時間，但速度很快。它偶爾會對緩衝區進行指數重新分配。見C源追加到陣列：https://github.com/JuliaLang/julia/blob/master/src/array.c#L564

Answer 2

正如哈倫所說，push!是攤銷不變的時間。請參閱C++的類似數據結構的描述以解釋爲什麼：Amortized analysis of std::vector insertion

如果您想要一個合法的恆定時間數據結構，您可能需要實現鏈接列表。我見過很多示例實現，但沒有準備好用於生產。