random choice from dictionary
ben.usenet at bsb.me.uk
Sun Dec 23 22:09:14 EST 2018
"Avi Gross" <avigross at verizon.net> writes:
> The following is a function that iterates over the dictionary one key at a
> time and when it reaches a random one, it returns the key without further
> evaluation. On the average, it takes N/2 iterations for N keys. Asking to
> make a list(data) may be efficient in terms of time and indexing is fast but
> space is used maximally unless it just points to existing storage.
> Here is one way to do the function. Some might use an emum instead.
> def rand_key(data):
> """Get a random key from a dict without using all of memory."""
> import random
> randy = random.randrange(len(data))
> this = 0
> for key in data:
> if (this == randy):
> this += 1
There is beautiful variation on this that can select k random keys:
def sample_keys(data, k = 1):
"""Return k random keys from a dict."""
items = len(data)
keys = 
for key in data:
r = random.random()
if r < k/items:
k -= 1
items -= 1
And there is a variation on /that/ will use fewer random numbers --
essentially picking a number of "skip" distances as you pick one. But
it's late, and I need to get ready to eat lots...
More information about the Python-list