Если задан взаимно однозначный словарь (= биекция), сгенерированный à la
for key, value in someGenerator:
myDict[key] = value
словарь обратного поиска можно создать тривиально, добавив
invDict[value] = key
в цикле for. Но является ли это путинским? Должен ли я вместо этого написать class Bijection(dict), который дополнительно управляет этим инвертированным словарем и предоставляет вторую функцию поиска? Или такая структура (или аналогичная) уже существует?
То, что я делал в прошлом, создало функцию reversedict, которая принимает dict и возвращает противоположное сопоставление, либо значения для ключей, если бы я знал, что это было один к одному (бросая исключения при просмотре то же значение два раза) или значения для списков ключей, если это не так. Таким образом, вместо того, чтобы каждый раз создавать два dicts каждый раз, когда мне нужен обратный поиск, я мог бы создать свои dicts как обычные и просто вызвать общую функцию reversedict в конце.
Однако кажется, что решение bidict, которое Джон упомянул в комментариях, вероятно, лучше. (Моя функция reversedict представляется его оператором bidict ~).
если вы хотите O (log (n)) время для доступа к значениям, вам потребуется как представление карты, так и представление обратного отображения.
в противном случае лучшее, что вы можете сделать, это O (log (n)) в одном направлении и O (n) в другом.
Изменить: не O (log (n)), спасибо Claudiu, но вам все равно понадобятся две структуры данных для реализации быстрого доступа. И это будет более или менее то же пространство, что и dict и обратный dict.