while-loop schneller als für die Rückkehr Iterator

Question

Ich versuche, dies so weit wie möglich zu vereinfachen.

Funktionen f1 und f2 eine sehr vereinfachte Version eines roulette wheel selection über einen Vektor R implementieren. Der einzige Unterschied zwischen ihnen ist, dass f1 eine für und f2 eine Weile verwendet. Beide Funktionen geben den Index des Arrays zurück, in dem die Bedingung erfüllt war.

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 

jetzt habe ich ein paar Testfunktionen ... M die Anzahl der Male ist, dass wir die Funktion Ausführung wiederholen.

Jetzt ist dies kritisch ... Ich möchte die Werte speichern, die ich von den Funktionen bekomme, weil ich sie später brauche ... Um den Code zu vereinfachen, habe ich gerade eine neue Variable r erstellt, wo ich die Rückgaben von den Funktionen zusammenfasse . So

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 

neben ich:

@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) 

also aus irgendeinem Grund kann ich nicht herausfinden, f1 ordnet eine Menge Speicher und seine noch größer, je größer M bekommt. Ich sagte die Zeile r += a war kritisch, denn wenn ich es aus beiden Testfunktionen entferne, bekomme ich das gleiche Ergebnis mit beiden Tests, also keine Probleme! Also dachte ich, es gibt ein Problem mit dem Typ a, der von den Funktionen zurückgegeben wird (weil f1 den Iterator der for-Schleife zurückgibt, und f2 verwendet eine eigene Variable i "manuell deklariert" innerhalb der Funktion).

Aber ...

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

true 

Also ... was die Hölle los ist ???

Ich entschuldige mich, wenn dies eine Art von grundlegender Frage ist, aber ich habe das jetzt über 3 Stunden durchgegangen und konnte keine Antwort finden ... Auch wenn die Funktionen mit einer While-Schleife behoben werden hasse es nicht zu wissen, was vor sich geht.

Danke.

Answer 1

Wenn Sie viele überraschende Zuordnungen wie diese sehen, ist eine gute erste Sache zu überprüfen type-stability. Die @code_warntype Makro ist sehr hilfreich, hier:

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

Vergleichen Sie das mit f2:

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

Also, warum sind die beiden unterschiedlich? Julia denkt, dass f1 manchmal nothing (die von Typ Void ist) zurückgeben kann! Schauen Sie sich nochmal Ihre f1 Funktion an: Was würde passieren, wenn das letzte Element von X NaN ist? Es wird nur mit einer expliziten Rückgabeanweisung vom Ende der Funktion fallen. In f2 werden Sie jedoch über die Grenzen von X hinaus indexieren und stattdessen einen Fehler erhalten. Korrigieren Sie diese Art der Instabilität, indem Sie entscheiden, was zu tun ist, wenn die Schleife abgeschlossen ist, ohne die Antwort zu finden, und Sie sehen ähnliche Zeiten.

Answer 2

Wie ich im Kommentar erwähnt, enthalten Ihre Funktionen f1 und f2 beide Zufallszahlen darin, und Sie verwenden die Zufallszahlen als Abbruchkriterium. Daher gibt es keinen deterministischen Weg zu messen, welche der Funktionen schneller ist (hängt nicht von der Implementierung ab).

Sie können f1 und f2 Funktionen ersetzen r als Parameter zu übernehmen:

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 

Und dann die Zeit richtig mit dem gleichenR und r für beide Funktionen messen:

>>> 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) 

Wie Sie sehen können, sind die Timings jetzt nahezu identisch.Irgendein Unterschied wird für externe Faktoren verursacht (Erwärmung oder Prozessor beschäftigt mit anderen Aufgaben).