我有一個需要“老化”的程序的情況。這意味著我
- 從p值開始，p比較小
- 對于 n>p，使用最近生成的 p 值生成第 n 個值（例如，從值 1 到 p 生成的 p 1、從值 2 生成的 p 2、p 1 等）
- 重復直到 n=N，其中 N 很大
現在，只有最近生成的 p 值對我有用，所以我有兩種方法來實作它。我可以
- 從 p 個初始值的向量開始。在每次迭代中，改變向量，洗掉第一個元素，并用最近生成的值替換最后一個元素，或者，
- 預分配一個長度為 N 的大陣列，其中前 p 個元素是初始值。在迭代 n 處，用最近生成的值改變第 n 個值
這兩種方法各有利弊。
第一個的優點是我們只存盤最相關的值。第一個缺點是我們在每次迭代時都在改變向量的長度。
第二種方法的優點是我們預先分配了我們需要的所有記憶體。第二個缺點是我們存盤的東西比我們需要的多得多。
最好的方法是什么？這取決于我最需要關心的性能方面嗎？什么會最快？
提前喝彩。
編輯：大約，p通常在低十的數量級，N可以是幾千
uj5u.com熱心網友回復：
第一個解決方案還有另一個巨大的缺點：洗掉陣列的第一項需要O(n)時間，因為元素應該在記憶體中移動。這肯定會導致演算法在二次時間中運行，這是不合理的。@ForceBru 建議的移動專案也應該導致這個二次運行時間（因為移動許多專案只是為了每次添加一個值）。
與第一個解決方案相比，第二種解決方案應該相當快，但實際上，它可以使用大量記憶體，因此它應該是次優的（將值寫入 RAM 需要時間）。
更快的解決方案是使用稱為deque的資料結構。這種資料結構使您可以在恒定時間內洗掉第一項，并在最后添加一個新值。話雖如此，它也引入了一些開銷來做到這一點。Julia 提供了這樣的資料結構（尤其是佇列）。
由于在您的演算法中飛行中專案的數量似乎是有限的，因此您可以實作一個滾動緩沖區。幸運的是，Julia 也實作了這一點：參見CircularBuffer。這個解決方案應該是相當簡單和快速的（因為你想做的操作都是在O(1)上面及時完成的??）。
uj5u.com熱心網友回復：
將 CircularArrays.jl 用于您的用例可能是最簡單的：
julia> using CircularArrays
julia> c = CircularArray([1,2,3,4])
4-element CircularVector(::Vector{Int64}):
1
2
3
4
julia> for i in 5:10
c[i] = i
@show c
end
c = [5, 2, 3, 4]
c = [5, 6, 3, 4]
c = [5, 6, 7, 4]
c = [5, 6, 7, 8]
c = [9, 6, 7, 8]
c = [9, 10, 7, 8]
通過這種方式 - 如您所見 - 您可以繼續使用增加的索引，并且陣列將根據需要在內部環繞（丟棄不再需要的舊值）。
通過這種方式，您始終將最后一個p值存盤在陣列中，而無需在每個步驟中復制任何內容或重新分配記憶體。
uj5u.com熱心網友回復：
...只有最近生成的 p 值對我有用...
從 p 個初始值的向量開始。在每次迭代中，對向量進行變異，洗掉第一個元素，并用最近生成的值替換最后一個元素。
第一個缺點是我們在每次迭代時都在改變向量的長度。
無需更改向量的長度。只需將其元素向左移動（覆寫第一個元素）并將新資料寫入the_vector[end]：
the_vector = [1,2,3,4,5,6]
function shift_and_add!(vec::AbstractVector, value)
vec[1:end-1] .= @view vec[2:end] # shift
vec[end] = value # replace the last value
vec
end
@assert shift_and_add!(the_vector, 80) == [2,3,4,5,6,80]
# `the_vector` will be mutated
@assert the_vector == [2,3,4,5,6,80]
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/474468.html
上一篇：比較多個不同長度的numpy陣列
下一篇：在查詢優化方面需要幫助