외부 정렬이 필요한 이유는 무엇입니까?

Question

외부 정렬의 주된 이유는 데이터가 메인 메모리보다 클 수 있다는 것입니다. 그러나 이제 가상 메모리를 사용하고 가상 메모리가 주 메모리와 디스크를 서로 바꿔줍니다. 왜 우리는 그럼 외부 정렬을해야합니까?

Answer 1

외부 정렬 알고리즘을 사용하면 대량의 데이터를 효율적으로 정렬 할 수 있습니다 (데이터가 실제 RAM에 맞지 않는 경우에도 마찬가지 임).

메모리 내 정렬 알고리즘을 사용하고 가상 메모리가 외부 정렬 (즉, 데이터를 정렬 함)에 대한 기능 요구 사항을 충족시키는 동안 효율적이지 않은 비 기능 요구 사항을 달성하지 못합니다. 좋은 외부 정렬은 외부 저장소에 읽혀지고 쓰여지는 데이터의 양을 최소화하며 (역사적으로는 탐색 시간이기도 함),이를 위해 설계되지 않은 정렬 알고리즘의 범용 가상 메모리 구현은 IO를 최소화하십시오.

Answer 2

외장 정렬이 적은 디스크 IO를 위해 더 잘 최적화 된 @ Anonymous의 대답 외에도 가끔 가상 메모리를 사용하고 가상 메모리를 사용하는 것이 가상 메모리 공간이 파일 크기보다 작기 때문에 실행 불가능합니다.

예를 들어 32 비트 시스템이 있고 (여전히 많이있는 경우), 20GB 파일을 정렬하려면 32 비트 시스템을 사용하면 2^32 ~ = 4GB 가상 주소를 가질 수 있지만

이 문제는 64 비트 시스템이 아직 많이 사용되지 않았기 때문에 이전에는 여전히 32 비트 시스템 및 일부 임베디드 장치에서 여전히 중요한 문제였습니다.

---

그러나, 이전 답변에 expained으로도 64 비트 시스템, 외부 정렬 알고리즘은 더 정렬의 성격에 최적화되고, OS를시키는 것보다 훨씬 적은 디스크 IO가 필요합니다 "일을 돌볼 ".

Answer 3

Windows를 사용하고 있는데, 공용 줄 셸에서 "systeminfo"를 실행할 수 있습니다. 내 노트북의 메모리 사용 정보를 제공합니다.

Total Physical Memory:  8,082 MB 
Available Physical Memory: 2,536 MB 
Virtual Memory: Max Size: 11,410 MB 
Virtual Memory: Available: 2,686 MB 
Virtual Memory: In Use: 8,724 MB 

난 그냥 내 노트북에서 초기화 할 수있는 배열의 최대 크기을 테스트 할 수있는 응용 프로그램을 작성합니다.

public static void BurnMemory() 
{ 
    for(var i = 1; i <= 1024; i++) 
    { 
     long size = 1 << i; 
     long t = 4 * size/(1 << 30); 
     try 
     { 
      // 1 int32 takes 32 bit(4 byte) memmory, 
      var arr = new int[size]; 

      Console.WriteLine("Test pass initialize a array with size = 2^" + i.ToString()); 
     } 
     catch(OutOfMemoryException err) 
     { 
      Console.WriteLine("Reach memory limitation when initialize a array with size = 2^{0} int32 = 4 x {1}B= {2}TB",i, size, t); 
      break; 
     } 
    } 
} 

크기가 2^29 인 어레이를 초기화하려고 할 때 종료되는 것처럼 보입니다.

Reach memory limitation when initialize a array with size = 2^29 int32 = 4 x 536870912B= 2TB 

나는 시험에서 얻을 무엇 :

• 메모리 제한에 도달하기 어렵지 않다.
• 서버의 기능을 이해하고 메모리 내 정렬 또는 외부 정렬 사용 여부를 결정해야합니다.