我正在嘗試在 Julia 中實作合并排序演算法，但我似乎無法理解該演算法所需的遞回步驟。我的代碼如下：
m? = [1, 10, 7, 4, 3, 6, 8, 2, 9]
b?(t, z, half?, half?)= ((t<=length(half?)) && (z<=length(half?))) && (half?[t]<half?[z])
b?(t, z, half?, half?)= ((z<=length(half?)) && (t<=length(half?)) ) && (half?[t]>half?[z])
function Merge(m?, m?)
N = length(m?) length(m?)
B = zeros(N)
i = 1
j = 1
for k in 1:N
if b?(i, j, m?, m?)
B[k] = m?[i]
i = 1
elseif b?(i, j, m?, m?)
B[k] = m?[j]
j = 1
elseif j >= length(m?)
B[k] = m?[i]
i = 1
elseif i >= length(m?)
B[k] = m?[j]
j = 1
end
end
return B
end
function MergeSort(M)
if length(M) == 1
return M
elseif length(M) == 0
return nothing
end
n = length(M)
i? = n ÷ 2
i? = n - i?
h? = M[1:i?]
h? = M[i?:end]
C = MergeSort(h?)
D = MergeSort(h?)
return Merge(C, D)
end
MergeSort(m?)
當 C 成為單個元素時，它總是會卡住，因為它會回傳它然后再次拆分它，唯一的解決方案是一旦它成為單個元素就讓它成為一個回圈。但是，這不是遞回方法。
解決方案
接受@Sundar R 的回答和建議。這是一個有效的實作
#implementation of MergeSort in julia
# merge function, it joins two ordered arrays and returning one single ordered array
function merge(m?, m?)
N = length(m?) length(m?)
# create a zeros array of the same input type (int64)
B = zeros(eltype(m?), N)
i = 1
j = 1
for k in 1:N
if !checkbounds(Bool, m?, i)
B[k] = m?[j]
j = 1
elseif !checkbounds(Bool, m?, j)
B[k] = m?[i]
i = 1
elseif m?[i]<m?[j]
B[k] = m?[i]
i = 1
else
B[k] = m?[j]
j = 1
end
end
return B
end
# merge mergesort, this function recursively orders m/2 sub array given an array M
function mergeSort(M)
# base cases
if length(M) == 1
return M
elseif length(M) == 0
return nothing
end
# dividing array in two
n = length(M)
i? = n ÷ 2
# be careful with the indexes, thank you @Sundar R
i? = i? 1
h? = M[1:i?]
h? = M[i?:end]
# recursively sorting the array
C = mergeSort(h?)
D = mergeSort(h?)
return merge(C, D)
end
#test the function
m? = [1, 10, 7, 4, 3, 6, 8, 2, 9]
b = mergeSort(m?)
println(b)
uj5u.com熱心網友回復：
問題在于用于拆分的索引，特別是i?. n - i?是陣列后半部分中的元素數，但不一定是后半部分開始的索引 - 因為你只是想要 i? = i? 1。
用i? = n - i?，當n為2即當你回落到[1, 10]作為陣列進行排序，i? = n ÷ 2是1，并且i?是（2 - 1）= 1也。因此，您最終不是將其拆分為[1], [10]，而是將其“拆分”為[1], 和[1, 10]，因此是無限回圈。
一旦你解決了這個問題，由于一個小錯誤，會有一個BoundsErrorfrom Merge：elseif條件應該檢查>，而不是>=（因為 Julia 使用基于 1 的索引，j當 時仍然是有效索引j == length(m?)）。
其他一些建議：
zeros(N)回傳一個Float64陣列，所以這里的結果總是一個浮點陣列。我建議zeros(eltype(m?), N)改為。- 感覺就像
b?并且b?只會使代碼復雜化并使其不太清晰，我建議在其中嵌套一個簡單的嵌套if，一個外部的用于檢查索引 -checkbounds例如查找。checkbounds(Bool, m?, i)- 和一個內在的，看看哪個更大。 - Julia 約定是對函式使用小寫字母，所以用
mergeandmergesort代替MergeandMergeSort
uj5u.com熱心網友回復：
為了補充前面的答案，這些答案處理了現有代碼中的一些問題，這里是一個相對有效和直接的 Julia 實作供參考mergesort：
# Top-level function will allocate temporary arrays for convenience
function mergesort(A)
S = similar(A)
return mergesort!(copy(A), S)
end
# Efficient in-place version
# S is a temporary working (scratch) array
function mergesort!(A, S, n=length(A))
width = 1
swapcount = 0
while width < n
# A is currently full of sorted runs of length `width` (starting with width=1)
for i = 1:2*width:n
# Merge two sorted lists, left and right:
# left = A[i:i width-1], right = A[i width:i 2*width-1]
merge!(A, i, min(i width, n 1), min(i 2*width, n 1), S)
end
# Swap the pointers of `A` and `S` such that `A` now contains merged
# runs of length 2*width.
S,A = A,S
swapcount = 1
# Double the width and continue
width *= 2
end
# Optional, if it is important that `A` be sorted in-place:
if isodd(swapcount)
# If we've swapped A and S an odd number of times, copy `A` back to `S`
# since `S` will by now refer to the memory initially provided as input
# array `A`, which the user will expect to have been sorted in-place
copyto!(S,A)
end
return A
end
# Merge two sorted subarrays, left and right:
# left = A[i?:i?-1], right = A[i?:i?-1]
@inline function merge!(A, i?, i?, i?, S)
left, right = i?, i?
@inbounds for n = i?:(i?-1)
if (left < i?) && (right >= i? || A[left] <= A[right])
S[n] = A[left]
left = 1
else
S[n] = A[right]
right = 1
end
end
end
這足以讓我們與Base' 實作相同的演算法在同一個球場
julia> using BenchmarkTools
julia> @benchmark mergesort!(A,B) setup = (A = rand(50); B = similar(A))
BenchmarkTools.Trial: 10000 samples with 194 evaluations.
Range (min … max): 497.062 ns … 1.294 μs ┊ GC (min … max): 0.00% … 0.00%
Time (median): 501.438 ns ┊ GC (median): 0.00%
Time (mean ± σ): 526.171 ns ± 49.011 ns ┊ GC (mean ± σ): 0.00% ± 0.00%
█▅ ▁ ▁ ▃▇▄ ▁ ▂
█████▇▇▆▇█▇████▇▅▆▅▅▅▆█▆██▄▅▅▄▆██▆▆▄▄▆██▅▃▄██▄▅▅▃▃▃▃▄▅▁▄▄▃▁█ █
497 ns Histogram: log(frequency) by time 718 ns <
Memory estimate: 0 bytes, allocs estimate: 0.
julia> issorted(mergesort(rand(50)))
true
julia> issorted(mergesort(rand(10_000)))
true
julia> @benchmark Base.sort!(A, alg=MergeSort) setup=(A = rand(50))
BenchmarkTools.Trial: 10000 samples with 216 evaluations.
Range (min … max): 344.690 ns … 11.294 μs ┊ GC (min … max): 0.00% … 95.73%
Time (median): 352.917 ns ┊ GC (median): 0.00%
Time (mean ± σ): 401.700 ns ± 378.399 ns ┊ GC (mean ± σ): 3.57% ± 3.76%
█▇▄▄▄▂▁▂▁▂▃▁▁ ▃▂ ▁ ▁▁ ▁
████████████████▇██████▆▆▆▅▆▆▆▆▅▃▅▅▄▅▃▅▅▄▆▅▄▅▄▅▃▄▄██▇▅▆▆▇▆▄▅▅ █
345 ns Histogram: log(frequency) by time 741 ns <
Memory estimate: 336 bytes, allocs estimate: 3.
盡管在大多數數值情況下，兩者在時間和記憶體方面的成本（后者由于需要作業陣列）都比類似有效的純 Julia 實作要多quicksort!：
julia> @benchmark VectorizedStatistics.quicksort!(A) setup = (A = rand(50))
BenchmarkTools.Trial: 10000 samples with 993 evaluations.
Range (min … max): 28.854 ns … 175.821 ns ┊ GC (min … max): 0.00% … 0.00%
Time (median): 35.268 ns ┊ GC (median): 0.00%
Time (mean ± σ): 38.703 ns ± 7.478 ns ┊ GC (mean ± σ): 0.00% ± 0.00%
▂ ▃█▁ ▃▃ ▃▆▂ ▂ ▃ ▂ ▁ ▂ ▂
█▆▃▅▁▁▄▅███▆███▆▆███▁▇█▇▅▇█▆▇█▁▆▅▃▅▄▄██▅▆▅▇▅▄▃▁▄▃▁▄▁▃▃▃▁▄▄▇█ █
28.9 ns Histogram: log(frequency) by time 68.7 ns <
Memory estimate: 0 bytes, allocs estimate: 0.
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409375.html
標籤：