성능을 위해 퀵 포트를 최적화하려고했습니다. 4M (1 < < 22) 정수 항목 (각각 4 바이트)의 경우 72 개의 동시 스레드 (72 개 코어)를 지원할 수있는 시스템에서 정렬하려면 병렬 퀵 정렬 알고리즘 0.5 (0.499703) 초가 필요합니다. 나는 병렬 퀵 소트를 더욱 최적화 할 수있는 효율적인 방법을 배우는 데 관심이있다. 또한, 특정 작업 부하가 주어지면 모든 정렬 알고리즘에 대한 리그 테이블이있는 경우 다른 정렬 알고리즘과 비교하는 데 관심이 있습니까?정렬 알고리즘을위한 가장 빠른 quicksort-League 테이블은 무엇입니까?
내가 아는 바로는 정렬 알고리즘을위한 표준 리더 보드가 없습니다. 정렬 알고리즘의 성능은 많은 다른 요소에 달려 있습니다 - 입력 분포, 입력 크기, 프로그래밍 언어 선택, 사용 된 컴파일러의 유형과 설정, 코어 수, 주변 온도 방, 운영체제 등
귀하의 코드를 보지 않고도 귀하의 퀵 소트를 최적화하는 방법에 관해서는 확실히 말하기 어렵습니다. 간단한 quicksort 최적화 목록은 다음과 같습니다. 작은 입력에 빠른 종류로 전환
인트로 스펙 션을 추가합니다. Introsort는 재귀 깊이를 추적하고 알고리즘이 퇴행하는 것처럼 보이면 힙으로 전환하는 빠른 변종입니다. 이렇게하면 런타임이 O (n log n)이되며이 경우가 트리거되지 않으면 적은 비용이 발생합니다.
더 나은 분할 알고리즘을 사용하십시오. 최근 듀얼 피벗 퀵 소트 (Dual-pivot quicksort)가 전통적인 파티셔닝 알고리즘의 대안으로 등장했습니다. 그것은 많은 입력에 더 나은 성능을 가지고 있습니다. 또한 중복이 많은 입력을 얻을 것으로 예상되는 경우 중복 요소를 정상적으로 처리하는 분할 스키마를 사용하는 것이 좋습니다.
꼬리말 제거를 도입하십시오. 많은 퀵 정렬 구현은 정렬해야하는 두 개의 하위 배열에 대해 두 번의 재귀 호출을 시작하지만 실제로는 그렇게 할 필요가 없습니다. 하나의 순환 호출을 시작한 다음 두 번째 호출을 마무리 호출로 처리 할 수 있으며 매개 변수를 초기 호출에 겹쳐 쓰고 전체를 while 루프에 넣을 수 있습니다.
모두가 중요합니다. 키 집합에 대한 선험적 지식 –
일종의 스레드에서 모든 작업을 수행하면 훨씬 쉽습니다. 개발자가 다중 코어에 작업량을로드하고 알고리즘 및 메타 데이터의 최적화가 아키텍처에 따라 크게 달라지면서 캐시 크기 등이 커지고 있습니다. 아직 그 부분이나 테이블/그래프/차트를 많이 보지 못했습니다./알고리즘은 다양한 시스템에서 최상의 정렬 알고리즘과 메타 데이터를 제안 할 수 있습니다. –
나는 rand()에 의해 생성 된 랜덤 키 세트를 고소했다. 실제로 Big (O)도 중요하며 병행 성도 중요합니다. 일부 알고리즘은 효율적으로 병렬화 될 가능성이 적습니다. smoothsort와 같은 일부 다른 객체는 가장 큰 O 속성을 가지고 있지만 구현하기 어렵습니다. – user1147800