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

Мне нужна структура данных, которая поддерживает вставку и удаление FAST пар (ключ, значение), а также «получить случайный ключ», который делает то же самое, что и random.choice (dict.keys ()) для словаря. Я искал в Интернете, и большинство людей, похоже, удовлетворены подходом random.choice (dict.keys ()), несмотря на то, что это линейное время.

Я знаю, что реализация этого быстрееpossible:

I could use a resizing hash table. If I maintain that the ratio of keys to slots is between 1 and 2, then I can just choose random indices until I hit a non-empty slot. I only look at 1 to 2 keys, in expectation. I can get these operations in guaranteed worst case O(log n) using an AVL tree, augmenting with rank.

Есть ли простой способ получить это в Python? Кажется, что должно быть!

 Joel Cornett31 мая 2012 г., 22:55
Вот идея: сохранить другойdict формы{i: key}, гдеi это счетчик. Затем, чтобы сделать случайный поиск, позвонитеrandint в этом другом словаре. Поправьте меня, если я ошибаюсь, но это звучит как O (1).
 WuTheFWasThat31 мая 2012 г., 23:37
Ну, из того, что вы сказали, не очевидно, как сделать вставку и удаление. Тем не менее, это работает, в некоторой степени. Следите за максимальным значением счетчика, называйте его n. Для вставок мы сначала пробуем 2 (или 5, или любое постоянное число) случайных значений от 1 до n. Если они оба были взяты, используйте n и увеличьте максимальное значение счетчика. В противном случае вставьте в пустой. Ухоженная!
 WuTheFWasThat01 июн. 2012 г., 01:02
Не легко объяснить. 500-символьная версия: я пишу компилятор для вероятностного языка программирования (см.link), а логический вывод требует случайного обхода возможных вариантов случайности (см.link). Существует сложная система маркировки точек выполнения программы, где происходит случайность. Эти метки являются ключами в моем словаре. Чтобы сделать вывод, требуется вставка, удаление и & quot; получить случайный ключ & quot; (Для того, чтобы использовать плотность предложения в Метрополис-Гастингс).
 Daenyth01 июн. 2012 г., 00:42
Мне любопытно, как предполагается использовать эту структуру данных. Какой вариант использования?

Ответы на вопрос(4)

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

https://github.com/robtandy/randomdict

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

 27 сент. 2015 г., 17:55
Публикация ссылки на внешний источник нецелесообразна, так как в дальнейшем может оборваться. Я хотел бы предложить вам дать некоторые объяснения здесь и дать ссылку.

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

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

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
 11 нояб. 2016 г., 16:45
next(iter(d)) работает как на Python3, так и на Python2 (вместоd.iterkeys().next())
 14 нояб. 2016 г., 22:34
@ kd88 Спасибо! Я обновил свой ответ, чтобы включить этот совет.

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

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

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

Это очень сложно реализовать, пока вы не поймете, что мы можем воспользоваться тем, чтоthe mapping can be arbitrary. The key idea to achieve a hard bound of O(1) time is this: whenever you delete an element, you swap it with the highest arbitrary-id element, and update any pointers.

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])
 31 мая 2012 г., 22:43
Держатьlist из ключей, а неset.
 31 мая 2012 г., 22:54
Ну, это не может быть "Быстро, Хорошо и Дешево" в то же время :) Но все равно мой плохой и спасибо за объяснения.
 31 мая 2012 г., 22:48
@BasicWolf: нет,set.pop не случайно.
 01 июн. 2012 г., 00:22
@WuTheFWasThat. Проблема создания списка в CPython заключается в том, что он не сможет выполнить O (1) удалений. Как правило, это должно быть в состоянии, если язык программирования хорошо реализован, если вы удаляете только из конца или начала списка, но CPython не претендует на то, что сможет сделать это за O (1). Хотя, возможно, мой источник просто не достаточно конкретен:wiki.python.org/moin/TimeComplexity С CPython можноappend в O (1) время, вероятно, можно удалить в O (1) время с конца, но источник не сказал.
 31 мая 2012 г., 22:42
Это не нужно. Словарь в основном такой же, как набор ключей, за исключением того, что они также имеют значения.

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

Assign an index to each key, storing it with the value in the dictionary. Keep an integer representing the next index (let's call this next_index). Keep a linked list of removed indices (gaps). Keep a dictionary mapping the indices to keys. When adding a key, check the use (and remove) the first index in the linked list as the index, or if the list is empty use and increment next_index. Then add the key, value, and index to the dictionary (dictionary[key] = (index, value)) and add the key to the index-to-key dictionary (indexdict[index] = key). When removing a key, get the index from the dictionary, remove the key from the dictionary, remove the index from the index-to-key dictionary, and insert the index to the front of the linked list. To get a random key, get a random integer using something like random.randrange(0, next_index). If the index is not in the key-to-index dictionary, re-try (this should be rare).

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

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]
 31 мая 2012 г., 23:41
@WuTheFWasThat Да, я не мог придумать простой способ обойти это. По крайней мере, когда вы добавляете вещи после удаления, они снова используют их индексы.
 31 мая 2012 г., 23:46
@ninjagecko Вы правы, мы только что обсуждали это. (Хотя технически вы не правы,1000000 - 1000000 = 0, так что сразу возникнет исключение. Вы, вероятно, имели в виду удалить 999999 элементов.)
 31 мая 2012 г., 23:41
Я не верю, что это приведет к O (1)random_key() функция. Например, если вы вставите 1000000 элементов и удалите 1000000 элементов, каждый вызовrandom_key даст шанс 1/1000000 на успех, несмотря на наличие нескольких элементов в отображении.
 WuTheFWasThat31 мая 2012 г., 23:52
@ninjagecko - Да, я думаю, что Мэтт и я оба знали об этой проблеме. Вот решение, которое не хуже, чем изменение размера хеш-таблицы, но не требует повторной реализации словарей. Следите за количеством вещей в таблице. Когда он опустится ниже next_index / 2, перестройте всю систему индексации с помощью new_next_index = next_index / 2, используя индексы 1, ..., new_next_index для парней из таблицы
 WuTheFWasThat31 мая 2012 г., 23:32
Спасибо! Да, это будет работать Не знаю, почему я об этом не подумал. Хм ... это не очень хорошо, если вы делаете много удалений, так что next_index намного больше, чем количество элементов. Это может иногда случаться в моей программе. Однако я могу оптимизировать, чтобы это не было проблемой.

Ваш ответ на вопрос