不思議なセグメンテーションフォールト

Question

私は単純なheapifyアルゴリズムをプログラミングしています。大きなデータサイズで動作する必要があります。サイズは100,000、数字は0〜10^9です。

このアルゴリズムは、およそ25,000のサイズで動作します。しかし、データセットがそれよりも大きくなると、セグメンテーション違反がスローされます。

私はunsigned long long intを全面的に使用しています。だから、どこに問題があるのか​​分かりません。私はベクトルを使用してデータを格納していますが、すべてのデータは長いlong int型です。

誰もこのような問題に遭遇しましたか？ここで

は、私が使用しているheapify手順である：ここでは

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

は、私が使用しているランダムデータジェネレータ関数です。 Countはここのデータのサイズ（20kや30kなど）で、maxは範囲です。

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

私はアルゴリズムが正しい願っていますが、ちょうどカントは小さなものセグメンテーションフォールトがビッグデータ・セットのために何が起こっている理由を見つけ、そしてません。

Answer 1

& &は、左から右（書込み順序）で評価されるので、私は行を変更し、これは「クラッシュ」しません（セグメンテーションフォルト）。

に置き換え

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

：

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

完全なコード：

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