long long을 C로 정렬하고 싶습니다. 일반적으로 malloc() 배열로 사용하는 버퍼는 qsort()이지만 4 백만 * 8 바이트는 하나입니다 거대한 연속적인 메모리 덩어리.C에서 매우 큰 배열을 정렬하는 방법
가장 쉬운 방법은 무엇입니까? 나는 이것을 위해 순수한 속도보다 쉬워진다. 나는 어떤 라이브러리도 사용하지 않기를 바랄 것이고 그 결과는 Windows와 Linux 모두에서 겸손한 넷북에서 실행되어야 할 것이다.
그냥 버퍼를 할당하고 qsort을 호출하십시오. 32MB는 요즘은 겸손한 넷북 에서조차별로 크지 않습니다.
정말로 분할해야하는 경우 : 더 작은 청크를 정렬하고, 파일에 쓰고 병합합니다. 병합은 병합되는 각각의 것들에 대해 단일 선형 패스를 사용합니다. 그러나 정말로,하지 마라. 그냥 정렬.
(Knuth의 볼륨 2에서 "외부 정렬"이라고 불리는 정렬 및 병합 접근법에 대한 좋은 설명이 있습니다 .Knuth가이 글을 쓰고 있었을 때 외부 데이터는 자기 테이프에 있었을 것이지만 원칙은 디스크와별로 다르지 않은 점은 가능한 한 순차적으로 I/O를 원한다는 것인데, 그 이유는 SSD와 약간 다릅니다.)
+1 크 누스를 참조했습니다. 그게 _always_ 작동 – sehe
내가 추가 할 수있는 유일한 것은 데이터가 이미 디스크에 원시 이진 경우, 당신은 그것을로드하고 다시 쓰는 대신에'mmap' (또는 동급) 수 있습니다. 그러나 시스템 오류가 발생했을 때 데이터의 안전을 중요하게 생각한다면 이는 잘못된 생각 일 수 있습니다. –
'qsort()'는 잘 작동했다. 나는 내가 무엇에 대해 걱정했는지 모른다. 몇 메가 바이트가 많은 RAM이었을 때 C에서 스크립팅 언어로 옮겨온 이후로 메모리 관리가 얼마나 많이 제공되었는지는 몰랐습니다. – hippietrail
32 MB? 너무 크지 않아 .... 퀵소트가 트릭을해야 해.
가능한 한 데이터의 순서가 지정되지 않도록하는 것이 가장 좋습니다. 언급 된 것처럼 디스크 (또는 네트워크 또는 소스와 상관없이)에서 직접 데이터를 조직의 자체 컨테이너 (나무, 아마도 std::set)로 읽어들이는 것이 좋습니다.
그런 식으로 많은 것을 정리하거나 메모리 관리에 대해 걱정할 필요가 없습니다. 컨테이너의 필요한 용량을 알고있는 경우 std::vector(initialcapacity)을 사용하여 추가 성능을 압박하거나 vector::reserve을 앞에 불러야 할 수 있습니다.
님의 다음 최고의 std::make_heap heapify 에 대한 기존의 요소를 사용하고 push_heap를 사용하여 요소에 의해 요소를 추가하는 것이 좋습니다 할 것 (또한 pop_heap 참조). 이것은 본질적으로 같은 자기 주문 세트로 패러다임하지만
(오, 사소한 세부 사항, 힙에 sort_heap N은 요소 수)
이것이 흥미로운 접근이라고 생각한다면 알려주십시오. 유스 케이스에 대한 정보가 더 필요합니다.
그는 C가 아니라 C++이라고 말했습니다 –
Bloddy ... 저는 오늘 장님입니다. 좋아요, C에서 동등한 접근법이 있어야합니다; 나는 이것이 아직도 가치가 있기를 바란다. – sehe
어디에서 오는 값은 어디로 가고, 어디로 갈까요? 그들은 모두 기억에 남을 것입니까? –
디스크에 현재 어디에 저장되어 있습니까? 64 비트 시스템을 실행하지 않는다고 가정합니까? –
4 백만 번 8은 ~ 32 메가 바이트입니다. 인접하지 않아도됩니다. - 많은 4K 블록의 매핑 된 주소에 대해 연속적인 주소 공간이 필요합니다. IOW, malloc/qsort가 좋을 것입니다. –