有沒有一種數學方法來計算動態數組的最佳增長因子？

Question

對於類項目，我們需要根據循環動態數組找到優先級隊列的最優增長因子。 我跑了一些測試，但他們沒有結果。我們被告知有一種顯示數字的方式，但我無法在任何地方找到它。

我查了一下，發現Java ArrayList使用3/2，這也是pyhton列表中使用9/8因子的c實現，基本上我認爲它在不同的編程語言之間有所不同。

那麼，有沒有找到「最優」生長因子的動態數組的任何數學方法嗎？

Answer 1

簡短的回答是「否」。

對於大多數應用中，最佳的生長因子。將其精確地生長的陣列其最大所需尺寸在單個步驟中的一個。所以事後很容易確定，但通常很難預測。

所以缺乏有關該最大尺寸，從而優化內存需求的策略信息是在每個步驟中分配單個附加單元中的一個。優化重新分配次數的是分配儘可能多的內存以滿足單步執行所需的內存。對於大多數實際應用而言，兩者都不合理。通常需要在內存和重新分配之間進行權衡。

你可以用數學術語來描述你的偏好。例如。通過制定一些成本作爲分配數量或頻率，總分配空間量和實際使用的百分比的函數。如果除此之外還有典型使用模式的數學模型，那麼您可以開始優化，即改變增長因子以最小化成本。

在實踐中，無論是成本還是使用是衆所周知的，既取決於很多外部因素。因此它歸結爲直覺和經驗。如果您注意到您的應用程序浪費內存，則可能會降低增長因子，並且如果您發現它在重新分配上花費太多時間，則可能會增加該因子。這兩個變化都是非常特殊的，不需要太多的數學建模。