二者合并的最快方法：dicts vs list

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}}

我的问题是，对于这两个dict中的值，当我的优先级是使用尽可能多的内存以最大限度地利用CPU时，我应该使用dict（如上所示）还是list（如下所示）？在

为了澄清，使用列表如下所示：

^{pr2}$

旁注：我使用嵌套在dict中的dict而不是嵌套在dict中的集合的原因是JSON不允许我这样做json.dumps文件因为集合不是键/值对，所以它是（就JSON库而言）{“a”，“series”，“of”，“keys”}

另外，在选择使用dict到一个列表之后，我将如何实现最有效的，就CPU而言，合并它们的方法呢？在

我很感激你的帮助。在

Answer 1

这实际上取决于您想如何处理内部列表/字典中的值。如果添加新条目时，希望内部列表只有唯一值，那么对于大型列表，列表实现将变慢。它的规模大致为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注册编码器和解码器，这样您就可以自动地进行此转换。然而，当问题如此小且包含在内时，我通常不必费心。

因此，在基于字典的方法中，您可以做到：

^{pr2}$

如果您希望大的dict只对字典进行copy操作，则在最后一行使用^{{cd1>}而不是^{cd2>}。您也可以在最后一个循环中使用^{{cd3>}和^{{cd4>}，但是^{{cd5>}…^{cd6>}是一个更快的分数（在我的机器上，YMMV）。

Answer 2

任何哈希容器都比这类东西的列表好。在

我仍然使用set而不是dict；如果您在使用json.dumps时遇到问题，可以在开始序列化时将集合转换为dict:dict.fromkeys(the_set, 1) 把它们拔出来：set(the_dict.keys())
这比注册JSON提供程序要容易得多。在

至于合并：merged_set = bigger_set.union(smaller_set)

Answer 3

首先，我将采用dict-of-dicts方法，因为Python有一个经过优化的dict实现，所以我非常怀疑使用dict-of-list是否能更好。在

至于合并dicts，这就足够了：

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

我可能还会尝试使用子类化json.JSONEncoder来序列化集合类型：

^{pr2}$

然而，后一种方法可能会在序列化方面增加一些开销，而且您还需要在反序列化时将这些dict转换为集合，方法是通过子类化json.JSONDecoder，或者在额外的步骤中自己执行。在