Selecting a Random Value from dictionary in constant time in Python 3?

Question

I know that you can select a random value from a dictionary in several ways.

In Python 2:

random.choice(d.keys())

In Python 3:

random.choice(list(d.keys()))

Nonetheless, both approaches require a transformation, i.e. linear time O(n), to a list before the random selection. For example, I know that in Python 3 d.keys() returns an iterator and I am guessing that in Python 3 the list is created internally from the dictionary.

Is it possible to select a value from a dictionary in constant time, i.e. O(1)?

EDIT: For the comments so far, I think that it is not possible, at least not in a straight forward fashion. Auxiliary structures are required.

EDIT 2: I thought that the dictionary could have a random choice in constant time since internally it is a hash table, i.e. internally it has to have an array or something similar. Of course, it depends on the internal implementation, but theoretically I think it is possible.

Answer 1

There in only one kind of (minor) optimization I can imagine in this situation: do not create list, just get a random number r and iterate d.keys() until you get r-th item.

def take_nth(sequence, n):
    i = iter(sequence)
    for _ in range(n):
        next(i)

    return next(i)

import random
rand_key = d[take_nth(d.keys(), random.randint(0, len(d)-1))]

This would give you a bit better performance, because you wouldn't have to iterate the whole list each time, but it's still a bad idea.

If you want do that random selection repeatedly over a fixed dictionary, than just cache its keys into a separate list and index it with a random index value.

UPD:

To sum up the discussion in comments, the following class with forward/backward caching and reusing deleted items may be helpful:

import random

class RandomSampleDict(object):

    def __init__(self):
        self.data     = {}
        self.cache_ik = {}
        self.cache_ki = {}
        self.track    = []

    def lookup(self, key):
        return self.data[key]

    def set(self, key, value):
        self.data[key] = value

    def add(self, key, value):
        self.data[key] = value
        if len(self.track) == 0:
            i = len(self.data) - 1
        else:
            i = self.track.pop()

        self.cache_ik[i] = key
        self.cache_ki[key] = i

    def delete(self, key):
        del self.data[key]
        i = self.cache_ik[i]
        del self.data_ik[i]
        del self.data_ki[key]

        self.track.append(i)

    def random_sample_key(self):
        key = None
        while key is None:
            i = random.randint(0, len(self.data))
            if i in self.cache_ik:
                return self.cache_ik[i]

Answer 2

next(islice(d.values(),np.random.randint(0, len(d)-1),None)) is the best performing method I've found to select a random value from dict d in Python 3. This is explained in the following discussion.

Some standard library random methods take much more run time than comparable numpy.random methods. For example:

import numpy as np

timeit random.randint(0, 10)
100000 loops, best of 3: 2.52 µs per loop

timeit np.random.randint(0, 10)
1000000 loops, best of 3: 453 ns per loop

Using numpy.random.randint can improve the runtime of methods for selecting a random value of a dict:

from itertools import islice
import random

d = {1:'a',2:'b',3:'c',4:'d',5:'e',6:'f',7:'g',8:'h',9:'i',10:'j'}

timeit next(islice(d.values(),random.randint(0, len(d)-1),None))
100000 loops, best of 3: 3.58 µs per loop

timeit next(islice(d.values(),np.random.randint(0, len(d)-1),None))
100000 loops, best of 3: 1.26 µs per loop

# d[5] access time is about 25X smaller than 1.26 µs
timeit d[5]
10000000 loops, best of 3: 51.3 ns per loop

def take_nth(sequence, n):
    i = iter(sequence)
    for _ in range(n):
        next(i)
    return next(i)

timeit d[take_nth(d.keys(), random.randint(0, len(d)-1))]
100000 loops, best of 3: 5.07 µs per loop

timeit d[take_nth(d.keys(), np.random.randint(0, len(d)-1))]
100000 loops, best of 3: 2.66 µs per loop

Answer 3

It is clear, I think, that this is not possible through the standard dict public API.

However, there are several drop-in replacements for dict which provide efficient access to the keys in some sorted order. This can then be indexed to obtain a random element. Although their theoretical asymptotics are not identical to dict, in practice they generally perform as well or better.

The blist package from Stutzbach Enterprises provides blist.sorteddict which is specifically tested to be completely compatible with dict. It provides indexing into its key view which is logarithmic complexity. It is implemented with B+Trees.

The SortedContainers package from Grant Jenks provides sortedcontainers.SortedDict which similarly provides efficient indexing of its key view.

Others are also available, typically based on search trees.

Answer 4

Under the assumption that this can't be done using the Python dict alone and that a second data structure is required, then here's a cheap and efficient secondary data structure which just tracks the current nodes.

It just keeps nodes in a list. To support delete it just empties the location and keeps another list of free space.

Note that if you only delete nodes randomly then this is fine as it stands. If you want to delete nodes that are chosen by some other method, then you'll need to store the sequence numbers in the nodes, so that you can find them to delete.

It works well unless you get into the situation where the nodes list becomes mostly empty when the random sampling becomes slow. If you need to handle that situation, then you'll need to reallocate the list at that point - which is OK as an amortised cost but adds quite a bit of complication. For example, you'll need to add a dictionary from nodes to sequence numbers and update that when you reallocate the nodes list.

import random
RNG = random.Random()

class Tracker(object):

    def __init__(self):
        self.free = []
        self.nodes = []

    def add(self,node):
        if self.free:
            seq_num = self.free.pop()
            self.nodes[seq_num] = node
        else:
            seq_num = len(self.nodes)
            self.nodes.append(node)

    def random_node(self):
        seq_num = RNG.randint(0,len(self.nodes)-1)
        while self.nodes[seq_num] == None:
            seq_num = RNG.randint(0,len(self.nodes)-1)
        return self.nodes[seq_num],seq_num

    def delete(self,seq_num):
        self.nodes[seq_num] = None
        self.free.append(seq_num)

    def delete_random_node(self):
        node,seq_num = self.random_node()
        self.delete(seq_num)
        return node

There may be some small optimisations available here. Replacing the free list by a collections.deque might make it a little faster because lists slow down a little if their size changes too often. But it's no big deal. I think your nodes list will hit an equilibrium size and then become very efficient but you could pad it out with Nones to start with to avoid the start up cost of repeatedly growing. You could do a little common sub-expression elimination. But all these will have only small effects.