如何在C中声明和使用10亿个整数的庞大数组?
我正在实现一个顺序程序,用于像quicksort一样进行排序。 我想用大量的1或10亿个整数来测试我的程序的性能。 但问题是由于数组的大小,我得到了分段错误。
此数组声明的示例代码:
#include #include #include #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函数的命题。 但我不知道如何使用它? 任何人都可以帮我使用它吗?
我正在研究Ubuntu 10.04 64位,gcc 4.4.3版。
谢谢你的回复。
迈克尔是对的,你不能在堆栈上适应那么多。 但是,如果您不想使用malloc,则可以将其设置为全局(或静态)。
#include #include #include #define N 1000000000 int list[N]; int main(int argc, char **argv) { int i; srand(time(NULL)); for(i=0; i
您必须使用malloc
进行此类分配。 堆栈上的那么多几乎每次都会失败。
int *list; list = malloc(N * sizeof(int));
这会将分配放在堆上有更多可用内存的地方。
你可能不会创建如此大的数组,如果你这样做,你当然不会在堆栈上创建它; 堆栈不是那么大。
如果你有一个32位的地址空间和一个4字节的int
,那么你就不能创建一个拥有十亿个int
的数组; 对于那个大的对象,在内存中就没有足够的连续空间(对于对象来说可能没有足够的连续空间,只有那个大小的一小部分)。 如果你有一个64位的地址空间,你可能会分配那么多的空间。
如果你真的想尝试,你需要静态地创建它(即,在文件范围内声明数组或在函数中使用static
限定符)或动态地(使用malloc
)。
在linux系统上,非常大的块的malloc
只是在mmap
做一个mmap
,所以调查它可能太繁琐了。
请注意,对于数组边界和索引,既没有溢出(有符号整数)也没有静默换行(无符号整数)。 使用size_t
作为一种类型,因为你在64位机器上,这应该工作。
但是作为一种习惯,你应该明确地检查你对SIZE_MAX
的界限,比如assert(N*sizeof(data[0]) <= SIZE_MAX)
。
堆栈分配使其中断。 N = 1Gig ints => 4Gig内存(均带有32位和64位编译器)。 但是如果你想测量快速排序的性能,或者你的类似算法,那么这不是解决问题的方法。 尝试在大尺寸的样品上依次使用多个快速排序。
-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 ( eg 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
现在,您可以非常精确地回答算法消耗的时间。 运行几次以感受“精确度”(每次使用新的种子(种子)种子)。 并更改N以进行更多检查。
另一种选择是动态分配较小数组的链表。 你必须使用访问器函数来包装它们,但是你可以获得16 256 MB的内存块而不是单个4 GB的块。
typedef struct node_s node, *node_ptr; struct node_s { int data[N/NUM_NODES]; node_ptr next; };