Python中的散列字典

我有一個非常大的矩陣，我打算將它存儲爲Python中的字典列表。矩陣大多爲0，我想知道字典中的散列函數是否會爲每一行存儲前導空間。因此，例如，如果我初始化了一個100,000 x 100,000的矩陣，但是每個行存儲的實際元素只有大約1,000個條目，並且對於行50,000，我有從48,500到50,500的條目，Python會創建一個大小爲50,500或2,000的字典嗎？此外，如果前者是真的，我可以在Python的當前字典類中進行優化，還是需要創建自己的？Python中的散列字典

由於我的代碼的例子，我有這樣的：

class DictArray: 

    def __init__(self, width, height): 
     self.Width = width 
     self.Height = height 
     self.Data = [0 for _ in range(self.Height) ] 

    def __getitem__(self, k): 
     if (self.Data[ k[0] ] == 0): 
      return 0 
     elif (k[1] in self.Data[ k[0] ]): 
      return self.Data[ k[0] ][ k[1] ] 
     else: 
      return 0 

    def __setitem__(self, k, value): 
     if (self.Data[ k[0] ] == 0): 
      self.Data[ k[0] ] = { k[1] : value } 
     else: 
      self.Data[ k[0] ][ k[1] ] = value

來源

2016-01-14 Woody1193

向我們展示如何初始化100,000 x 100,000矩陣。 – Kevin

顯示較小矩陣的示例以及將容納它的字典 – m7mdbadawy

如果要有效處理稀疏矩陣處理，SciPy和NumPy可能是您需要的庫。 – sal

字典將根據您在其存儲密鑰的數量的大小。

如果您有2000個密鑰（每個(x, y)座標，也許？），那麼它的大小將保持2000個密鑰（加上一點額外開銷以方便未來增長而不需要調整大小）。然而，如果要爲矩陣中的所有10^10元素創建密鑰（除2000以外的所有元素都參考None），那麼您將擁有一個包含100億個密鑰的字典，並且它的大小因此。

使用字典來建立一個稀疏矩陣可以那麼容易，因爲：

class DictArray: 
    def __init__(self, width, height): 
     self.width = width 
     self.height = height 
     self._data = {} 

    def _validate_coords(self, x, y): 
     if not (0 <= x < self.width and 0 <= y < self.height): 
      raise IndexError((x, y)) 

    def __getitem__(self, x_y): 
     self._validate_coords(*x_y) 
     return self._data.get(x_y, 0) 

    def __setitem__(self, x_y, value): 
     self._validate_coords(*x_y) 
     if value == 0: 
      try: 
       del self._data[x_y] 
      except KeyError: 
       pass 
     else: 
      self._data[x_y] = value

演示：

>>> da = DictArray(10, 10) 
>>> da[0, 0] = 42 
>>> da[0, 4] = 81 
>>> len(da._data) 
2 
>>> da[0, 4] = 0 
>>> len(da._data) 
1 
>>> da._data 
{(0, 0): 42} 
>>> da[0, 0] 
42 
>>> da[0, 4] 
0

我也希望你看一下SciPy的或NumPy的這樣一個大任務但是。他們爲這些任務提供了專用的數據結構，例如scipy.sparse module中的那些。

來源

2016-01-14 19:46:11

我喜歡你的建議。我會爲此使用NumPy或SciPy，但此項目將在以後用於翻譯，因此我想盡可能少地依賴外部庫。 – Woody1193

@ Woody1193：無論您將其翻譯爲何種語言，您都應該可以獲得該語言的稀疏矩陣庫或者至少讀過標準稀疏矩陣格式和算法。標準方法將比你首先想到的要好得多。 – user2357112

如果你有一個稀疏矩陣，你可以嘗試脫離字典的關鍵是一個（行，列）元組（或其他方式來快速獲取行和列）。

E.g.

# assume get_matrix(i,j) gives your (i,j)th element 
m = {} 
for i in xrange(0,100000): 
    for j in xrange(0,100000): 
     t = get_matrix(i,j) 
     if t: 
      m[(i,j)] = t

關於詞典的表現，假設它具有對數搜索的複雜性，你也可以看看它有多少內存要採取。取決於你使用的是什麼樣的機器，類似10K條目的東西可能會工作，但是像1000K條目可能不會。

（但使用numpy或scipy可能是更好的選擇）

來源

2016-01-14 19:47:49 Ashalynd

Python中的散列字典

回答

相關問題