random choice from dictionary

[Ben Bacarisse]

"Avi Gross" <avigross at verizon.net> writes:
<snip>
> 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):
>             return(key)
>         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."""
    import random
    items = len(data)
    keys = []
    for key in data:
        r = random.random()
        if r < k/items:
            keys.append(key)
            k -= 1
        items -= 1
    return keys

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...

<snip>
-- 
Ben.