V8은 10 개 이상의 요소 길이에 대해 정렬을 사용하고 그 이하의 배열에 대해서는 삽입 정렬을 사용합니다. 여기 the sources은 다음과 같습니다V8의 Array.sort에서 쉘 정렬보다 삽입 정렬을 사용하는 이유는 무엇입니까?
function InnerArraySort(array, length, comparefn) {
// In-place QuickSort algorithm.
// For short (length <= 10) arrays, insertion sort is used for efficiency.
나는 쉘 일종의 대신 삽입 정렬을 사용하지에 대한 이론적 근거는 무엇 궁금하네요? 나는 아마 10 요소의 배열에 대해 차이를 만들지는 않지만 여전히 이해할 수 있습니다. 어떤 아이디어?
원래의 근거는 기록에서 손실됩니다. 짧은 배열을위한 InsertionSort를 도입 한 commit (2008 년 전후)은 QuickSort (짧은 배열의 경우)보다 빠르다고 언급합니다. 그래서 그것은 다음과 같이 요약 할 수 있습니다. 누군가 그 식으로 그런 식으로 구현되었으므로 다른 사람이 이후로 변경해야 할 이유를 찾지 못했습니다.
InsertionSort는 짧은 배열에 대해 매우 효율적이므로, 차이를 만들지는 않을 것이라는 점에 동의합니다. 팀에서 실제로 작업하는 데는 많은 작업이 필요합니다.
고마워요, 그래서 당신이 말하는 것은 아마도 누군가가'삽입 정렬 '을 구현했고 그것을 쉘 - 정렬로 바꾸는 것을 고려해야 만한다는 것입니까? –
예. 예전에는 QuickSort 만 사용 했었고 작은 배열의 경우 InsertionSort 케이스가 추가되었으며 그 이후로는 "충분 함"이었습니다. – jmrk
, 도와 주셔서 감사합니다. –
큰 질문입니다. 그 이유는 간단합니다. 적어도 작은 배열에서는 삽입 정렬을 사용하는 것이 실제로 더 빠릅니다. Java는 사실 오래 전에 동일한 스위치를 만들었습니다. 이제 배열의 길이가 코드에서 7보다 작 으면 삽입 정렬을 수행합니다. here을 참조하십시오. 상단의 함수 sort1 아래에 있습니다.
기본적으로 이러한 작은 배열에 대해 (대부분의 경우) Quicksort의 오버 헤드가 삽입 정렬보다 느립니다. 이러한 경우의 삽입 정렬은 O (n)에서 최상의 성능에 접근하는 경향이 훨씬 큽니다. 반면 Quicksort는 여전히 O (n log n)에 머무를 가능성이 큽니다.
반면에 쉘 정렬은 삽입 정렬보다 훨씬 느립니다. 즉, 훨씬 더 빠를 수 있습니다 (상대적으로). 삽입 정렬을위한 최상의 경우는 여전히 0 (n) 인 반면 쉘 정렬의 경우는 O (n log n)입니다. 10 세 이하의 모든 숫자는 수학적 관점에서 더 빠를 가능성이 있습니다. 불행하게도 쉘 정렬을 위해서는 더 많은 스와핑이 필요합니다. 쉘 정렬은 훨씬 느려질 수 있습니다. 삽입 정렬은 O (1) 스왑을 사용하여 스와핑을 수행 할 수 있지만 쉘 정렬은 O (n) 스왑을 중심으로 이루어질 수 있습니다. 스왑은 기계에서 비용이 많이 든다. 왜냐하면 스왑 핑을 위해 세 번째 임시 레지스터를 사용하는 경향이 있기 때문이다 (XOR을 사용하는 방법이 있지만, 여전히 CPU에서 세 가지 명령이 일반적이다). 따라서 삽입 정렬은 실제 머신에서 여전히 승리합니다.
링크 및 정보를 보내 주셔서 감사합니다.하지만 질문은 셸 정렬 대 삽입 정렬, 퀵 정렬이 아닙니다. –
죄송합니다. 나는 그것을 놓쳤습니다. –
분명히 작은 스위치가 스위치를 포함하는 데있어 성능 차이가 충분합니다. – Bergi
@Bergi, 예, '삽입 정렬'은 '빠른 정렬'보다 작은 배열에서 더 좋지만 '쉘 정렬'은 작은 배열에서 '삽입 정렬'보다 우수합니다. –
Afaik 쉘 정렬은 삽입 정렬과 크게 다르지 않지만 가치있는 변화라고 생각하고 현실적인 벤치 마크를 작성할 수 있다면 V8 팀이 패치에 만족할 것이라고 확신합니다. – Bergi