Python: получить ключ с наименьшим значением из словаря, НО несколько минимальных значений

Question

я пытаюсь сделать так же, как Получить ключ, соответствующий минимальному значению в словаре , где мы хотим получить ключ, соответствующий минимальному значению в словаре.

Лучший способ выглядит так:

min(d, key=d.get)

НО Я хочу применить это к словарю с несколькими минимальными значениями:

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

Обратите внимание, что ответ из приведенного выше будет:

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

Однако мне нужны оба два ключа, которые имеют минимальное значение, а именно a и c.

Какой будет лучший подход?

(В конечном итоге я хочу выбрать один из двух случайным образом, но я не думаю, что это уместно).

Answer 1

Один простой вариант - сначала определить минимальное значение, а затем выбрать все ключи, соответствующие этому минимуму:

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

Для Python 3 используйте d.values() вместо d.itervalues().

Для этого требуется два прохода по словарю, но в любом случае это должен быть один из самых быстрых способов сделать это.

Используя отбор проб резервуара , вы можете реализовать подход с одним проходом, который выбирает один из следующих вариантов:случайные элементы:

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

После записи этого кода, я думаю, этот вариант представляет довольно теоретический интерес ...:)

Answer 2

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

или, слегка оптимизированный

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

Это не так эффективно, как другие решения, но демонстрирует красоту Python (ну, по крайней мере, мне).

Answer 3

РЕДАКТИРОВАНИЕ: Теперь, используя setdefault, как предложено:)

Я не знаю, поможет ли это вам, но вы могли бы создать обратный словарь со значениями в качестве ключа и ключей (всписок как значения).

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

Он напечатает это:

['a', 'c']

Однако я думаю, что другие решения более компактны и, вероятно, более элегантны ...

Answer 4

Решение за один проход будет:

 >>> 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']]

Answer 5

Вот еще один способ сделать это за один проход:

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 6

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

Из-за вашей семантики вам необходимо пройти весь словарь хотя бы один раз. Это восстановит ровно 1 минимальный элемент.

Если вы хотите, чтобы все минимальные элементы за время запроса O (log (N)), вы можете вставить свои элементы в очередь с приоритетами по мере их создания (если можете). Очередь приоритетов должна иметь время вставки O (1) и время извлечения O (log (N)). (Это будет так же плохо, как сортировка, если все ваши элементы имеют одинаковое значение, но в противном случае могут работать довольно хорошо.)

Answer 7

Это работает:

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.Исправив код для работы, я получил ответ @Sven Marnach, так что не обращайте на это внимание;

Answer 8

Вы можете использовать heapq.nsmallest, чтобы получить N самых маленьких членов dict, а затем отфильтровать все, что не равно самому низкому. Это при условии, что вы знаете максимальное количество самых маленьких членов, которое вы можете иметь, давайте предположим, что здесь N. что-то вроде:

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 9

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)