20

(キー、値) ペアの FAST 挿入と削除、および辞書の random.choice(dict.keys()) と同じことを行う「ランダム キーの取得」をサポートするデータ構造が必要です。私はインターネットで検索しましたが、線形時間であるにもかかわらず、ほとんどの人は random.choice(dict.keys()) アプローチに満足しているようです。

これをより速く実装できることは承知しています:

  • サイズ変更ハッシュテーブルを使用できます。スロットに対するキーの比率が 1 から 2 の間であると維持する場合、空でないスロットにヒットするまで、ランダムなインデックスを選択できます。期待して、私は1つから2つのキーだけを見ます。
  • AVL ツリーを使用して、ランクを増やして、最悪の場合の O(log n) を保証してこれらの操作を取得できます。

ただし、Pythonでこれを取得する簡単な方法はありますか? あるはずです！

4

5 に答える 5

5

これは、上記の特定のユースケースとは特に関係がないかもしれませんが、辞書で「任意の」キーをうまく取得する方法を探しているときに私が受ける質問です。

本当にランダムな選択は必要ないが、任意のキーが必要な場合は、私が見つけた 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
于 2012-09-11T06:49:57.870 に答える
4

[編集：完全に書き直されましたが、コメントはそのままにしてここに質問を残します。]

以下は、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])
于 2012-05-31T20:42:20.980 に答える
3

これはやや複雑なアプローチです：

  • 各キーにインデックスを割り当て、値とともにディクショナリに格納します。
  • 次のインデックスを表す整数を保持します (これを 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]
于 2012-05-31T21:00:47.427 に答える
0

私は同じ問題を抱えていて、書いた

https://github.com/robtandy/randomdict

お役に立てば幸いです。ランダムなキー、値、またはアイテムへの O(1) アクセスを提供します。

于 2015-09-27T15:17:25.037 に答える