13

米国国勢調査の名前リストからランダムな名前を選択するプログラムを作成しようとしています。リストの形式は

Name           Weight Cumulative line
-----          -----  -----      -
SMITH          1.006  1.006      1
JOHNSON        0.810  1.816      2
WILLIAMS       0.699  2.515      3
JONES          0.621  3.136      4
BROWN          0.621  3.757      5
DAVIS          0.480  4.237      6

次のような構造にデータをロードすると仮定します

Class Name
{
    public string Name {get; set;}
    public decimal Weight {get; set;}
    public decimal Cumulative {get; set;}
}

名前のリストを保持するのに最適なデータ構造と、リストからランダムな名前を選択するが、名前の分布を実際の世界と同じにするための最良の方法は何でしょうか。

データ構造に違いがある場合にのみ、最初の10,000行を処理します。

加重ランダム性に関する他のいくつかの質問を調べてみましたが、理論をコードに変換するのに少し問題があります。私は数学理論についてあまり知らないので、これが「置換の有無にかかわらず」ランダムな選択であるかどうかはわかりません。同じ名前が複数回表示されるようにしたいのです。

4

4 に答える 4

9

これを処理する「最も簡単な」方法は、これをリストに保持することです。

次に、次を使用できます。

Name GetRandomName(Random random, List<Name> names)
{
    double value = random.NextDouble() * names[names.Count-1].Culmitive;
    return names.Last(name => name.Culmitive <= value);
}

速度が問題になる場合は、Culmitive値だけの個別の配列を格納できます。Array.BinarySearchこれにより、適切なインデックスをすばやく見つけることができます。

Name GetRandomName(Random random, List<Name> names, double[] culmitiveValues)
{
    double value = random.NextDouble() * names[names.Count-1].Culmitive;
    int index = Array.BinarySearch(culmitiveValues, value);
    if (index >= 0)
        index = ~index;

    return names[index];
}

おそらく最も効率的な別のオプションは、 C5 GenericCollectionLibraryのツリークラスの1つのようなものを使用することです。次に、を使用RangeFromして適切な名前を見つけることができます。これには、個別のコレクションを必要としないという利点があります

于 2011-09-09T20:06:44.057 に答える
3

ランダムに選択された加重アイテム用のC＃ライブラリを作成しました。

  • ツリー選択とウォーカーエイリアスメソッドアルゴリズムの両方を実装し、すべてのユースケースで最高のパフォーマンスを提供します。
  • ユニットテストされ、最適化されています。
  • LINQをサポートしています。
  • これは無料でオープンソースであり、MITライセンスの下でライセンスされています。

いくつかのサンプルコード：

IWeightedRandomizer<string> randomizer = new DynamicWeightedRandomizer<string>();
randomizer["Joe"] = 1;
randomizer["Ryan"] = 2;
randomizer["Jason"] = 2;

string name1 = randomizer.RandomWithReplacement();
//name1 has a 20% chance of being "Joe", 40% of "Ryan", 40% of "Jason"

string name2 = randomizer.RandomWithRemoval();
//Same as above, except whichever one was chosen has been removed from the list.
于 2015-06-19T22:31:14.933 に答える
0

配列（必要に応じてベクトル）を保持するのが最適だと思います。加重平均については、合計を求め、ゼロと合計の間の乱数を選び、累積値が小さい姓を選びます。（たとえば、ここでは、<1.006 =スミス、1.006-1.816=ジョンソンなど。

PSそれは累積です。

于 2011-09-09T20:08:05.283 に答える
0

ただ楽しみのために、そして決して最適ではありません

List<Name> Names = //Load your structure into this

List<String> NameBank = new List<String>();
foreach(Name name in Names)
   for(int i = 0; i <= (int)(name.Weight*1000); i++)
     NameBank.Add(name.Name)

それから：

String output = NameBank[rand(NameBank.Count)];
于 2011-09-09T20:09:10.953 に答える