Visual Studio 2015에서 `std::list::sort()`가 하향식 병합 정렬로 전환된 이유는 무엇입니까?

std::list::sort()에서 갑자기 하향식 전략으로 전환한 이유는 무엇입니까?

Visual Studio에서 2015년(VS2015), Microsoft는 std::list::sort()의 정렬 전략을 전통적인 상향식 병합 정렬에서 하향식 접근 방식으로 전환했습니다. 이 변경으로 인해 내부 목록 배열의 사용이 제거되고 원래 목록 내에서 정렬된 실행 경계를 추적하기 위해 반복자가 채택되었습니다.

변경 이유

Stephan T. Lavavej 하향식 접근 방식의 개발자인 는 메모리 할당과 기본이 아닌 할당자의 구성을 피할 필요성을 언급했습니다. VS2015에는 더 이상 기본 구성 가능 및 상태 저장이 아닌 할당자가 도입되어 이전 상향식 접근 방식을 사용할 때 문제가 발생했습니다.

하향식 접근 방식 구현

상위 -down 접근 방식은 목록이 비어 있거나 단일 요소를 포함하는 기본 사례에 도달할 때까지 목록을 반복적으로 절반으로 나누는 재귀 알고리즘을 활용합니다. _Sort 함수는 목록을 왼쪽 실행, 오른쪽 실행 및 끝 반복기의 세 세그먼트로 분할합니다. 병합 논리는 std::list::splice를 사용하여 수행되어 원래 목록 내에서 노드를 이동하고 예외 안전성을 유지합니다.

성능 고려 사항

하향식은 이 접근 방식은 메모리 할당 문제를 해결하지만 원래 상향식 병합 정렬에 비해 성능이 저하됩니다. 분산된 노드가 있는 대규모 목록의 경우 하향식 접근 방식은 캐시 누락이 증가하여 실행 시간이 느려집니다. 그러한 경우에는 목록을 배열이나 벡터로 이동하여 정렬한 후 정렬된 배열이나 벡터에서 새 목록을 만드는 것이 더 빠를 수 있습니다.

위 내용은 Visual Studio 2015에서 `std::list::sort()`가 하향식 병합 정렬로 전환된 이유는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!