How to find the index of the maximum over a subset of elements in julialang?

Question

I have an array A=[3, 5, 1, 2, 7, 9, 10, 2, 3] of length length(A)=9 and a set S that contains a subset of the indices 1:9, e.g., S=Set([1, 3, 6, 8]). I would like to find the maximum (the value and the index) of A over S. That is, the maximum is 9 and the index is 6.

I tried to do it this way

A = [3, 5, 1, 2, 7, 9, 10, 2, 3];
S = Set([1, 3, 6, 8]);
B = [if i in S A[i] else 0 end for i in 1:length(A)];
findmax(B);

but I feel like there is a better and clever way.

Answer 1

How about?

julia> maximum((A[i],i) for i in S)
(9, 6)

This relies on the fact that tuples are sorted in lexicographical order. This only iterates over the subset, so it should be faster when S has significantly fewer elements than A.

maximum is a better choice than findmax here as Dan Getz pointed out.

Answer 2

This is more verbose, but on my computer roughly 2.5x as fast as the generator solution (version 0.6):

function mymax(A, S)
    val, ind = typemin(eltype(A)), -1
    for i in S
        val_ = A[i]
        if val_ > val
            val, ind = val_, i
        end
    end
    return val, ind
end

Answer 3

If A would contain no duplicates (or at least, the maximum were unique), I'd find the following more readable:

julia> i = findfirst(A, maximum(A[i] for i in S))
6
julia> A[i], i
(9, 6)

The maximum works on a generator, so there should be no memory overhead. If S is small, the size of A dominates, and you have to traverse that anyway.

Answer 4

In case there is more maximums you could do:

function maximums(A,S) 
    maxvalue = maximum(A[i] for i in S)
    (maxvalue, [i for i in S if A[i]==maxvalue])
end

A = [3,3,3]
S = Set([1,3])
maximums(A, S)  # (3, [3, 1])

If you like to preserve order and Set is not necessary type for S then you could use unique function:

S = unique([1,3])
maximums(A, S)  # (3, [1, 3])