Findmin/max and generators

I noticed the following oddity

println(findmin(identity, x for x in [3, 2, 1]))
println(findmin(identity, x for x in [3, 2, 1] if x != 1))

showing

(1, 3)
ERROR: MethodError: no method matching keys(::Base.Iterators.Filter{var"#9#10", Vector{Int64}})

Do you know an easy fix for this?

This seems to fix the issue:

julia> import Base: keys

julia> keys(itr::Base.Iterators.Filter) = Iterators.map(first, enumerate(itr))

julia> println(findmin(identity, x for x in [3, 2, 1] if x != 1))
(2, 2)

Might be a good idea to make an appropriate change in Base. Not sure this fix is ideal (as iterator might be cycled twice during findmin which is bad for heavy iterations)

1 Like

This update, moves the fix up the call chain and prevents the double cycling of iterator. On the other hand, I’m not familiar enough with other side-effects this fix might have.

julia> import Base: pairs

julia> pairs(g::Base.Generator{T,I}) where {T<:Base.Iterators.Filter, I} =
         Iterators.map(((i,v),) -> i=>v, enumerate(g.iter))
pairs (generic function with 11 methods)

julia> findmin(x for x in [3,2,1] if x != 1)
(2, 2)
1 Like

adding parens works

julia> findmin(identity, (x for x in [3, 2, 1] if x != 1))
(2, 2)

@Dan: to make this work for

@btime findmin(x * x for x in (3, 2, 1) if x != 1)

I had to use

Base.pairs(g::Base.Generator{I,F}) where {I<:Base.Iterators.Filter, F<: Function} = Iterators.map(=>, 1:typemax(Int), g)

To all: thanks for your help!

You shouldn’t be using findmin here, but instead minimum.

findmin returns a tuple of the minimum value and its index in the collection or iterator. If you pass to it a filtered iterator, the index is meaningless, so it rightly throws a fit. Thus, to get it to work, you’re forced to collect all the iterator’s values into memory as a tuple or array first before calling findmin on it.

minimum simply returns the minimum value without concern for what its index in the collection or iterator is, so you can freely pass filtered iterators to it.

julia> minimum(x^2 for x ∈ (3, 2, 1) if x ≠ 1)
4
1 Like

@uniment is right. It is important to get the semantics accurately.
Perhaps what we are looking for is:

julia> minimum(x => x * x for x in (6,5,4) if x != 4)
5 => 25

The confusing bit is that above expression calculates the mathematical argmin of the expression x^2 in the set. The Julia argmin function calculates the minimum and its index, which is the mathematical argmin of function i -> val[i]

This is incorrect; this code is not calculating the argmin, but instead the minimum argument.

If you’re using findmin because you’re hoping to find both the minimum squared value and its index, for any value not equal to 1, then this is likely what you’re looking for:

julia> findmin(x==1 ? Inf : x^2 for x ∈ (4, 3, 2, 1))
(4, 3)

Again @uniment , you are right. A Pair is ordered by key first and value later. Somehow I had assumed it was ordered by value first. To get the result I wanted:

julia> minimum((x * x, x) for x in (6,5,4) if x != 4)
(25, 5)

which is the same output, but gets things right when function is not order preserving.

1 Like
julia> findmin(x==1 ? Inf : x^2 for x ∈ (4, 3, 2, 1))
(4, 3)

This is:
a. not type stable.
b. the second tuple number is somewhat useless, you would want the value of x for an argmin of the function x^2.

1 Like

Not type stable just because the generator iterates both ints and floats. Replace x^2 by x^2.0 and it becomes stable.

julia> findmin(x==1 ? typemax(x) : x^2 for x ∈ (4, 3, 2, 1))
(4, 3)

(x^2.0 is much slower than x^2).

2 Likes

Not here:

julia> findmin(identity, (x for x in [3, 2, 1] if x != 1))
ERROR: MethodError: no method matching keys(::Base.Iterators.Filter{var"#23#24", Vector{Int64}})

Anyway, I think the original question is well worth an issue. I don’t see why it shouldn’t work. (did it here)

3 Likes