[C#] .NET으로 배열을 무작위 화하는 가장 좋은 방법

C# / 글쓴이

.NET으로 문자열 배열을 무작위 화하는 가장 좋은 방법은 무엇입니까? 내 배열에는 약 500 개의 문자열이 포함되어 Array있으며 동일한 문자열을 사용하지만 임의의 순서 로 새 문자열 을 만들고 싶습니다 .

답변에 C # 예를 포함하십시오.

답변

.NET 3.5를 사용하는 경우 다음 IEnumerable coolness (C #이 아닌 VB.NET을 사용할 수 있지만 아이디어는 명확해야합니다 …)를 사용할 수 있습니다.

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

편집 : 확인 및 해당 VB.NET 코드는 다음과 같습니다.

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

두 번째 편집은 시간 기반 시퀀스를 반환하여 System.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]);
    }

답변

다음 구현은 Fisher-Yates 알고리즘 ( 일명 Knuth Shuffle)을 사용합니다. 그것은 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만큼 좋습니다.

답변

셔플 링 알고리즘을 찾고 있습니까?

이 작업을 수행하는 두 가지 방법이 있습니다. 영리하지만 항상 사람들은 항상 잘못 이해하고 잘못 이해하고 잘못 이해하면 그다지 영리하지 않습니다. 방법, 그리고 바위처럼 멍청하지만 누가 돌봐주는 방식으로 작동합니다.

멍청한 길

  • 첫 번째 배열의 복제본을 생성하지만 각 문자열에 임의의 숫자로 태그를 지정하십시오.
  • 난수를 기준으로 중복 배열을 정렬합니다.

이 알고리즘은 잘 작동하지만 난수 생성기가 두 개의 문자열에 같은 숫자를 태그하지 않도록하십시오. 소위 Birthday Paradox로 인해 예상보다 자주 발생합니다. 시간 복잡도는 O ( n log n )입니다.

영리한 방법

이것을 재귀 알고리즘으로 설명하겠습니다.

크기가 n 인 배열을 섞으려면 ([0 .. n -1] 범위에 있음 ) :

만약 N = 0

  • 아무것도하지 마세요

만약 N > 0

  • (재귀 단계) 배열 의 첫 번째 n -1 요소를 섞습니다.
  • [0 .. n -1] 범위에서 랜덤 인덱스 x를 선택하십시오 .
  • 인덱스 n -1의 요소를 인덱스 x 의 요소와 교체

반복되는 동등 물은 반복자를 배열을 통해 걷는 것으로, 임의의 요소로 바꾸면서 반복자가 가리키는 요소 뒤에는 요소를 바꿀 수 없다는 점에 유의하십시오. 이것은 매우 일반적인 실수이며 편향된 셔플로 이어집니다.

시간 복잡도는 O ( n )입니다.

답변

이 알고리즘은 간단하지만 효율적이지 않습니다. O (N 2 ). 모든 “순서 순”알고리즘은 일반적으로 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 (N 2 ) 인 이유 는 미묘합니다. 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);
}