Как определить наименьшее уникальное значение в словаре?

Question

[Александр]

Ещё только учусь. Так что сильно не ругайте. Пытаюсь разобраться со словарями.
Поставил себе такую задачку:
Словарь: "имя": значение (штук 20)
Значения могут повторятся
Как определить наименьшее уникальное значение в словаре?
Например:
коля=23, света=26, настя=45, саня=23
Ожидаемый результат => света=26

Пока у меня получилось:

a = "roma"
b = "nastia"
c = "sasha"

aa = 12
bb = 23
cc = 45

qw = {a:aa, b:bb, c:cc}

if qw[a] < qw[b] and qw[a] < qw[c]:
    print a, qw.get(a)
elif qw[a] == qw[b] or qw[a] == qw[c] or qw[b] == qw[c]:
    print("нет наименьшего")
elif qw[b] < qw[a] and qw[b] < qw[c]:
    print b, qw.get(b)
else:
    print c, qw.get(c)

А теперь понимаю что если добавить в словарь ещё 10-20 значений будет полная Ж. Да и проверка на уникальность - как?

Comments

[Ivan Velichko]

Когда-то давно я точно таким же способом пытался перебрать все возможные комбинации в игре "Крестики-Нолики". Это был ад! 4000+ строк if-ов.

Answer 1

[Andrey Dugin]

Самое простое и эффективное решение без лишних действий:

from collections import Counter

def min_unique(dictionary):
    minval, result = float('inf'), None
    counter = Counter(dictionary.itervalues())
    for key, val in dictionary.iteritems():
        if (val < minval) and (counter[val] == 1):
            minval = val
            result = (key, val)
    return result

data = {'a': 23, 'b': 26, 'c': 45, 'd': 23}
print min_unique(data)

Или так:

from operator import itemgetter
from itertools import ifilter

def min_unique(dictionary):
    inverted = dict()
    for key, value in dictionary.iteritems():
        inverted[value] = None if value in inverted else key
    filtered = ifilter(itemgetter(1), inverted.iteritems())
    try:
        value, key = min(filtered, key=itemgetter(0))
    except ValueError:
        value, key = None, None
    return key, value

Ещё интересный вариант с итераторами (узкое место - сортировка):

from operator import itemgetter
from itertools import groupby

def min_unique(dictionary, ig=itemgetter(1)):
    grouped = groupby(sorted(dictionary.viewitems(), key=ig), key=ig)
    for key, entries in grouped:
        entry = entries.next()
        try:
            entries.next()
        except StopIteration:
            return entry
        else:
            continue

Comments

[Ivan Velichko]

Снимаю шляпу, ваше новое решение элегантное, простое и не требует использования python-specific тулов.

[Andrey Dugin]

Иван Величко: Спасибо :)

Answer 2

[Ivan Velichko]

Необходимо стараться написать общий алгоритм решения задачи, а не перебрать допустимые варианты. Это можно делать даже без использования конкретного языка программирования, пользуясь лишь логическими утверждениями. Например: для начала подсчитаем количество вхождений каждого из значений в словаре (см. counter в коде). Затем выберем наименьшее уникальное значение. Для этого необходимо отфильтровать массив уникальных, затем отсортировать его по возрастанию и взять первый элемент (см. lowest_unique = (sorted([k for k in counter if counter[k] == 1]) or [None])[0]). Теперь необходимо найти ключ в начальном словаре, соответствующий найденному минимальному значению. Можно, конечно, перебрать все ключи в словаре и проверить их значения, но это долго. Если же сделать отражение начального словаря (переворот, flip), то заданное значение ключа можно будет найти простейшим обращением flipped_dict[lowest_unique]. Делаем переворот: flipped_dict = dict(zip(initial_dict.values(), initial_dict.keys())).

Полная версия кода:

initial_dict = {'Foo': 23, 'Bar': 26, 'Baz': 45, 'Bang': 23}
flipped_dict = dict(zip(initial_dict.values(), initial_dict.keys()))  
# print(flipped_dict)
# {26: 'Bar', 45: 'Baz', 23: 'Foo'}

counter = {}
for k in initial_dict:
	val = initial_dict[k]
	counter[val] = counter.get(val, 0) + 1
 # print(counter)  
 # {26: 1, 45: 1, 23: 2}

