python - python - 用于快速添加、删除和随机选择的数据结构

Question

我需要一个用于添加项目、删除项目和选择随机项目的数据结构。

从我读过的内容来看，我认为从列表中选择一个随机项目random.choice需要恒定的时间。但是，从列表中删除一个项目需要 O(n) 时间。

另一方面，从集合中删除和添加项目需要 O(1) 时间，但从集合中选择随机元素random.sample需要 O(n) 时间。

有没有办法在 O(1) 时间内支持这三个操作？

标签： pythonpython-3.xdata-structures

Answer 1

为什么不使用字典？我知道这有点奇怪，但平均而言 dict 查找和插入是 O(1)。您可以在其上使用 random.choice，因为它支持索引！

这是一张图表，显示了在 dict 上使用 random.choice 所花费的时间。x 轴是字典的大小，y 轴是时间。