힙 할당을 사용하는 대형 배열의 세그먼트 오류

Question

다음 코드는 1GB 항목을 보유하는 배열에 공간을 동적으로 할당 한 후에도 4Gb 머신에서 실행될 때 세그먼트 화 오류를 발생시킵니다. 1 백만 항목, 즉 n = 1000000에서 잘 작동합니다. 다음 코드는 기수 정렬을 사용하여 정수 값과 색인 값을 정렬합니다. 이 프로그램을 1 천만 개 항목에 사용할 수 있도록하려면 어떻게해야합니까?

int main() 
{ 
    int n=10000000; // 10 million entries 
    int *arr=new int [n]; // declare heap memory for array 
    int *arri=new int [n]; // declare heap memory for array index 

    for(int i=0;i<n;i++) // initialize array with random number from 0-100 
     { 
      arr[i]=((rand()%100)+0); 
     } 

    for(i=0;i<n;i++) // initialize index position for array 
     { 
      arri[i]=i; 
     } 

    radixsort(arr, n ,arri); 
    return 0; 
} 

// The main function to that sorts arr[] of size n using Radix Sort 
void radixsort(int *arr, int n,int *arri) 
{ int m=99; //getMax(arr,n,arri); 

    // Find the maximum number to know number of digits 


    // Do counting sort for every digit. Note that instead 
    // of passing digit number, exp is passed. exp is 10^i 
    // where i is current digit number 
    for (int exp = 1; m/exp > 0; exp *= 10) 
     countSort(arr, n, exp,arri); 


} 

void countSort(int *arr, int n, int exp,int *arri) 
{ 
    int output[n],output1[n]; // output array 
    int i, count[10] = {0}; 

    // Store count of occurrences in count[] 
    for (i = 0; i < n; i++) 
     { 
      count[ (arr[i]/exp)%10 ]++; 

     } 

    // Change count[i] so that count[i] now contains actual 
    // position of this digit in output[] 
    for (i = 1; i < 10; i++) 
     count[i] += count[i - 1]; 

    // Build the output array 
    for (i = n - 1; i >= 0; i--) 
     { 

      output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
      output1[count[ (arr[i]/exp)%10 ] - 1] = arri[i]; 
      count[ (arr[i]/exp)%10 ]--; 
     } 

    // Copy the output array to arr[], so that arr[] now 
    // contains sorted numbers according to current digit 
    for (i = 0; i < n; i++) 
     { 
      arr[i] = output[i]; 
      arri[i]=output1[i]; 
     } 

} 

Answer 1

문제는 countSort입니다. output 및 output1 배열은 로컬 배열이며 동적으로 할당되지 않으며 로컬 변수에 비해 너무 큽니다. 또한 표준 C++의 일부가 아닌 가변 길이 배열의 C 기능을 사용하고 있습니다. 로 변경 :

int *output = new int[n]; 
int *output1 = new int[n]; 

와 함수의 끝에서

delete[] output; 
delete[] output1; 

를 추가합니다.