最快的方法合并的两个：字典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)