Wie finde ich den Index des letzten Maximums in juliallang?

Question

Ich habe ein Array, das wiederholte nichtnegative Ganzzahlen enthält, z. B. A=[5,5,5,0,1,1,0,0,0,3,3,0,0]. Ich möchte die Position des letzten Maximums in A finden. Das ist der größte Index i, so dass A[i]>=A[j] für alle j. In meinem Beispiel i=3.

Ich habe versucht, die Indizes aller maximal A dann das Maximum dieser Indizes finden zu finden:

A = [5,5,5,0,1,1,0,0,0,3,3,0,0]; 
Amax = maximum(A); 
i = maximum(find(x -> x == Amax, A)); 

Gibt es einen besseren Weg?

Answer 1

length(A) - indmax(@view A[end:-1:1]) + 1 

sollte ziemlich schnell sein, aber ich habe es nicht Benchmark.

EDIT: Ich sollte beachten, dass per Definition @crstnbr 's Lösung (um den Algorithmus von Grund auf neu schreiben) ist schneller (wie viel schneller ist in Xiaodai Antwort gezeigt). Dies ist ein Versuch, dies mit den eingebauten Array-Funktionen von Julia zu tun.

Answer 2

Was ist mit findlast(A.==maximum(A)) (was ist natürlich konzeptionell ähnlich zu Ihrem Ansatz)?

Die schnellste Sache wäre wahrscheinlich explizite Schleife Umsetzung wie folgt aus:

function lastindmax(x) 
    k = 1 
    m = x[1] 
    @inbounds for i in eachindex(x) 
     if x[i]>=m 
      k = i 
      m = x[i] 
     end 
    end 
    return k 
end 

Answer 3

Michaels Lösung unterstützt keine Strings (ERROR: MethodError: no method matching view(::String, ::StepRange{Int64,Int64})) oder Sequenzen so dass ich eine andere Lösung hinzu:

julia> lastimax(x) = maximum((j,i) for (i,j) in enumerate(x))[2] 
julia> A="abžcdž"; lastimax(A) # unicode is OK 
6 
julia> lastimax(i^2 for i in -10:7) 
1 

Wenn Sie mehr wie keine Ausnahme für leere Sequenz fangen:

julia> lastimax(x) = !isempty(x) ? maximum((j,i) for (i,j) in enumerate(x))[2] : 0; 
julia> lastimax(i for i in 1:3 if i>4) 
0 

Einfach (!) Benchmarks:

Dies ist bis zu 10 mal langsamer als Michael-Lösung für Float64:

julia> mlastimax(A) = length(A) - indmax(@view A[end:-1:1]) + 1; 
julia> julia> A = rand(Float64, 1_000_000); @time lastimax(A); @time mlastimax(A) 
    0.166389 seconds (4.00 M allocations: 91.553 MiB, 4.63% gc time) 
    0.019560 seconds (6 allocations: 240 bytes) 
80346 

(Ich bin überrascht), ist es 2-mal schneller für Int64!

julia> A = rand(Int64, 1_000_000); @time lastimax(A); @time mlastimax(A) 
    0.015453 seconds (10 allocations: 304 bytes) 
    0.031197 seconds (6 allocations: 240 bytes) 
423400 

es ist 2-3 mal langsamer für Strings

julia> A = ["A$i" for i in 1:1_000_000]; @time lastimax(A); @time mlastimax(A) 
    0.175117 seconds (2.00 M allocations: 61.035 MiB, 41.29% gc time) 
    0.077098 seconds (7 allocations: 272 bytes) 
999999 

EDIT2: @crstnbr Lösung ist schneller und arbeitet mit Strings zu (nicht mit Generatoren arbeiten).Es Unterschied zwischen lastindmax und lastimax - ersten Rück Byte-Index, zweiter Rückzeichenindex:

julia> S = "1š3456789ž" 
julia> length(S) 
10 
julia> lastindmax(S) # return value is bigger than length 
11 
julia> lastimax(S) # return character index (which is not byte index to String) of last max character 
10 

julia> S[chr2ind(S, lastimax(S))] 
'ž': Unicode U+017e (category Ll: Letter, lowercase) 

julia> S[chr2ind(S, lastimax(S))]==S[lastindmax(S)] 
true 

Answer 4

Ich versuchte @ Michael-Lösung und @ crstnbr-Lösung und ich fand diese viel schneller

a = rand(Int8(1):Int8(5),1_000_000_000) 

@time length(a) - indmax(@view a[end:-1:1]) + 1 # 19 seconds 
@time length(a) - indmax(@view a[end:-1:1]) + 1 # 18 seconds 


function lastindmax(x) 
    k = 1 
    m = x[1] 
    @inbounds for i in eachindex(x) 
     if x[i]>=m 
      k = i 
      m = x[i] 
     end 
    end 
    return k 
end 

@time lastindmax(a) # 3 seconds 
@time lastindmax(a) # 2.8 seconds