數字索引數據結構的最快數據結構？

-1

我使用普通的Python 2.79，只想使用標準庫。我想創建基本上是二維數組的元素，其中每個由兩個維度引用的單元格將指向一個小型的雜項數據字典。我想要最快的方式來訪問包含字典的單元格。數據將有兩個整數索引，通過它我可以引用每個單元格。我已經知道x和y了（我們稱它們爲...）數字索引數據結構的最快數據結構？

1）x和y元素的允許值在-58600和+58600之間。

2）不是每個單元格都包含信息，但我需要快速查找並通過數字x，y索引獲取單元格數據。

3）中的數據單元格的內容可以是任何尺寸或構造，並且可以隨着時間而改變，因爲我升級代碼或包括新參數等

我首先想到的是一個嵌套字典使得

dictionary_structure[x][y]["data"]

會查找數據..或測試存在通過

if "data" in dictionary_structure[x][y]:

我應該使用最快的查找什麼樣的數據結構？

來源

2015-07-02 Surest Texas

我認爲如果您只有一個頂級字典，而不是每個維度都有一個字典，則性能會提高。這裏有幾個可能性：

使用的元組：由它可能值的數量

if (x, y) in dictionary_structure: 
    print(dictionary_structure[(x, y)]["data"])

乘一個座標，並添加到其他（你的鑰匙現在是整數;乘法確保沒有獨特的x和y組合將成爲相同的密鑰 - 但不要包的關鍵計算了一個功能，你還可以用除法和模數來提取一鍵X和Y）：

key = 117201 * x + y 
if key in dictionary_structure: 
    print(dictionary_structure[key]["data"])

我不知道哪個t這會在你的情況下更快;你需要自己測量一下。

來源

2015-07-02 20:17:59

布魯姆過濾器在最內層。這裏有幾個實現：

https://github.com/bitly/dablooms

https://github.com/axiak/pybloomfiltermmap

https://bitbucket.org/crankycoder/hydra/src

非常快處理，數據大小不因爲內部散列技術重要。但是，有誤報 - 因此您需要驗證這是否適合您的確切問題。

來源

2015-07-02 00:55:48 Aditya

誤報？這是什麼意思？當我擡頭看看37,42時，它會「混合」細胞，比如給我細胞34,56嗎？或告訴我細胞37,42沒有數據等？ –

假陽性意味着它可能會說即使沒有（儘管很少），也存在特定的「數據」。檢查https://en.wikipedia.org/wiki/Bloom_filter – Aditya

但是，如果「數據」存在，它肯定會返回true。 – Aditya

數字索引數據結構的最快數據結構？

回答

相關問題