Maximum with a custom ordering

Question

I have a array like the following:

julia> list = [(x, rand(0:9), rand(0:9)) for x in 1:5]
5-element Array{Tuple{Int64,Int64,Int64},1}:
 (1, 7, 2)
 (2, 1, 3)
 (3, 4, 7)
 (4, 4, 8)
 (5, 8, 3)

I'd like to find the element in that list whose third value is greatest. If I just do maximum(list), it uses the default (lexicographic) ordering, which is not what I want:

julia> maximum(list)
(5, 8, 3)

I can use a custom by transformation/predicate if I sort the entire list:

julia> sort(list, by=x->x[3], rev=true)
5-element Array{Tuple{Int64,Int64,Int64},1}:
 (4, 4, 8)
 (3, 4, 7)
 (2, 1, 3)
 (5, 8, 3)
 (1, 7, 2)

But that does a lot of extra work — all I need is that first value — but it appears maximum does not support the by keyword argument:

julia> maximum(list, by=x->x[3])
ERROR: MethodError: no method matching maximum(::Array{Tuple{Int64,Int64,Int64},1}; by=var"#21#22"())

And if I use the "transforming" first argument function, I only get the third value back:

julia> maximum(x->x[3], list)
8

I want the entire element — (4, 4, 8) in this case. How can I do this?

Answer 1

While maximum does not support by keyword, it does support a "transformer" function. In this particular case, we can find the maximum of the reversed elements, and then reverse it back:

julia> reverse(maximum(reverse, list))
(4, 4, 8)

More generally, you can use the sorting infrastructure (with all its fancy by transformers and custom lt comparisons) without actually sorting the entire list with partialsort:

julia> partialsort(list, 1, by=x->x[3], rev=true)
(4, 4, 8)

This isn't quite as efficient but it's far more capable — and it saves quite a bit over sorting the entire thing. With a larger vector:

julia> using BenchmarkTools

julia> list = [(x, rand(0:9), rand(0:9)) for x in 1:10_000];

julia> @btime reverse(maximum(reverse, $list));
  7.833 μs (0 allocations: 0 bytes)

julia> @btime partialsort($list, 1, by=x->x[3], rev=true);
  37.772 μs (3 allocations: 234.48 KiB)

julia> @btime sort($list, by=x->x[3], rev=true);
  339.570 μs (5 allocations: 351.81 KiB)

Answer 2

Another possibility is to use sortperm to get the permutation indices of the reduced array (only containing the keys by which you want to sort), and then use those indices to sort the full array:

a = [(x, rand(0:9), rand(0:9)) for x in 1:5]
perm = sortperm(a, by=x->x[3], rev=true)
b = a[perm]

Or in case you're only interested in the maximum, use

b_max = a[perm[1]]

Or

i_max = findmax(map(x->x[3], a)[2]
b_max = a[i_max]