Реверсивный неуникальный словарь

Question

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

>>> graph = { 'a': ['car','red'], 'b': ['car','blue'] }
>>> inv_map = {}
>>> for k,v in graph.items():
        inv_map[v] = inv_map.get(v,[])
        inv_map[v].append(k)

TypeError: unhashable type: 'list'

>>> isinstance(graph, dict)
True

Предложения

Answer 1

Если вы хотите использовать каждый элемент каждого списка в качестве ключа (что кажется более полезным), см. wim's answer .

---

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

---

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

for k,v in graph.items():
    t = tuple(v)
    inv_map[t] = inv_map.get(t,[])
    inv_map[t].append(k)

---

Если вы хотите сравнить списки по идентичности, а не по значению (что гораздо реже, но все же иногда полезно), вы можете использовать их идентификаторы в качестве ключей:

for k,v in graph.items():
    i = id(v)
    inv_map[i] = inv_map.get(i,[])
    inv_map[i].append(k)

---

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

val = ['car', 'ref']
keys = inv_map_tup[tuple(val)]
keys = inv_map_id[id(val)]

Если вы собираетесь делать много этого, вы можете получить «трансформдикт» от PyPI или коллекции рецептов ActiveState или создать его самостоятельно. ¹ Если вы заботитесь только о это простое использование, это может быть довольно простая оболочка вокруг dict, которая вызывает функцию для клавиши перед каждой операцией. Например:

def __getitem__(self, key):
    return super().__getitem__(self.transformer(key))
def __setitem__(self, key, value):
    super().__setitem__(self.transformer(key), value)
# etc.

Тогда вы можете просто сделать transformdict(tuple) или transformdict(id).

---

_{1. У меня нет рекомендации для конкретной, но PEP 455 , отклоненное предложение добавить его в stdlib, содержит ссылки на несколько реализаций и предлагаемую «эталонную реализацию» для stdlib, и подробное обсуждение идеи.}

Answer 2

Я нашел решение своей проблемы Внешняя ссылка :

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

def invert_dol_nonunique(d):
    newdict = {}
    for k in d:
        for v in d[k]:
            newdict.setdefault(v, []).append(k)
    return newdict

Answer 3

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

from collections import defaultdict
inv_map = defaultdict(list)

for k, vs in graph.items():
    for v in vs:
        inv_map[v].append(k)

inv_map.default_factory = None  # quack like a normal dict