O(1)中的字典中的Python获取随机密钥
我需要一个支持快速插入和删除(键，值)对的数据结构，以及“获取随机键”，它的作用与字典的random.choice(dict.keys())相同。我在互联网上搜索过，大多数人似乎对random.choice(dict.keys())方法很满意，尽管它是线性时间。
我意识到可以更快地实现这一点
- 我可以使用一个调整大小的哈希表。如果我保持键与槽的比率在1和2之间，那么我可以选择随机索引，直到我命中一个非空的槽。我只看了1到2个键，在保证最坏情况下O(
n)的情况下，我可以使用AVL树，增加等级来得到这些操作。
但是，在Python中有什么简单的方法可以做到这一点吗？看起来应该是这样的！
回答 5
Stack Overflow用户
发布于 2012-09-11 14:49:58
这可能与上面列出的特定用例不是特别相关，但这是我在搜索如何在字典中很好地获得"any“键时遇到的问题。
如果你不需要一个真正的随机选择，而只是需要一些任意的密钥，这里有两个我发现的简单的选择：
key = next(iter(d)) # may be a little expensive, but presumably O(1)只有当你乐于使用字典中的key+value时，第二种方法才真正有用，而且由于突变在算法上效率不高：
key, value = d.popitem() # may not be O(1) especially if next step
if MUST_LEAVE_VALUE:
d[key] = valueStack Overflow用户
发布于 2012-06-01 04:42:21
编辑:完全重写，但在这里保留问题和评论。
下面是一个具有O(1) get/insert/delete和O(1)随机元素拾取的字典包装器的实现。
主要的想法是，我们希望有一个O(1)但任意的从range(len(mapping))到键的映射。这将让我们获得random.randrange(len(mapping))，并通过映射传递它。
这是很难实现的，直到你意识到我们可以利用映射可以是任意的这一事实。实现O(1)时间硬界限的关键思想是:无论何时删除一个元素，您都可以将其与最高的任意id元素交换，并更新任何指针。
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 elementsGet、set和delete：
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])Stack Overflow用户
发布于 2012-06-01 05:00:47
下面是一个有点复杂的方法：
为每个键分配一个索引，将它与dictionary.
- Keep中的值一起存储表示下一个索引的整数(让我们称它为已删除索引(间隙)的链表)。
- 保持一个将索引映射到键的字典。
- 添加键时，检查是否使用(和删除)链表中的第一个索引作为索引，或者如果列表为空，请使用并递增next_index。然后将键、值和索引添加到字典(
dictionary[key] = (index, value))中，并将键添加到索引到键字典中删除键，从字典中获取索引，从字典中删除键，从索引到键字典中删除索引，并将索引插入到链表的前面。
- 要获得随机键，请使用类似
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]https://stackoverflow.com/questions/10840901
复制相似问题