lowest_unique = (sorted([k for k in counter if counter[k] == 1]) or [None])[0]
if lowest_unique is None:
	print("Not found!")
else:
	print("Found [%s]->[%s]" % (flipped_dict[lowest_unique], lowest_unique))

Comments

[Andrey Dugin]

Ваш ответ - яркий пример того, как неправильные рассуждения об "общем" решении задачи приводят к написанию низкопроизводительного и трудночитаемого говнокода. В этой задаче достаточно единственной сортировки, и всё. Никаких фильтраций и инвертирований словаря, не говоря уже о zip. А Вы ещё насоздавали минимум 4 списка, которые не нужны. Вместо keys() и values() можно было использовать один iteritems(), а ещё лучше - dictionary view (который, к сожалению, редко встречается в литературе).

[Ivan Velichko]

Андрей Дугин: речи про оптимальный код не было. Автор вопроса только учится программировать. Ему сейчас нужно разобраться с построением алгоритмов. Да, ваш вариант решения быстрый - но посмотрите, со сколькими новыми концепциями придется познакомиться автору вопроса? 2 новых модуля, итераторы, исключения! Это питоник-код, да, я же писал скорее просто понятный алгоритм на псевдокоде.

[Andrey Dugin]

Иван Величко: Иван, я стараюсь давать достаточно сложные ответы, чтобы новички могли познакомиться с новыми для себя концепциями. Простого Pascal-style на тостере в избытке :) Хотя в данном случае простое решение самое эффективное (я написал два варианта).

[Ivan Velichko]

Андрей Дугин: Да, ваше новое решение просто отличное. У меня схожие, но видимо не столь радикальные взгляды, поэтому я упомянул в своем ответе лишь zip и list comprehension.

Answer 3

[Илья]

Не претендую на идеальность решения и максимальную скорость выполнения программы, я сам новичек.

d = {'a': 21, 'b': 5, 'c': 7, 'd': 5, 'e': 10}
u = {k: v for k, v in d.items() if tuple(d.values()).count(v) < 2}
print(min(u.items(), key=lambda i: i[1])[0])

Некоторые пояснения:
1. d - данный словарь
2. u - сформированный словрь, в котором остались только элементы с уникальными значениями
3. С помощью функции min вычисляем элемент путем сравнения значения значений (не ключей), получаем кортеж вида (key, value) и возвращаем и возвращаем [0] элемент, т.е. key.
---
Если использовать python2.7, тогда вместо u.itеmes(), лучше использовать u.iteritems()

Comments

[Andrey Dugin]

1) Зачем используете tuple, если у list тоже есть функция count()?
2) Вообще искать в списке очень неэффективно, но оставим пока так.
3) Функцию d.values().count имеет смысл определить отдельно, чтобы не вызвать d.values() каждую итерацию. И вообще dotted notation в цикле не рекомендуется: https://wiki.python.org/moin/PythonSpeed/Performan...
4) min() вызовет ошибку в случае, когда уникального значения нет.
5) Вместо лямбды лучше использовать operator.itemgetter(1)

Как увеличить скорость в 2+ раза:

>>> d = {'a': 21, 'b': 5, 'c': 7, 'd': 5, 'e': 10}
>>> def v1(d=d):
	return {k: v for k, v in d.items() if d.values().count(v) == 1}
>>> def v2(d=d, cnt=d.values().count):
	{k: v for k, v in d.items() if cnt(v) == 1}
>>> def v3(d=d, cnt=d.values().count):
	{k: v for k, v in d.viewitems() if cnt(v) == 1}
>>> from timeit import timeit
>>> timeit(v1, number=1000000)
9.940651956859298
>>> timeit(v2, number=1000000)
6.061919530989137
>>> timeit(v3, number=1000000)
4.280532062150144

[Илья]

Спасибо за пояснение. Я пока что ниразу не замерял производительность и про itemgetter и viewitems вообще не знал.

[Andrey Dugin]

Илья: здесь не самое лучшее применение viewitems(), можно заменить на iteritems()

[Andrey Dugin]

Илья: А производительность замеряйте, это отлично учит писать эффективный код. И итераторы/генераторы используйте везде, где только можно.

[Илья]

Ну генераторы - стараюсь, на edx про них уже рассказали, да и в python3 многие вещи стали генераторами в отличии от python2.