Каков самый быстрый способ получить произвольный элемент из словаря Python?

Ответ 1

Существует несколько способов, но вам нужно сделать некоторые компромиссы. Один из способов - освободить словарь, используя popitem; он является атомарным и будет использовать произвольный порядок. Но он сам модифицирует словарь; какой бы элемент ни был выбран, в нем больше нет. Следующий метод, который приходит на ум, повторяется, как обычно, даже при изменении словаря; порядок элементов может измениться, поэтому вы можете получать предметы сколько угодно раз. Чтобы отслеживать это, вы могли бы создать второй set видимых клавиш. Достаточно дешево добавить ключи к набору, дешево проверить, есть ли в нем каждый элемент, и когда вы прошли весь словарь, вы можете проверить, соответствует ли набор клавишам словаря, чтобы определить, есть ли у вас пропущенные (или удалены). В итоге вы создаете набор ключей, но только один элемент на итерацию; в пессиментальном случае мы модифицируем словарь таким образом, что перед поиском нового элемента мы просматриваем весь набор посещенных элементов.

Есть ли причина, по которой эти данные должны храниться только в словаре? Например, если мы рассмотрим систему, в которой мы перетасовываем песни, мы, возможно, не захотим посетить всю библиотеку, а ограничимся только тем, как недавно была воспроизведена песня. Это можно было бы более эффективно обрабатывать, используя список песен, в которых мы можем прочитать случайный индекс, набор недавно воспроизведенных песен, чтобы избежать дубликатов, и очередь (возможно, в списке или дека) песен, что позволяет нам обновлять набор в порядке (удаление последней записи на каждой итерации). Имейте в виду, что ссылки достаточно дешевы.

Переосмыслив еще один шаг, нам не нужны ключи для проверки дубликатов, если они просто не в наших кандидатах; просто заменяя самую старую пьесу со случайно выбранной следующей песней, как список воспроизведения, так и список кандидатов остаются постоянными, и поиск не требуется, так как песни находятся только в одном из списков.

Другая идея - использовать collections.ChainMap, чтобы обеспечить последовательное отображение двух словарей; те, которые были посещены, и те, которые этого не сделали. Затем вы можете перенести элементы из последнего в прежнее с помощью popitem, обеспечивая читаемый способ обработки всего в коллекции, сохраняя при этом словарь.

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

Поскольку это означает, что оба словаря продолжают меняться, это, вероятно, не самый быстрый результат, но он поддерживает как сборник в словаре, так и возможность обрабатывать все элементы. Он утрачивает возможность прямого удаления элементов, поскольку ChainMap не может скрыть наследуемые сопоставления; вам нужно будет удалить их из поддерживающих словарей.

Ответ 2

Как упоминается в комментариях SRC, идеальным решением является индексированный словарь, который доступен через randomdict:

Создание 17 000 k, v dict и время выполнения:

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

[2.3373830318450928, 2.284735918045044, 2.2462329864501953]

который дает около 2.2μs/choice.

Другие предлагаемые ответы либо не так быстро, не случайны, либо оба.

Ответ 3

Спасибо, vaultah! Вы предложили:

next(iter(dict)))

Это занимает приблизительно 0,00003 секунды, сокращая время на бит более чем в 10 раз, и поэтому работает так же быстро, как мне нужно.

n1c9, вы также сделали интересное предложение:

dict.popitem()

Это функция, о которой я раньше не знал, но, к сожалению, занимает 0.0002 секунды, а не улучшение по сравнению с моим начальным временем.

Ответ 4

Поскольку dict() сортируется в соответствии с внутренними хэшами, используемыми для быстрого доступа, а не по порядку, в который вы добавили к нему элементы, вы можете считать его случайным и использовать dict.popitem().

Но popitem() также удалит этот элемент из словаря. Поэтому вы можете использовать:

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

вместо этого. Однако обратите внимание, что любой dict с одинаковыми/похожими ключами может иметь одинаковый порядок ключей.

Если вы хотите получить правильное случайное получение, выполните:

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

Конечно, если вы хотите предотвратить повторение, вам придется использовать дополнительные dict() и 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)

Здесь я использую dict как хранилище, потому что его поиск быстрее, чем список.

Ты попросил самый быстрый способ.: D

Пока я нахожусь на этом, давайте посмотрим, смогу ли я получить еще более быстрый способ получения случайных элементов без повторений:

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.