25

セットのように機能し (高速挿入、削除、およびメンバーシップ チェック)、ランダムな値を返す機能を持つ Python (2.7) オブジェクトが必要です。stackoverflow に関する以前の質問には、次のような回答があります。

import random
random.sample(mySet, 1)

しかし、これは大規模なセットでは非常に遅くなります (O(n) 時間で実行されます)。

他の解決策は十分にランダムではありません (非常にランダムではない結果を生成する Python セットの内部表現に依存します):

for e in mySet:
    break
# e is now an element from mySet

一定時間のルックアップ、削除、およびランダム値を持つ独自の初歩的なクラスをコーディングしました。

class randomSet:
    def __init__(self):
        self.dict = {}
        self.list = []

    def add(self, item):
        if item not in self.dict:
            self.dict[item] = len(self.list)
            self.list.append(item)

    def addIterable(self, item):
        for a in item:
            self.add(a)

    def delete(self, item):
        if item in self.dict:
            index = self.dict[item]
            if index == len(self.list)-1:
                del self.dict[self.list[index]]
                del self.list[index]
            else:
                self.list[index] = self.list.pop()
                self.dict[self.list[index]] = index
                del self.dict[item]

    def getRandom(self):
        if self.list:
            return self.list[random.randomint(0,len(self.list)-1)]

    def popRandom(self):
        if self.list:
            index = random.randint(0,len(self.list)-1)
            if index == len(self.list)-1:
                del self.dict[self.list[index]]
                return self.list.pop()
            returnValue = self.list[index]
            self.list[index] = self.list.pop()
            self.dict[self.list[index]] = index
            del self.dict[returnValue]
            return returnValue

これに対するより良い実装、またはこのコードに行われる大きな改善はありますか?

4

6 に答える 6

20

MutableSetこれを行う最善の方法は、.NET で抽象基本クラスを使用することだと思いますcollections。から継承し、 、、、および;MutableSetを定義します。また、コンストラクターと同じように、オプションでシーケンスを受け入れるように書き換えます。これらのメソッドに基づいて、他のすべてのメソッドの組み込み定義を提供します。そうすれば、完全なインターフェースを安価に手に入れることができます。(そして、これを行うと、 という名前で定義されます。)adddiscard__len__, __iter____contains____init__setMutableSetsetsetaddIterableextend

discard標準setインターフェースでは、deleteここで呼び出したようです。に名前を変更deleteしdiscardます。また、別のメソッドを用意する代わりに、次のようpopRandomに定義することもできます。popRandom

def popRandom(self):
    item = self.getRandom()
    self.discard(item)
    return item

そうすれば、2 つの個別のアイテム削除方法を維持する必要がなくなります。

最後に、アイテムの削除メソッド (標準セット インターフェイスdeleteにdiscardよると) では、if ステートメントは必要ありません。かどうかをテストする代わりにindex == len(self.list) - 1、リストの最後の項目を、ポップするリストのインデックスにある項目と交換し、必要な変更を逆インデックス辞書に加えます。次に、リストから最後の項目をポップして、辞書から削除します。これは、次のindex == len(self.list) - 1場合でも機能します。

def discard(self, item):
    if item in self.dict:
        index = self.dict[item]
        self.list[index], self.list[-1] = self.list[-1], self.list[index]
        self.dict[self.list[index]] = index
        del self.list[-1]                    # or in one line:
        del self.dict[item]                  # del self.dict[self.list.pop()]
于 2012-09-25T17:25:46.443 に答える
2

あなたが取ることができる1つのアプローチは、から派生setしたタイプのランダムなオブジェクトで自分自身をソルトする新しいクラスを派生させることintです。

次に、 を使用popしてランダムな要素を選択し、それがソルト タイプでない場合は再挿入して返しますが、ソルト タイプの場合は、ランダムに生成された新しいソルト オブジェクトを挿入します (ポップして新しい要素を選択します)。物体）。

これにより、オブジェクトが選択される順序が変わる傾向があります。平均して、試行回数はソルティング要素の比率、つまり償却された O(k) パフォーマンスに依存します。

于 2012-09-25T17:20:48.540 に答える
1

setO(1) ルックアップ時間でリストからランダムな要素を取得できるようにするいくつかの (ハック的な) 変更を使用して、 を継承する新しいクラスを実装できませんか? ところで、Python 2.x では から継承object、つまり を使用する必要がありますclass randomSet(object)。また、PEP8はあなたのために考慮すべきものです:-)

編集:ハックソリューションで何ができるかについてのアイデアを得るには、このスレッドを読む価値があります: http://python.6.n6.nabble.com/Get-item-from-set-td1530758.html

于 2012-09-25T17:02:18.693 に答える
0

同等の要素のみをサポートすることを気にしない場合は、を使用できますblist.sortedset。

于 2012-09-28T05:09:12.203 に答える
0

はい、あなたが行ったのとほぼ同じ方法で「順序付きセット」を実装し、リストを内部データ構造として使用します。

ただし、「set」から直接継承し、追加されたアイテムを内部リストに追跡するだけで（あなたが行ったように）、使用しないメソッドをそのままにしておきます。

*_update メソッドなどのセット固有の操作によってセットが更新されるたびに、内部リストを更新する「同期」メソッドを追加することもできます。

「順序付き辞書」を使用してもユースケースがカバーされない場合。（ordered_dictキーを通常のセットにキャストしようとすることは最適化されていないことがわかりました。そのため、オプションではないデータに対するセット操作が必要な場合）

于 2012-09-25T17:30:57.980 に答える