Làm thế nào để khai báo và sử dụng mảng lớn 1 tỷ số nguyên trong C?

Question

Tôi đang triển khai một chương trình tuần tự để sắp xếp như quicksort. Tôi muốn kiểm tra hiệu suất của chương trình của tôi trong một mảng lớn của 1 hoặc 10 tỷ số nguyên. Nhưng vấn đề là tôi nhận được lỗi phân đoạn do kích thước của mảng.

Một mã mẫu tờ khai của mảng này:

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

Tôi có một đề xuất để sử dụng chức năng mmap. Nhưng tôi không biết cách sử dụng nó? ai cũng có thể giúp tôi sử dụng nó?

Tôi đang làm việc trên Ubuntu 10.04 64-bit, gcc phiên bản 4.4.3.

Cảm ơn câu trả lời của bạn.

Answer 1

Michael nói đúng, bạn không thể phù hợp với nhiều thứ trong ngăn xếp. Tuy nhiên, bạn có thể làm cho nó toàn cầu (hoặc tĩnh) nếu bạn không muốn malloc nó.

#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

Bạn phải sử dụng malloc cho loại phân bổ này. Điều đó nhiều trên stack sẽ thất bại gần như mọi thời gian.

int *list; 

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

Điều này đặt phân bổ trên vùng lưu trữ có nhiều bộ nhớ hơn.

Answer 3

Bạn có thể không tạo ra một mảng quá lớn và nếu bạn chắc chắn bạn không tạo nó trên ngăn xếp; ngăn xếp không phải là lớn.

Nếu bạn có không gian địa chỉ 32 bit và 4 byte int, thì bạn không thể tạo mảng có tỷ lệ int s; sẽ không có đủ không gian liền kề trong bộ nhớ cho một đối tượng lớn (có lẽ sẽ không có đủ không gian tiếp giáp đối với một đối tượng có kích thước nhỏ như vậy). Nếu bạn có một không gian địa chỉ 64-bit, bạn có thể lấy đi với phân bổ nhiều không gian đó.

Nếu bạn thực sự muốn thử, bạn sẽ cần phải tạo nó tĩnh (tức là, khai báo mảng tại phạm vi tệp hoặc với vòng loại static trong hàm) hoặc động (sử dụng malloc).

Answer 4

Tùy chọn khác là phân bổ động danh sách liên kết các mảng nhỏ hơn. Bạn sẽ phải bọc chúng với chức năng truy cập, nhưng nó có nhiều khả năng là bạn có thể lấy 16 256 MB khối bộ nhớ hơn một đoạn 4 GB duy nhất.

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

Answer 5

Trên các hệ thống Linux malloc của khối rất lớn chỉ làm một mmap dưới mui xe, vì vậy nó có lẽ là quá tẻ nhạt để nhìn vào đó.

Hãy cẩn thận rằng bạn không có tràn (số nguyên đã ký) hoặc quấn im lặng (số nguyên không dấu) cho giới hạn mảng và chỉ mục của bạn. Sử dụng size_t làm loại cho điều đó, vì bạn đang sử dụng máy 64 bit, điều này sẽ hoạt động.

Nhưng như một thói quen, bạn nên kiểm tra dứt khoát các giới hạn của mình theo số SIZE_MAX, chẳng hạn như assert(N*sizeof(data[0]) <= SIZE_MAX), để chắc chắn.

Answer 6

Phân bổ ngăn xếp làm cho nó bị hỏng. N = 1Gig ints => 4Gig bộ nhớ (cả với trình biên dịch 32 bit và 64 bit).Nhưng nếu bạn muốn đo hiệu suất của quicksort, hoặc một thuật toán tương tự của bạn, đây không phải là cách để đi về nó. Thay vào đó hãy thử sử dụng nhiều quicksorts theo thứ tự trên các mẫu đã chuẩn bị có kích thước lớn.

-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 

Bây giờ bạn có câu trả lời rất chính xác về thời gian thuật toán của bạn đã tiêu thụ. Chạy nó một vài lần để có được một cảm giác "chính xác như thế nào" (sử dụng một hạt giống srand (hạt giống) mới mỗi lần). Và thay đổi N để kiểm tra thêm.