Coding Horrorで、さまざまなシャッフル アルゴリズムに関する記事を読みました。リストをシャッフルするために、どこかで人々がこれを行っているのを見たことがあります。
var r = new Random();
var shuffled = ordered.OrderBy(x => r.Next());
これは良いシャッフル アルゴリズムですか? 正確にはどのように機能しますか？これは受け入れられる方法ですか？
49448 次
13 に答える
218
これは、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
于 2009-08-17T12:02:20.597 に答える
72
これは、JonSkeetの回答に基づいています。
その答えでは、配列はシャッフルされてから、を使用して返されyieldます。最終的な結果として、配列はforeachの期間中、および反復に必要なオブジェクトとともにメモリに保持されますが、コストはすべて最初にあります。yieldは基本的に空のループです。
このアルゴリズムは、最初の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];
}
于 2009-11-03T03:33:17.790 に答える
10
Skeet のこの引用から始めます。
これは、O(n) シャッフルを実装するのが簡単な場合に正当な理由もなく O(n log n) であるという理由で、私が好きなシャッフルの方法ではありません。質問のコードは、基本的に各要素にランダムな（できれば一意の）番号を付け、その番号に従って要素を並べ替えることで「機能」します。
うまくいけばユニークな理由を少し説明します！
さて、Enumerable.OrderByから:
このメソッドは安定ソートを実行します。つまり、2 つの要素のキーが等しい場合、要素の順序は維持されます。
これはとても重要です！2 つの要素が同じ乱数を「受け取る」とどうなりますか? それらが配列内にあるのと同じ順序のままになることがあります。さて、これが起こる可能性は何ですか？正確に計算するのは難しいですが、まさにこの問題である誕生日問題があります。
さて、それは本当ですか？本当ですか？
いつものように、疑わしい場合は、プログラムの行をいくつか書いてください: http://pastebin.com/5CDnUxPG
この小さなコード ブロックは、逆方向に実行される Fisher-Yates アルゴリズムと順方向に実行される Fisher-Yates アルゴリズムを使用して、3 つの要素の配列を特定の回数シャッフルします ( wikiページには 2 つの擬似コード アルゴリズムがあります...それらは同等のものを生成しますただし、1 つは最初の要素から最後の要素まで実行され、もう 1 つは最後から最初の要素まで実行されます)、http://blog.codinghorror.com/the-danger-of-naivete/の素朴な間違ったアルゴリズムと、.OrderBy(x => r.Next())と.OrderBy(x => r.Next(someValue)).
さて、Random.Nextは
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 要素) の配列を並べ替えることができるはずです。
于 2015-03-15T09:04:10.463 に答える
6
おそらくほとんどの目的で問題なく、ほとんどの場合、真にランダムな分布が生成されます (Random.Next() が 2 つの同一のランダムな整数を生成する場合を除く)。
シリーズの各要素にランダムな整数を割り当て、これらの整数でシーケンスを並べ替えることで機能します。
99.9% のアプリケーションで完全に許容されます (上記のエッジ ケースを絶対に処理する必要がある場合を除きます)。また、ランタイムに対する skeet の反論は有効であるため、長いリストをシャッフルする場合は、それを使用したくない場合があります。
于 2009-08-17T12:03:02.093 に答える
4
これは以前に何度も出てきました。StackOverflow で Fisher-Yates を検索します。
このアルゴリズム用に私が書いたC# コード サンプルを次に示します。必要に応じて、他の型でパラメーター化できます。
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;
}
}
}
于 2009-08-17T13:17:36.107 に答える
3
パフォーマンスをあまり気にしないのであれば、良いシャッフル アルゴリズムのようです。私が指摘したい唯一の問題は、その動作を制御できないことです。そのため、テストするのに苦労するかもしれません。
考えられるオプションの 1 つは、乱数ジェネレーター (またはパラメーターとしての乱数ジェネレーター) にパラメーターとしてシードを渡すことです。これにより、より多くの制御を行い、より簡単にテストすることができます。
于 2009-08-17T12:03:47.867 に答える
3
Jon Skeet の回答は完全に満足のいくものでしたが、クライアントのロボ スキャナーはRandomセキュリティ上の欠陥として報告します。ということで交換しましたSystem.Security.Cryptography.RNGCryptoServiceProvider。おまけとして、言及されたスレッドセーフの問題が修正されます。一方、RNGCryptoServiceProviderは を使用するよりも 300 倍遅いと測定されていますRandom。
使用法：
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];
}
}
于 2016-07-05T17:52:36.350 に答える
3
アルゴリズムをお探しですか？私の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の間の乱数を取り、それをリストの最後に移動します。0count
次のステップバイステップの例では、移動できる項目は斜体で、選択された項目は太字です:
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
于 2015-11-06T11:06:41.493 に答える
1
このアルゴリズムは、リスト内の各値に対して新しいランダム値を生成してシャッフルし、それらのランダム値でリストを並べ替えます。これは、インメモリ テーブルに新しい列を追加し、GUID を入力してから、その列で並べ替えるものと考えてください。私には効率的な方法のように見えます（特にラムダシュガーを使用する場合！）
于 2009-08-17T12:03:05.340 に答える
1
「このアルゴリズムは、リスト内の各値に対して新しいランダム値を生成し、それらのランダム値でリストを並べ替えることによってシャッフルします」のような多くの答えは、非常に間違っている可能性があります。
これは、ソース コレクションの各要素にランダムな値を割り当てないと思います。代わりに、比較関数を約 n log n 回呼び出す Quicksort のように実行されるソート アルゴリズムが存在する可能性があります。一部のソートアルゴリズムは、この比較関数が安定していて、常に同じ結果を返すことを本当に期待しています!
IEnumerableSorter が、たとえばクイックソートの各アルゴリズム ステップに対して比較関数を呼び出し、x => r.Next()これらをキャッシュせずに両方のパラメーターに対して関数を呼び出すたびに、これらの関数を呼び出すことはできませんでした!
その場合、並べ替えアルゴリズムを本当に台無しにして、アルゴリズムが構築されている期待よりもはるかに悪いものにする可能性があります。もちろん、最終的には安定して何かを返します。
新しい "Next" 関数内にデバッグ出力を入れて後で確認するかもしれないので、何が起こるか見てみましょう。Reflector では、それがどのように機能するのかすぐにはわかりませんでした。
于 2012-04-26T17:42:21.290 に答える
-5
すべてのスレッドをクリアし、すべての新しいテストをキャッシュしてコードを実行するための起動時間、
最初の失敗コード。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()) は、最初のソリューションのユーザー定義のシャッフル メソッドよりも悪くありません。
答え: 矛盾しています。
于 2014-02-26T17:47:32.883 に答える