सी में 1 अरब पूर्णांक के विशाल सरणी घोषित करने और उपयोग करने के लिए कैसे?

Question

मैं quicksort जैसे सॉर्टिंग के लिए एक अनुक्रमिक प्रोग्राम लागू कर रहा हूँ। मैं अपने कार्यक्रम के प्रदर्शन को 1 या 10 अरब पूर्णांक में एक विशाल सरणी में परीक्षण करना चाहता हूं। लेकिन समस्या यह है कि मुझे सरणी के आकार के कारण सेगमेंटेशन त्रुटि प्राप्त होती है।

इस सरणी की घोषणा का एक नमूना कोड:

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define N 1000000000 

int main(int argc, char **argv) 
{ 
    int list[N], i; 
    srand(time(NULL)); 
    for(i=0; i<N; i++) 
    list[i] = rand()%1000; 
    return 0; 
} 

मैं एक प्रस्ताव mmap समारोह का उपयोग करने के मिला है। लेकिन मुझे नहीं पता कि इसका उपयोग कैसे किया जाए? क्या कोई इसे इस्तेमाल करने में मेरी सहायता कर सकता है?

मैं उबंटू 10.04 64-बिट, जीसीसी संस्करण 4.4.3 पर काम कर रहा हूं।

आपके उत्तरों के लिए धन्यवाद।

Answer 1

माइकल सही है, आप ढेर पर इतना फिट नहीं कर सकते हैं। हालांकि, यदि आप इसे मॉलोक नहीं करना चाहते हैं तो आप इसे वैश्विक (या स्थैतिक) बना सकते हैं।

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define N 1000000000 
int list[N]; 

int main(int argc, char **argv) 
{ 
    int i; 
    srand(time(NULL)); 
    for(i=0; i<N; i++) 
    list[i] = rand()%1000; 
    return 0; 
} 

Answer 2

आपको इस तरह के आवंटन के लिए मॉलोक का उपयोग करना होगा। ढेर पर इतना हर समय असफल हो जाएगा।

int *list; 

list = (int *) malloc(N * sizeof(int)); 

यह ढेर पर आवंटन रखता है जहां बहुत अधिक स्मृति उपलब्ध है।

Answer 3

शायद आप इतनी बड़ी सरणी नहीं बनाते हैं और यदि आप करते हैं तो आप निश्चित रूप से इसे ढेर पर नहीं बनाते हैं; ढेर बस इतना बड़ा नहीं है।

आप एक 32-बिट पता स्थान और एक 4-बाइट int है, तो आप नहीं एक अरब int के साथ एक सरणी बना सकते हैं; उस बड़े ऑब्जेक्ट के लिए मेमोरी में बस पर्याप्त संगत स्थान नहीं होगा (संभवत: किसी ऑब्जेक्ट के उस आकार के अंश के लिए पर्याप्त संगत स्थान नहीं होगा)। यदि आपके पास 64-बिट पता स्थान है, तो आप उस स्थान को आवंटित करने से दूर हो सकते हैं।

यदि आप वास्तव में कोशिश करना चाहते हैं, तो आपको इसे स्थिर रूप से बनाने की आवश्यकता होगी (यानी, फ़ाइल स्कोप पर सरणी घोषित करें या static फ़ंक्शन में क्वालीफायर के साथ) या गतिशील रूप से (malloc का उपयोग करके)।

Answer 4

एक और विकल्प गतिशील रूप से छोटे सरणी की एक लिंक की गई सूची आवंटित करना है। आपको उन्हें एक्सेसर फ़ंक्शंस के साथ लपेटना होगा, लेकिन यह एक और 4 जीबी खंड की तुलना में स्मृति के 16 256 एमबी भाग को पकड़ सकता है।

typedef struct node_s node, *node_ptr; 
struct node_s 
{ 
    int data[N/NUM_NODES]; 
    node_ptr next; 
}; 

Answer 5

Linux सिस्टम बहुत बड़े हिस्से की malloc पर सिर्फ एक mmap हुड के नीचे होता है, तो यह शायद बहुत कठिन है कि इस पर गौर करने के लिए है।

ध्यान रहे कि आप न अतिप्रवाह (हस्ताक्षरित पूर्णांक) और न ही अपने सरणी सीमा और सूचकांक के लिए चुप रैप (अहस्ताक्षरित पूर्णांकों) की जरूरत नहीं है रहो। उस के लिए size_t का उपयोग करें, क्योंकि आप 64 बिट मशीन पर हैं, फिर यह काम करना चाहिए।

लेकिन एक आदत के रूप में आपको के खिलाफ निश्चित रूप से assert(N*sizeof(data[0]) <= SIZE_MAX) के विरुद्ध अपनी सीमाओं की जांच करनी चाहिए, सुनिश्चित करने के लिए।

Answer 6

स्टैक आवंटन इसे तोड़ देता है। एन = 1 गीग इनट्स => 4 मेग ऑफ मेमोरी (दोनों 32-बिट और 64-बिट कंपाइलर के साथ)।लेकिन यदि आप क्विकॉर्ट, या आपके समान एल्गोरिदम के प्रदर्शन को मापना चाहते हैं, तो यह इसके बारे में जाने का तरीका नहीं है। बड़े आकार के साथ तैयार नमूने पर अनुक्रम में एकाधिक Quicksorts का उपयोग करने के बजाय प्रयास करें।

-create a large random sample not more than half your available memory. 
make sure it doesn''t fill your ram! 
If it does all measuring efforts are in vain. 
500 M elements is more than enough on a 4 gig system. 

-decide on a test size (e.g. N = 100 000 elements) 
-start timer 
--- do the algoritm for (*start @ i*N, *end @ (i+1)*N) 
(rinse repeat for next i until the large random sample is depleted) 
-end timer 

अब आपके पास बहुत सटीक उत्तर है कि आपके एल्गोरिदम ने कितना समय व्यतीत किया है। "कितना सटीक" महसूस करने के लिए इसे कुछ बार चलाएं (प्रत्येक बार एक नया srand (बीज) बीज का उपयोग करें)। और अधिक निरीक्षण के लिए एन बदलें।