while循環比返回迭代器時更快

Question

我試圖儘可能地簡化它。

功能f1和f2通過Vector R執行roulette wheel selection的非常簡化版本。他們之間的唯一區別是，f1一段時間使用一個for和f2。這兩個函數都返回符合條件的數組的索引。

R=rand(100)

function f1(X::Vector) 
    l = length(X) 
    r = rand()*X[l] 
    for i = 1:l 
     if r <= X[i] 
      return i 
     end 
    end  
end 

function f2(X::Vector) 
    l = length(X) 
    r = rand()*X[l] 
    i = 1 
    while true 
     if r <= X[i] 
      return i 
     end 
     i += 1 
    end  
end 

現在我創建了幾個測試功能... M是的次數，我們重複此函數執行。

現在這是至關重要的...我想存儲我從函數中得到的值，因爲我稍後需要它們...爲了簡化代碼，我剛剛創建了一個新變量r，其中我總結了函數的返回值。

function test01(M,R) 
    cumR = cumsum(R) 
    r = 0 
    for i = 1:M 
     a = f1(cumR) 
     r += a 
    end 
    return r 
end 

function test02(M,R) 
    cumR = cumsum(R) 
    r = 0 
    for i = 1:M 
     a = f2(cumR) 
     r += a 
    end 
    return r 
end 

所以，下次我得到：

@time test01(1e7,R) 
elapsed time: 1.263974802 seconds (320000832 bytes allocated, 15.06% gc time) 

@time test02(1e7,R) 
elapsed time: 0.57086421 seconds (1088 bytes allocated) 

所以，由於某種原因，我無法弄清楚f1分配存儲了很多，它的更大的較大M得到。 我說行r += a是至關重要的，因爲如果我從兩個測試函數中刪除它，我得到了與兩個測試相同的結果，所以沒有問題！所以我認爲函數返回a的類型有問題（因爲f1返回for循環的迭代器，並且f2在函數內部使用自己的變量i「手動聲明」）。

但是......

aa = f1(cumsum(R)) 
bb = f2(cumsum(R)) 
typeof(aa) == typeof(bb) 

true 

所以......那是什麼到底是怎麼回事???

我很抱歉，如果這是一個基本的問題，但是，我已經超過了3個多小時，現在無法找到答案...即使函數是通過使用while循環討厭不知道發生了什麼事。

謝謝。

Answer 1

當你看到很多令人驚訝的分配時，首先需要檢查的是type-stability。該@code_warntype宏是非常有幫助的位置：

julia> @code_warntype f1(R) 
# … lots of annotated code, but the important part is this last line: 
    end::Union{Int64,Void} 

與此相比，f2：

julia> @code_warntype f2(R) 
# ... 
    end::Int64 

那麼，爲什麼是兩個不同的？朱莉婭認爲f1有時可能會返回nothing（這是Void類型）！再看看你的f1函數：如果X的最後一個元素是NaN會發生什麼？它只會在函數的末尾沒有顯式的return語句。然而，在f2中，您將最終編制超出X範圍的索引，而不是獲得錯誤。通過決定如果循環完成而沒有找到答案要做什麼來解決這種類型不穩定問題，您將看到更多類似的時間。

Answer 2

正如我在評論中所述，您的函數f1和f2都包含隨機數字，並且您將隨機數用作停止標準。因此，沒有確定性的方法來測量哪個函數更快（不依賴於實現）。

可以更換f1和f2功能接受r作爲參數：

function f1(X::Vector, r) 
    for i = 1:length(X) 
     if r <= X[i] 
      return i 
     end 
    end  
end 

function f2(X::Vector, r) 
    i = 1 
    while i <= length(X) 
     if r <= X[i] 
      return i 
     end 
     i += 1 
    end  
end 

然後用相同R和r兩個功能正常測量時間：

>>> R = cumsum(rand(100)) 
>>> r = rand(1_000_000) * R[end] # generate 1_000_000 random thresholds 

>>> @time for i=1:length(r); f1(R, r[i]); end; 
0.177048 seconds (4.00 M allocations: 76.278 MB, 2.70% gc time) 

>>> @time for i=1:length(r); f2(R, r[i]); end; 
0.173244 seconds (4.00 M allocations: 76.278 MB, 2.76% gc time) 

如你所見，時間現在幾乎相同。任何差異都會導致外部因素（變暖或處理器忙於其他任務）。