(キー、値) ペアの FAST 挿入と削除、および辞書の random.choice(dict.keys()) と同じことを行う「ランダム キーの取得」をサポートするデータ構造が必要です。私はインターネットで検索しましたが、線形時間であるにもかかわらず、ほとんどの人は random.choice(dict.keys()) アプローチに満足しているようです。
これをより速く実装できることは承知しています:
ただし、Pythonでこれを取得する簡単な方法はありますか? あるはずです！
これは、上記の特定のユースケースとは特に関係がないかもしれませんが、辞書で「任意の」キーをうまく取得する方法を探しているときに私が受ける質問です。
本当にランダムな選択は必要ないが、任意のキーが必要な場合は、私が見つけた 2 つの簡単なオプションを次に示します。
key = next(iter(d)) # may be a little expensive, but presumably O(1)
2 つ目は、ディクショナリからキー + 値を使用することに満足している場合にのみ、実際に役立ちます。ミューテーションにより、アルゴリズム的に効率的ではなくなります。
key, value = d.popitem() # may not be O(1) especially if next step
if MUST_LEAVE_VALUE:
d[key] = value
[編集：完全に書き直されましたが、コメントはそのままにしてここに質問を残します。]
以下は、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 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])
これはやや複雑なアプローチです：
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]
私は同じ問題を抱えていて、書いた
https://github.com/robtandy/randomdict
お役に立てば幸いです。ランダムなキー、値、またはアイテムへの O(1) アクセスを提供します。