프리젠 테이션을 위해 많은 문자열을 병렬로 효율적으로 정렬

Question

표시를 위해 정렬해야하는 정보 목록 (287,843 개)이있는 문제가 있습니다. 자기 정렬 빨강 - 검정 이진 트리를 사용하여 배열을 유지하거나 배열을 만든 다음 정렬하는 것이 더 효율적입니다. 내 키는 문자열입니다. 이 알고리즘은 다중 프로세서 코어를 사용해야합니다.

감사합니다.

Answer 1

이것은 실제로 설정에 따라 다릅니다. 멀티 코어 시스템을 사용하는 경우 parallel version of quicksort을 사용하여 문자열을 매우 빨리 정렬 할 수 있습니다. 각 재귀 호출은 서로 다른 호출과 동시에 실행됩니다. 많은 코어를 사용하면 이미 빠른 퀵 소트를 사용하여 훨씬 빨라질 수 있습니다. 병합 정렬과 같은 다른 정렬 알고리즘도 병렬 처리 할 수 ​​있지만 병렬 퀵 정렬은 메모리를 덜 필요로한다는 이점이 있습니다. 문자열을 정렬한다는 것을 알고 있으므로 parallel radix sort을 조사하는 것이 좋습니다.이 경우 잠재적으로 매우 빠를 수 있습니다.

대부분의 바이너리 검색 트리는 멀티 스레딩이 쉽지 않습니다. 리 밸런싱 작업은 종종 트리의 여러 부분을 동시에 변경해야하기 때문에 균형 잡힌 빨간색/검은 색 트리가 여기에서 최선의 방법이 아닐 수도 있습니다. 그러나 병렬로 효율적으로 작업 할 수있는 데이터 구조 인 concurrent skiplist을 조사하고 싶을 수 있습니다. 병렬 구조를 위해 설계된 몇 가지 새로운 이진 검색 트리가 있습니다 (skiplist (here is one such data structure)를 능가하는 경우도 있음). 그러나이 새로운 구조에 대한 기존 구현 및 토론이 줄어들 것으로 예상됩니다.

요소가 자주 변경되지 않거나 정렬 된 순서 만 필요한 경우 병렬 퀵 소트로 한 번 정렬하는 것이 가장 좋은 방법 일 수 있습니다. 요소가 자주 변경되면 병렬 skiplist와 같은 동시 데이터 구조가 더 나은 방법이 될 것입니다.

희망이 도움이됩니다.

Answer 2

파일이나 다른 데이터 소스에서 해당 목록을 읽는다고 가정하면 모든 것을 배열로 읽어서 정렬하는 것이 옳은 것처럼 보입니다. 어떤 종류의 GUI를 가지고 있다면 GUI에서 "완료 대기 중"상태를 유지하면서 스레드에서 읽기 및 정렬을 수행하는 것이 더 적합합니다. 값의 트리를 유지하는 것은 많은 삭제/삽입을 수행해야만 가능하기 때문에 실현 가능성이 있습니다.이 경우 배열을 덜 유용하게 만듭니다.

멀티 코어 정렬의 경우 병합 정렬이 병렬 처리가 가장 쉽다고 생각합니다. 그러나 나는 이것에 관해서 전문가가 아니므로 확실한 대답을 위해 내 말을 듣지 마십시오.