Seltsame Segmentierungsfehler

Question

Ich programmiere einen einfachen Heap-Algorithmus. Es muss mit großen Datenmengen arbeiten, die Größe ist 100.000 und die Zahlen im Bereich von 0 bis 10^9.

Der Algorithmus funktioniert für die Größe irgendwo um 25.000. Wenn der Datensatz jedoch größer wird, werden Segmentierungsfehler ausgelöst.

Ich habe unsigned lange lange int verwendet, so sehe ich nicht, wo das Problem ist. Ich verwende Vektoren, um meine Daten zu speichern, und alle Daten sind von langen Int-Typen.

Hat jemand schon einmal solche Probleme gehabt?

Hier ist die heapify Prozedur Ich verwende:

vector<unsigned long long> array; 
vector<unsigned long long> orig_index; 
vector<unsigned long long> new_index; 

unsigned long long heapify (unsigned long long count) { 

unsigned long long temp, left, right, min; 
long long j; 
unsigned long long n_swaps = 0; 


for(long long i=(count%2 ? (count-2)/2 : (count-1)/2); i>=0; --i) { 
    left= (2*i)+1 ; 
    right= (2*i)+2 ; 



    j= i; 
    while(((array[j] > array[left]) && left<count) || ((array[j] > array[right]) && (right<count))){ 

     //Swap 

     //Find lesser of left or right 
     if(right>= count) { 
      min= array[left]; 
     } else { 
      min= array[left] > array[right] ? array[right] : array[left]; 
     } 

      if(array[j] > array[left] && (min== array[left])) { 
      temp= array[j]; 
      array[j]= array[left] ; 
      array[left]= temp; 

      //Update indexes 
      orig_index.push_back(j); 
      new_index.push_back(left); 

      j= left; 
      right= (2*left)+2 ; 
      left= (2*left)+1 ; 
      ++n_swaps; 
     } 
     else if ((right < count) && (array[j] > array[right])) { 
      temp= array[j]; 
      array[j]= array[right] ; 
      array[right]= temp; 

      //Update indexes 
      orig_index.push_back(j); 
      new_index.push_back(right); 

      j= right; 
      left= (2*right)+1 ; 
      right= (2*right)+2 ; 
      ++n_swaps; 
     } 

    } 
} 
return n_swaps; 
} 

Hier ist die Zufallsdaten Generator-Funktion Ich verwende. Anzahl ist die Größe der Daten hier (wie 20k oder 30k) und max ist der Bereich.

void generate(unsigned long long count, unsigned long long max) { 
srand(time(NULL)); 
//Dummy array of max size 
vector<unsigned long long> dummy; 

//Populate the dummy 
for(unsigned long long i=0; i<max; ++i) { 
    dummy.push_back(i); 
} 

//Select random number from dummy, swap with last and pop 
unsigned long long temp; 
unsigned long long swap; 
unsigned long long dummy_size= max-1; 

cout<<"****************Indices************"<<endl; 
for(unsigned long long i=0; i<count; ++i) { 
    temp= rand() % dummy_size ; 
    cout<<temp<<endl; 
    array.push_back(dummy[temp]); 

    //Swap and pop 
    swap= dummy[temp]; 
    dummy[temp] = dummy[dummy_size]; 
    dummy[dummy_size] = swap; 
    --dummy_size; 
} 
cout<<"*************End*****************"<<endl; 
dummy.clear(); 
} 

Die Hauptfunktion

int main(void) { 

unsigned long long count= 25000; 
unsigned long long max= 1000000 ; 

//Generate random numbers and push on array 
generate(count, max); 

//Print array 
for(unsigned long long i=0; i<array.size(); ++i) { 
    cout<<array[i]<<" "; 
} 
cout<<endl; 

//Build heap 
unsigned long long n_swaps = heapify(count); 

cout<<n_swaps<<"\n"; 
for(unsigned long long i=0; i<orig_index.size(); ++i) { 
    cout<<orig_index[i]<<" "<<new_index[i]<<endl; 
} 
return 0; 
} 

