Random と OrderBy の使用は優れたシャッフル アルゴリズムですか?
https://stackoverflow.com/questions/1287567
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian解決
これは私が好むシャッフル方法ではありません。主な理由は、O(n) シャッフルを実装するのは簡単であるにもかかわらず、正当な理由もなく O(n log n) になるという理由です。質問のコードは、基本的に各要素にランダムな（できれば一意の）番号を与え、その番号に従って要素を順序付けることによって「機能」します。
私はダーステンフィールドの変種の方が好きです。 フィッシャー・イェーツのシャッフル 要素を交換します。
簡単な実装 Shuffle 拡張メソッドは基本的に呼び出しで構成されます ToList または ToArray 入力では、Fisher-Yates の既存の実装を使用します。( Random 生活をより良くするためのパラメータとして使用します。) 周囲にはたくさんの実装があります...おそらくどこかに答えがあると思います。
このような拡張メソッドの良い点は、実際に何をしようとしているのかが読者にとって非常に明確になることです。
編集：これは簡単な実装です (エラーチェックはありません!)。
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
T[] elements = source.ToArray();
// Note i > 0 to avoid final pointless iteration
for (int i = elements.Length-1; i > 0; i--)
{
// Swap element "i" with a random earlier element it (or itself)
int swapIndex = rng.Next(i + 1);
T tmp = elements[i];
elements[i] = elements[swapIndex];
elements[swapIndex] = tmp;
}
// Lazily yield (avoiding aliasing issues etc)
foreach (T element in elements)
{
yield return element;
}
}
編集：以下のパフォーマンスに関するコメントを見て、要素をシャッフルするときに実際に要素を返すことができることを思い出しました。
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
T[] elements = source.ToArray();
for (int i = elements.Length - 1; i >= 0; i--)
{
// Swap element "i" with a random earlier element it (or itself)
// ... except we don't really need to swap it fully, as we can
// return it immediately, and afterwards it's irrelevant.
int swapIndex = rng.Next(i + 1);
yield return elements[swapIndex];
elements[swapIndex] = elements[i];
}
}
これで、必要な作業のみが実行されるようになります。
どちらの場合も、次のインスタンスに注意する必要があることに注意してください。 Random 次のように使用します:
- の 2 つのインスタンスを作成する
Randomほぼ同時に、同じ乱数のシーケンスが生成されます (同じ方法で使用した場合)。 Randomスレッドセーフではありません。
私は持っている に関する記事 Random これらの問題についてさらに詳しく説明し、解決策を提供します。
他のヒント
これはジョンスキートの<のhref =「https://stackoverflow.com/questions/1287567/c-is-using-random-and-orderby-a-good-shuffle-algorithm/1287572#1287572」に基づいています>回答するます。
その答えでは、アレイはyieldを使用して戻され、その後、シャッフルされます。正味の結果が配列ならびに反復に必要なオブジェクト、まだコストは、すべて先頭にある、foreachの期間中メモリに保持されていることである - 。収率は基本的に空のループである
このアルゴリズムは、最初の3つの項目が選択されますゲームで多く使用され、他は以降のみで、すべての場合は必要になります。私の提案は、すぐに彼らが交換される数字をyieldすることです。 Oで反復コストを維持しながらこれは、スタートアップコストを減少させる（1）（基本的に反復当たり5つの操作）。総コストは同じままだろうが、シャッフル自体は速くなります。これは、それは理論的に違いはありませんでしょうが、前述のユースケースでは、起動を高速化されますcollection.Shuffle().ToArray()と呼ばれているケースでは。また、これはあなたがほんの数ユニークなアイテムが必要な場合のためのアルゴリズムが便利になるだろう。例えば、あなたが52のデッキから3枚のカードを引き出すために必要がある場合、あなたはdeck.Shuffle().Take(3)を呼び出すことができますし、（配列全体が最初にコピーされなければならないだろうが）唯一の3スワップが行われます。
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
T[] elements = source.ToArray();
// Note i > 0 to avoid final pointless iteration
for (int i = elements.Length - 1; i > 0; i--)
{
// Swap element "i" with a random earlier element it (or itself)
int swapIndex = rng.Next(i + 1);
yield return elements[swapIndex];
elements[swapIndex] = elements[i];
// we don't actually perform the swap, we can forget about the
// swapped element because we already returned it.
}
// there is one item remaining that was not returned - we return it now
yield return elements[0];
}
スキートの次の引用から始めます。
これは私が好むシャッフル方法ではありません。主な理由は、O(n) シャッフルを実装するのは簡単であるにもかかわらず、正当な理由もなく O(n log n) になるという理由です。質問のコードは、基本的にランダムな(できればユニークです！) 各要素に番号を付け、その番号に従って要素を順序付けします。
その理由を少し説明していきます できればユニークです！
さて、から Enumerable.OrderBy:
このメソッドは安定した並べ替えを実行します。つまり、2 つの要素のキーが等しい場合、要素の順序は保持されます。
これはとても重要です！2 つの要素が同じ乱数を「受け取った」場合はどうなるでしょうか?配列内での順序が同じままになることが起こります。さて、これが起こる可能性は何でしょうか？正確に計算するのは難しいですが、 誕生日の問題 それがまさにこの問題です。
さて、それは本当ですか？本当ですか？
いつものように、疑問がある場合は、プログラムを数行書いてください。 http://pastebin.com/5CDnUxPG
この小さなコード ブロックは、後方実行のフィッシャー・イェーツ アルゴリズムと、前方実行のフィッシャー・イェーツ アルゴリズムを使用して、3 要素の配列を一定回数シャッフルします ( ウィキ ページには 2 つの疑似コード アルゴリズムがあります...これらは同等の結果を生成しますが、1 つは最初の要素から最後の要素まで実行され、もう 1 つは最後の要素から最初の要素まで実行されます)。 http://blog.codinghorror.com/the-danger-of-naivete/ そしてそれを使用して .OrderBy(x => r.Next()) そしてその .OrderBy(x => r.Next(someValue)).
今、 ランダム。次へ は
0 以上、MaxValue 未満の 32 ビットの符号付き整数。
したがって、それはと同等です
OrderBy(x => r.Next(int.MaxValue))
この問題が存在するかどうかをテストするには、配列を拡大する (非常に遅い) か、単純に乱数発生器の最大値を減らすことができます (int.MaxValue 「特別な」番号ではありません...それは単に非常に大きな数です）。最終的に、アルゴリズムが安定性によって偏っていなければ、 OrderBy, の場合、どの範囲の値でも同じ結果が得られるはずです。
次に、プログラムは 1 ～ 4096 の範囲のいくつかの値をテストします。結果を見ると、低い値 (< 128) では、アルゴリズムが非常に偏っている (4 ～ 8%) ことが明らかです。少なくとも必要な 3 つの値 r.Next(1024). 。配列を大きくすると (4 または 5)、 r.Next(1024) 十分ではありません。私はシャッフルや数学の専門家ではありませんが、配列の長さの追加ビットごとに、最大値の追加ビットが 2 ビット必要になると思います (誕生日のパラドックスが sqrt(numvalues) に関連しているため)。最大値が 2^31 の場合、最大 2^12/2^13 ビット (4096 ～ 8192 要素) の配列をソートできるはずです。
これは、ほとんどの目的のためにprobablly大丈夫だ、とほとんど常にそれが（Random.Next（）は二つの同一の整数の乱数を生成する場合を除く）、真にランダムな分布を生成します。
これは、これらの整数でシーケンスを順序付け、次いで、一連の各要素のランダムな整数を割り当てることによって動作します。
（あなたが絶対に上のエッジケースを処理する必要がない場合）これは、アプリケーションの99.9％のために完全に許容です。また、その実行時にスキートの異議が有効であるので、あなたは、長いリストをシャッフルしている場合は、それを使用したくない場合があります。
パフォーマンスをあまり心配しないのであれば、良いシャッフル アルゴリズムのように思えます。私が指摘したい唯一の問題は、その動作が制御できないため、テストするのが難しいかもしれないということです。
考えられるオプションの 1 つは、シードをパラメーターとして乱数ジェネレーター (または乱数ジェネレーターをパラメーターとして) に渡すことです。これにより、より詳細な制御が可能になり、より簡単にテストできるようになります。
これは前に何度も来ています。 StackOverflowの上フィッシャーイエーツを検索ます。
ここで私は、このアルゴリズムのために書いたの
static public class FisherYates
{
// Based on Java code from wikipedia:
// http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
static public void Shuffle(int[] deck)
{
Random r = new Random();
for (int n = deck.Length - 1; n > 0; --n)
{
int k = r.Next(n+1);
int temp = deck[n];
deck[n] = deck[k];
deck[k] = temp;
}
}
}
私はジョンスキートの答えは完全に満足のいくものであることが判明したが、私のクライアントのロボ・スキャナは、セキュリティ上の欠陥としてRandomの任意のインスタンスを報告します。だから私はSystem.Security.Cryptography.RNGCryptoServiceProviderのためにそれをスワップアウト。ボーナスとして、それは言及されたそのスレッドの安全性の問題が修正されます。一方、RNGCryptoServiceProviderはRandomを使用するよりも300倍も遅いように測定されている。
使用方法：
using (var rng = new RNGCryptoServiceProvider())
{
var data = new byte[4];
yourCollection = yourCollection.Shuffle(rng, data);
}
方法：
/// <summary>
/// Shuffles the elements of a sequence randomly.
/// </summary>
/// <param name="source">A sequence of values to shuffle.</param>
/// <param name="rng">An instance of a random number generator.</param>
/// <param name="data">A placeholder to generate random bytes into.</param>
/// <returns>A sequence whose elements are shuffled randomly.</returns>
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, RNGCryptoServiceProvider rng, byte[] data)
{
var elements = source.ToArray();
for (int i = elements.Length - 1; i >= 0; i--)
{
rng.GetBytes(data);
var swapIndex = BitConverter.ToUInt32(data, 0) % (i + 1);
yield return elements[swapIndex];
elements[swapIndex] = elements[i];
}
}
少し関係のない、しかし、ここで興味深い方法であるサイコロのロールの真の乱数生成のために（それがexcessibe実際にあるにもかかわらず、本当に実装されていることを）！
私はここにこれを掲示していた理由は、彼が彼のユーザーが実際のサイコロの上に、シャッフルするアルゴリズムを使用しての考えに反応する方法についていくつかの興味深い点になることです。もちろん、現実の世界では、このようなソリューションは、唯一のランダム性は、このような大きな影響を与えていると、おそらく影響がお金に影響スペクトルの本当に両極端のためです;）
。私はここに、「それらのランダムな値リストを注文する、リスト内の各値に対して新しいランダム値を生成することにより、このアルゴリズムシャッフル」のような多くの答えは非常に間違っているかもしれないと言うでしょう！
私は、これはソースコレクションの各要素にランダムな値を割り当てていないことを考えると思います。代わりに、コンペア機能は約nログn回呼んでクイックソートのように実行しているソートアルゴリズムがあるかもしれません。ある種algortihm本当にこの比較機能が安定していると、常に同じ結果を返すことを期待！
は、それがIEnumerableSorterは、例えば、各アルゴリズムのステップのための比較関数を呼び出すことはできませんでしたクイックソートと毎回、これらをキャッシュすることなく、両方のパラメータの関数x => r.Next()を呼び出します！
その場合、あなたは本当に台無しソートアルゴリズムをとはアルゴリズムが上に蓄積され予想よりも、それは非常に悪化させる可能性があります。もちろん、それは最終的に安定して何かを返します。
私は何が起こるか見て、新しい「次へ」関数内でデバッグ出力を置くことによって、後でそれを確認することがあります。 リフレクターでは、私はすぐにそれがどのように動作するかを見つけることができませんでした。
アルゴリズムをお探しですか?私のものを使ってもいいよ ShuffleList クラス：
class ShuffleList<T> : List<T>
{
public void Shuffle()
{
Random random = new Random();
for (int count = Count; count > 0; count--)
{
int i = random.Next(count);
Add(this[i]);
RemoveAt(i);
}
}
}
次に、次のように使用します。
ShuffleList<int> list = new ShuffleList<int>();
// Add elements to your list.
list.Shuffle();
どのように機能するのでしょうか?
最初の 5 つの整数の最初のソートされたリストを見てみましょう。 { 0, 1, 2, 3, 4 }.
このメソッドは要素の数をカウントすることから始まり、それを呼び出します。 count. 。それから、 count 各ステップで減少するため、次の間の乱数が必要になります。 0 そして count そしてそれをリストの最後に移動します。
次の段階的な例では、移動できる項目は次のとおりです。 イタリック, 、選択された項目は 大胆な:
0 1 2 3 4
0 1 2 3 4
0 1 2 4 3
0 1 2 4 3
1 2 4 3 0
1 2 4 3 0
1 2 3 0 4
1 2 3 0 4
2 3 0 4 1
2 3 0 4 1
3 0 4 1 2
このアルゴリズムは、それらのランダムな値リストを注文する、リスト内の各値に対して新しいランダム値を生成することによって、シャッフルします。その列によってソート次いで、その後、メモリ内のテーブルに新しい列を追加のGUIDでそれを充填すると考えます。私への効率的な方法のように見える（特にラムダ砂糖！）
すべてのスレッドをクリアし、すべての新しいテストをキャッシュしてコードを実行するための起動時間、
最初の失敗したコード。LINQPad上で動作します。このコードをテストするには次のようにします。
Stopwatch st = new Stopwatch();
st.Start();
var r = new Random();
List<string[]> list = new List<string[]>();
list.Add(new String[] {"1","X"});
list.Add(new String[] {"2","A"});
list.Add(new String[] {"3","B"});
list.Add(new String[] {"4","C"});
list.Add(new String[] {"5","D"});
list.Add(new String[] {"6","E"});
//list.OrderBy (l => r.Next()).Dump();
list.OrderBy (l => Guid.NewGuid()).Dump();
st.Stop();
Console.WriteLine(st.Elapsed.TotalMilliseconds);
list.OrderBy(x => r.Next()) は 38.6528 ミリ秒を使用します
list.OrderBy(x => Guid.NewGuid()) は 36.7634 ミリ秒を使用します (MSDN から推奨されています)。
2回目以降は両方が同時に使用されます。
編集：Intel Core i7 4@2.1GHz、Ram 8 GB DDR3 @1600、HDD SATA 5200 rpm でのテスト コード [データ:www.dropbox.com/s/pbtmh5s9lw285kp/data]
using System;
using System.Runtime;
using System.Diagnostics;
using System.IO;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Threading;
namespace Algorithm
{
class Program
{
public static void Main(string[] args)
{
try {
int i = 0;
int limit = 10;
var result = GetTestRandomSort(limit);
foreach (var element in result) {
Console.WriteLine();
Console.WriteLine("time {0}: {1} ms", ++i, element);
}
} catch (Exception e) {
Console.WriteLine(e.Message);
} finally {
Console.Write("Press any key to continue . . . ");
Console.ReadKey(true);
}
}
public static IEnumerable<double> GetTestRandomSort(int limit)
{
for (int i = 0; i < 5; i++) {
string path = null, temp = null;
Stopwatch st = null;
StreamReader sr = null;
int? count = null;
List<string> list = null;
Random r = null;
GC.Collect();
GC.WaitForPendingFinalizers();
Thread.Sleep(5000);
st = Stopwatch.StartNew();
#region Import Input Data
path = Environment.CurrentDirectory + "\\data";
list = new List<string>();
sr = new StreamReader(path);
count = 0;
while (count < limit && (temp = sr.ReadLine()) != null) {
// Console.WriteLine(temp);
list.Add(temp);
count++;
}
sr.Close();
#endregion
// Console.WriteLine("--------------Random--------------");
// #region Sort by Random with OrderBy(random.Next())
// r = new Random();
// list = list.OrderBy(l => r.Next()).ToList();
// #endregion
// #region Sort by Random with OrderBy(Guid)
// list = list.OrderBy(l => Guid.NewGuid()).ToList();
// #endregion
// #region Sort by Random with Parallel and OrderBy(random.Next())
// r = new Random();
// list = list.AsParallel().OrderBy(l => r.Next()).ToList();
// #endregion
// #region Sort by Random with Parallel OrderBy(Guid)
// list = list.AsParallel().OrderBy(l => Guid.NewGuid()).ToList();
// #endregion
// #region Sort by Random with User-Defined Shuffle Method
// r = new Random();
// list = list.Shuffle(r).ToList();
// #endregion
// #region Sort by Random with Parallel User-Defined Shuffle Method
// r = new Random();
// list = list.AsParallel().Shuffle(r).ToList();
// #endregion
// Result
//
st.Stop();
yield return st.Elapsed.TotalMilliseconds;
foreach (var element in list) {
Console.WriteLine(element);
}
}
}
}
}
結果の説明: https://www.dropbox.com/s/9dw9wl259dfs04g/ResultDescription.PNG
結果統計: https://www.dropbox.com/s/ewq5ybtsvesme4d/ResultStat.PNG
結論：
仮定する：LINQ OrderBy(r.Next()) と OrderBy(Guid.NewGuid()) は、最初のソリューションのユーザー定義のシャッフル メソッドよりも悪くはありません。
答え：それらは矛盾しています。
