rekursive Merge-Sortierung, Segmentierungsfehler für große Arrays

Question

Ich habe die Merge-Sortierung rekursiv implementiert. Es funktioniert bis zu einer bestimmten Größe des sortierten Arrays und stürzt dann mit "segmentation fault" ab. Beim Intel Xeon, 16GB, beträgt die maximale Größe des Float-Arrays 17352, höher für das int-Array, niedriger für das Double-Array. Beim AMD A10, 16GB, liegt das Limit bei Floats bei 2068. Offensichtlich gibt es ein Speicherproblem. Andere Sortieralgorithmen, die ich für Arrays (nicht rekursiv) gemacht habe, funktionieren gut bis zu ~ 2e6. Der Compiler ist GCC 4.4.7. Wie verbessere ich diese Zusammenführung, so dass sie für die größeren Arrays funktioniert?

#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

Die folgende, ganz allein ist, genug, um einen Segmentierungsfehler zu verursachen, wenn N groß genug ist, wegen der notorischen stack overflow. Wenn nicht, sollte das Array gefüllt werden.

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]; 
} 

Der Grund dafür ist, dass lokale Variablen auf dem Stack zugeordnet werden neigen, aber der Stapel in der Größe und nicht für die massiven Speicherzuordnungen begrenzt. Wenn Sie stattdessen

tat

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

oder

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

würden Sie keine Probleme haben, da beide Methoden Speicher auf dem Heap zugewiesen werden.

Answer 2

Betrachten wir die Art und Weise Sie das Array kopiert werden:

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

Wenn dies abgeschlossen ist, temp enthält ihigh - ilow + 1 Werte, die temp[0]-temp[ihigh - ilow] zugänglich sind. Dies bedeutet, dass alle Werte in temp um -ilow gegenüber arr versetzt sind.

jedoch der Rest des Codes temp mit den Indizes der Array Quelle zugreift, zum Beispiel:

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

Daraus ergibt sich die zum Absturz bringen. Wenn Sie den richtigen Offset in temp verwenden, scheint Ihr Code work correctly.