On Tue, Nov 3, 2009 at 5:10 PM, Antoine Pitrou <solipsis@pitrou.net> wrote:
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)
Clever. But I don't think the set implementation should have a dependency on random(), so it would have to expose an "indexing" operation, which smells like it would expose too much of the implementation for comfort. -- --Guido van Rossum (python.org/~guido)