blocks|key|228246|text|编辑:完全重写，但在这里保留问题和评论。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|228247|下面是一个具有O(1)+get/insert/delete和O(1)随机元素拾取的字典包装器的实现。|228248|主要的想法是，我们希望有一个O(1)但任意的从range(len(mapping))到键的映射。这将让我们获得random.randrange(len(mapping))，并通过映射传递它。|offset|length|style|CODE|228249|这是很难实现的，直到你意识到我们可以利用映射可以是任意的这一事实。实现O(1)时间硬界限的关键思想是:无论何时删除一个元素，您都可以将其与最高的任意id元素交换，并更新任何指针。|228250|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|code-block|syntax|javascript|228251|Get、set和delete：|228252|++++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]|228253|选择一个随机的(键，元素)：|228254|++++def+randomItem(self):++#+O(1)
++++++++r+=+random.randrange(len(self.mapping))
++++++++k+=+self.idToKey[r]
++++++++return+(k,+self.mapping[k])|228255|entityMap^0|0|0|N|J|1J|U|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|11|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|12|8|@$F|13|G|14|H|I]|$F|15|G|16|H|I]]|9|@]|A|$]]|$1|J|3|K|5|6|7|17|8|@]|9|@]|A|$]]|$1|L|3|M|5|N|7|18|8|@]|9|@]|A|$O|P]]|$1|Q|3|R|5|6|7|19|8|@]|9|@]|A|$]]|$1|S|3|T|5|N|7|1A|8|@]|9|@]|A|$O|P]]|$1|U|3|V|5|6|7|1B|8|@]|9|@]|A|$]]|$1|W|3|X|5|N|7|1C|8|@]|9|@]|A|$O|P]]|$1|Y|3|-4|5|6|7|1D|8|@]|9|@]|A|$]]]|Z|$]]

[edit: Completely rewritten, but keeping question here with comments intact.]

Below is the realization of a dictionary wrapper with O(1) get/insert/delete, and O(1) picking of a random element.

The main idea is that we want to have an O(1) but arbitrary map from <code>range(len(mapping))</code> to the keys. This will let us get <code>random.randrange(len(mapping))</code>, and pass it through the mapping.

This is very difficult to implement until you realize that we can take advantage of the fact that 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.

<pre><code>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
</code></pre>

Get, set, and delete:

<pre><code> 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]
</code></pre>

Picking a random (key,element):

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

blocks|key|3094281|text|下面是一个有点复杂的方法：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3094282|为每个键分配一个索引，将它与dictionary.|3094283|Keep中的值一起存储表示下一个索引的整数(让我们称它为已删除索引(间隙)的链表)。|unordered-list-item|3094284|
|3094285|保持一个将索引映射到键的字典。|3094286|3094287|添加键时，检查是否使用(和删除)链表中的第一个索引作为索引，或者如果列表为空，请使用并递增next_index。然后将键、值和索引添加到字典(dictionary[key]+=+(index,+value))中，并将键添加到索引到键字典中删除键，从字典中获取索引，从字典中删除键，从索引到键字典中删除索引，并将索引插入到链表的前面。|offset|length|style|CODE|3094288|3094289|要获得随机键，请使用类似random.randrange(0,+next_index)的命令获取随机整数。如果索引不在键到索引字典中，请重试(这种情况应该很少见)。|3094290|3094291|下面是一个实现：|3094292|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+%2B=+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+%2B=+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]|code-block|syntax|javascript|3094293|entityMap^0|0|0|0|0|0|0|1Z|W|0|0|C|V|0|0|0|0^^$0|@$1|2|3|4|5|6|7|14|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|15|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|16|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|17|8|@]|9|@]|A|$]]|$1|I|3|J|5|F|7|18|8|@]|9|@]|A|$]]|$1|K|3|H|5|6|7|19|8|@]|9|@]|A|$]]|$1|L|3|M|5|F|7|1A|8|@$N|1B|O|1C|P|Q]]|9|@]|A|$]]|$1|R|3|H|5|6|7|1D|8|@]|9|@]|A|$]]|$1|S|3|T|5|F|7|1E|8|@$N|1F|O|1G|P|Q]]|9|@]|A|$]]|$1|U|3|-4|5|6|7|1H|8|@]|9|@]|A|$]]|$1|V|3|W|5|6|7|1I|8|@]|9|@]|A|$]]|$1|X|3|Y|5|Z|7|1J|8|@]|9|@]|A|$10|11]]|$1|12|3|-4|5|6|7|1K|8|@]|9|@]|A|$]]]|13|$]]

