CODEWITHSUNDEEP
julia
Ribz
Ribz

Reputation: 551

How to find the index of the last maximum in julialang?

I have an array that contains repeated nonnegative integers, e.g., A=[5,5,5,0,1,1,0,0,0,3,3,0,0]. I would like to find the position of the last maximum in A. That is the largest index i such that A[i]>=A[j] for all j. In my example, i=3.

I tried to find the indices of all maximum of A then find the maximum of these indices:

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

Is there any better way?

Upvotes: 3

Views: 1204

Answers (4)

Michael K. Borregaard
Michael K. Borregaard

Reputation: 8044

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

should be pretty fast, but I didn't benchmark it.

EDIT: I should note that by definition @crstnbr 's solution (to write the algorithm from scratch) is faster (how much faster is shown in Xiaodai's response). This is an attempt to do it using julia's inbuilt array functions.

Upvotes: 5

Liso
Liso

Reputation: 2260

Michael's solution doesn't support Strings (ERROR: MethodError: no method matching view(::String, ::StepRange{Int64,Int64})) or sequences so I add another solution:

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

If you more like don't catch exception for empty Sequence:

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

Simple(!) benchmarks:

This is up to 10 times slower than Michael's solution for 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

(I am surprised) it is 2 times faster for 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

it is 2-3 times slower for 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 solution is faster and works with Strings too (doesn't work with generators). There difference between lastindmax and lastimax - first return byte index, second return character index:

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

Upvotes: 3

xiaodai
xiaodai

Reputation: 16014

I tried @Michael's solution and @crstnbr's solution and I found the latter much faster

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

Upvotes: 3

carstenbauer
carstenbauer

Reputation: 10127

What about findlast(A.==maximum(A)) (which of course is conceptually similar to your approach)?

The fastest thing would probably be explicit loop implementation like this:

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

Upvotes: 4

Related Questions