.NETで配列をランダム化する最良の方法

StackOverflow https://stackoverflow.com/questions/108819

質問

.NET で文字列の配列をランダム化する最良の方法は何ですか?私の配列には約 500 個の文字列が含まれており、新しい配列を作成したいと考えています。 Array 同じ文字列ですが、順序はランダムです。

回答には C# の例を含めてください。

役に立ちましたか？

解決

.NET 3.5 を使用している場合は、次の IEnumerable 機能を使用できます (C# ではなく VB.NET ですが、考え方は明らかです...)。

Random rnd=new Random();
string[] MyRandomArray = MyArray.OrderBy(x => rnd.Next()).ToArray();

編集：OK、対応する VB.NET コードは次のとおりです。

Dim rnd As New System.Random
Dim MyRandomArray = MyArray.OrderBy(Function() rnd.Next()).ToArray()

2 番目の編集は、System.Random が時間ベースのシーケンスを返すため「スレッドセーフではない」、「おもちゃのアプリにのみ適している」という指摘に応えて、次のようになります。私の例で使用したように、配列をランダム化するルーチンの再入力を許可しない限り、Random() は完全にスレッドセーフです。その場合、次のようなものが必要になります。 lock (MyRandomArray) とにかくデータを破損しないようにするために、 rnd 同じように。

また、エントロピーのソースとしての System.Random はそれほど強力ではないこともよく理解する必要があります。に記載されているように、 MSDN ドキュメント, 、から派生したものを使用する必要があります System.Security.Cryptography.RandomNumberGenerator セキュリティ関連のことをしている場合。例えば：

using System.Security.Cryptography;

...

RNGCryptoServiceProvider rnd = new RNGCryptoServiceProvider();
string[] MyRandomArray = MyArray.OrderBy(x => GetNextInt32(rnd)).ToArray();

...

static int GetNextInt32(RNGCryptoServiceProvider rnd)
    {
        byte[] randomInt = new byte[4];
        rnd.GetBytes(randomInt);
        return Convert.ToInt32(randomInt[0]);
    }

他のヒント

次の実装では、 フィッシャー・イェーツアルゴリズム 別名クヌース・シャッフル。これは O(n) 時間で実行され、所定の位置でシャッフルされるため、コード行数は多くなりますが、「ランダムで並べ替え」手法よりもパフォーマンスが優れています。見る ここ いくつかの比較パフォーマンス測定については、私は System.Random を使用しましたが、これは暗号化以外の目的には適しています。*

static class RandomExtensions
{
    public static void Shuffle<T> (this Random rng, T[] array)
    {
        int n = array.Length;
        while (n > 1) 
        {
            int k = rng.Next(n--);
            T temp = array[n];
            array[n] = array[k];
            array[k] = temp;
        }
    }
}

使用法：

var array = new int[] {1, 2, 3, 4};
var rng = new Random();
rng.Shuffle(array);
rng.Shuffle(array); // different order from first call to Shuffle

* 長い配列の場合、(非常に大きな) 数の順列を同じ確率にするために、スワップごとに擬似乱数ジェネレーター (PRNG) を何度も繰り返し実行して十分なエントロピーを生成する必要があります。500 要素の配列の場合、可能な 500 のほんの一部にすぎません。順列は PRNG を使用して取得できます。それにもかかわらず、Fisher-Yates アルゴリズムには偏りがないため、シャッフルは使用する RNG と同じくらい優れたものになります。

シャッフル アルゴリズムを探しているんですね?

これを行うには 2 つの方法があります。賢いけど、人々はいつも誤解して間違っているように見えるので、結局のところそれほど賢明ではないかもしれない、そして岩のように愚かな方法しかし、それはうまくいくので、誰が気にするわけでもありません。

愚かな方法

  • 最初の配列の複製を作成しますが、各文字列に乱数をタグ付けする必要があります。
  • 重複した配列を乱数に関してソートします。

このアルゴリズムはうまく機能しますが、乱数ジェネレーターが 2 つの文字列に同じ番号のタグを付ける可能性が低いことを確認してください。いわゆる 誕生日のパラドックス, 、これは予想よりも頻繁に発生します。その時間計算量は O(n ログ n).

賢い方法

これを再帰的アルゴリズムとして説明します。

サイズの配列をシャッフルするには n (範囲 [0..n-1]):

もし n = 0
  • 何もしない
もし n > 0
  • (再帰ステップ) 最初をシャッフルする n配列の -1 要素
  • ランダムなインデックスを選択し、 バツ, 、範囲 [0..n-1]
  • インデックスの要素を交換する nインデックスの要素の場合は -1 バツ

反復処理に相当するのは、反復子を配列内で処理し、途中でランダムな要素と交換することですが、要素と交換できないことに注意してください。 後 イテレータが指すもの。これは非常によくある間違いであり、偏ったシャッフルにつながります。

時間計算量は O(n).

このアルゴリズムは単純ですが効率的ではありません。O(N2）。通常、すべての「order by」アルゴリズムは O(N log N) です。おそらく、数十万の要素以下では違いはありませんが、大きなリストの場合は違いがあります。

var stringlist = ... // add your values to stringlist

var r = new Random();

var res = new List<string>(stringlist.Count);

while (stringlist.Count >0)
{
   var i = r.Next(stringlist.Count);
   res.Add(stringlist[i]);
   stringlist.RemoveAt(i);
}

O(N2) 微妙です: List.RemoveAt() 端から順に削除しない限り、O(N) 操作になります。

Matt Howells から拡張メソッドを作成することもできます。例。

   namespace System
    {
        public static class MSSystemExtenstions
        {
            private static Random rng = new Random();
            public static void Shuffle<T>(this T[] array)
            {
                rng = new Random();
                int n = array.Length;
                while (n > 1)
                {
                    int k = rng.Next(n);
                    n--;
                    T temp = array[n];
                    array[n] = array[k];
                    array[k] = temp;
                }
            }
        }
    }

次に、次のように使用できます。 

        string[] names = new string[] {
                "Aaron Moline1", 
                "Aaron Moline2", 
                "Aaron Moline3", 
                "Aaron Moline4", 
                "Aaron Moline5", 
                "Aaron Moline6", 
                "Aaron Moline7", 
                "Aaron Moline8", 
                "Aaron Moline9", 
            };
        names.Shuffle<string>();

配列のランダム化は、多数の文字列を移動する必要があるため、負荷がかかります。なぜ配列からランダムに読み取らないのでしょうか?最悪の場合、getNextString() を使用してラッパー クラスを作成することもできます。本当にランダムな配列を作成する必要がある場合は、次のようなことを行うことができます

for i = 0 -> i= array.length * 5
   swap two strings in random places

*5は任意です。

思いついただけで、次のようにすることができます。

public string[] Randomize(string[] input)
{
  List<string> inputList = input.ToList();
  string[] output = new string[input.Length];
  Random randomizer = new Random();
  int i = 0;

  while (inputList.Count > 0)
  {
    int index = r.Next(inputList.Count);
    output[i++] = inputList[index];
    inputList.RemoveAt(index);
  }

  return (output);
}

同じ長さのランダムな float または int の配列を生成します。その配列をソートし、ターゲット配列で対応するスワップを実行します。

これにより、真に独立した並べ替えが行われます。

Random r = new Random();
List<string> list = new List(originalArray);
List<string> randomStrings = new List();

while(list.Count > 0)
{
int i = r.Random(list.Count);
randomStrings.Add(list[i]);
list.RemoveAt(i);
}

Jacco、あなたのソリューションがカスタム IComparer であるのは安全ではありません。ソート ルーチンが適切に機能するには、比較器がいくつかの要件に準拠する必要があります。その第一は一貫性です。比較子がオブジェクトの同じペアに対して呼び出された場合、常に同じ結果を返す必要があります。(比較も推移的である必要があります)。

これらの要件を満たさないと、並べ替えルーチンで無限ループの可能性を含むさまざまな問題が発生する可能性があります。

ランダムな数値を各エントリに関連付け、その値で並べ替えるソリューションに関しては、2 つのエントリに同じ数値が割り当てられるたびに、出力のランダム性が損なわれるため、出力に固有のバイアスが生じます。(「安定した」ソート ルーチンでは、入力の最初にあるものが出力の最初になります。Array.Sort は安定していませんが、Quicksort アルゴリズムによって行われる分割に基づく偏りは依然として存在します)。

どのレベルのランダム性が必要かについて少し考える必要があります。断固とした攻撃者から保護するために暗号レベルのランダム性が必要なポーカー サイトを運営している場合、単に曲のプレイリストをランダム化したいだけの場合とはまったく異なる要件があります。

曲リストのシャッフルには、シードされた PRNG (System.Random など) を使用しても問題ありません。ポーカー サイトの場合、それは選択肢ですらないので、スタックオーバーフローで誰かが代わりにやってくれるよりもずっと難しく問題を考える必要があります。(暗号化 RNG の使用は始まりにすぎません。アルゴリズムがバイアスを導入しないこと、十分なエントロピー ソースがあること、その後のランダム性を損なう内部状態が公開されていないことを確認する必要があります)。

この投稿にはすでにかなりの回答が寄せられています。高速で公平な結果を得るには、フィッシャー・イェーツ・シャッフルのダーステンフェルド実装を使用してください。いくつかの実装も投稿されていますが、いくつかは実際には間違っていることに注意してください。

少し前にいくつかの記事を書きましたが、 この手法を使用して完全シャッフルと部分シャッフルを実装する, 、そして (この 2 番目のリンクは私が価値を追加したいと考えている場所です) 実装に偏りがないかどうかを確認する方法に関するフォローアップの投稿, 、シャッフル アルゴリズムをチェックするために使用できます。2 番目の投稿の最後で、乱数選択における単純な間違いが引き起こす影響を確認できます。

わかりました、これは明らかに私からの迷惑です (申し訳ありません...) が、私は非常に一般的で暗号的に強力な方法をよく使用します。

public static class EnumerableExtensions
{
    static readonly RNGCryptoServiceProvider RngCryptoServiceProvider = new RNGCryptoServiceProvider();
    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> enumerable)
    {
        var randomIntegerBuffer = new byte[4];
        Func<int> rand = () =>
                             {
                                 RngCryptoServiceProvider.GetBytes(randomIntegerBuffer);
                                 return BitConverter.ToInt32(randomIntegerBuffer, 0);
                             };
        return from item in enumerable
               let rec = new {item, rnd = rand()}
               orderby rec.rnd
               select rec.item;
    }
}

Shuffle() は IEnumerable の拡張機能なので、たとえば、リスト内の 0 から 1000 までの数値をランダムな順序で取得することができます。

Enumerable.Range(0,1000).Shuffle().ToList()

また、この方法では、並べ替えの値がシーケンス内の要素ごとに 1 回だけ生成されて記憶されるため、並べ替えの際に驚くようなことはありません。

複雑なアルゴリズムは必要ありません。

たった 1 行の簡単な行:

Random random = new Random();
array.ToList().Sort((x, y) => random.Next(-1, 1)).ToArray();

変換する必要があることに注意してください。 Array に List まず、使用しない場合 List そもそも。

また、これは非常に大きな配列では効率的ではないことに注意してください。それ以外の場合は、クリーンでシンプルです。

これは、以下に基づいた完全に機能するコンソール ソリューションです。 ここで提供されている例:

class Program
{
    static string[] words1 = new string[] { "brown", "jumped", "the", "fox", "quick" };

    static void Main()
    {
        var result = Shuffle(words1);
        foreach (var i in result)
        {
            Console.Write(i + " ");
        }
        Console.ReadKey();
    }

   static string[] Shuffle(string[] wordArray) {
        Random random = new Random();
        for (int i = wordArray.Length - 1; i > 0; i--)
        {
            int swapIndex = random.Next(i + 1);
            string temp = wordArray[i];
            wordArray[i] = wordArray[swapIndex];
            wordArray[swapIndex] = temp;
        }
        return wordArray;
    }         
}

        int[] numbers = {0,1,2,3,4,5,6,7,8,9};
        List<int> numList = new List<int>();
        numList.AddRange(numbers);

        Console.WriteLine("Original Order");
        for (int i = 0; i < numList.Count; i++)
        {
            Console.Write(String.Format("{0} ",numList[i]));
        }

        Random random = new Random();
        Console.WriteLine("\n\nRandom Order");
        for (int i = 0; i < numList.Capacity; i++)
        {
            int randomIndex = random.Next(numList.Count);
            Console.Write(String.Format("{0} ", numList[randomIndex]));
            numList.RemoveAt(randomIndex);
        }
        Console.ReadLine();

このコードは、配列内の数値をシャッフルします。

using System;

// ...
    static void Main(string[] args)
    {
        Console.ForegroundColor = ConsoleColor.Cyan;
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        Shuffle(numbers);

        for (int i = 0; i < numbers.Length; i++)
            Console.Write(numbers[i] + (i < numbers.Length - 1 ? ", " : null));
        Console.WriteLine();

        string[] words = { "this", "is", "a", "string", "of", "words" };
        Shuffle(words);

        for (int i = 0; i < words.Length; i++)
            Console.Write(words[i] + (i < words.Length - 1 ? ", " : null));
        Console.WriteLine();

        Console.ForegroundColor = ConsoleColor.Gray;
        Console.Write("Press any key to quit . . . ");
        Console.ReadKey(true);
    }

    static void Shuffle<T>(T[] array)
    {
        Random random = new Random();

        for (int i = 0; i < array.Length; i++)
        {
            T temporary = array[i];
            int intrandom = random.Next(array.Length);
            array[i] = array[intrandom];
            array[intrandom] = temporary;
        }
    }

OLINQ を使用した簡単な方法は次のとおりです。

// Input array
List<String> lst = new List<string>();
for (int i = 0; i < 500; i += 1) lst.Add(i.ToString());

// Output array
List<String> lstRandom = new List<string>();

// Randomize
Random rnd = new Random();
lstRandom.AddRange(from s in lst orderby rnd.Next(100) select s);

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;
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top