Nov. 3, 2009
6:10 p.m.
Greg Ewing <greg.ewing <at> canterbury.ac.nz> writes:
Picking a random element can be done in O(1) only if the data structure supports access by index, which Python's hash tables don't.
Well, at the implementation level, they can. You'd just have to pick a new random index until it points to a non-empty slot.
But that's hardly O(1).
It is, assuming that the set has a built-in minimum fill level (e.g. it always keeps at least x% of its entries filled), and the random generator is good. (of course, it is "statistically O(1)", like lookups in a hash table actually) Regards Antoine.