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

Question

我有一个包含大约 17,000 个键的字典。我想一次选择一个键——哪个键并不重要，我不需要它以任何特定顺序发生(随机就好)。但是，在我选择一个键之后，我会在选择另一个键之前更改字典，可能是通过添加或删除一个键。因此，我没有可以循环访问的一组键列表。

因为我不需要以任何特定顺序访问它们，所以我可以每次都将字典键转换成一个列表，然后弹出第一个元素。但是，由于有 17,000 个键，每次迭代制作一个列表大约需要 0.0005-7 秒，这对我需要的来说会花费太多时间。有没有我可以采取的捷径，这样我就不必每次想选择一个键时都用字典键编译一个巨大的列表？

Answer 1

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

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

再考虑一步，如果它们根本不在我们的候选人中，我们就不需要 key 来检查重复项；通过仅将最旧播放的歌曲与随机选择的下一首歌曲交换，播放列表和候选列表的大小保持不变，并且不需要查找，因为歌曲仅在其中一个列表中。

另一个想法是使用 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 无法隐藏继承的映射；您需要将它们从支持词典中删除。