Python: поиск ключей с уникальными значениями в словаре?

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

Я уточню с примером. Скажем, мой ввод - словарь a, построенный следующим образом:

<code>a = dict()
a['cat'] =      1
a['fish'] =     1
a['dog'] =      2  # <-- unique
a['bat'] =      3
a['aardvark'] = 3
a['snake'] =    4  # <-- unique
a['wallaby'] =  5
a['badger'] =   5  
</code>

Результат, который я ожидаю['dog', 'snake'].

Существуют очевидные способы грубой силы для достижения этой цели, однако мне было интересно, есть ли аккуратный Pythonian способ выполнить свою работу.

Ответы на вопрос(9)

Решение Вопроса

что эффективный способ, если dict слишком велик, был бы

countMap = {}
for v in a.itervalues():
    countMap[v] = countMap.get(v,0) + 1
uni = [ k for k, v in a.iteritems() if countMap[v] == 1]
 Ryan Ginstrom24 июн. 2009 г., 03:13
Было бы лучше, если бы он коллекционировал. Defaultdict (int), IMO
 Anurag Uniyal24 июн. 2009 г., 15:49
да, но я бы оставил это так, чтобы люди знали, что мы делаем, когда не было дефолтов
 John Machin25 июн. 2009 г., 02:25
WASTEFUL: делаетfor k, v in a.iteritems(): но не использует k !!!
 Anurag Uniyal29 июл. 2011 г., 02:34
@ Джон Мачин, спасибо, удалил отходы

Вот решение, которое требует только одного раза:

def unique_values(d):
    seen = {} # dict (value, key)
    result = set() # keys with unique values
    for k,v in d.iteritems():
        if v in seen:
            result.discard(seen[v])
        else:
            seen[v] = k
            result.add(k)
    return list(result)
 John Machin23 июн. 2009 г., 15:41
Если значение встречается 3 раза, вы попытаетесь удалить несуществующий элемент изresult ... документы говорят "" "remove (elem) Удалить элемент elem из набора. Вызывает KeyError, если elem не содержится в наборе." ""
 Rick Copeland23 июн. 2009 г., 15:55
Вы правы! Я исправил это, чтобы использовать discard () вместо этого.

revDict = {}
for k, v in a.iteritems():
  if v in revDict:
     revDict[v] = None
  else:
     revDict[v] = k

[ x for x in revDict.itervalues() if x != None ]

(Надеюсь, это сработает, поскольку я не могу проверить это здесь)

 John Machin23 июн. 2009 г., 15:51
Не работает, если один из ключей словаря - None. Например, если a равно {None: 1}, вывод должен быть [None], но приведенный выше код выдаст []. Также:x is not None предпочтительнееx != None.
 Juergen23 июн. 2009 г., 15:59
Спасибо за комментарий! Вы совершенно правы. В практике редко случается, что None используется ... но даже тогда можно использовать некоторый DummyObject: "Dummy = object ()" вместо использования None.

Обратите внимание, что это на самом деле грубая сила:

l = a.values()
b = [x for x in a if l.count(a[x]) == 1]
 Bartosz Radaczyński25 июн. 2009 г., 16:00
ok, я вижу, что Cobbal уже исправил код. Благодарность
 Anurag Uniyal23 июн. 2009 г., 14:52
это не будет выводить ['собака', 'змея']
 Paul Stephenson23 июн. 2009 г., 15:30
Разве l.count ('dog') не равен нулю? l - это [3, 3, 2, 1, 4, 5, 1, 5] в моей системе.
>>> b = []
>>> import collections
>>> bag = collections.defaultdict(lambda: 0)
>>> for v in a.itervalues():
...     bag[v] += 1
...
>>> b = [k for (k, v) in a.iteritems() if bag[v] == 1]
>>> b.sort() # optional
>>> print b
['dog', 'snake']
>>>
 Ryan Ginstrom24 июн. 2009 г., 03:14
collection.defaultdict (int) также будет работать
 John Machin24 июн. 2009 г., 04:10
@ Райан: Да, ноlambda: 0 более явный, чемint ... AFAICT, до наступления defaultdict [2.5] число людей, знавших, что int () выдает 0 [начиная с 2.2] вместо исключения, было <epsilon, а число тех, кто использовал эти знания, было еще меньше: -)

ждений для каждого значения):

def unique(a):
    from collections import defaultdict
    count = defaultdict(lambda: 0)
    for k, v in a.iteritems():
        count[v] += 1
    for v, c in count.iteritems():
        if c <= 1:
            yield v
 John Machin23 июн. 2009 г., 15:15
