Слияние ключей словаря, если значения одинаковы

Question

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

{ 
    'bathroom': <Song: Blur - Song 2>, 
    'bedroom1': <Song: Blur - Song 2>, 
    'kitchen': <Song: Meat Loaf - I'd Do Anything for Love (But I Won't Do That)>, 
} 

Иногда подмножества этих игроков синхронизируются. Так что - выше - они отображают одно и то же значение. Я хотел бы сгруппировать их в интерфейсе. Я могу быть более умным, когда я создаю словарь, но если я не буду этого делать, есть ли хороший способ объединить ключи по значению?

Нужный выход из выше будет, что-то вроде:

{ 
    'bathroom,bedroom1': <Song: Blur - Song 2>, 
    'kitchen': <Song: Meat Loaf - I'd Do Anything for Love (But I Won't Do That)>, 
} 

Однако это делает перерыв, как я хотел бы посмотреть вещи (я хотел бы указать на имя, следовательно, это словарь) ... Есть ли лучшая коллекция, которая может иметь несколько ключей на каждое значение и указывать, когда есть объединенные дубликаты (и назад - все ключи)?

Существует хороший ответ, который переворачивает это вокруг ключа песен и список игроков в качестве значения. Это замечательно, за исключением того, что иногда я хочу знать, какая песня играет на имени игрока. Вот почему я изначально пошел со словарем.

Есть ли хороший способ сохранить поиск в обоих направлениях (не дожидаясь сохранения обеих коллекций)?

Answer 1

Когда количество значимых данных является значительным, это тот тип вещей, где реляционная база данных пригодится. База данных с двумя столбцами, ключом и значением и индексом в ключевом столбце действует как диктофон. Но вы также можете поместить индекс в столбец значений, чтобы обеспечить эффективный обратный поиск.

В вашем случае, тем не менее, поскольку объем данных невелик, я просто сделаю defaultdict и добавлю пары (value, key).

reverse_lookup = defaultdict(list) 
for k, v in now_playing.items(): 
    reverse_lookup[v].append(k) 

И тогда вы можете ','.join() значения для создания составных клавиш. Поскольку эти составные клавиши будут использоваться для отображения , похоже, на самом деле не для поиска, я бы просто сохранил как оригинальный dict, так и обратный поиск dict в памяти и использовал то, что вам нужно, когда вы do need для выполнения поиска. Задача поиска других игроков, играющих ту же песню, что и данная (и предположительно синхронизированная), затем включает два поиска, один вперед и один назад, но они хеш-таблицы, поэтому добавленная стоимость минимальна.

---

После некоторых размышлений о других, более «интересных» способов сделать это: вы могли бы извратить disjoint set data structure для удовлетворения ваших потребностей. У вас будет узел для каждого игрока и узел для каждой воспроизводимой песни. Узлы группируются в группы по песням, где один набор содержит как узел для песни, так и узлы для любых игроков, которые в данный момент играют эту песню. Если вы помещаете узлы каждого набора (песня плюс игроки) в циклический связанный список, при условии, что общая структура данных должным образом поддерживается, вы можете начинать с любого узла и ходить по списку, чтобы перебирать как песню, так и список игроков, которые играют эту песню.

Трюк, конечно же, находит эффективный способ поддерживать эту общую структуру данных, то есть обновлять циклические списки по мере изменения песен.Если игроки действительно синхронизированы, это так же просто, как замена одного узла песни другим, каждый раз, когда вся группа игроков переходит на следующий трек. Но я могу представить, что приложение, подобное тому, которое вы создаете, часто должно выполнять другие виды поиска, для которых структура несвязанных множеств не дает вам никакой пользы.

Answer 2

from itertools import groupby 

x = { 
    'bathroom': 'a', 
    'bedroom1': 'a', 
    'kitchen': 'b' 
} 


{ 
    ','.join(i[0] for i in v): k 
    for k,v in groupby(sorted(x.iteritems(), key=lambda p: p[1]), lambda p: p[1]) 
}