`findmax` bug?

Usage
#1

On Julia v0.6.4 the following worked, but no longer on v0.7, v1.0.x and v1.1.0:

a = rand(3)
findmax( a[j] for j = 1:3 )

results in

ERROR: MethodError: no method matching keys(::Base.Generator{UnitRange{Int64},getfield(Main, Symbol("##13#14"))})
Closest candidates are:
  keys(::Cmd) at process.jl:940
  keys(::Core.SimpleVector) at essentials.jl:570
  keys(::Tuple) at tuple.jl:46
  ...
Stacktrace:
 [1] pairs(::Base.Generator{UnitRange{Int64},getfield(Main, Symbol("##13#14"))}) at ./abstractdict.jl:132
 [2] _findmax(::Base.Generator{UnitRange{Int64},getfield(Main, Symbol("##13#14"))}, ::Colon) at ./array.jl:2052
 [3] findmax(::Base.Generator{UnitRange{Int64},getfield(Main, Symbol("##13#14"))}) at ./array.jl:2049
 [4] top-level scope at none:0

Bug or intended behaviour? What makes me wonder whether it is a bug is that replacing findmax with maximum works as expected.

But maybe it isn’t a bug then I suppose the issue is that I’m passing a generator instead of a collection. How do I convert a generator into a collection? I am not sure what to look for in the documentation…

#2

Enclose the generator inside square brackets []:

julia> findmax( [A[j] for j = 1:3] )
(0.5601650744483095, 1)

(note that you have small-caps ‘a’ in stead of a capital ‘A’ in your example)

#3

Using collect, or as @yakir12 showed with a comprehension.

However, this is a bit odd as running the code in Julia 0.7 does not give a deprecation warning. I don’t know whether this was removed on purpose (and the deprecation was forgotten) or not (and it’s just a bug).

#4

Sort about the typo - will fix momentarily.

I don’t want to use collect or since Inwant to avoid the allocation.

#5

Generators don’t really have indices so what would this return? You can do something like:

julia> maximum( (a[j], j) for j=1:3)
(0.7026710903900824, 3)

to get the number of times the iterator iterated to find the max (and the value).

3 Likes
#6

If you have a non-indexable iterator (which I presume might be the case since you’re using a generator?), the above solution won’t work:

julia> itr = Iterators.drop(rand(10), 0);

julia> maximum((itr[j], j) for j=1:length(itr))
ERROR: MethodError: no method matching getindex(::Base.Iterators.Drop{Array{Float64,1}}, ::Int64)

In that case, you can use the following (largely allocation free, and about the same performance):

julia> maximum(reverse, Iterators.enumerate(itr))
(0.9338279491162726, 6)
2 Likes
#7

I’m not sure if I understand you correctly, but why not simply findmax(a)? It is so fast and doesn’t allocate.

julia> a = rand(3)
3-element Array{Float64,1}:
 0.19843206660329815
 0.1534497798559591
 0.4435263304297765

julia> @btime findmax($a)
  8.467 ns (0 allocations: 0 bytes)
(0.4435263304297765, 3)
#8

Did you read the first post? It shows that findmax doesn’t work for a generator.

#9

As @kristoffer.carlsson points out, this is just an MWE. Suppose I have a non-trivial generator, and I really want to avoid allocations (e.g. in a hot inner loop). Further, my main confusion is that maximum accepts the generator as an argument but findmax does not. So far nobody has offered a justification for this, so I am beginning to think this must be a bug.

#10

interesting, but very ugly :slight_smile:

#11

As Kristoffer said, generators in general don’t have indices (there’s no method getindex for generators) so findmax, which would return an index, doesn’t really make sense here.

#12

thanks for pressing the point - I had completely missed it on my first reading. I guess that makes perfect sense then…

#13

What do you think is ugly about it? To be clear, the drop part was just a way to simulate a non-indexable iterator, it’s not part of finding the maximum. The reverse is there to swap around the tuple arguments, completely allocation free. The performance should be about the same as Kristoffer’s solution, but works with any iterator, not just those that you can index into (which I presume could be the case if you’re using the generator form?).

julia> a = rand(1_000_000);

julia> @btime maximum(($a[j], j) for j=1:length($a))
  2.487 ms (2 allocations: 48 bytes)
(0.9999989093229165, 50243)

julia> @btime maximum(reverse, Iterators.enumerate($a))
  2.465 ms (1 allocation: 16 bytes)
(0.9999989093229165, 50243)
1 Like
#14

I think this is the same as https://github.com/JuliaLang/julia/issues/23680

1 Like
#15

I just can’t parse it - it’s a bit too functional for my taste, but I appreciate that it is a matter of taste.