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

15

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

Я уточню с примером. Скажем, мой ввод - словарь 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   ответов
13

что эффективный способ, если 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]
Было бы лучше, если бы он коллекционировал. Defaultdict (int), IMO Ryan Ginstrom
да, но я бы оставил это так, чтобы люди знали, что мы делаем, когда не было дефолтов Anurag Uniyal
WASTEFUL: делаетfor k, v in a.iteritems(): но не использует k !!! John Machin
@ Джон Мачин, спасибо, удалил отходы Anurag Uniyal
5

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

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)
Если значение встречается 3 раза, вы попытаетесь удалить несуществующий элемент изresult ... документы говорят "" "remove (elem) Удалить элемент elem из набора. Вызывает KeyError, если elem не содержится в наборе." "" John Machin
Вы правы! Я исправил это, чтобы использовать discard () вместо этого. Rick Copeland
2

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 ]

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

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

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

l = a.values()
b = [x for x in a if l.count(a[x]) == 1]
это не будет выводить ['собака', 'змея'] Anurag Uniyal
ok, я вижу, что Cobbal уже исправил код. Благодарность Bartosz Radaczyński
Разве l.count ('dog') не равен нулю? l - это [3, 3, 2, 1, 4, 5, 1, 5] в моей системе. Paul Stephenson
4
>>> 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']
>>>
collection.defaultdict (int) также будет работать Ryan Ginstrom
@ Райан: Да, ноlambda: 0 более явный, чемint ... AFAICT, до наступления defaultdict [2.5] число людей, знавших, что int () выдает 0 [начиная с 2.2] вместо исключения, было <epsilon, а число тех, кто использовал эти знания, было еще меньше: -) John Machin
-1

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

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
Это дает значения (2, 4), когда должны выдаваться ключи («собака», «змея»). John Machin
Я нахожуdefaultdict(int) быть немного яснее, чемdefaultdict(lambda:0). Так как по умолчанию dict почти любого другого типа будет просто использовать имя типа. S.Lott
А, да, извините. Alex Morega
2

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

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']
Еще одна проблема: ОП не налагает никаких ограничений на то, как было получено содержание диктата. Так что можно ожидать, чтоdel a['bat']; print a.unique_values() приведет кaardvark появится в выводе, но, к сожалению, это не так, и исправление, которое потребует еще большего количества сверток и Double__underscores: - John Machin
Это имеет преимущество в меньшем объеме памяти, но вы заканчиваете тем, что выполняете поиск O (N) каждый раз, когда устанавливаете элемент, поэтому он будет намного медленнее, чем метод составления словаря. Кроме того, я думаю, что вы могли бы использовать набор для _inverse вместо dict. Ryan Ginstrom
-2

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

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]
Rax попросил «аккуратный Pythonian способ сделать работу», в отличие от «очевидных» решений в других тривиальных задач. Greg Bacon
(1) Используйтеk in a вместо тогоk in a.keys() (2) Используйтеwhatever.itervalues() вместо тогоwhatever.values() (3) Часть dict (yadda yadda) создает уже перевернутую инверсиюa неэффективно (4) Это ни аккуратно, ни Python (ic | ian) ... но это, конечно, не очевидно! (5) Подсчитайте количество респондентов, чьи первые попытки решить так называемую тривиальную проблему были сложными. John Machin
-1 Неэффективный O (N ^ 2), сложный, нечитаемый Tom Leys
Это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] John Machin
Я не понимаю, как такое использование списочного понимания - это победа. Для меня это только усложняет понимание решения (без каламбура). Удобочитаемость является ключевым фактором, и это решение не так просто для чтени Bryan Oakley
0

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

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

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

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

Похожие вопросы