C dilinde 1 milyar tamsayı büyük aralıklarla nasıl bildirilir ve kullanılır?

Question

Quicksort gibi sıralamak için sıralı bir program uyguluyorum. Programımın performansını büyük bir 1 veya 10 milyar tam sayı aralığında test etmek istiyorum. Ancak sorun, dizinin boyutundan dolayı bölümleme hatası almamdır. Bu dizinin beyanının

Bir örnek kod:

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

Ben mmap işlevini kullanmak için bir önerim var. Ama nasıl kullanacağımı bilmiyorum? Kullanmama yardım eden var mı?

Ubuntu 10.04 64-bit, gcc sürüm 4.4.3 üzerinde çalışıyorum.

Yanıtlarınız için teşekkür ederiz.

Answer 1

Michael haklı, bu kadar yığını sığamaz. Ancak, malloc yapmak istemiyorsanız global (veya statik) yapabilirsiniz.

#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

Bu tür bir ayırma için malloc kullanmalısınız. Yığındaki o kadar çok şey neredeyse her zaman başarısız olur.

int *list; 

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

Bu, ayırmayı çok daha fazla belleğin bulunduğu yığına koyar.

Answer 3

Muhtemelen çok büyük bir dizi oluşturmuyorsunuz ve eğer yaparsanız kesinlikle onu yığın üzerinde oluşturmuyorsunuz; yığın sadece o kadar büyük değil.

32 bitlik bir adres alanınız ve 4 baytlık bir int varsa, bir milyar int s olan bir dizi oluşturamazsınız; o büyük bir nesne için bellekte yeterli bitişik alan olmayacak (muhtemelen o nesnenin bir kısmı için yeterli bitişik alan olmayacaktır). 64 bit adres alanınız varsa, o kadar alan ayırmaktan kurtulabilirsiniz.

Gerçekten denemek istiyorsanız, bunu statik olarak oluşturmak (yani, diziyi dosya kapsamındaki veya static niteleyici ile işlevde bildirmek) veya dinamik olarak (malloc kullanarak) oluşturmanız gerekir.

Answer 4

Başka bir seçenek, daha küçük dizilerin bağlantılı bir listesini dinamik olarak ayırmaktır. Onları accessor işlevleriyle sarmanız gerekecek, ancak 16 GB'lık bir bellek parçasını tek bir 4 GB'lık parçadan daha fazla yakalayabiliyorsunuz. Linux sistemleri çok büyük boyutta malloc günü

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

Answer 5

sadece kaputun altında bir mmap yapar, bu yüzden belki de sıkıcı olduğunu içine bakmaktır.

Eğer dizi sınırları ve endeksleri için ne taşma (imzalı tamsayı) ne de sessiz wrap (işaretsiz tamsayılar) yok dikkatli olun. Bunun için bir tür olarak size_t kullanın, 64bit makinede olduğunuzdan, bu işe yaramalıdır. Ancak bir alışkanlık olarak, emin olmak için assert(N*sizeof(data[0]) <= SIZE_MAX) gibi SIZE_MAX'a karşı sınırlarınızı kesin olarak kontrol etmelisiniz.

Answer 6

Yığın ayırma işlemleri onu parçalara ayırır. N = 1Gig ints => 4Gig bellek (her ikisi de 32-bit ve 64-bit bir derleyici ile).Ama , quicksort'un performansını veya benzer bir algoritmasını ölçmek istiyorsanız, bununla ilgili bir yol yoktur. Bunun yerine, büyük boyutta hazırlanmış örneklerde birden fazla hızlı sıralamayı kullanmayı deneyin.

-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 

Şimdi, algoritmanızın ne kadar süre tükettiğine dair çok kesin bir yanıtınız var. "Ne kadar hassas" bir his elde etmek için birkaç kez çalıştırın (her seferinde yeni bir tane (tohum) tohumu kullanın). Ve daha fazla inceleme için N değiştirin.