「並べ替え」（シャッフル）C＃での整数のリストをランダムに最も効率的な方法
https://stackoverflow.com/questions/375351
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は「ソート」可能な限り最も効率的な方法で整数（0-1999）のリストをランダムにする必要があります。任意のアイデア？
現在、私はこのような何かをしています：
bool[] bIndexSet = new bool[iItemCount];
for (int iCurIndex = 0; iCurIndex < iItemCount; iCurIndex++)
{
int iSwapIndex = random.Next(iItemCount);
if (!bIndexSet[iSwapIndex] && iSwapIndex != iCurIndex)
{
int iTemp = values[iSwapIndex];
values[iSwapIndex] = values[iCurIndex];
values[iCurIndex] = values[iSwapIndex];
bIndexSet[iCurIndex] = true;
bIndexSet[iSwapIndex] = true;
}
}
解決
良い線形時間シャッフルアルゴリズムはhref="http://en.wikipedia.org/wiki/Fisher-Yates_shuffle" rel="noreferrer">フィッシャー-Yates氏はのシャッフル あなたが提案したアルゴリズムで見つける一つの問題は、あなたのようにシャッフルの終わり近くに、あなたのループはまだスワップされていないのランダムに選択された要素を探して多くの時間を費やすだろうということです。それは交換するために最後の要素になったら、これは時間の不確定量がかかる場合があります。 また、それはソートする要素の数が奇数であれば、あなたのアルゴリズムを終了することはありませんように見えます。
他のヒント
static Random random = new Random();
public static IEnumerable<T> RandomPermutation<T>(IEnumerable<T> sequence)
{
T[] retArray = sequence.ToArray();
for (int i = 0; i < retArray.Length - 1; i += 1)
{
int swapIndex = random.Next(i, retArray.Length);
if (swapIndex != i) {
T temp = retArray[i];
retArray[i] = retArray[swapIndex];
retArray[swapIndex] = temp;
}
}
return retArray;
}
のIEnumerableを実装するリストや他のオブジェクトを処理するように変更。
私たちはどんなのIListコレクションのランダムな列挙子を取得するには、この外の拡張メソッドを作ることができます。
class Program
{
static void Main(string[] args)
{
IList<int> l = new List<int>();
l.Add(7);
l.Add(11);
l.Add(13);
l.Add(17);
foreach (var i in l.AsRandom())
Console.WriteLine(i);
Console.ReadLine();
}
}
public static class MyExtensions
{
public static IEnumerable<T> AsRandom<T>(this IList<T> list)
{
int[] indexes = Enumerable.Range(0, list.Count).ToArray();
Random generator = new Random();
for (int i = 0; i < list.Count; ++i )
{
int position = generator.Next(i, list.Count);
yield return list[indexes[position]];
indexes[position] = indexes[i];
}
}
}
これは、フィッシャー・イエーツは、我々はランダムを列挙したいリストのインデックスにシャッフルの逆を使用しています。サイズ豚のそのビットは、（4 * list.Countバイト割り当てる）が、O（N）で実行されます。
public static void shuffle (int[] array)
{
Random rng = new Random(); // i.e., java.util.Random.
int n = array.length; // The number of items left to shuffle (loop invariant).
while (n > 1)
{
int k = rng.nextInt(n); // 0 <= k < n.
n--; // n is now the last pertinent index;
int temp = array[n]; // swap array[n] with array[k] (does nothing if k == n).
array[n] = array[k];
array[k] = temp;
}
}
上記の実装が依存しています Random.nextInt（int型）を提供 十分にランダムかつ公平な 結果
私は効率係数のかわからないが、あなたはArrayListのを使用するのではなくされていない場合、私は、次のようなものを使用しています：
private ArrayList ShuffleArrayList(ArrayList source)
{
ArrayList sortedList = new ArrayList();
Random generator = new Random();
while (source.Count > 0)
{
int position = generator.Next(source.Count);
sortedList.Add(source[position]);
source.RemoveAt(position);
}
return sortedList;
}
これを使用して、中間スワップを心配する必要はありません。
あなたの効率を改善するために、あなたは彼らが入れ替わった示すためではなくブール値よりも入れ替わっている値/インデックスのセットを維持することができます。残りのプールからあなたの無作為化スワップ指数を選択します。プールが0である、またはあなたが最初のリストを通してそれを作ったとき、あなたは行われていた場合。あなたは、ランダムなスワップ指標値を選択しようとする可能性を持っていません。
あなたはスワップを行うと、ちょうどプールからそれらを削除します。
あなたはそれを見ているデータのサイズに関しては大したことないです。
itemList.OrderBy(x=>Guid.NewGuid()).Take(amount).ToList()
ICRの答えは非常に高速ですが、結果の配列は正規分布していません。あなたが正規分布をしたい場合は、ここでのコードは次のとおりです。
public static IEnumerable<T> RandomPermutation<T>(this IEnumerable<T> sequence, int start,int end)
{
T[] array = sequence as T[] ?? sequence.ToArray();
var result = new T[array.Length];
for (int i = 0; i < start; i++)
{
result[i] = array[i];
}
for (int i = end; i < array.Length; i++)
{
result[i] = array[i];
}
var sortArray=new List<KeyValuePair<double,T>>(array.Length-start-(array.Length-end));
lock (random)
{
for (int i = start; i < end; i++)
{
sortArray.Add(new KeyValuePair<double, T>(random.NextDouble(), array[i]));
}
}
sortArray.Sort((i,j)=>i.Key.CompareTo(j.Key));
for (int i = start; i < end; i++)
{
result[i] = sortArray[i - start].Value;
}
return result;
}
私のテストでは、このアルゴリズムは1 ICRが提供されるよりも6倍遅かったことに注意してください、しかし、これは私が正常な結果の分布を得るために考え出すことができる唯一の方法である。
ではないでしょう、この作品のようなもの？
var list = new[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
var random = new Random();
list.Sort((a,b)=>random.Next(-1,1));
私は最後の2行は、ミカの答えに交換することがなければならないと思います。だから、コードは次のようになります。
public static void shuffle(int[] array) {
Random rng = new Random(); // i.e., java.util.Random.
int n = array.Length; // The number of items left to shuffle (loop invariant).
while (n > 1) {
int k = rng.Next(n); // 0 <= k < n.
n--; // n is now the last pertinent index;
int temp = array[n]; // swap array[n] with array[k] (does nothing if k == n).
array[n] = array[k];
array[k] = temp;
}
}
かについてます：
System.Array.Sort(arrayinstance, RandomizerMethod);
...
//any evoluated random class could do it !
private static readonly System.Random Randomizer = new System.Random();
private static int RandomizerMethod<T>(T x, T y)
where T : IComparable<T>
{
if (x.CompareTo(y) == 0)
return 0;
return Randomizer.Next().CompareTo(Randomizer.Next());
}
出来上がり！
私は、ハッシュテーブルの自然キーのソートをランダム化することができ、一時的なハッシュテーブルを用いた方法を作りました。単純に、追加の読み取りおよび破棄します。
int min = 1;
int max = 100;
Random random;
Hashtable hash = new Hashtable();
for (int x = min; x <= max; x++)
{
random = new Random(DateTime.Now.Millisecond + x);
hash.Add(random.Next(Int32.MinValue, Int32.MaxValue), x);
}
foreach (int key in hash.Keys)
{
HttpContext.Current.Response.Write("<br/>" + hash[key] + "::" + key);
}
hash.Clear(); // cleanup
