सिगकिल

Question

द्वारा मारे गए प्रक्रिया में मेरे पास एक प्रक्रिया है जो प्रोग्राम को निष्पादित करने के तुरंत बाद मार दी जाती है। यह संकलित निष्पादन योग्य का कोड है, और यह एक छोटा प्रोग्राम है जो मानक इनपुट (आमतौर पर एक वर्णनात्मक फ़ाइल) से संख्याओं द्वारा प्रतिनिधित्व किए गए कई ग्राफ पढ़ता है और प्राइम के एल्गोरिदम का उपयोग करके प्रत्येक ग्राफ के लिए न्यूनतम स्पैनिंग पेड़ पाता है (यह दिखाता नहीं है परिणाम अभी तक, यह समाधान ढूंढ गया है)।

#include <stdlib.h> 
#include <iostream> 

using namespace std; 

const int MAX_NODOS = 20000; 
const int infinito = 10000; 

int nnodos; 
int nAristas; 
int G[MAX_NODOS][MAX_NODOS]; 
int solucion[MAX_NODOS][MAX_NODOS]; 
int menorCoste[MAX_NODOS]; 
int masCercano[MAX_NODOS]; 



void leeGrafo(){ 
    if (nnodos<0 || nnodos>MAX_NODOS) { 
     cerr << "Numero de nodos (" << nnodos << ") no valido\n"; 
     exit(0); 
    } 
    for (int i=0; i<nnodos ; i++) 
     for (int j=0; j<nnodos ; j++) 
      G[i][j] = infinito; 
    int A,B,P; 
    for(int i=0;i<nAristas;i++){ 
     cin >> A >> B >> P; 
     G[A][B] = P; 
     G[B][A] = P; 
    } 
} 


void prepararEstructuras(){ 
    // Grafo de salida 
    for(int i=0;i<nnodos;i++) 
     for(int j=0;j<nnodos;j++) 
      solucion[i][j] = infinito; 
    // el mas cercaano 
    for(int i=1;i<nnodos;i++){ 
     masCercano[i]=0; 
     // menor coste 
     menorCoste[i]=G[0][i]; 
    }   
} 

void prim(){ 
    prepararEstructuras(); 
    int min,k; 
    for(int i=1;i<nnodos;i++){ 
     min = menorCoste[1]; 
     k = 1; 
     for(int j=2;i<nnodos;j++){ 
      if(menorCoste[j] < min){ 
       min = menorCoste[j]; 
       k = j; 
      } 
     } 
     solucion[k][masCercano[k]] = G[k][masCercano[k]]; 
     menorCoste[k] = infinito; 
     for(int j=1;j<nnodos;j++){ 
      if(G[k][j] < menorCoste[j] && menorCoste[j]!=infinito){ 
       menorCoste[j] = G[k][j]; 
       masCercano[j] = k; 
      }  
     }   
    } 
} 

void output(){ 
    for(int i=0;i<nnodos;i++){ 
     for(int j=0;j<nnodos;j++) 
      cout << G[i][j] << ' '; 
     cout << endl; 
    } 
} 

int main(){ 
    while(true){ 
     cin >> nnodos; 
     cin >> nAristas; 
     if((nnodos==0)&&(nAristas==0)) break; 
     else{ 
      leeGrafo(); 
      output(); 
      prim(); 
     } 
    } 
} 

मैं सीख लिया है कि मैं क्या चल रहा है खोजने के लिए strace का उपयोग करना चाहिए, और यह मैं क्या मिलता है:

execve("./412", ["./412"], [/* 38 vars */] <unfinished ...> 
+++ killed by SIGKILL +++ 
Killed 

मैं ubuntu runing कर रहा हूँ और यह पहली बार मैं इस प्रकार मिलता है त्रुटियों का कार्यक्रम इनपुट से एक पंक्ति में दो शून्य पढ़ने के बाद बंद होना चाहिए, मैं गारंटी दे सकता हूं कि मेरे ग्राफ में वर्णनात्मक फ़ाइल है। इसके अलावा समस्या तब भी होती है जब मैं अपने ग्राफ फ़ाइल में इनपुट पुनर्निर्देशन किए बिना प्रोग्राम निष्पादित करता हूं।

Answer 1

हालांकि मैं 100% यकीन नहीं है कि यह समस्या है हूँ, अपने वैश्विक सरणियों के आकार पर एक नज़र डालें:

const int MAX_NODOS = 20000; 

int G[MAX_NODOS][MAX_NODOS]; 
int solucion[MAX_NODOS][MAX_NODOS]; 

मान लिया जाये कि int 4 बाइट है, तो आप की आवश्यकता होगी:

20000 * 20000 * 4 bytes * 2 = ~3.2 GB 

एक के लिए, आपके पास यह भी स्मृति नहीं हो सकती है। दूसरा, यदि आप 32-बिट पर हैं, तो संभवतः ओएस एक एकल प्रक्रिया को उस स्मृति को अनुमति देने की अनुमति नहीं देगा।

मान लें कि आप 64-बिट पर हैं (और मानते हैं कि आपके पास पर्याप्त स्मृति है), समाधान रन-टाइम पर इसे आवंटित करना होगा।

Answer 2

आपके सरणी G और solucion प्रत्येक में 400,000,000 पूर्णांक होते हैं, जो अधिकांश मशीनों पर लगभग 1.6 जीबीबी होते हैं। जब तक आपके पास पर्याप्त (वर्चुअल) मेमोरी नहीं है (3.2 जीबीबी और गिनती), और इसका उपयोग करने की अनुमति (ulimit -d आज़माएं; यह मैकोज़ एक्स 10.7.2 पर bash के लिए सही है), आपकी प्रक्रिया शुरू होने में विफल रहेगी और सिगकिल द्वारा मार डाला जाएगा (जो फंस नहीं जा सकता है, यह नहीं कि प्रक्रिया वास्तव में अभी तक जा रही है)।