julia - How to find the key for the min/max value of a Dict?

Question

I want to find the key corresponding to the min or max value of a dictionary in julia. In Python I would to the following:

my_dict = {1:20, 2:10}
min(my_dict, my_dict.get)

Which would return the key 2.

How can I do the same in julia ?

my_dict = Dict(1=>20, 2=>10)
minimum(my_dict)

The latter returns 1=>20 instead of 2=>10 or 2.

Vedi

indmin() or findmin() should work. Don't know why minimum() does the wrong thing... – Nad

findmin doesn't work actually; it even gives a strange result in this case: (1=>20,16) – Oxyacetylene

@DavidP.Sanders Strange, I get (10,2). – Nad

@Nad minimum iterates Pairs, which compare lexicographically. Therefore, and because here the keys are unique, minimum(x) returns the contained Pair with the lowest key. And indmin returns the index, which is different from the key. – Smoulder

There is now an issue about this in the Julia repo: github.com/JuliaLang/julia/issues/14672 – Chaise

Answer 1

another option is:

collect(keys(d))[indmin(collect(values(d)))]

it depends on properties of keys and values iterators which are not guaranteed, but in fact work for Dicts (and are guaranteed for OrderedDicts). like the reduce answer, d must be non-empty.

why mention this, when the reduce, pretty much nails it? it is 3 to 4 times faster (at least on my computer) !

Slapdash

I think it should be guaranteed that the keys and values iterator return elements in the same order. The order itself is undefined, but it'd be pretty crazy if they did something different from each other. – Crept

@MattB I don't think you should rely on this. As long as it's not documented, this is an implementation detail. But I agree that this should be guaranteed. – Smoulder

Let's document it, then. Care to submit a pull request? – Crept

This can be written without the collects, which will presumably be much faster: d.keys[indmin(values(d))]. However, d.keys is an internal data structure. – Oxyacetylene

Is the inner collect() needed? I think this would work too: collect(keys(d))[indmin(values(d))] ;P – Endmost

necroedit: As of Julia 1.0, indmin() is argmin(). – Nad

Answer 2

You could use reduce like this, which will return the key of the first smallest value in d:

reduce((x, y) -> d[x] ≤ d[y] ? x : y, keys(d))

This only works for non-empty Dicts, though. (But the notion of the “key of the minimal value of no values” does not really make sense, so that case should usually be handled seperately anyway.)

---

Edit regarding efficiency.

Consider these definitions (none of which handle empty collections)...

m1(d) = reduce((x, y) -> d[x] ≤ d[y] ? x : y, keys(d))

m2(d) = collect(keys(d))[indmin(collect(values(d)))]

function m3(d)
  minindex(x, y) = d[x] ≤ d[y] ? x : y
  reduce(minindex, keys(d))
end

function m4(d)
  minkey, minvalue = next(d, start(d))[1]
  for (key, value) in d
    if value < minvalue
      minkey = key
      minvalue = value
    end
  end
  minkey
end

...along with this code:

function benchmark(n)
  d = Dict{Int, Int}(1 => 1)
  m1(d); m2(d); m3(d); m4(d); m5(d)

  while length(d) < n
    setindex!(d, rand(-n:n), rand(-n:n))
  end

  @time m1(d)
  @time m2(d)
  @time m3(d)
  @time m4(d)
end

Calling benchmark(10000000) will print something like this:

1.455388 seconds (30.00 M allocations: 457.748 MB, 4.30% gc time)
0.380472 seconds (6 allocations: 152.588 MB, 0.21% gc time)
0.982006 seconds (10.00 M allocations: 152.581 MB, 0.49% gc time)
0.204604 seconds

From this we can see that m2 (from user3580870's answer) is indeed faster than my original solution m1 by a factor of around 3 to 4, and also uses less memory. This is appearently due to the function call overhead, but also the fact that the λ expression in m1 is not optimized very well. We can alleviate the second problem by defining a helper function like in m3, which is better than m1, but not as good as m2.

However, m2 still allocates O(n) memory, which can be avoided: If you really need the efficiency, you should use an explicit loop like in m4, which allocates almost no memory and is also faster.

Smoulder

a version without unicode and working for empty Dicts: reduce((x, y) -> (isa(x,Void) || (d[x] > d[y])) ? y : x, nothing, keys(d)) – Slapdash

Very nice comparison. I like the use of next to get the first value in the dictionary, even if the syntax is not elegant! – Oxyacetylene

d.keys[indmin(values(d))] is very slightly slower than the explicit loop, but 3 times faster than the other short options. (However, d.keys is an internal data structure.) – Oxyacetylene

Any idea, why isn't m4 part of any julia library? – Timid

Answer 3

Here is another way to find Min with Key and Value

my_dict = Dict(1 => 20, 2 =>10)

findmin(my_dict) gives the output as below

(10, 2)

to get only key use

findmin(my_dict)[2]

to get only value use

findmin(my_dict)[1]

Hope this helps.

Thielen

Answer 4

If you only need the minimum value, you can use

minimum(values(my_dict))

If you need the key as well, I don't know a built-in function to do so, but you can easily write it yourself for numeric keys and values:

function find_min_key{K,V}(d::Dict{K,V})

    minkey = typemax(K)
    minval = typemax(V)

    for key in keys(d)
        if d[key] < minval
            minkey = key
            minval = d[key]
        end
    end

    minkey => minval
end

my_dict = Dict(1=>20, 2=>10)

find_min_key(my_dict)

Oxyacetylene

(I have removed my other comment as it is now obsolete.) But doesn't this have type-stability problems as well, for instance if d::Dict{Int, Int}? Isn't then the comparison between Int and either Int or Float? Am I missing something? – Smoulder

Ah, I see what you mean. I thought you meant that the output of the function was not type stable, but you mean that minkey and minval change type during the function. I'll give it another go... – Oxyacetylene

Thanks. Fixed to use typemax. This will work for any numeric types, but not e.g. for any kind of Strings. It's surprisingly difficult to make this general! The reduce solution does work for that case, though. – Oxyacetylene

Agreed, this is why I only consider the non-empty case in my solution ;). – Smoulder

Answer 5

findmax(dict)[2]
findmin(dict)[2]

Should also return the key corresponding to the max and min value(s). Here [2] is the index of the key in the returned tuple.

Hilarity