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

[Guido van Rossum]

On Tue, Nov 3, 2009 at 5:10 PM, Antoine Pitrou <solipsis at 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)