목록을 섞거나 임의로 생성하는 것이 더 빠릅니까?

Question

프로파일 링 정렬 알고리즘에 사용하려면 ArrayList<Integer>에 1 백만 dollars 정수가 필요합니다. 정수의 범위는 중요하지 않습니다. [0, MAX_VALUE], [MIN_VALUE,, MAX_VALUE] 등은 모두 괜찮 으면서도 광범위하게 배포되기를 원합니다.

나는 통지가이 코드를 사용할 때 : 병합 정렬은 2 밀리 초를 소요하면서

이

for (int i=0; i<1_000_000; i++) { 
    list.add(i); 
} 
Collections.shuffle(list); 
mergeSorter.sort(list); 

shuffle 호출, 실행하는 데 약 10 초가 걸립니다.

따라서 내 질문 : shuffle을 사용하는 것보다이 숫자를 무작위로 생성하는 것이 더 빠르지 만 (이유는 무엇입니까?)

는 (나는이 자신하지만 내 홈 하드웨어가이 문제를 테스트하기에 충분하지 않습니다 프로파일 것이다. 또한, 나는 이론/개념 설명을하고 싶습니다.)

Answer 1

Collections.shuffle()는 후드 Random를 사용합니다.

public static void shuffle(List<?> list, Random rnd) { 
    int size = list.size(); 
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) { 
     for (int i=size; i>1; i--) 
      swap(list, i-1, rnd.nextInt(i)); 
    } else { 
     Object arr[] = list.toArray(); 

     // Shuffle array 
     for (int i=size; i>1; i--) 
      swap(arr, i-1, rnd.nextInt(i)); 

     // Dump array back into list 
     ListIterator it = list.listIterator(); 
     for (int i=0; i<arr.length; i++) { 
      it.next(); 
      it.set(arr[i]); 
     } 
    } 
} 

당신이 자세히 보면

, 이 루프가 실행됩니다. 목록을 업데이트하기위한 새로운 배열

하나를 만들기위한

• 하나. 당신이 직접 할 경우

, 당신은 멀리 초 루프를 수행하고 GC이 목록를 수집하도록 할 수 있습니다. 그리고 배열을 가지고 있다면 새로운 복사본을 만들지 않아도됩니다.

는 그래서 그래, 자신이 성능을 향상시킬 것입니다 그 일을하지만, 시간 복잡도는 계속 될 것입니다 O (n)이

Answer 2

셔플을 사용하는 것보다 무작위 (list.add((int) (Math.random() * 1_000_000)))을이 숫자를 생성하기 위해 빠를 것이며, 왜?

이렇게 숫자를 생성하는 것이 더 빠르지 만 다른 결과가 나옵니다.

• 숫자 0 ~ N-1의 목록을 임의로 섞으면 중복이없는 목록이 나타납니다.

• 0에서 N-1 범위의 N 개의 난수가 생성되면 일 것입니다. 중복 된 목록을 얻습니다.

  ---

  N에게 난수를 생성하는 정상이면

는, 그 확실히 셔플보다 더 빠르게 될 것입니다. 코드에서 알 수 있듯이 shuffle의 가장 좋은 경우는 N 개의 난수를 생성하고 N 스왑을 수행하는 것입니다.

는

---

셔플 호출은 병합 정렬은 2 밀리 초를 소요하면서 실행하는 데 약 10 초가 걸립니다.

당신이 셔플과 머지 소트 (또는 당신이 사용하는! 분류기를 병합)를 비교하는 이유는 확실하지 않다 그러나 나는 불일치 당신이 무엇보다도 벤치 마크를 코딩 한 방법과 더이라고 생각한다. (JVM 예열 효과를 허용하지 않았을 수 있습니다.)