LINQ で重複なしのランダムサンプリング[A]を行うもっとも単純な方法は，おそらくランダムに並び替えて先頭から所望の数だけ要素を取り出す方法でしょう。
var random = new Random(); source.OrderBy(_ => random.NextDouble()).Take(n);
重み付きでサンプリングしたい場合は乱数に重みを与えて大きい順に取り出します。
source.Zip(weight, (x, w) => new { Value = x, Weight = w })
.OrderByDescending(x => {
var u = random.NextDouble();
return Math.Pow(u, 1.0 / x.Weight);
})
.Take(n)
.Select(x => x.Value);
しかしこの方法では全体をソートするので，データ数が大きくなってくると非常に効率が悪くなります。巨大なデータ数に対応するにはどうすれば良いでしょうか。
ランダムサンプリングを行う際は，普通はメモリー上に乗るサイズの要素を取得します。したがって，サンプルサイズの分だけ先頭の要素を記録しておき，以降は重みにしたがって記録している要素と交換する・しないの判断をしていけば良いです。
var keyedSource = source.Zip(weight, (x, w) => {
var key = Math.Pow(random.NextDouble(), 1.0 / w);
return new KeyValuePair<double, T>(key, x);
});
using (var enumerator = keyedSource.GetEnumerator())
{
var buffer = new List<KeyValuePair<double, T>>(count);
Func<double, double, int> compareKey = Comparer<double>.Default.Compare;
while (buffer.Count < count && enumerator.MoveNext())
{
var current = enumerator.Current;
var key = current.Key;
// キーの値で降順を維持しながら挿入。
// キーが最小の要素を取り除く際に，末尾の要素を取り除くと少し効率だけが良い。
// ただし実際はリストを使わない方がもっと良い (本文参照)。
int index = 0;
while (index < buffer.Count && compareKey(key, buffer[index].Key) < 0)
{
index++;
}
buffer.Insert(index, current);
}
var lastIndex = count - 1; // 以降 buffer サイズが変わらないので固定値。
while (enumerator.MoveNext())
{
var current = enumerator.Current;
var key = current.Key;
if (buffer[lastIndex].Key < key) // ソートしているので最後の要素のキーが最小。
{
buffer.RemoveAt(lastIndex);
int index = 0;
while (index < buffer.Count && compareKey(key, buffer[index].Key) < 0)
{
index++;
}
buffer.Insert(index, current);
}
}
return buffer.Select(pair => pair.Value);
}
これで全体をソートすることなく一部のソートだけでランダムサンプリングが行えます。ただし上の実装は手を抜いてリストに対してソートしながら挿入をしているので遅いです。二分探索木のようなデータ構造を用いるべきでしょう[B]。
実はさらに工夫してループ内での乱数生成とバッファーへの削除・挿入の回数を減らすこともできます。詳しくは参考文献を参照してください。
ちなみに実装例では重みを IEnumerable<double> で指定していますが， Func<T, double> で要素から重みを選択する方式にした方が LINQ っぽいかもしれません。
おまけ
F# で二分探索木を使った版。
参考文献
更新履歴
- [2013-01-11 00:00] 2 回目の
whileの中のcompareKeyの符号が逆になっていたのを修正。 - [2013-01-12 14:00]
whileの中のcompareKeyの符号が逆になっていたのを修正 (前の修正で修正する方を間違えていました)。