외부 멀티 스레딩 정렬

Question

외부 멀티 스레딩 정렬을 구현해야합니다. 나는 멀티 스레딩 프로그래밍에 대한 경험이 없으며, 현재 알고리즘이 좋은지 아닌지 잘 모르겠다. 어떻게 완료해야할지 모르겠다. 내 생각은 다음과 같습니다

1. 스레드가 입력 파일에서 데이터의 다음 블록을 읽어
2. 정렬 그것의 standart algorith에게 (표준 : : 일종)
3. 난에있는이 후 다른 파일

4. 에 기록을 사용하여 그러한 파일을 병합하십시오. 어떻게해야합니까? 병합 가 난 후 바로 종류의 파일을 병합하려고하면, 내가 피하기 위해 알고리즘을 마련 할 수

5. 임시 파일을 많이받을 때까지
   • 내가 전까지 입력 파일을 기다리면
     완전히 처리됩니다 매우 다른 크기의 파일을 병합하는 경우 은 O (N^2) 난이도로 연결됩니다.

또한 나는 그러나 나는가 EnterNet 좋은 준비 알고리즘으로 찾을 수 없습니다, 이것은 매우 일반적인 작업입니다 가정합니다. 나는 특히 C++ 구현을 위해 그러한 링크에 대해 매우 감사하게 생각합니다.

Answer 1

글쎄, 그 대답은 간단하지 않으며 실제로 처리하려는 항목의 수와 스토리지 시스템과 CPU의 상대적 속도와 같은 많은 요인에 따라 달라집니다.

하지만 여기서는 멀티 스레딩을 사용하는 것이 좋습니다. 데이터가 너무 커서 메모리에 저장되지 않습니까? qsort 알고리즘조차도 충분히 빨리 정렬 할 수없는 많은 항목이 있습니까? 여러 개의 프로세서 또는 코어를 활용하십니까? 모르겠다.

먼저 입력 파일과 출력 파일을 읽고 쓰는 데 필요한 시간과 정렬에 필요한 CPU 시간을 측정하는 테스트 루틴을 작성하는 것이 좋습니다. I/O는 일반적으로 CPU 실행 속도보다 느리고 (실제로는 비교할 수 없다), 데이터를 병렬로 읽는다면 I/O가 효율적이지 않을 수 있습니다 (이동해야하는 디스크 헤드가 하나 있습니다. 출력은 사실 직렬화됩니다. 디지털 드라이브 인 경우에도 여전히 입력 및 출력 채널이있는 장치입니다. 즉, 임시 파일 읽기/쓰기의 추가 오버 헤드가 멀티 스레딩의 이점을 제거하는 것 이상일 수 있습니다. 먼저 메모리에있는 전체 파일을 읽고 정렬하고 쓰는 알고리즘을 만들고 상대 속도를 확인하기위한 시간 카운터를 넣어보십시오. I/O가 전체 시간의 30 % 인 경우 (예, 그다지!), 임시 파일을 읽고/병합/작성하는 데있어 훨씬 많은 시간이 소요될 것이기 때문에 분명히 가치가 없습니다. 한 번에 전체 데이터가 바람직 할 것입니다.

왜 여기에 멀티 스레딩을 사용해야하는지 모르겠다. 데이터가 실제로 블록으로 전달되는 경우에만 그럴 것이지만, 위의 고려 사항, 상대적인 I/O-CPU 속도 및 추가 임시 파일 읽기/쓰기 오버 헤드. 그리고 힌트는 파일 액세스가 매우 효율적이어야합니다. 예를 들어 응용 프로그램 버퍼를 사용하는 큰 블록에서 읽기/쓰기 (시스템 호출 저장)가 필요합니다. 그렇지 않으면 파일이 저장되는 경우 해로운 영향을 줄 수 있습니다. 너 이외의 기계 (예 : 서버).

내 제안이 유용하다고 생각하길 바랍니다.