最快的方法合併的兩個：字典vs列表

Question

我正在做一些索引和內存是足夠的，但CPU不是。所以，我有一個巨大的字典，然後一個小字典，我合併成一個更大：

big_dict = {"the" : {"1" : 1, "2" : 1, "3" : 1, "4" : 1, "5" : 1}} 
smaller_dict = {"the" : {"6" : 1, "7" : 1}} 
#after merging 
resulting_dict = {"the" : {"1" : 1, "2" : 1, "3" : 1, "4" : 1, "5" : 1, "6" : 1, "7" : 1}} 

我的問題是在這兩種類型的字典中的值，我應該使用的字典（如上顯示）或列表（如下圖所示）當我的優先級是儘可能多地使用內存以充分利用我的CPU時？

爲了清楚起見，使用列表將如下所示：

big_dict = {"the" : [1, 2, 3, 4, 5]} 
smaller_dict = {"the" : [6,7]} 
#after merging 
resulting_dict = {"the" : [1, 2, 3, 4, 5, 6, 7]} 

邊注：我使用的是嵌套在一個字典，而不是嵌套在一個字典一組字典的原因是因爲JSON不會讓我做json.dumps，因爲一組不是鍵/值對，它（就JSON庫而言）{「a」，「series」，「of」，「keys」}

，在選擇使用字典到列表之後，我將如何去實現最高效的CPU合併方法？

我很感激幫助。

Answer 1

嗯。我首先會選擇一種字典的方式，因爲Python是最精細的字典實現之一，所以我非常懷疑你可以通過使用字典來獲得更好的效果。

至於合併類型的字典，這已經足夠了：

for key, value in smaller_dict.iteritems(): 
    try: 
     big_dict[key].update(value) 
    except KeyError: 
     big_dict[key] = dict(value) 

我可能也與子類json.JSONEncoder實驗，以進行串行化的集類型：

class SetEncoder(json.JSONEncoder): 
    def default(self, obj): 
     if isinstance(obj, set): 
      return dict.fromkeys(obj) 
     return json.JSONEncoder.default(self, obj) 

後一種方法可能會增加但是，在序列化方面需要一些開銷，並且您還需要在反序列化時將這些字符串轉換爲集合，可以通過子類化json.JSONDecoder或在額外的步驟中自己完成。

Answer 2

這實際上取決於你想對內部列表/字典中的值做什麼。如果當你添加一個新條目時，你希望內部列表只有唯一值，那麼對於大型列表來說，列表實現將會是很多較慢。它大致在O（n）處縮放，而不是O（1）[字典的平均情況]。

如果你不關心這些內部列表中的倍數，那麼它是更接近的事情。

我會使用字典，因爲你有。 Python的字典有很高的效率（作爲試圖在C中實現實時應用程序的字典數據結構的人說話）。

至於不使用集合。這會更好一些（因爲內存不是問題，你說）來調整序列化，並且讓代碼中速度至關重要的部分儘可能簡單。反序列化後，只需通過並將列表轉換爲集：

big_dict = {"the" : [1, 2, 3, 4, 5]} # imagine we got this from JSON 

for key, value in big_dict: 
    big_dict[key] = set(value) 

應該這樣做。除非您始終對整個索引進行序列化/反序列化，否則這些額外的預處理成本應該按照足夠多的請求進行攤銷而無需擔心。

或者，您可以使用JSON註冊編碼器和解碼器，以便您可以自動執行此轉換。但是，當問題很小並且被包含時，我通常不打擾。

所以在你的字典爲基礎的方法，你可以這樣做：

for key, value in smaller_dict.items(): 
    if key in big_dict: 
     big_dict[key].update(value) 
    else: 
     big_dict[key] = value 

如果你想big_dict只副本字典，在最後一行用dict(value)代替value。您也可以在最後一個循環中使用try:和except KeyError，但if ... else的分數更快（在我的機器上，YMMV）。

Answer 3

任何哈希容器都會比這種東西的列表更好。

我仍然使用set而不是dict;如果您遇到json.dumps問題，您可以通過將該設置轉換爲字典來進行序列化：dict.fromkeys(the_set, 1) 並拉出它們：set(the_dict.keys())
這比註冊JSON提供者更容易。

至於合併：merged_set = bigger_set.union(smaller_set)