Here is a somewhat convoluted approach: 

<ul>
<li>Assign an index to each key, storing it with the value in the dictionary.</li>
<li>Keep an integer representing the next index (let's call this next_index).</li>
<li>Keep a linked list of removed indices (gaps).</li>
<li>Keep a dictionary mapping the indices to keys.</li>
<li>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 (<code>dictionary[key] = (index, value)</code>) and add the key to the index-to-key dictionary (<code>indexdict[index] = key</code>).</li>
<li>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.</li>
<li>To get a random key, get a random integer using something like <code>random.randrange(0, next_index)</code>. If the index is not in the key-to-index dictionary, re-try (this should be rare).</li>
</ul>

Here is an implementation:

<pre><code>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]
</code></pre>

blocks|key|223289|text|这可能与上面列出的特定用例不是特别相关，但这是我在搜索如何在字典中很好地获得"any“键时遇到的问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|223290|如果你不需要一个真正的随机选择，而只是需要一些任意的密钥，这里有两个我发现的简单的选择：|223291|key+=+next(iter(d))++++#+may+be+a+little+expensive,+but+presumably+O(1)|code-block|syntax|javascript|223292|只有当你乐于使用字典中的key%2Bvalue时，第二种方法才真正有用，而且由于突变在算法上效率不高：|223293|key,+value+=+d.popitem()+++++#+may+not+be+O(1)+especially+if+next+step
if+MUST_LEAVE_VALUE:
++++d[key]+=+value|223294|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Q|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|R|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|S|8|@]|9|@]|A|$G|H]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

This may not specifically relevant to the specific use case listed above, but this is the question I get when searching for a way to nicely get a hold of "any" key in a dictionary.

If you don't need a truly random choice, but just need some arbitrary key, here are two simple options I've found:

<pre><code>key = next(iter(d)) # may be a little expensive, but presumably O(1)
</code></pre>

The second is really useful only if you're happy to consume the key+value from the dictionary, and due to the mutation(s) will not be as algorithmically efficient:

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

blocks|key|3094333|text|我也有同样的问题，于是我写道|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3094334|https://github.com/robtandy/randomdict|offset|length|3094335|我希望它能帮助你！它提供对随机键、值或项的O(1)访问。|3094336|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|12|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@$D|Q|E|R|1|S]]|A|$]]|$1|F|3|G|5|6|7|T|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|U|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|C]]]]

I had the same problem and wrote

<a href="https://github.com/robtandy/randomdict" rel="nofollow">https://github.com/robtandy/randomdict</a>

I hope it helps you! It provides O(1) access to random keys, values or items.

blocks|key|3094365|text|要获得O(1)空间，您需要一个数组数据结构和一个存储数组中的值及其索引的字典。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3094366|然后，在添加值时，您只需将它们与数组中的索引一起推送到数组和字典中。|3094367|然后，由于您使用的是数组数据结构，因此您有随机访问。|3094368|在删除值时，您可以在字典中查看要删除的值的索引。然后将数组中的该值替换为数组中的最后一个值(确保它不是最后一个元素)，并将数组中的最后一个值弹出()。之后，使用删除的值索引更新字典中被替换的值(数组中的最后一个值)的键。最后，删除要删除的值的键和值，因为它在字典中没有意义。|3094369|class+RandomizedSet:

