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)
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4