是否存在一個更好的方式來存儲雙向字典，而不是存儲其逆向分離？

給定一個對一字典（=雙射）點菜是否存在一個更好的方式來存儲雙向字典，而不是存儲其逆向分離？

for key, value in someGenerator: 
    myDict[key] = value

逆查找字典產生可以通過加入

invDict[value] = key

到for循環而輕易地產生。但這是一種Pythonic方式嗎？我應該寫一個class Bijection(dict)來管理這個逆字典嗎？並且提供第二個查找功能？或者這樣的結構（或類似的結構）已經存在？

來源

2013-05-28 Tobias Kienzler

這[bidict]怎麼樣（https://pypi.python.org/pypi/bidict） –

@JonClements聽起來很完美，謝謝！我會接受這個答案。使用切片進行反向查找是一個好主意 –

通過它的外觀，「bidict」只是封裝了兩個帶有前向和反向映射的單獨Python字典，所以它不會比自己做同樣的效率更高。事實上，如果你正在做大量的關鍵字查找，由於函數調用的開銷，它會慢得多。 – Aya

我在過去所做的是創建了一個reversedict函數，該函數需要一個字典並返回相反的映射，如果我知道它是一對一的值，則返回值（在看到相同的時候拋出異常值兩次），或者如果值不是鍵值列表，則返回值列表。這樣，每次我想要反向查找時，不需要同時構造兩個字典，我可以像平常一樣創建我的字典，並在最後調用通用的reversedict函數。

但是，Jon似乎在評論中提到的bidict解決方案可能是更好的解決方案。（我的reversedict功能似乎是他的bidict的~運營商）。

來源

2013-05-28 13:46:13 Claudiu

bidict是完美的我的目的 - 它基本上存儲逆字典裏面，但通過使用切片運算符改進訪問 –

如果您希望O（log（n））時間用於訪問值，則需要映射表示和逆映射表示。

否則，你可以做的最好的是一個方向上的O（log（n））和另一個方向上的O（n）。

編輯：不是O（log（n）），感謝Claudiu，但您仍然需要兩個數據結構來實現快速訪問時間。這與字典和逆字典或多或少是一樣的空間。

來源

2013-05-28 13:56:45 Zackkenyon

字典沒有O（log（n））查找，他們已攤銷O（1） lookup ... – Claudiu

是的，應該看起來之前我張貼:) – Zackkenyon

是否存在一個更好的方式來存儲雙向字典，而不是存儲其逆向分離？

回答

相關問題