++++def+__init__(self):
++++++++self.container+=+[]
++++++++self.indices+=+{}
+++++++
++++++++
++++def+insert(self,+val:+int)+->+bool:
++++++++if+val+in+self.indices:
++++++++++++return+False
++++++++
++++++++self.indices[val]+=+len(self.container)
++++++++self.container.append(val)
++++++++return+True

++++def+remove(self,+val:+int)+->+bool:
++++++++if+val+not+in+self.indices:
++++++++++++return+False
++++++++
++++++++idxOfValueToRemove+=+self.indices[val]
++++++++lastValue+=+self.container[-1]
++++++++
++++++++if+idxOfValueToRemove+<+len(self.container)-1:
++++++++++++self.container[idxOfValueToRemove]+=+lastValue
++++++++++++self.indices[lastValue]+=+idxOfValueToRemove
++++
++++++++self.container.pop()
++++++++
++++++++del+self.indices[val]
++++
++++++++return+True
++++++++
++++++++
++++++++++++

++++def+getRandom(self)+->+int:
+++++++++return+random.choice(list(self.container))|code-block|syntax|javascript|3094370|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|Q|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|R|8|@]|9|@]|A|$]]|$1|H|3|I|5|J|7|S|8|@]|9|@]|A|$K|L]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

To get O(1) space you need an array data structure and a dictionary that stores values in the array and their indices.
Then when adding values you simply push them onto your array and dictionary with its index in the array.
Then you have acces randomly since you are using array data structure.
When removing values you look at the index of the value you want to remove in the dictionary. Then replace that value in the array with the last value in the array (make sure it is not the last element already) and pop() the last value in the array.
After that you update the key of the replaced value (last value in array) in the dictionary with the deleted value index. Finally you delete the key and value of the value you want to remove since it doesnt make sense it to be on the dictionary.
<pre><code>class RandomizedSet:

 def __init__(self):
 self.container = []
 self.indices = {}
 
 
 def insert(self, val: int) -&gt; bool:
 if val in self.indices:
 return False
 
 self.indices[val] = len(self.container)
 self.container.append(val)
 return True

 def remove(self, val: int) -&gt; bool:
 if val not in self.indices:
 return False
 
 idxOfValueToRemove = self.indices[val]
 lastValue = self.container[-1]
 
 if idxOfValueToRemove &lt; len(self.container)-1:
 self.container[idxOfValueToRemove] = lastValue
 self.indices[lastValue] = idxOfValueToRemove
 
 self.container.pop()
 
 del self.indices[val]
 
 return True
 
 
 

 def getRandom(self) -&gt; int:
 return random.choice(list(self.container))
</code></pre>

I need a data structure that supports FAST insertion and deletion of (key, value) pairs, as well as "get random key", which does the same thing as random.choice(dict.keys()) for a dictionary. I've searched on the internet, and most people seem to be satisfied with the random.choice(dict.keys()) approach, despite it being linear time. 

I'm aware that implementing this faster is possible:

<ul>
<li>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.</li>
<li>I can get these operations in guaranteed worst case O(log n) using an AVL tree, augmenting with rank. </li>
</ul>

Is there any easy way to get this in Python, though? It seems like there should be!

Python get random key in a dictionary in O(1)

数据结构

Python

我需要一个支持快速插入和删除(键，值)对的数据结构，以及“获取随机键”，它的作用与字典的random.choice(dict.keys())相同。我在互联网上搜索过，大多数人似乎对random.choice(dict.keys())方法很满意，尽管它是线性时间。我意识到可以更快地实现这一点我可以使用一个调整大小的哈希表...

问O(1)中的字典中的Python获取随机密钥
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问O(1)中的字典中的Python获取随机密钥EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问O(1)中的字典中的Python获取随机密钥
EN