在O(1)时间内从一个集合中选择一个随机元素。

Question

在O(1)时间内从一个集合中选择一个随机元素。

3

我希望能够在Python集合中以O(1)的时间复杂度内随机选择一个元素（均匀分布）。这是否可能？有人建议先将集合转换为列表，然后从列表中选择随机元素，但这将需要O(n)的时间，其中n是集合的大小。如果不可能实现这一点，那么有什么合理快速的替代方案吗？

- Mathew

1

你可以使用字典并保持键和值不变，然后在其上调用 random.choice。你的使用情况是什么 - 是否需要一个集合？据我所知，我认为没有比 O(n) 更好的方法，但也许我错了，因为直觉上似乎应该没有问题。 - ggorlen

我认为你不能在O(1)时间内从一个集合中随机选择。使用列表似乎是一个合理的方法。除非你的集合非常大，否则这似乎不应该成为问题。 - khelwood

2

时间复杂度，来自Python维基百科。 - jsmart

1

如果你真的需要一个集合数据结构，有许多第三方的 orderedset 实现可用 - 可以参考 PyPi，并且应该可以从支持索引的集合中删除一个随机元素。还可以参考 Does Python have an ordered set?。 - martineau

你是否试图拥有一个数据结构，既可以暴露类似于集合的操作，又可以使用 random() 方法？ - Alexandru Barbarosie

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- iz_ · Accepted Answer

我认为从哈希表（实现集合的方式）中获取一个随机元素是不可能的，因为它不支持随机访问。这就是为什么random.choice不能使用。你可以使用set.pop作为一个很好的替代方法，但它似乎不够均匀（参见https://github.com/python/cpython/blob/master/Objects/setobject.c#L616）。

只要它不是在紧密循环中对性能至关重要，将其转换为列表就可以了。然而，如果非常重要，也许你可以考虑在一开始就使用不同的数据结构。