Ich hoffe, dass die Algorithmen korrekt sind, aber kann nicht finden, nur, warum Segmentierungsfehler ist für große Datenmengen geschieht, und nicht klein.

Answer 1

Die & & wird von links nach rechts ausgewertet (als Schreibreihenfolge), also habe ich eine Zeile geändert und dies kein "Absturz", (Segmentierungsfehler).

while((left<count && (array[j] > array[left])) || ((right<count) && (array[j] > array[right]))){ 

komplette Code:

while(((array[j] > array[left]) && left<count) || ((array[j] > array[right]) && (right<count))){ 

ersetzt durch?

using namespace std; 

vector<unsigned long long> array; 
vector<unsigned long long> orig_index; 
vector<unsigned long long> new_index; 

unsigned long long heapify(unsigned long long count) { 
    unsigned long long temp, left, right, min; 
    long long j; 
    unsigned long long n_swaps = 0; 

    for (long long i = (count % 2 ? (count - 2)/2 : (count - 1)/2); i >= 0; 
     --i) { 
    left = (2 * i) + 1; 
    right = (2 * i) + 2; 

    j = i; 
    while ((left < count && (array[j] > array[left])) || 
      ((right < count) && (array[j] > array[right]))) { 
     // Swap 

     // Find lesser of left or right 
     if (right >= count) { 
     min = array[left]; 
     } else { 
     min = array[left] > array[right] ? array[right] : array[left]; 
     } 

     if (array[j] > array[left] && (min == array[left])) { 
     temp = array[j]; 
     array[j] = array[left]; 
     array[left] = temp; 

     // Update indexes 
     orig_index.push_back(j); 
     new_index.push_back(left); 

     j = left; 
     right = (2 * left) + 2; 
     left = (2 * left) + 1; 
     ++n_swaps; 
     } else if ((right < count) && (array[j] > array[right])) { 
     temp = array[j]; 
     array[j] = array[right]; 
     array[right] = temp; 

     // Update indexes 
     orig_index.push_back(j); 
     new_index.push_back(right); 

     j = right; 
     left = (2 * right) + 1; 
     right = (2 * right) + 2; 
     ++n_swaps; 
     } 
    } 
    } 
    return n_swaps; 
} 

void generate(unsigned long long count, unsigned long long max) { 
    srand(time(NULL)); 
    // Dummy array of max size 
    vector<unsigned long long> dummy; 

    // Populate the dummy 
    for (unsigned long long i = 0; i < max; ++i) { 
    dummy.push_back(i); 
    } 

    // Select random number from dummy, swap with last and pop 
    unsigned long long temp; 
    unsigned long long swap; 
    unsigned long long dummy_size = max - 1; 

    cout << "****************Indices************" << endl; 
    for (unsigned long long i = 0; i < count; ++i) { 
    temp = rand() % dummy_size; 
    cout << temp << endl; 
    array.push_back(dummy[temp]); 

    // Swap and pop 
    swap = dummy[temp]; 
    dummy[temp] = dummy[dummy_size]; 
    dummy[dummy_size] = swap; 
    --dummy_size; 
    } 
    cout << "*************End*****************" << endl; 
    dummy.clear(); 
} 

int main(void) { 
    unsigned long long count = 25000; 
    unsigned long long max = 1000000; 

    // Generate random numbers and push on array 
    generate(count, max); 

    // Print array 
    for (unsigned long long i = 0; i < array.size(); ++i) { 
    cout << array[i] << " "; 
    } 
    cout << endl; 

    // Build heap 
    unsigned long long n_swaps = heapify(count); 

    cout << n_swaps << "\n"; 
    for (unsigned long long i = 0; i < orig_index.size(); ++i) { 
    cout << orig_index[i] << " " << new_index[i] << endl; 
    } 
    return 0; 
}