優化的Python詞典/負向索引存儲

Question

提出了this問題的評論（我可以看到這是無關緊要的），現在我意識到使用字典中需要定期查詢/訪問的數據並不好，速度快。

我有這樣的情況：

someDict = {} 
someDict[(-2, -2)] = something 
somedict[(3, -10)] = something else 

我存儲的座標鍵來充當遊戲中的瓦片的數組的對象。這些在某些時候會是負面的，所以我不能使用列表或某種稀疏數組（我認爲這是術語？）。

我要麼可以：

• 加快字典查找，所以這不會是一個問題
• 發現某種容器將支持稀疏，負指數？

我會使用一個列表，但然後查詢將從O（log n）到O（n），以找到（x，y）處的區域。 （我認爲我的時間也在這裏）。

Answer 1

詞典的查找非常快。搜索部分密鑰（例如，第x行中的所有圖塊）是不快的。你可以使用字典的字典。而不是由2元組索引的一個快譯通，使用嵌套類型的字典是這樣的：

somedict = {0: {}, 1:{}} 
somedict[0][-5] = "thingy" 
somedict[1][4] = "bing" 

然後，如果你想在一個給定的「行」所有的瓷磚，它只是somedict[0]。

您需要一些邏輯才能在必要時添加輔助詞典等。提示：檢查標準dict類型的getitem()和setdefault()，或可能的collections.defaultdict類型。

該方法可讓您快速訪問給定行中的所有圖塊。如果你想要給定列中的所有圖塊，它仍然很慢（儘管至少你不需要查看每一個單元格，只是每一行）。但是，如果需要，您可以通過使用兩個字典的字典（列中的一個，行順序，另一個字段，列順序）來解決這個問題。更新後的工作量會增加兩倍，這對於大多數瓷磚都是靜態的遊戲來說可能並不重要，但訪問在任何方向都非常容易。

如果你只需要存儲的數字和大部分的細胞爲0，退房SciPy的的稀疏矩陣類。

Answer 2

要與

加快字典查找開始，所以這不會是一個問題

字典查找是非常快的O（1），但是（從您的其他問題）你不依賴於字典的哈希表查找，而是依賴於字典鍵的線性搜索。

找到某種支持稀疏負指數的容器？

這不是索引到字典中。一個元組是一個不可變的對象，並且你將整個元組哈希化。字典真的不知道密鑰的內容，只是他們的散列。

與其他人一樣，我將建議您重構您的數據。例如，您可以創建封裝所需數據的對象，並將它們排列在O（n lg n）搜索的二叉樹中。你甚至可以把整個東西包裝在一個類中，它會給你想要的漂亮的if foo in Bar:語法。

你可能需要一對夫婦協調結構來完成你想要的。這裏有一個使用字典和集合的簡單例子（稍微調整用戶6502的建議）。

# this will be your dict that holds all the data 
matrix = {} 
# and each of these will be a dict of sets, pointing to coordinates 
cols = {} 
rows = {} 

def add_data(coord, data) 
    matrix[coord] = data 
    try: 
     cols[coord[0]].add(coord) 
    except KeyError: 
     # wrap coords in a list to prevent set() from iterating over it 
     cols[coord[0]] = set([coord]) 
    try: 
     rows[coord[1]].add(coord) 
    except KeyError: 
     rows[coord[1]] = set([coord]) 

# now you can find all coordinates from a row or column quickly 
>>> add_data((2, 7), "foo4") 
>>> add_data((2, 5), "foo3") 
>>> 2 in cols 
True 
>>> 5 in rows 
True 
>>> [matrix[coord] for coord in cols[2]] 
['foo4', 'foo3'] 

現在只是包裝在一個類或一個模塊，你就可以了，和往常一樣，如果你想之前的速度不夠快的個人資料和測試。

Answer 3

使用多維列表 - 通常實現爲嵌套對象。用一點算術就可以很容易地使這個句柄的負指數。它可能會使用更多的內存比一本字典，因爲在每一個可能的插槽（通常爲None空的）放在東西了，但訪問將通過簡單的索引的查找來完成，而不是因爲它會藉助詞典散列。

Answer 4

一種選擇是簡單地改變指數，所以它是積極的。

E.g.如果你的指數是連續這樣的：

... 
-2 -> a 
-1 -> c 
0 -> d 
1 -> e 
2 -> f 
... 

就做這樣的事情LookupArray [索引+ MinimumIndex]，其中MinimumIndex是你會用最小的指數的絕對值。

這樣，如果你的最小值爲說，-50，它會映射到0 -20將映射到30，等等。

編輯：

另一種方法是對你如何使用索引使用技巧。定義以下鍵功能

Key(n) = 2 * n (n >= 0) 
Key(n) = -2 * n - 1. (n < 0) 

這將所有正鍵映射到正偶數索引，並將所有負數元素映射到正奇數索引。這可能是不實用的，雖然，因爲如果添加100個負鍵，你就必須通過200

的另一件事，擴大你的數組要注意：如果你打算做一下UPS和按鍵的數量是恆定的（或非常緩慢地變化），堅持陣列。否則，字典一點都不壞。

Answer 5

Python字典是非常非常快的，並使用一個整數的元組是不會成爲一個問題。然而，你的用例似乎有時你需要做一個單一的座標檢查，並且遍歷所有的字典當然很慢。

而不是做一個線性搜索，你可以但加快存取的數據結構則需要使用三點字典：

class Grid(object): 
    def __init__(self): 
     self.data = {} # (i, j) -> data 
     self.cols = {} # i -> set of j 
     self.rows = {} # j -> set of i 

    def __getitem__(self, ij): 
     return self.data[ij] 

    def __setitem__(self, ij, value): 
     i, j = ij 
     self.data[ij] = value 
     try: 
      self.cols[i].add(j) 
     except KeyError: 
      self.cols[i] = set([j]) 
     try: 
      self.rows[j].add(i) 
     except KeyError: 
      self.rows[j] = add([i]) 

    def getRow(self, i): 
     return [(i, j, data[(i, j)]) 
       for j in self.cols.get(i, [])] 

    def getCol(self, j): 
     return [(i, j, data[(i, j)]) 
       for i in self.rows.get(j, [])] 

注意，有這取決於很多其他可能的數據結構正是你正在嘗試要做什麼，閱讀的頻率如何，更新頻率如何，如果通過矩形查詢，是否查找最近的非空單元格等等。