Python получает случайный ключ в словаре в O (1)

Ответ 1

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

Если вам не нужен действительно случайный выбор, а просто нужен какой-то произвольный ключ, вот два простых варианта, которые я нашел:

key = next(iter(d))    # may be a little expensive, but presumably O(1)

Второй действительно полезен только в том случае, если вы счастливы использовать ключ + значение из словаря, и из-за мутации (-ов) это не будет столь же алгоритмически эффективным:

key, value = d.popitem()     # may not be O(1) especially if next step
if MUST_LEAVE_VALUE:
    d[key] = value

Ответ 2

[edit: Полностью переписано, но сохраняю вопрос здесь с комментариями нет.]

Ниже представлена ​​реализация словарной оболочки с O (1) get/insert/delete и выбор O (1) случайного элемента.

Основная идея заключается в том, что мы хотим иметь O (1), но произвольное отображение от range(len(mapping)) к ключам. Это позволит нам получить random.randrange(len(mapping)) и передать его через отображение.

Это очень сложно реализовать, пока вы не поймете, что мы можем воспользоваться тем, что отображение может быть произвольным. Ключевой идеей для достижения жесткой границы времени O (1) является следующее: всякий раз, когда вы удаляете элемент, вы меняете его с наивысшим элементом произвольного идентификатора и обновляете любые указатели.

class RandomChoiceDict(object):
    def __init__(self):
        self.mapping = {}  # wraps a dictionary
                           # e.g. {'a':'Alice', 'b':'Bob', 'c':'Carrie'}

        # the arbitrary mapping mentioned above
        self.idToKey = {}  # e.g. {0:'a', 1:'c' 2:'b'}, 
                           #      or {0:'b', 1:'a' 2:'c'}, etc.

        self.keyToId = {}  # needed to help delete elements

Получить, установить и удалить:

    def __getitem__(self, key):  # O(1)
        return self.mapping[key]

    def __setitem__(self, key, value):  # O(1)
        if key in self.mapping:
            self.mapping[key] = value
        else: # new item
            newId = len(self.mapping)

            self.mapping[key] = value

            # add it to the arbitrary bijection
            self.idToKey[newId] = key
            self.keyToId[key] = newId

    def __delitem__(self, key):  # O(1)
        del self.mapping[key]  # O(1) average case
                               # see http://wiki.python.org/moin/TimeComplexity

        emptyId = self.keyToId[key]
        largestId = len(self.mapping)  # about to be deleted
        largestIdKey = self.idToKey[largestId]  # going to store this in empty Id

        # swap deleted element with highest-id element in arbitrary map:
        self.idToKey[emptyId] = largestIdKey
        self.keyToId[largestIdKey] = emptyId

        del self.keyToId[key]
        del self.idToKey[largestId]

Выбор случайного (ключ, элемент):

    def randomItem(self):  # O(1)
        r = random.randrange(len(self.mapping))
        k = self.idToKey[r]
        return (k, self.mapping[k])

Ответ 3

Вот несколько запутанный подход:

• Назначьте индекс каждой клавише, сохраняя ее со значением в словаре.
• Сохраняйте целое число, представляющее следующий индекс (позвольте этому next_index).
• Сохранять связанный список удаленных индексов (пробелов).
• Держите словарь, сопоставляющий индексы с ключами.
• При добавлении ключа проверьте использование (и удалите) первый индекс в связанном списке в качестве индекса, или если список пуст, используйте и увеличивайте значение next_index. Затем добавьте ключ, значение и индекс в словарь (dictionary[key] = (index, value)) и добавьте ключ в словарь с индексом-ключом (indexdict[index] = key).
• При удалении ключа, получите индекс из словаря, удалите ключ из словаря, удалите индекс из словаря индекса-ключа и вставьте индекс в начало связанного списка.
• Чтобы получить случайный ключ, получите случайное целое, используя что-то вроде random.randrange(0, next_index). Если индекс не находится в словаре "ключ-к-индексу", повторите попытку (это должно быть редко).

Вот реализация:

import random

class RandomDict(object):
    def __init__(self): # O(1)
        self.dictionary = {}
        self.indexdict = {}
        self.next_index = 0
        self.removed_indices = None
        self.len = 0

    def __len__(self): # might as well include this
        return self.len

    def __getitem__(self, key): # O(1)
        return self.dictionary[key][1]

    def __setitem__(self, key, value): # O(1)
        if key in self.dictionary: # O(1)
            self.dictionary[key][1] = value # O(1)
            return
        if self.removed_indices is None:
            index = self.next_index
            self.next_index += 1
        else:
            index = self.removed_indices[0]
            self.removed_indices = self.removed_indices[1]
        self.dictionary[key] = [index, value] # O(1)
        self.indexdict[index] = key # O(1)
        self.len += 1

    def __delitem__(self, key): # O(1)
        index = self.dictionary[key][0] # O(1)
        del self.dictionary[key] # O(1)
        del self.indexdict[index] # O(1)
        self.removed_indices = (index, self.removed_indices)
        self.len -= 1

    def random_key(self): # O(log(next_item/len))
        if self.len == 0: # which is usually close to O(1)
            raise KeyError
        while True:
            r = random.randrange(0, self.next_index)
            if r in self.indexdict:
                return self.indexdict[r]

Ответ 4

У меня была та же проблема, и я написал

https://github.com/robtandy/randomdict

Я надеюсь, что это поможет! Он обеспечивает O (1) доступ к случайным клавишам, значениям или элементам.