再帰的マージソート、大きな配列のセグメント化エラー

Question

マージソートを再帰的に実装しました。それはソートされた配列の特定のサイズまで動作し、 "segmentation fault"でクラッシュします。 Intel Xeon（16GB）では、最大浮動小数点配列のサイズは17352で、int配列の方が高く、double配列の方が低くなります。 AMD A10、16GBでは、フロートの制限は2068です。明らかに記憶上の問題があります。配列に対して（再帰的にではなく）行った他のソートアルゴリズムは〜2e6までうまく動作します。コンパイラはGCC 4.4.7です。どのように私は大きな配列のために動作するようにこのマージソートを改善するのですか？

#include <iostream> 
#include <stdlib.h> 
#include <cmath> 
#include <vector> 
using namespace std; 

// -------------------------------------------------------- 
// merge 2 subarrays of 1 array around its middle im 
template <class C> 
void merge(C* arr, int ilow, int imid, int ihigh) 
{ 
vector<C> temp; // array seg faults earlier than vector 
for(int i=ilow; i<=ihigh; i++) temp.push_back(arr[i]); // copy array 

int i1=ilow, i2=imid+1, ai=ilow; // starting positions 

while(i1<=imid && i2<=ihigh) // compare 1st and 2nd halves 
{ 
    if(temp[i1]<=arr[i2]) 
    { 
     arr[ai] = temp[i1]; 
     i1++; // leave smaller val behind 
    } 
    else 
    { 
     arr[ai] = temp[i2]; 
     i2++; // leave smaller val behind 
    } 
    ai++; // move forward 
} 

if(i2>ihigh) while(i1<=imid) // if 2nd is done, copy the rest from 1st 
{ 
    arr[ai] = temp[i1]; 
    i1++; 
    ai++; 
} 

if(i1>imid) while(i2<=ihigh) // if 1st is done, copy the rest from 2nd 
{ 
    arr[ai] = temp[i2]; 
    i2++; 
    ai++; 
} 

} // merge() 



// -------------------------------------------------------- 
// merge sort algorithm for arrays 
template <class C> 
void sort_merge(C* arr, int ilow, int ihigh) 
{ 

if(ilow < ihigh) 
{ 
    int imid = (ilow+ihigh)/2; // get middle point 
    sort_merge(arr, ilow, imid); // do 1st half 
    sort_merge(arr, imid+1, ihigh); // do 2nd half 
    merge(arr, ilow, imid, ihigh); // merge 1st and 2nd halves 
} 

return; 
} // sort_merge() 



/////////////////////////////////////////////////////////// 
int main(int argc, char *argv[]) 
{ 
// crashes at 17353 on Intel Xeon, and at 2069 on AMD A10, both 16Gb of ram 
const int N=17352+0; 
float arr[N]; // with arr[double] crashes sooner, with arr[int] crashes later 

// fill array 
for(long int i=0; i<N; i++) 
{ 
    //arr[i] = rand()*1.0/RAND_MAX; // random 
    arr[i] = sin(i*10)+cos(i*10); // partially sorted 
    //arr[i] = i; // sorted 
    //arr[i] = -i; // reversed 
} 

sort_merge(arr, 0, N-1); 

return 0; 
} 

Answer 1

すべて自身によって、以下では、Nが原因悪名高いstack overflowに、十分に大きい場合、セグメンテーションフォールトを引き起こすのに十分です。もしそうでなければ、配列を満たす必要があります。

int main(int argc, char *argv[]) 
{ 
    // crashes at 17353 on Intel Xeon, and at 2069 on AMD A10, both 16Gb of ram 
    const int N=17352+0; 
    float arr[N]; 
} 

理由は、傾向ローカル変数がスタックに割り当てられるが、スタックのサイズが制限されており、大量のメモリの割り当てのために設計されていないということです。あなたの代わりに

float *arr = new arr[N]; // probably should be unique_ptr instead.... 

または

std::vector<float> arr(N); 

をした場合、これらのメソッドの両方がヒープ上にメモリを割り当てるので、あなたは、何の問題を持っていないでしょう。これが完了するとtempがtemp[0]からtemp[ihigh - ilow]にアクセス可能なihigh - ilow + 1値が含まれ、

vector<C> temp; // array seg faults earlier than vector 
for(int i=ilow; i<=ihigh; i++) temp.push_back(arr[i]); // copy array 

：

Answer 2

あなたは、配列をコピーする方法を考えてみましょう。つまり、tempのすべての値は、arrと比較して-ilowでオフセットされています。コードの残りの部分は、例えば、ソースアレイのインデックスを有するtempにアクセスしかし

：

if(temp[i1]<=arr[i2]) // i1 isn't a valid index into temp, should be (i1 - ilow) 

したがってクラッシュ。 tempに適切なオフセットを使用すると、work correctlyのように見えます。