What is the fastest way to get an arbitrary element out of a Python dictionary?

Question

I have a dict with approximately 17,000 keys. I would like to select one key at a time--it doesn't matter which one, and I don't need it to happen in any particular order (random is fine). However, after I select a key, I will alter the dictionary, perhaps by adding or deleting a key, before selecting another one. Therefore, I do not have a set list of keys that I can iterate through.

Since I don't need to access them in any particular order, I could convert the dict keys into a list each time, and then pop the first element. However, since there are 17,000 keys, making a list takes approximately 0.0005-7 seconds over each iteration, which will take too much time for what I need. Is there a shortcut I could take so that I don't have to compile an enormous list out of dict keys each time I want to select a single key?

Answer 1

There are multiple ways, but you'll need to make some tradeoffs. One way is to empty the dictionary out using popitem; it is atomic, and will use an arbitrary order. But it modifies the dictionary itself; whatever item was selected isn't in it anymore. The next method that comes to mind is iterating as usual, even while modifying the dictionary; the order of items might change, so you could get items any number of times. To track that, you could build a second set of visible keys. It's reasonably cheap to add keys to the set, cheap to check if each item is in it, and when you've gone through the whole dictionary you can check if the set matches the dictionary's keys to determine if there are ones you missed (or removed). You do end up building a key set but only one item per iteration; in the pessimal case we have the dictionary being modified in such a way we scan through the whole set of visited items before finding the new item.

Is there a reason this data needs to be kept in a dictionary only? For instance, if we consider a system where we're shuffling songs, we might not want to visit the whole library but only place a limit on how recently a song has been played. That could be more efficiently handled using a list of songs wherein we can read a random index, a set of recently played songs to avoid duplicates, and a queue (perhaps in a list or deque) of songs allowing us to update the set in order (removing the last entry each iteration). Bear in mind that references are reasonably cheap.

Rethinking one more step we wouldn't need the keys to check for duplicates if they simply aren't in our candidates; by just swapping the oldest played song with the randomly selected next song, both the played and candidate lists stay constant size and no lookups are needed since songs are in only one of the lists.

Another idea is to use collections.ChainMap to keep a consistent view into two dictionaries; ones that have been visited and ones that have not. You could then migrate items from the latter to the former by way of popitem, ensuring a readable method of processing everything in the collection while keeping it dictionary-like.

def getnewitem(chainmap):
    # Raises KeyError when finished
    key,value=chainmap.maps[0].popitem()
    chainmap.maps[1][key]=value
    return key,value

As that means both dictionaries keep changing, it's likely not the fastest overall, but it maintains both a dictionarylike collection and a capability to process all items. It does lose the ability to directly delete items, since ChainMap cannot hide inherited mappings; you'd need to remove them from the backing dictionaries.

Answer 2

As SRC mentioned in the comments, the ideal solution is an indexed dictionary, which is available via randomdict:

Building a 17,000 k,v dict and running timeit:

t = timeit.Timer(my_dict.random_item)
print t.repeat()

[2.3373830318450928, 2.284735918045044, 2.2462329864501953]

which gives about 2.2μs/choice.

The other suggested answers are either not as fast, not random, or both.

Answer 3

Thank you, vaultah! You proposed:

next(iter(dict)))

This takes approximately 0.00003 seconds, reducing time by a bit more than a factor of 10, and therefore works as fast as I need it to.

n1c9, you also made an interesting suggestion of:

dict.popitem()

This is a function I hadn't known about before, but unfortunately takes 0.0002 seconds, not much of an improvement over my initial time.

Answer 4

As dict() is sorted according to internal hashes used for fast access and not by order in which you added elements to it, you can take it for be random enough and use dict.popitem().

But popitem() will also remove this element from the dictionary. So you may wish to use:

d = {...}
keys = d.keys()
item = keys.pop(0)
value = d[item]

instead. However, note that any dict with same/similar keys may have the same order of keys.

If you want proper random getting then do:

import random
d = {"red": "#ff0000", "green": "#00ff00", "blue": "#0000ff", "black": "#000000", "white": "#ffffff"}
keys = d.keys()
item = random.choice(keys)
value = d[item]

Of course, if you wish to prevent repetition you will have to use additional dict() and while loop:

import random
d = {"red": "#ff0000", "green": "#00ff00", "blue": "#0000ff", "black": "#000000", "white": "#ffffff"}
keys = d.keys()
used = {}
def get_rand_item (d):
    item = random.choice(keys)
    while item in used:
        item = random.choice(keys)
    value = d[item]
    used[item] = None
    return item, value
get_rand_item(d)

Here I use dict as storage because its search is faster than a list.

You asked for the fastest way. :D

While I am at it, let see if I can get even faster way of getting random items without repetitions:

from random import choice

class RandomGetter:
    def __init__ (self, d, adapt=1):
        self.keys = keys = d.keys()
        if adapt:
            # Could be done in place too
            dct = {}
            for k in keys:
                dct[k] = (d[k], 0)
            self.dct = dct
            self.count = 1
        else:
            self.dct = d
            # Assume all items have been visited
            self.count = d[keys[0]][1]+1
        self.visited = 0
        self.length = len(self.dct)

    def __len__ (self):
        return self.length

    def randitem (self, default=None):
        if self.visited==self.length:
            # After 'default' is returned (all items gotten),
            # same RandomGetter() can be used again:
            self.count += 1
            self.visited = 0
            return default
        d  = self.dct
        kz = self.keys
        c  = self.count
        key = choice(kz)
        value, flag = d[key]
        while flag>=c:
            key = choice(kz)
            value, flag = d[key]
        d[key] = (value, flag+1)
        self.visited += 1
        return key, value

    def next (self):
        i = self.randitem()
        if i==None: raise StopIteration
        return i

    def __iter__ (self):
        while 1: yield self.next()

# Now testing:
# Lets create a dictionary of one million items:
d = dict.fromkeys(xrange(1000000))
# This takes about 0.128 seconds
# Now, lets initialize Rg
r = RandomGetter(d)
# If dict is not prepared in advance, as this one isn't we use adapt=1 and it takes
# about 8.92 seconds. Yack!
# Now measure time for each random getting:
from time import time
def check ():
    randitem = r.randitem # Faster access to the method
    e = []
    for _ in xrange(len(r)):
        t = time()
        randitem()
        e.append(time()-t)
    print "Total/min/max/med/avg/(0 time count)"
    e.sort()
    s = sum(e)
    if len(r)%2==0: m = (e[len(r)/2]+e[len(r)/2+1])/2
    else: m = e[len(r)/2+1]
    print s, e[0], e[-1], m, ("%.15f" % (s/1000000)), e.count(0.0)
check()
# It yields following results on my machine:
# About 25.224 seconds to randomly get all 1000000 items
# Minimal time needed is not measurable using this technique so it is 0.0
# Maximal time needed to get an item is about 1.678 seconds
# Median results with 0.0, thus we know that more than half randomly gotten items took practically no time
# In fact, there are about 998808 items with getting time of 0.0 seconds
# Average getting time is about 0.000025224 seconds
# By examining results closely I deduced that only last few items took a long time to get them.
# All in all, not bad for one million items, in my opinion anyway.
# For dict of 2000 items, total time was 0.016 and that was also the maximal value and it was for the last gotten item
# Time didn't cross one second until length of a given dictionary wasn't bigger than 100000
# If you want, you can run my code through timeit to recheck, but it seems that it is faster
# than suggested random dictionary.