I want to choose a random element (uniform distribution) from a python set in O(1) time. Is this possible? I've seen it suggested that one first convert the set to a list then select the random element from the list however this will take O(n) time where n is the size of the set. If this is not possible, what is a reasonably fast alternative?
1 Answers
I think it is impossible to get a random element from a hashtable (how a set is implemented) because it does not support random access. random.choice needs random access for this reason. You have a good alternative in set.pop, but it doesn't appear to be uniform (see https://github.com/python/cpython/blob/master/Objects/setobject.c#L616).
As long as it's not performance critical in a tight loop, converting to a list should be fine. However, if it does matter a lot, maybe you can consider using a different data structure in the first place.
Related