빠른 캐시 정렬의 캐시 성능

Question

최근에 나는이 의심을 겪었습니다.

빠른 정렬의 캐시 성능이 병합 정렬보다 낫기 때문에 병합 정렬보다 빠른 정렬을 선택합니다. 누군가가 어떻게 설명 할 수 있습니까?

Answer 1

평균 사례가 없습니다!

최악의 경우와 극단적 인 경우가 종종 거의 발생하지 않으므로 평균 사례 분석이 수행됩니다. 그러나 모든 평균 사례 분석은 투입물의 일부 분배를 가정합니다! 정렬을 위해 전형적인 선택은 무작위 순열 모델 (위키피디아에서 암묵적으로 가정 됨)입니다.

왜 O 표기인가?

알고리즘 분석에서 상수를 버리는 것은 주된 이유 중 하나입니다. 정확한 실행 시간에 관심이 있다면 관련된 모든 기본 작업의 비용이 필요합니다 (심지어 캐시 문제를 무시하고 현대 프로세서에서 파이프 라이닝하는 것).). 수학적 분석은 각 명령어가 얼마나 자주 실행되는지 계산할 수 있지만 단일 명령어의 실행 시간은 프로세서 세부 사항에 달려 있습니다. 32 비트 정수 곱셈에 더 많은 시간이 걸리는 지 여부

두 가지 방법이 있습니다.

일부 기계 모델을 수정했습니다.

이것은 Don Knuth의 책 시리즈 "The Art of Computer Programming"에서 저자가 고안 한 인공적인 "전형적인"컴퓨터를 대상으로합니다. 볼륨 3에서는 많은 정렬 알고리즘에 대한 정확한 평균 사례 결과를 찾습니다 (예 :

퀵 : 11.667 (N + 1) (LN) (N) - 18.74 -1.74n 머지 소트 : 12.5nln (N) 힙 정렬 (Heapsort) : 16nln (N) + 0.01N 삽입 정렬 : 2.25n2 + 7.75n-3ln (n) 여러 정렬 알고리즘의 실행 시간

이 결과는 Quicksort가 가장 빠름을 나타냅니다. 그러나 Knuth의 인공 기계에서만 증명 된 바, x86 PC에 대해서는 아무런 의미가 없습니다. 알고리즘은 작은 입력에 대해 다르게 관련됩니다. 작은 입력에 대한 여러 정렬 알고리즘의 런타임

추상 기본 작업을 분석합니다.

비교 기준 정렬의 경우 일반적으로 스왑 및 키 비교입니다. Robert Sedgewick의 저서, 예 : "알고리즘",이 접근 방식을 추구합니다. 당신은 거기 찾을

퀵 : 1.44nln (n)의 비교를하지만, 8.66nln까지 (n)의 배열 때문에, 머지 소트 기반으로 스왑되지 않은 (액세스 : 2nln (n)의 비교와 13nln (n)은 평균 머지 소트에 스왑 우리는 그것을 셀 수 없다). Insertionsort : 14n2 비교 및 ​​14n2 스왑 평균. 알다시피, 이것은 정확한 런타임 분석으로 알고리즘을 비교하는 것을 쉽게 허용하지 않지만, 결과는 기계 세부 사항과는 독립적입니다.