julia - Come trovare la chiave per il valore minimo/massimo di un Dict?

Question

Voglio trovare la chiave corrispondente al valore minimo o massimo di un dizionario in julia. In Python lo farei al seguente:

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

Che sarebbe restituire la chiave 2.

Come posso fare lo stesso in julia?

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

Quest'ultima restituisce 1 => 20 invece di 2 => 10 o 2.

Answer 1

un'altra opzione è:

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

dipende proprietà di chiavi e valori iteratori non garantite, ma nel lavoro fatto per Dicts (e sono garantito per OrderedDicts). come la risposta reduce, d deve essere non vuoto.

perché menzionare questo, quando il reduce, praticamente unghie esso? è da 3 a 4 volte più veloce (almeno sul mio computer)!

Answer 2

Se avete solo bisogno il valore minimo, è possibile utilizzare

minimum(values(my_dict)) 

Se avete bisogno della chiave così, non so una funzione built-in di farlo, ma si può facilmente scrivere voi stessi per le chiavi e valori numerici:

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) 

Answer 3

si potrebbe noi e reduce come questo, che restituirà la chiave del primo valore più piccolo d:

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

Questo funziona solo per non vuote Dict s, però. (Ma la nozione di “chiave del valore minimo di nessun valore” non ha molto senso, in modo che di solito caso dovrebbe essere gestita separatamente in ogni caso.)

---

Modifica per quanto riguarda l'efficienza.

considerare queste definizioni (nessuno dei quali gestisce collezioni vuote) ...

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 

... con questo codice:

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) stamperà qualcosa di simile:

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 

Da questo possiamo vedere che m2 (da user3580870's answer) è effettivamente più veloce della mia soluzione originale m1 da un fattore di circa 3 a 4 e utilizza anche meno memoria. Ciò è apparentemente dovuto alla funzione di overhead delle chiamate, ma anche al fatto che l'espressione λ in m1 non è ottimizzata molto bene. Siamo in grado di alleviare il secondo problema definendo una funzione di supporto come in m3, che è meglio di m1, ma non buono come m2.

Tuttavia, m2 assegna ancora O (n) memoria, che può essere evitato: se si ha realmente bisogno l'efficienza, è necessario utilizzare un ciclo esplicito come in m4, che assegna quasi nessun memoria ed è anche più veloce.