6

がある場合Map<T, Integer>、整数値が「いくつの」Tを表すとしましょう。したがって、整数値に基づいてTを一律に選択したいと思います。マップに「a」=4および「b」=6の文字列が含まれている場合、「a」の時間の40％が選択され、「b」の時間の60％が選択されるようにします。

最も重要なのは、これをO（n）で使用したいことです。前の例では、nは2 （10ではなく）です。私は元々、キーを含むArrayListを、それが持つ値の数で作成しました（そして、単にランダムなインデックスを返します）が、このプロセスは非常に遅いだけでなく、Map<T, Integer>表現するものに対して完全に直感に反します。

4

6 に答える 6

11

O(n lg n)遅れて申し訳ありませんが、構築時間とO(lg n)ランダム要素のフェッチ時間で比較的エレガントなソリューションがあると思います。ここに行きます。

WeightedProbMap: このクラスは、ランダム要素ジェネレーターを実装します。に基づいて構築されIterableます。以下を参照してくださいTest.java。

import java.util.Random;
import java.util.SortedMap;
import java.util.TreeMap;

class WeightedProbMap<EltType>  {
    private SortedMap<Integer, EltType> elts = new TreeMap<Integer, EltType>();
    private Random rand = new Random();
    private int sum = 0;

    // assume: each weight is > 0; there is at least one element;
    //         elements should not be repeated
    // ensure: this.elts maps cumulative weights to elements;
    //         this.sum is the total weight
    public WeightedProbMap(Iterable<Pair<Integer, EltType>> weights) {
        for (Pair<Integer, EltType> e : weights) {
            this.elts.put(this.sum, e.second);
            this.sum += e.first;
        }
    }

    // assume: this was initialized properly (cf. constructor req)
    // ensure: return an EltType with relative probability proportional
    //         to its associated weight
    public EltType nextElt() {
        int index = this.rand.nextInt(this.sum) + 1;
        SortedMap<Integer, EltType> view = this.elts.headMap(index);
        return view.get(view.lastKey());
    }
}

Pair.java:シンプルな Pair クラスです。

class Pair<X, Y> {
    public Pair(X x, Y y) {
        first = x;
        second = y;
    }

    X first;
    Y second;
}

Test.java:WeightedProbMap (WPM) クラス用の非常に単純なテスト ハーネスです。関連する重みを持つ要素の ArrayList を構築し、それを使用して WPM を構築し、WPM から 10,000 サンプルを取得して、要素が期待される頻度で表示されるかどうかを確認します。

import java.util.ArrayList;

class Test {
    public static void main(String argc[]) {
        ArrayList<Pair<Integer, String> > elts = new ArrayList<Pair<Integer, String>>();
        elts.add(new Pair<Integer, String>(20, "Hello"));
        // elts.add(new Pair<Integer, String>(70, "World"));
        // elts.add(new Pair<Integer, String>(10, "Ohai"));

        WeightedProbMap<String> wpm = new WeightedProbMap<String>(elts);

        for (int i = 0; i < 10000; ++i) {
            System.out.println(wpm.nextElt());
        }
    }
}

これをテストする：

  1. elts.add(...)のいずれかまたは両方の行のコメントを外しTest.javaます。

  2. コンパイル:

    $ javac Pair.java WeightedProbMap.java Test.java

  3. 次のように実行します (たとえば、Unix の場合):

    $ java Test | grep "Hello" | wc -l

これにより、その特定の実行のカウントが得られます。

説明：

コンストラクター: ( WeightedProbMapWPM) クラスは、aを使用しjava.util.SortedMapて累積重みを要素にマップします。グラフィカルな説明:

The constructor takes weights...     ...and creates a mapping from the
      3 +---+                            number line:
        |   | 
  2 +---+   +---+ 2                   0      2         5      7
    |   |   |   |                     +------+---------+------+
    |   |   |   |                     |   X  |    Y    |   Z  |
  --+---+---+---+--                   +------+---------+------+
      X   Y   Z

nextElt(): ASortedMapはデータをキーの順序で格納します。これにより、マップのサブセットの「ビュー」を低コストで提供できます。特に、ライン

SortedMap<Integer, EltType> view = this.elts.headMap(index)

