1

セットを持ち、その要素に確率が関連付けられているようにしたいので、セットから要素をランダムに選択すると、分布は要素に関連付けられた確率に従います。見たい映画のリストを保存する非常に小さなJavaアプリケーションでそれを使用して、ランダムな映画を提案できるようにしたいと思います（そうでなければ、映画を選ぶのにいつも何時間もかかります）。各映画に、その映画が私に提案された回数を関連付けたいと思います。これは、その映画が次の提案のリストから選択される確率に反比例します。

不均一な分布でランダムに要素を選択できるデータ構造はありますか?

そうでない場合、そのようなデータ構造を記述する最も効率的な方法は何ですか? もちろん、常に配列を作成し、リストのすべての要素を十分な頻度で配列に配置して、配列内の値の分布が希望する確率と一致し、その配列からランダムな要素を選択することもできます。しかし、映画の大規模なセットの場合、それは非常に非効率的です. 私が持っていた別のアイデアは、要素とそれまでのすべての要素の確率の合計をカプセル化することでした (したがって、最初の要素は (first, p(first)) としてカプセル化され、2 番目の要素は (second, p(second) + p(最初)) など)、次に 0 から 1 の間の乱数を選択し、それらのカプセル化された要素のソートされたリストでバイナリ検索を実行します。それは賢明に聞こえますか？

TL:DR (そしてやや抽象的): Java で非一様分布をセットの要素に効率的にマップするにはどうすればよいですか?

4

3 に答える 3

5

質問が正しいかどうかわかりません。を使用しTreeMap<Double, Movie>ます。

例: 映画 A (60 %)、映画 B (30 %)、映画 C (10 %) があるとします。

TreeMap<Double, Movie> movies = new TreeMap<>();
movies.put(0.6, new Movie("Movie A"));
movies.put(0.9, new Movie("Movie B")); // 0.6 + 0.3
movies.put(1.0, new Movie("Movie C")); // 0.6 + 0.3 + 0.1
Double probability = Math.random(); // between 0 (inclusive) and 1.0 (exclusive)
Movie chosen = movies.higherEntry(probability).getValue();

母集団と確率の並べ替えはあなたに任せます。

于 2013-02-16T22:48:30.547 に答える
2

私は単に定義します：

class Movie {
    int recommendations;
}

それからする

public Movie chooseMovie(ArrayList<Movie> movies) {
    Random rand = new Random();
    int sum = 0;
    for(Movie movie : movies) {
        sum += movie.recommendations;
    }
    int choice = rand.nextInt(sum);
    int soFar = 0;
    for(Movie movie : movies) {
        soFar += movie.recommendations;
        if(choice < soFar) {
            return movie;
        }
    }
    return null;
}

範囲が大きいほど、選択変数は映画の推奨範囲内に収まる可能性が高くなります。遅いですが、実際にはムービーの数はおそらく十分に小さいので、問題なく動作します。多くのルックアップを行っている場合は、提案した方法と同様に、推奨事項の合計と増分合計をキャッシュできます。

編集 - 推奨数に反比例する確率

public Movie chooseMovie(ArrayList<Movie> movies) {
    Random rand = new Random();
    double sum = 0;
    for(Movie movie : movies) {
        if(movie.recommendations > 0) {
            sum += 1 / (double) (movie.recommendations);
        }
    }
    int choice = rand.nextDouble() * sum;
    double soFar = 0;
    for(Movie movie : movies) {
        if(movie.recommendations > 0) {
            soFar += 1 / (double) (movie.recommendations);
            if(choice < soFar) {
                return movie;
            }
        }
    }
    return null;
}
于 2013-02-16T22:58:46.057 に答える