dict.update() 计算效率高还是有更有效的替代方案? [英] Is dict.update() computationally efficient or are there more efficient alternatives?

问题描述

我正在运行的代码使用 16 个进程来构建 16 个长度约为 62,500 的字典(总共约 1,000,000).每个过程完成后，我会更新一个字典，如下所示:

I'm running code which uses 16 processes to build up 16 dictionaries of length approximately 62,500 (that's about 1,000,000 in total). After each process finishes I update a single dictionary like this:

main_dict.update(sub_dict)

我发现我的代码似乎在整个脚本的结尾处挂了很多(大约在我希望我的一些进程开始返回它们的 sub_dict 时).所以我怀疑字典更新了.

I'm finding that my code seems to hang a lot near the end of the whole script (around when I'd expect some of my processes to start returning their sub_dicts). So I'm suspecting the dictionary update.

据说更新需要根据 main_dict 的每个键检查 sub_dict 的每个键，所以在我的例子中，这可能意味着对上次更新进行多达 62500*937500 次检查，对吗?

Supposedly update needs to check every key of the sub_dict against those of the main_dict so with my example that could mean up to 62500*937500 checks for the last update, right?

我在正确的轨道上吗?如果是这样，有没有办法加快速度?我知道这些键将是唯一的，并且 sub_dict 之间永远不会重叠，所以也许这会有所帮助.

Am I on the right track here? And if so, is there a way to speed things up? I know the keys are going to be unique and there will never be overlap between the sub_dicts so maybe that helps.

推荐答案

python 中的时间复杂度已记录这里.

The time complexity in python is documented here.

正如@MicahSmith 已经回答(在评论中)更新 dict 的复杂性平均为 O(1) 和 摊销最坏情况.这是因为它遍历 dict 键和值.

As @MicahSmith already answered (in the comments) the complexity with updating a dict is O(1) in the average and O(n) in Amortized Worst Case. This is due it iterating over the dict keys and values.

这篇关于dict.update() 计算效率高还是有更有效的替代方案?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！