this.eltsは、厳密に より小さいキーのみを持つ元のマップ ( ) のビューを返しますindex。この操作 ( headMap) は一定時間です。構築に時間viewがかかり、後で変更した場合、変更も に反映されます。O(1)this.eltsview

view乱数以外のすべての を作成したら、そのサブセットで最大のキーを見つける必要があります。でそれを行いますがSortedMap.lastKey()、 のTreeMap場合は時間がかかり\Theta(lg n)ます。

于 2011-03-06T19:58:26.020 に答える
2

合計を保存できる場合、それは非常に簡単に実行できます。

ペア（T、int）をクラスなどとして通常の配列に格納し、それを調べます。

int val = Random.nextInt(total);
for (Pair p : pairs) {
    val -= p.val;
    if (val < 0) return p;
}

ArrayListをループすることが、n個の値を反復処理する最も効率的な方法であり、明らかにO（n）よりも優れていることを考えると、はるかに速くなることはできません。唯一のオーバーヘッドはnextInt（）であり、すべてのソリューションでそれ（または同様のもの）も必要です。ArrayListをどのように編成するか（ソートされているかどうか）に応じて、他の操作はより安く/より高価になりますが、その特定のアクションにとっては重要ではありません

編集：それについて考えると、「あなたは明らかにO（n）が必要です」は真実ではありません。配列の値をめったに変更せず、費用のかかる準備が可能であり、メモリが問題にならない場合は、HashMapを保存することでより適切に行うことができます。たとえば、ディストリビューションがある場合：T0：2 T1：3 T2：1

ハッシュマップに（0、T0）、（1、T0）、（2、T1）、。、（4、T1）、（5、T2）を挿入できます。

Edit2：または、より大きなデータセットに対して実行可能であるはずのphoojiのアプローチを参照してください。

于 2011-03-06T17:38:21.030 に答える
2

これを行うには、各値Tの相対度数をキャッシュする必要があります。これにより、O（n）挿入コストの価格に対するO（n）確率分布が得られます（すべてのTの相対度数を更新する必要があります）。挿入するたびに）。

于 2011-03-06T17:28:47.357 に答える
1

Map<Integer,T>すべてのキーがこれまでに処理されたすべての重みの合計になるように、逆マップを作成します。

たとえば、このマップがある場合:

T1 -> 10
T2 -> 8
T3 -> 3

この逆マップは次のとおりです。

10 -> T1
18 -> T2
21 -> T3

(パフォーマンスを向上させるために、最初に重みを降順に並べ替えることができます。)

次に、0 とすべての重みの合計の間で均等に分散された乱数を生成し、逆写像のキー セットでこの数のバイナリ検索を実行します。

于 2011-03-06T21:22:27.010 に答える
0

O（1）で実行できるため、arraylistを使用すると、Mapを使用するよりも実際にはさらに高速になります。

class RandVal<T> {

    List<T> list = new ArrayList<T>();
    Random rand = new Random();

    public T randomValue() {
        int next = rand.nextInt(list.size());
        return list.get(next);
    }

}

これが悪いことである唯一の方法は、順序が重要な場合 (AABBAB と ABBABA など) ですが、順序のないマップを使用しているため、そうでないことは明らかです...

于 2011-03-06T17:46:47.810 に答える
0

OPはこちら。

エレガントなソリューションを思いつきました！誤解がある場合: ArrayList の値の数によってすべてのキーを格納するという私の最初のアイデアは、Map を使用して「整数を使用したキーのインスタンス」を格納するという点を完全に無視していました。同様のソリューションは逆効果です。Map が順不同であると仮定すると、ここに私の解決策があります:

public T randomPick(Random r) {

        int randomValue = r.nextInt(size());
        int currentSum = 0;
        T lastElement = null;

        for (T t : map.keySet()){
            if (randomValue < currentSum + map.get(t)){
                return t;
            }
            currentSum+= map.get(t);
            lastElement = t;
        }
        return lastElement;
    }

と を比較random valueしcurrent sum + the current element's valueます。それより小さい場合は、現在のキーを返します。それ以外の場合は、続けてその値を合計に追加します。ランダム値がどの値よりも小さくなることがない場合は、 を返しますlastElement。

これで解決することを願っています。

于 2011-03-08T02:28:06.587 に答える