Это дает значения (2, 4), когда должны выдаваться ключи («собака», «змея»).
 S.Lott23 июн. 2009 г., 15:20
Я нахожуdefaultdict(int) быть немного яснее, чемdefaultdict(lambda:0). Так как по умолчанию dict почти любого другого типа будет просто использовать имя типа.
 Alex Morega23 июн. 2009 г., 15:29
А, да, извините.

А как насчет подклассов?

class UniqueValuesDict(dict):

    def __init__(self, *args):
        dict.__init__(self, *args)
        self._inverse = {}

    def __setitem__(self, key, value):
        if value in self.values():
            if value in self._inverse:
                del self._inverse[value]
        else:
            self._inverse[value] = key
        dict.__setitem__(self, key, value)

    def unique_values(self):
        return self._inverse.values()

a = UniqueValuesDict()

a['cat'] =      1
a['fish'] =     1
a[None] =       1
a['duck'] =     1
a['dog'] =      2  # <-- unique
a['bat'] =      3
a['aardvark'] = 3
a['snake'] =    4  # <-- unique
a['wallaby'] =  5
a['badger'] =   5

assert a.unique_values() == ['dog', 'snake']
 John Machin24 июн. 2009 г., 07:00
Еще одна проблема: ОП не налагает никаких ограничений на то, как было получено содержание диктата. Так что можно ожидать, чтоdel a['bat']; print a.unique_values() приведет кaardvark появится в выводе, но, к сожалению, это не так, и исправление, которое потребует еще большего количества сверток и Double__underscores: -
 Ryan Ginstrom24 июн. 2009 г., 03:12
Это имеет преимущество в меньшем объеме памяти, но вы заканчиваете тем, что выполняете поиск O (N) каждый раз, когда устанавливаете элемент, поэтому он будет намного медленнее, чем метод составления словаря. Кроме того, я думаю, что вы могли бы использовать набор для _inverse вместо dict.

Используйте вложенные списки!

print [v[0] for v in 
           dict([(v, [k for k in a.keys() if a[k] == v])
                     for v in set(a.values())]).values()
       if len(v) == 1]
 Greg Bacon23 июн. 2009 г., 17:11
Rax попросил «аккуратный Pythonian способ сделать работу», в отличие от «очевидных» решений в других тривиальных задач.
 John Machin24 июн. 2009 г., 02:31
(1) Используйтеk in a вместо тогоk in a.keys() (2) Используйтеwhatever.itervalues() вместо тогоwhatever.values() (3) Часть dict (yadda yadda) создает уже перевернутую инверсиюa неэффективно (4) Это ни аккуратно, ни Python (ic | ian) ... но это, конечно, не очевидно! (5) Подсчитайте количество респондентов, чьи первые попытки решить так называемую тривиальную проблему были сложными.
 Tom Leys24 июн. 2009 г., 03:14
-1 Неэффективный O (N ^ 2), сложный, нечитаемый
 John Machin24 июн. 2009 г., 05:24
Этоsolution можно редактировать (используя только клавишу удаления!), чтобы избавиться от построения обратного; все еще O (N ^ 2), хотя:print [v[0] for v in [[k for k in a if a[k] == v] for v in set(a.values())] if len(v) == 1]
 Bryan Oakley23 июн. 2009 г., 16:15
Я не понимаю, как такое использование списочного понимания - это победа. Для меня это только усложняет понимание решения (без каламбура). Удобочитаемость является ключевым фактором, и это решение не так просто для чтени

Вот еще один вариант.

>>> import collections
>>> inverse= collections.defaultdict(list)
>>> for k,v in a.items():
...     inverse[v].append(k)
... 
>>> [ v[0] for v in inverse.values() if len(v) == 1 ]
['dog', 'snake']

Я неравнодушен к этому, потому что перевернутый словарь - такой распространенный шаблон проектирования.

 Paul Stephenson23 июн. 2009 г., 15:46
Вы хотите, чтобы [v [0] для k, v ...] в последней строке получало ['dog', 'snake'] в соответствии с запросом.
 John Machin24 июн. 2009 г., 02:17
(1) Вместо .items () используйте .iteritems (). (2) последняя строка извлекает ключ без необходимости; должно быть[v[0] for v in inverse.itervalues() if len(v) == 1 (3) В любом случае построение перевернутого диктата излишне.

Ваш ответ на вопрос