RetroSearch Browse

Wed Nov 4 02:10:58 CET 2009 · https://mail.python.org/pipermail/python-dev/2009-November/093691.html

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.

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://mail.python.org/pipermail/python-dev/2009-November/093691.html below:

[Python-Dev] Retrieve an arbitrary element from a set withoutremoving it