Random.Nex (int)에 배열 병목 현상을 섞으십시오.

Question

제공된 배열을 정렬하는 작은 조각의 코드를 작업하고 있습니다. 배열은 가능한 한 빨리 정렬되어야합니다. 무작위 화가 그다지 중요하지 않습니다. 방법을 프로파일 링 한 후에 가장 큰 돼지는 Random.Next이라는 것을 알게되었습니다. 어느 것이 메소드 실행 시간의 약 70 %를 차지합니다. 더 빠른 무작위 제너레이터를 온라인으로 검색 한 후에는 향상된 성능을 제공하는 플러그 앤 플레이 라이브러리가 없습니다.

그래서이 코드의 성능을 더 향상시킬 수있는 방법이 있는지 궁금합니다.

[MethodImpl(MethodImplOptions.NoInlining)] 
    private static void Shuffle(byte[] chars) 
    { 
     for (var i = 0; i < chars.Length; i++) 
     { 
      var index = rnd.Next(chars.Length); 
      byte tmpStore = chars[index]; 
      chars[index] = chars[i]; 
      chars[i] = tmpStore; 
     } 

    } 

Answer 1

좋아요, 이것이 미세 최적화 영역으로 들어가고 있습니다.

Random.Next(int)

실제로 우리가 최적화 할 수 있음을 내부적으로 어떤 작전을 수행

int index = (int)(rnd.Next() * (1.0/int.Max) * chars.Length); 

루프에서 반복해서 같은 maxValue를 사용하고 있기 때문에, 사소한 최적화는 외부에서 분모를 미리 계산하는 것 고리. 우리가 int 제거 이런 식으로 ->double 변환 및 곱셈 : 다음

double d = chars.Length/(double)int.Max; 

그리고 : 별도의 노트에

int index = (int)(rnd.Next() * d); 

는 : 당신의 셔플은 유니폼을해야 할 것하지 않습니다 분포. 제프 앳 우드의 게시물 The Danger of Naïveté에서이 주제를 다루며 유니폼 피셔 - 예이츠 셔플 수행 방법을 보여줍니다. n^n 만약

Answer 2

당신이 한 무작위 이중으로 만들 n^n하여 곱하면, 다음을위한 준비로 n으로 임의의 결과를 분할에 modulo(n) 현재 난수 각 반복을하기 전에 사용할 수있는 이중 범위가 너무 크지 않다 다음 반복.