私はアイテムのリストを持っています。リストを作成すると、各アイテムが選択される可能性が等しくなります。ただし、アイテムが選択されると、そのチャンスは下がり、他のチャンスは上がります。プロセス中に新しいアイテムが追加された場合、選択される可能性が最も高くなり、選択される可能性が低くなります。これを実現できる優れたアルゴリズムを探しているのは C# です。
一般化されたアイデア: 私は 5 つのアイテムを持っています。時間の経過とともに、5 つのアイテムすべてが時間の 20% で選択されます。外れ値を減らして、選択を可能な限りその 20% に近づけようとしています。存在する場合は、それを並べて戻すために多かれ少なかれ選択されます。
バケット加重キューを使用する:リストを使用する代わりに、コレクションをバケットに分割します。各バケットには取得頻度が関連付けられています。項目は、選択されると頻度の高いバケットから頻度の低いバケットに移動します。
これを実装する簡単な方法は、各バケットに値の範囲を割り当て、組み合わせた範囲内で乱数を生成して選択するバケットを選択することです。消費者に詳細を公開しないように、このコレクションをある種のクラスに抽象化することをお勧めします。
アルゴリズム：
最初は、すべてのアイテムが同じ (最上位) バケットで開始されます。
アイテムを選択したら、それが入っているバケットから次の下位のバケットに移動します。必要に応じて、次のレベルのバケットを作成します。
新しいアイテムが追加されたら、一番上の (最も頻繁に使用される) バケットに追加します。
アイテムをランダムに選択するには、まずバケットを選択してから、バケット内のアイテムを選択します。選択したアイテムを次のレベルのバケットに移動します。アイテムをより低いフリークエンシー バケットに移動することはオプションであることに注意してください。カットオフ ポイントを設定できます。
新しいバケットを作成するときは、すべてのバケットに関連付けられている取得範囲を更新して、新しいセットに必要な度数分布特性を与えます。
一般的なバケット化された加重キューの C# 実装 (最初のカット):
using System;
using System.Collections.Generic;
using System.Linq;
namespace Utility
{
public class BucketWeightedQueue<T>
{
private int m_MaxFallOff;
private readonly double m_FallOffRate;
private readonly List<List<T>> m_Buckets;
private readonly List<int> m_FallOffFactors;
private readonly Random m_Rand = new Random();
public BucketWeightedQueue(IEnumerable<T> items, double fallOffRate )
{
if( fallOffRate < 0 )
throw new ArgumentOutOfRangeException("fallOffRate");
m_MaxFallOff = 1;
m_FallOffRate = fallOffRate;
m_Buckets = new List<List<T>> { items.ToList() };
m_FallOffFactors = new List<int> { m_MaxFallOff };
}
public T GetRandomItem()
{
var bucketIndex = GetRandomBucketIndex();
var bucket = m_Buckets[bucketIndex];
var itemIndex = m_Rand.Next( bucket.Count );
var selectedItem = bucket[itemIndex];
ReduceItemProbability( bucketIndex, itemIndex );
return selectedItem;
}
private int GetRandomBucketIndex()
{
var randFallOffValue = m_Rand.Next( m_MaxFallOff );
for (int i = 0; i < m_FallOffFactors.Count; i++ )
if( m_FallOffFactors[i] <= randFallOffValue )
return i;
return m_FallOffFactors[0];
}
private void ReduceItemProbability( int bucketIndex, int itemIndex )
{
if( m_FallOffRate <= 0 )
return; // do nothing if there is no fall off rate...
var item = m_Buckets[bucketIndex][itemIndex];
m_Buckets[bucketIndex].RemoveAt( itemIndex );
if( bucketIndex <= m_Buckets.Count )
{
// create a new bucket...
m_Buckets.Add( new List<T>() );
m_MaxFallOff = (int)(m_FallOffFactors[bucketIndex] / m_FallOffRate);
m_FallOffFactors.Add( m_MaxFallOff );
}
var nextBucket = m_Buckets[bucketIndex + 1];
nextBucket.Add( item );
if (m_Buckets[bucketIndex].Count == 0) // drop empty buckets
m_Buckets.RemoveAt( bucketIndex );
}
}
}
ここでは、低い値を優先する分布を持つ乱数ジェネレーターを設計します。リストの先頭にあるアイテムを優先するために使用できます。何かが選択される確率を下げるには、その項目をリストの下に移動します。アイテムをリストの下に移動する方法には、いくつかのオプションがあります。最初に確率変数変換を復習しましょう。
次の関数を 0 と 1 の間の一様確率変数に適用します。
index = Int(l*(1-r^(0.5)) # l=length, r=uniform random var between 0 and 1
より大きなインデックスのオッズを大幅に減らすクールな分布が得られます
p(0)=0.09751
p(1)=0.09246
p(2)=0.08769
p(3)=0.08211
p(4)=0.07636
p(5)=0.07325
p(6)=0.06772
p(7)=0.06309
p(8)=0.05813
p(9)=0.05274
p(10)=0.04808
p(11)=0.04205
p(12)=0.03691
p(13)=0.03268
p(14)=0.02708
p(15)=0.02292
p(16)=0.01727
p(17)=0.01211
p(18)=0.00736
p(19)=0.00249
サイズ 2 のリストの分布は次のとおりです。
0.75139
0.24862
サイズ 3
0.55699
0.33306
0.10996
サイズ 4
0.43916
0.31018
0.18836
0.06231
ここで、項目をリストの下に移動するための 2 つのオプションについて説明します。私は2つをテストしました：
ToEnd - 最近選択したアイテムをリストの最後に移動します
並べ替え - 各アイテムが選択された回数の関連する配列を保持し、リストを選択されていないものから順に並べ替えます。
リストから選択して、各アイテムが選択された数の標準偏差を調べるシミュレーションを作成しました。標準偏差が低いほど良い。たとえば、10 項目のリストの 1 つのシミュレーションでは、50 の選択がスプレッドを作成しました。
{"a"=>5, "b"=>5, "c"=>6, "d"=>5, "e"=>4, "f"=>4, "g"=>5, "h"=>5, "i"=>6, "j"=>5}
このシミュレーションの標準偏差は
0.63
シミュレーションを実行する機能を使用して、シミュレーションを 500 回実行し、ToEnd と Sort の各メソッドの平均標準偏差を提供することで、いくつかのメタ統計を計算しました。ピック数が少ない場合は標準偏差が高くなると予想していましたが、実際には ToEnd アルゴリズムの標準偏差はピック数とともに増加しました。sort メソッドはこれを修正しました。
Testing ["a", "b", "c", "d", "e"]
-------------------------
Picks ToEnd (StdDev) Sort (StdDev)
5 0.59 0.57
10 0.76 0.68
15 0.93 0.74
20 1.04 0.74
25 1.20 0.73
30 1.28 0.73
35 1.34 0.74
40 1.50 0.75
45 1.53 0.75
45 1.56 0.77
80 2.04 0.79
125 2.52 0.74
180 3.11 0.77
245 3.53 0.79
320 4.05 0.75
405 4.52 0.76
500 5.00 0.78
より大きなセットのテスト結果を次に示します。
Testing ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
-------------------------
Picks ToEnd (StdDev) Sort (StdDev)
10 0.68 0.65
20 0.87 0.77
30 1.04 0.80
40 1.18 0.82
50 1.30 0.85
60 1.43 0.84
70 1.57 0.87
80 1.65 0.88
90 1.73 0.87
90 1.71 0.87
160 2.30 0.89
250 2.83 0.88
360 3.44 0.88
490 3.89 0.88
640 4.54 0.87
810 5.12 0.88
1000 5.66 0.85
優れたテスト フレームワークがあれば、別の乱数変換を試してみることに抵抗できませんでした。私の仮定は、x の平方根ではなく立方根を取ると、標準偏差が減少するというものでした。実際にそうしましたが、これによりランダム性が低下するのではないかと心配しました。ここでは、数式が次のように変更されたときのいくつかのシミュレーションを観察できます。
index = Int(l*(1-r^(0.33)) # l=length, r=uniform random var between 0 and 1
次に、実際のピックを調べます。私が思ったように、最初はリストの先頭に非常に重み付けされています。これを重視したい場合は、開始する前にリストをランダム化する必要があります。
StdDev = 0.632455532033676
{"a"=>10, "b"=>10, "c"=>11, "d"=>9, "e"=>10}
a d e c b c e b a d b e c a d d e b a e e c c b d a d c b c e b a a d d b e a e a b c b d c a c e c
StdDev = 0.0
{"a"=>10, "b"=>10, "c"=>10, "d"=>10, "e"=>10}
b c d a a d b c b a d e c d e c b e b a e e d c c a b a d a e e b d b a e c c e b a c c d d d a b e
StdDev = 0.632455532033676
{"a"=>9, "b"=>10, "c"=>10, "d"=>10, "e"=>11}
b d a e b c a d c e e b a c a d d c b c e d a e b b a c d c d a e a e e b d c b e a b c b c d d e e
StdDev = 0.0
{"a"=>10, "b"=>10, "c"=>10, "d"=>10, "e"=>10}
a b e d c e a b d c b c c a d b e e b e a d d c e a d b b c c a a a b e d d e c c a b b e a c d e d
StdDev = 0.632455532033676
{"a"=>11, "b"=>10, "c"=>9, "d"=>10, "e"=>10}
b a d c d c a e b e a e b c d b c a a d e e d c d e c b a b b e d c d b c e a a a d b c e b e a d a
それはすべて、特定のアイテムが選択されたときに選択される確率がどのように変化するかによって異なります。
これを実現する簡単な方法は、二重描画を使用することです。これにより、入力リスト (変更されない) と、ランダムに選択されたアイテムを追加する空のリストから開始します。(最初のリストから) 通常の各ドローの後、2 番目のリストから 1 つの項目をドローします。同じアイテム (またはむしろアイテム値) が再び表示された場合、それは選択されません (つまり、無効な描画、新たに開始)。それ以外の場合、描画がカウントされ、対応する値が 2 番目のリストに追加されます。
一般的な概念は、エルゴードの情報源に関連しているようです。
DigitalJoeは、このアプローチの明らかな欠点についてコメントしました。一言で言えば、Joe は、以前に描画された項目値 (アルゴリズムの 2 番目のリストにある値) の繰り返し (必ずしも連続した繰り返しではなく、単に「繰り返し」) を防止できる確率は、最初の数百回の描画で大きく変動することを指摘しました。 . もう 1 つの暗黙のコメントは、2 番目のリストに数十個の値が含まれた後、そのような重複を防ぐ可能性は非常に低いというものでした。これらは両方とも有効なポイントであり、資格が必要です。
この理由付けは、2 番目のリストが機能する方法に関する直感的な理解と一致します。項目の値がそこにあるほど、「二重描画」の可能性が低くなり、繰り返しを防ぐことができます。これは事実ですが、2 番目のリストにのみ焦点を当てています。[最初のリストから]以前に見たアイテムを引き出す確率を考慮する必要があります。このアイデアを直感的に理解するために 2 つの例を使用できますが、これはもちろんグラデーションです。
どちらの場合も、実際の図面の全体的な分布が入力リストの分布と一致することが重要です。これは、図面の数が統計的に有意になるにつれて特に当てはまります。
繰り返しフィルターが弱すぎる可能性の問題については、2 番目のリストが最初のリストの分布をますます反映するため、それも関連性が低くなります。おそらく、これらすべての感覚をつかむ方法は、OPの質問に記載されている目標を達成するための別の方法を検討することです.
代替アルゴリズム:アルゴリズム
1:最初のリストから置換なしで描画します。元のリストのコピーを使用して開始し、特定のアイテムが描画されるたびにそのリストから削除するため、同じ値が再び表示される可能性が全体的に低くなります. すべての項目を描画した時点で、元のリストの分布を正確に再現していました。
アルゴリズム 2:元のリストが指定された回数複製されたリストから、置換なしで描画します。これは上記と似ていますが、もう少しランダム性を導入します。つまり、図面の分散アプローチを元のリストと一致させるために、より多くの図面が必要になります。
ある意味で、私が最初に提案した 2 つのリスト アルゴリズム (元のリストから置換を使用して描画し、場合によっては繰り返しを防ぐために 2 つ目のリストを管理する) は、描画の分布を元のリストの分布に収束させるという点で、アルゴリズム 2 に似ています。ただし、元のアルゴリズムの利点は、リストの管理が容易になることです (ただし、公平を期すための簡単な方法は、描画されたアイテムをソートの「null」値に置き換え、再描画してからそのような値をヒットすることです)。 「空のセル」。2 番目のリストの描画が同じ項目値を生成する場合の再描画とは逆に、事実上同じことです..)
Item と重み付けを格納する (リスト用の) カスタム クラスを作成するなどのことができます。
アイテムを追加するときのデフォルトの重み付けを 1 にして、すべてのアイテムのすべての重み付けの合計を (「リスト」に) 保存します。
次に、アイテムをランダムに選択するときに、0 -> リスト内のすべてのアイテムの重みの合計の間の数値を選択し、リストをウォークスルーして、その「位置」にあるアイテムを (重み付けによって) 見つけることができます。そのアイテムの重み付けを減らします (これは、いくつかのフォールオフになる可能性があります。つまり、重み付けに 0.8 または 0.5 を掛けます。select がフォールオフする確率の速度を大幅に制御できます)、それを返します。
ここでの欠点は、アイテムがたくさんある場合、選択が O(n) になることです (リストを確認する必要があるため)。このため、おそらくストレージにはリンクされたリストを使用するでしょう (いずれにせよ取得のために歩かなければならないので、これにより挿入/削除が高速になります)。
ただし、膨大な数のオプションを保存していない場合、これは実装が非常に簡単で、確率を大幅に制御し、選択時に確率を減らすことができます。
リストから重み付けされたランダム要素を選択するための一般的な戦略は次のとおりです。各アイテムに重みを付けます。正規化して、合計の重みが 1 になるようにします (まず、すべてのアイテムの重みは 1/n です)。リストを重みで並べ替えます。0 から 1 の間のランダムな数字を選び、その数字を超えるまで合計を累積しながらリストを下っていきます。たとえば、重みが [0.4, 0.3, 0.2, 0.1] で、乱数が 0.63215 の場合、最初の 2 つのステップの合計 = 0.4、合計 = 0.7 で、0.7 が 0.63215 より大きいことに注意して、2 番目の要素を返します。
要素を選択したら、その重みを下方に調整します (自分に合ったものが見つかるまで、重みを下げる式を試す必要があります。最も簡単なのは、毎回一定の分数を掛けることです)。次に再正規化して繰り返します。 .
リストの長さが O(n) であるため、多くの要素がある場合、これはかなり非効率的であることに注意してください。最適化された、または同様のもの。それが問題であることが判明した場合は、レンジ ツリーなどの幾何学的データ構造を調べて、ルックアップを最適化できます。
アイテムが挿入されてからの経過時間または最後に選択されてからの経過時間を優先度修飾子として使用します... 各アイテムの優先度 = 挿入または最後に選択されてからの時間に設定し、この優先度を掛けて選択される可能性を調整します。
すべてのアイテムの可能性を把握したら、それらを正規化し (計算された同じ比率ですべてを調整して、すべての合計が 1.000 になるようにします)、それらの値を選択される確率として使用します。