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. _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com