尺寸高效字典（關聯數組）實現

什麼算法可用於尺寸高效A dictionary or associative array？例如，使用這個鍵/值集，如何避免在值中重複「Alice」？尺寸高效字典（關聯數組）實現

{ 
    "Pride and Prejudice": "Alice", 
    "The Brothers Karamazov": "Pat", 
    "Wuthering Heights": "Alice" 
}

我檢查Python's implementation on dictionary，但似乎實施的重點是速度（保持O（1））沒有大小。

來源

2013-07-09 prosseek

保持第二字典映射值ID（例如哈希）值，在這一個使用值ID。 –

你的數據結構應該支持mutable * values *嗎？ –

我想你可以存儲sys.intern的結果，如果你只想把字符串作爲值。 – bennofs

正如在評論中提到由bennofs，你可以使用intern()以確保相同的字符串存儲只有一次：

class InternDict(dict): 

    def __setitem__(self, key, value): 
     if isinstance(value, str): 
      super(InternDict, self).__setitem__(key, intern(value)) 
     else: 
      super(InternDict, self).__setitem__(key, value)

下面是具有效果的例子：

>>> d = {} 
>>> d["a"] = "This string is presumably too long to be auto-interned." 
>>> d["b"] = "This string is presumably too long to be auto-interned." 
>>> d["a"] is d["b"] 
False 
>>> di = InternDict() 
>>> di["a"] = "This string is presumably too long to be auto-interned." 
>>> di["b"] = "This string is presumably too long to be auto-interned." 
>>> di["a"] is di["b"] 
True

來源

2013-07-09 16:59:51

如果你的字典可以放在內存中，那麼可以使用一個簡單的Hashtable。

嘗試在散列表中插入每個鍵值。如果在插入之前存在密鑰，那麼你已經找到了重複。許多語言的執行次數爲hashtable。

基本上有兩種方法：array &樹。

Array專注於高記憶成本的速度。 Hashtable實現的主要區別在於unicity的行爲，有些實現強制unicity其他一些不行。
樹將重點放在以O（log（n））cpu使用爲代價的內存智能使用。 g ++地圖依靠非常強大的功能red black tree。

如果大小是非常非常問題羣，那麼你應該尋找一個Huffman壓縮和/或Lampel Ziv壓縮，但它的成本多一點，爲適應dictionnary。

如果您dictionnary不能在內存

適合你應該看看數據庫。 紅黑樹數據庫知道爲BTree（差不多）。它針對低延遲硬盤驅動器案例進行了分支因素優化。

我已經把許多鏈接到維基百科，但如果你喜歡這個問題，我建議您：提高空間效率（除了共享的價值觀，這（如bennofs中指出

Introduction to algorithms

來源

2013-07-09 16:55:40 Galigator

的一種方式註釋）你可以使用sys.intern來高效地完成）是使用hopscotch hashing，這是一個開放的尋址方案（一種線性探測的變體）來解決衝突 - 封閉的尋址方案使用更多的空間，因爲你需要分配一個鏈表對於每個存儲桶而言，採用開放式尋址方案時，您只需在後備陣列中使用一個開放的相鄰插槽而無需任何必要ng來分配任何鏈接列表。與其他開放尋址方案（如杜鵑散列或香草線性探測）不同，跳房散列在高負載因子（超過90％）下表現良好，可確保恆定時間查找。

來源

2013-07-09 16:55:51

尺寸高效字典（關聯數組）實現

回答

相關問題