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

Question

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

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

• Я мог бы использовать изменение размера хэш-таблицу. Если я утверждаю, что отношение ключей к слотам составляет от 1 до 2, тогда я могу просто выбрать случайные индексы, пока не нахожусь в непустой слот. Я только смотрю на 1-2 клавиши, в ожидании.
• Я могу получить эти операции в гарантированном наихудшем случае O (log n), используя дерево AVL, дополняя его рангом.

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

Answer 1

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

Ниже реализация словаря обертку с O (1) получить/вставка/удаление, и 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]) 

Answer 2

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

• Назначьте индекс каждой клавише, сохраняя ее с помощью va lue в словаре.
• Сохраните целое число, представляющее следующий индекс (назовем это 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] 

Answer 3

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

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

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 

Answer 4

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

https://github.com/robtandy/randomdict

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