저는 메모리에 맞지 않는 거대한 데이터 세트를 효율적으로 정렬하는 방법을 찾으려고합니다. 높은 수준의 분명한 대답은 몇 가지 표준 알고리즘을 사용하여 메모리에 들어있는 모든 묶음을 정렬하고이를 디스크에 쓴 다음 병합하는 것입니다. 그들을 합병하는 것이 문제입니다.효율적인 Out-Of-Core 정렬
데이터를 C 청크로 나눠서 병합 할 C 파일이 있다고 가정 해 보겠습니다. 한 패스에서 C-way 병합을 수행하면 기술적으로 O (N^2) 알고리즘을 사용하지만 O (N)을 수행해야만 한 알고리즘은 디스크에 씁니다. 반복적으로 C/2 파일, C/4 파일 등으로 병합하면 O (N log N) 알고리즘을 사용하지만 O (N log N)을 수행해야하는 디스크는 디스크에 씁니다. a 거대한 상수.
이 수수께끼의 전형적인 해결책은 무엇입니까? 어떤 좋은 것이 있습니까?
간단한 대답은이 질문에 대한 간단한 대답이 없다는 것입니다. 많은 답변이 있는데, 그 중 대부분은 상당히 복잡합니다. Knuth volume 3 (한 예로)은 많은 공간을 사용합니다.
수행 된 작업을 살펴볼 때 분명 해지는 한 가지가 있습니다. 정말로은 초기 정렬 중에 생성하는 파일의 수를 최소화하고 각 파일의 길이를 최대화하려고합니다. 그렇게하기 위해서는 일반적으로 메모리에 저장할 수있는만큼 많은 데이터를 읽으려고하지만 정렬 및 쓰지 않고 힙에 넣기를 원합니다. 그런 다음 각 레코드를 쓰면 다른 레코드를 IN으로 읽은 다음 힙에 넣습니다. 후속 레코드를 힙에서 파일로 쓸 때 기존 레코드보다 큰지 여부를 확인합니다. 그렇지 않은 경우 힙에서 제거하고 다른 힙에 삽입하십시오. 그런 다음 첫 번째 힙에서 다음으로 작은 레코드로 계속 진행하십시오. 첫 번째 힙이 완전히 비어 있고 두 번째 힙이 모든 메모리를 차지하면 레코드를 현재 파일에 저장하지 않습니다. 이 시점에서 레코드를 새 파일에 넣기 시작하고 기본적으로 두 힙의 사용을 "교환"합니다.
이렇게하면 초기 단계에서 상당히 긴 중간 파일이 생성되므로 파일을 병합하는 것이 상당히 효과적이지 않습니다.
편집 : 확실히 이것을 발명하지 못했습니다. 아마도 Knuth에서 처음 읽었을 지 모르지만, 아마도 알고리즘 + 데이터 구조 = 프로그램 (Niklaus Wirth)에서 모두 논의합니다. 크 누스 (Knuth)는 1954 년 MIT에서 석사 학위 논문 "H. Seward"에 처음으로이 책을 저술 한 바 있습니다. 크 누스 (Knuth)의 2 판을 가지고 있다면 그것은 3 권 중 254 페이지에 있습니다. 제 3 판에는 페이지 번호가 없습니다.
왜 다른 관점에서 문제를 보지 않습니까? 예를 들어, 이름을 정렬하고, 패스를 만들고, A-F으로 시작하는 항목을 정렬하고, G-M으로 시작하는 문자열을 정렬하는 두 번째 단계 등을 수행합니다. 그런 다음 결과를 순서대로 간단히 추가 할 수 있습니다. 단점은 데이터가 이어야하며 디스크 C 시간에서을 읽어야한다는 것입니다.
이것은 흥미로운 아이디어입니다.디스크 읽기가 디스크 쓰기보다 훨씬 빠르기 때문에 고전적인 알고리즘과 어떻게 비교할 수 있을지 궁금합니다. –
http://www.amazon.com/Art-Computer-Programming-Sorting-Searching/dp/0201896850의 알고리즘을 사용하지 않는 이유는 무엇입니까?
아주 훌륭하고 신중하게 설명되었습니다.
나는 당신이하는 책장에있는 모든 책자들이 똑같은 책을 가지고 있다고 가정 할 수 있을지 확신하지 못합니다! 추천하고 싶은 특정 알고리즘이 있습니까? 이 특정 사안에 어떻게 적용되는지에 대한 힌트를 줄 수 있습니까? –
@ 피터 : 내 요점은 좀 더 일반적입니다. 정렬 작업을 수행하는 경우이 책을 구입해야합니다. –
좋은 해결책은 external sorting입니다. 특히 외부 합병 알고리즘을 확인하십시오.
외부 정렬 데이터의 방대한 양을 처리 할 수있는 정렬 알고리즘의 클래스 에 대한 용어입니다. 데이터 는 컴퓨팅 장치 (일반적으로 RAM)의 주요 메모리에 맞지 않는 분류되고 대신 그들이 에 느린 외부 메모리 (보통 하드 드라이브)에 상주해야하는 경우 외부 정렬이 필요합니다. 일반적인 외부 정렬 알고리즘은 작은 하위 파일을 정렬하여 시작하는 정렬 - 병합 전략을 사용합니다. 기본 알고리즘은 두 단계로 구성됩니다. 즉, 단계를 병합하고 병합 단계입니다. 정렬 단계에서, 서브 파일은 사용 가능한 버퍼 공간이 주기억 을 가능한 판독 내부 정렬 알고리즘을 사용하여 정렬 및 임시 정렬 서브 파일로서 디스크에 다시 기록 에 들어갈 수있다. 병합 단계에서 정렬 된 하위 파일은 하나 이상의 패스 중에 병합됩니다.
그의 질문은 외부 정렬을 수행하는 방법이었습니다 (분명히 그 이름을 알지 못했지만). 그가 외부 정렬을 사용해야한다고 대답하면 인터넷 검색을위한 출발점이 될 수 있지만, 적어도 하나의 최대 득표 수를 받기에는 다소 부족한 것으로 보인다. –
@ Jerry Coffin, 외부 병합 알고리즘을 설명하기 때문에 위키피디아 항목을 게시했습니다. –
닉이 맞으면 외부 정렬을 사용하십시오. 귀하의 C 방식 병합은 O (N^2)를 의미하지 않습니다. 병합에 우선 순위 대기열을 사용하면 여전히 O (N lg N)입니다.
또한 cache oblivious algorithms에서 정렬 할 수 있습니다.
나는이 같은 질문을 한 달 전에 들었으므로 재미있다. 그리고 우리 지역 전문가가 준 반응도 재미있다.
우리가 admitedly는 아스 커의 비용으로 농담이라고 생각하지만
"일종의 명령을 유닉스 사용"... 그것은 아니라고 밝혀졌습니다. 그 똑똑한 사람들은 이미 매우 큰 파일의 문제를 해결하는 방법에 대해 많은 생각을했으며, 사용 가능한 리소스를 잘 활용하는 매우 인상적인 구현을 생각해 냈습니다.
따라서 휠을 다시 발명 할 계획이 없다면 : 즉 시간이 있고 이것이 업무상 중요한 경우 unix sort을 사용하는 것이 좋습니다.
유일한 단점은 신비한 구문입니다. This page은 명령 및 다양한 설명 전용입니다.
개인적인 조언 : 명령이 실제로 원하는대로 정확하게 수행되는지 테스트하기 위해 데이터의 작은 샘플을 가져 가십시오.
동의합니다. 나는 최근에 대용량 데이터 세트를 분류하고 병렬지도/축소 솔루션을 먼저 구현 한 교수의 이야기를 들었다. 단일 기계에서 GNU 정렬은 올바르게 기억한다면 약 20의 비율로 병렬 솔루션의 속도를 이겼습니다. –
장소를 정렬하거나 새 복사본을 만드시겠습니까? 정렬 작업을 수행하는 경우 일반적으로 메모리 매핑 IO가 좋은 옵션입니다. 전체 파일을 매핑하고 병합 정렬을 수행하십시오. OS는 파일의 대부분을 메모리에 보관할 것이고 데이터 세트에 따라 일반적으로 IO를 최소화 할 것입니다.
독자적인 정렬 알고리즘을 작성하는 경우 각 통과 후에 방향을 바꾸는 것이 하나의 트릭입니다. 따라서 첫 번째 패스가 처음부터 끝까지 시작한 다음 두 번째 패스에서 끝에서 시작으로 이동하십시오. 파일을 A, B, C, D 부분으로 나눈 다음 C와 D를 정렬 한 후에 C와 D를 병합하고 A와 B로 되돌아 가지 않아야합니다. 파일을 메모리에 저장하고 가능한 한 캐시를 사용하려고합니다.
A) mmap은 한 번에 2G 만 매핑합니다. 더 이상 코어 밖 구조는 거의 없습니다. –
B) 페이징 된 리소스를 처리하고 있다는 것을 이해하지 못하는 mergesort를 사용하는 것은 대개 재앙입니다. –
C) I/O 프리미티브를 잘 사용하면 복사본을 피할 수 있고 mmap을 순진하게 사용하여 달성 할 수있는 것보다 우수한 성능을 얻을 수 있습니다. –
아주 좋은 솔루션처럼 들립니다. 참조하는 힙은 http://en.wikipedia.org/wiki/Heap_%28data_structure%29에 설명 된 데이터 구조이며 동적 메모리 할당을 위해 C에서 사용 된 힙이 아니라는 점을 언급 할 필요가 있습니다. 또한, 알고리즘의 근원을 아는 것이 좋을 것입니다 - 그것은 당신의 발명입니까? – gooli