Python: obtener la clave con el menor valor de un diccionario PERO múltiples valores mínimos

Question

Estoy tratando de hacer lo mismo que Get the key corresponding to the minimum value within a dictionary, donde queremos obtener la clave correspondiente al valor mínimo en un diccionario.

La mejor manera parece ser:

min(d, key=d.get) 

PERO Quiero aplicar esto en un diccionario con múltiples valores mínimos:

d = {'a' : 1, 'b' : 2, 'c' : 1} 

Tenga en cuenta que la respuesta de lo anterior sería :

>>> min(d, key=d.get) 
'a' 

Sin embargo, necesito ambos las dos claves que tienen un valor mínimo, a saber a y c.

¿Cuál sería el mejor enfoque?

(En última instancia, quiero elegir uno de los dos al azar, pero no creo que esto sea relevante).

Answer 1

Una opción sencilla es determinar primero el valor mínimo, y luego seleccione todas las claves de asignación a ese mínimo:

min_value = min(d.itervalues()) 
min_keys = [k for k in d if d[k] == min_value] 

Para Python 3 d.values() uso en lugar de d.itervalues().

Esto necesita dos pasadas a través del diccionario, pero debería ser una de las opciones más rápidas para hacer esto de todos modos.

Usando reservoir sampling, se puede implementar un enfoque único pase que selecciona uno de los elementos al azar:

it = d.iteritems() 
min_key, min_value = next(it) 
num_mins = 1 
for k, v in it: 
    if v < min_value: 
     num_mins = 1 
     min_key, min_value = k, v 
    elif v == min_value: 
     num_mins += 1 
     if random.randrange(num_mins) == 0: 
      min_key = k 

Después de escribir el código, creo que esta opción es de interés más bien teórica ... :)

Answer 2

def get_rand_min(d): 
    min_val = min(d.values()) 
    min_keys = filter(lambda k: d[k] == min_val, d) 
    return random.choice(min_keys) 

Answer 3

Puede usar heapq.nsmallest para obtener los N miembros más pequeños del dict y luego filtrar todos los que no sean iguales al más bajo. Eso es siempre que conozcas la cantidad máxima de miembros más pequeños que puedas tener, supongamos que es N aquí. algo así como:

from heapq import nsmallest 
from operator import itemgetter 

#get the N smallest members 
smallestN = nsmallest(N, myDict.iteritems(), itemgetter(1))) 

#leave in only the ones with a score equal to the smallest one 
smallest = [x for x in smallestN if x[1] == smallestN[0][1]] 

Answer 4

Esto funciona:

d = {'a' :1, 'b' : 2, 'c' : 1} 
min_value = min(d.values()) 
result = [x[0] for x in d.items() if x[1] == k] 

Hmpf. Después de fijar el código para trabajar, que terminó con la respuesta de @Sven Marnach, así, pasar por alto esta;)

Answer 5

minValue,minKey = min((v,k) for k,v in d.items()) 

Debido a sus semántica tiene que ir a través de todo el diccionario al menos una vez. Esto recuperará exactamente 1 elemento mínimo.

Si desea todos los elementos mínimos en el tiempo de consulta O (log (N)), puede insertar sus elementos en una cola de prioridad a medida que los genera (si es posible). La cola de prioridad debe tener O (1) tiempo de inserción y O (log (N)) tiempo de extracción-min. (Esto será tan malo como ordenar si todos sus elementos tienen el mismo valor, pero de lo contrario puede funcionar bastante bien.)

Answer 6

EDITADO: Ahora, utilizando setdefault como se sugiere :)

No sé si eso le ayuda, pero se podría construir un diccionario inversa con los valores como clave y las claves (en una lista como valores)

d = {'a' : 1, 'b' : 2, 'c' : 1} 
d2 = {} 
for k, v in d.iteritems(): 
    d2.setdefault(v, []).append(k) 
print d2[min(d2)] 

Se imprimirá la siguiente:

['a', 'c'] 

Sin embargo, creo que las otras soluciones son más compactos y, probablemente, más elegante ...

Answer 7

min_keys = [k for k in d if all(d[m] >= d[k] for m in d)] 

o, ligeramente optimizado

min_keys = [k for k, x in d.items() if not any(y < x for y in d.values())] 

No es tan eficiente s otras soluciones, pero demuestra la belleza de Python (bueno, al menos para mí).

Answer 8

Ésta es otra manera de hacerlo en una sola pasada:

d = {'foo': 2, 'a' : 1, 'b' : 2, 'c' : 1, 'z': 99, 'x': 1} 
current_min = d[d.keys()[0]] 
min_keys = [] 
for k, v in d.iteritems(): 
    if v < current_min: 
     current_min = v 
     min_keys = [k] 
    elif v == current_min: 
     min_keys.append(k) 
print min_keys 
['a', 'x', 'c'] 

Answer 9

Una solución pase sería:

>>> result = [100000, []] 
>>> for key, val in d.items(): 
... if val < result[0]: 
... result[1] = [key]; result[0]=val; 
... elif val == result[0]: 
... result[1].append(key) 
... 
>>> result 
[1, ['a', 'c']]