从Python字典中获取任意元素的最快方法是什么？

Question

我有一个大约17,000键的字典.我想一次选择一个键 - 哪个键无关紧要,我不需要以任何特定顺序发生(随机就好了).但是,在我选择一个键之后,我会在选择另一个键之前更改字典,可能是通过添加或删除键.因此,我没有可以迭代的密钥集.

由于我不需要以任何特定顺序访问它们,我可以每次将dict键转换为列表,然后弹出第一个元素.但是,由于有17,000个键,因此在每次迭代时制作一个列表大约需要0.0005-7秒,这将花费我太多的时间来满足我的需要.有没有我可以采取的快捷方式,以便每次我想选择一个密钥时,我不必用dict键编译一个庞大的列表？

Answer 1

有多种方法,但你需要做出一些权衡.一种方法是使用popitem清空字典; 它是原子的,并将使用任意顺序.但它修改了字典本身; 选择的任何项目都不在其中.想到的下一个方法是像往常一样迭代,即使在修改字典时也是如此; 项目的顺序可能会发生变化,因此您可以多次获取项目.要跟踪它,您可以构建第二组可见键.将密钥添加到集合中是相当便宜的,检查每个项目是否在其中是否便宜,并且当您浏览整个字典时,您可以检查该集合是否与字典的密钥匹配以确定是否存在您错过的密钥(或去除).你最终建立一个密钥集,但每次迭代只有一个项目; 在pessimal情况下,我们以这样的方式修改字典,我们在找到新项目之前扫描整个被访问项目集.

这个数据是否只需要保存在字典中？例如,如果我们考虑一个我们正在洗牌的系统,我们可能不想访问整个图书馆,但只限制一首歌的播放时间.使用歌曲列表可以更有效地处理,其中我们可以读取随机索引,一组最近播放的歌曲以避免重复,以及歌曲的队列(可能在列表或双端队列中)允许我们按顺序更新集合(每次迭代删除最后一个条目).请记住,引用相当便宜.

重新思考一步,如果他们根本不在我们的候选人中,我们就不需要密钥来检查重复项; 通过用随机选择的下一首歌曲交换最老的播放歌曲,播放和候选列表都保持恒定大小并且不需要查找,因为歌曲仅在一个列表中.

另一个想法是使用collections.ChainMap将一致的视图保存到两个词典中; 已访问过的和未访问过的.然后,您可以通过popitem将项目从后者迁移到前者,确保处理集合中所有内容的可读方法,同时保持字典类似.

def getnewitem(chainmap):
    # Raises KeyError when finished
    key,value=chainmap.maps[0].popitem()
    chainmap.maps[1][key]=value
    return key,value

因为这意味着两个字典都在不断变化,它可能不是最快的整体,但它既保留了字典集合,又保持了处理所有项目的能力.它确实失去了直接删除项目的能力,因为ChainMap无法隐藏继承的映射; 你需要从支持词典中删除它们.