Find minimum argument with custom comparator

General Usage
1

I feel like something is missing from the available minimum functions. I’ve come across the issue multiple times where i want to get the value of a collection that gives the minimum value of a specified function. i.e. I want to specify my own comparator.

  • min returns the smallest value in a collection (or the arguments). I assume comparison is done by isless. I guess I could overload isless but that seems heavy-handed for a one-time minimisation.
  • minimum also finds the smallest value in a collection. It also provides a method minimum(f, itr) which returns the smallest result of calling f on itr. This is close, but it returns the minimum value of f, not the value of itr that gives the value of f
  • argmin returns the index of the smallest element, which is helpful, but again doesn’t allow specifying a custom comparator.

So far I’ve been solving this with the below function, but this seems like it might be something that already exists elsewhere.

julia> minimumby(f, itr) = itr[argmin(map(f, itr))]
julia> minimumby(x->x^2, [-2, 1, 2, 3, 4])
1

Am I missing something? Is this the correct way to do this?

Alternatively, is there a way to specify a temporary method for isless that will only be visible within scope?

2 Likes
2

I have seen this raise elsewhere, I suspect a PR to Julia Base would be accepted. Seems like an oversight or lack of time rather than anything else.

For your special-case the more archaic partialsort would also work

x = [-2, 1, 2, 3, 4]

partialsort(x, 1, by = x->x^2)

Another interesting way is via

struct XX
    x
end

Base.isless(x::XX, y::XX) = isless(x.x^2, y.x^2)
Base.isless(x::XX, y) = isless(x.x^2, y)

minimum(XX.(x))

But not very practical

3

One downside of partialsort is that it will copy the whole of x which may be expensive.

sort (and it’s derivatives) accepts keyword arguments to specify the functions used for ordering, perhaps minimum/maximum should as well.

4

The current map approach also copies

5

Found a better approach via mapped arrays

x = Int.(rand(Int8, 100_000_000))

using BenchmarkTools
using MappedArrays

minimumby_orig(f, itr) = itr[argmin(map(f, itr))]
minimumby(f, x) = x[argmin(mappedarray(f, x))]
f(x) = x^2

@benchmark minimumby_orig(f, x)
@benchmark minimumby(f, x)
6

It seems like a missing feature: I think argmin(f, iter) and findmin(f, iter) should be defined. You can avoid the temporary allocation of map(f, itr) using MappedArrays, as suggested by @xiaodai.

You can also implement the function yourself, as it is quite straightforward (remember, your functions in Julia can be as fast as built-in ones).

There are some fun ways to achieve what you want, too:

reduce([-2, -1, 2, 3, 4]) do x, y
	by = x -> x ^ 2
	by(x) < by(y) ? x : y
end

although function by is executed more times than needed (which should be avoided if by is expensive).

Another way is:

minimum([-2, -1, 2, 3, 4]) do x
	by = x -> x ^ 2
	by(x), x
end[2]

this works because Tuples are compared lexicographically:

julia> (1, 2) < (2, 1)
true

In these examples I’m not considering the case when f(a) == f(b) for a ≠ b. Also, you may need to adapt these examples if you have special values such as NaN.

7

There’s also partialsort!, for in-place sorting.

1 Like