使用realloc动态数组大小与初始大小C

我是C语言新手（来自java），想知道在我的情况下什么是更好的方法。我正在编程一个游戏，并且在生成动作的函数中，我想返回一些指向结构数组的指针（Move由结构体表示）。因为我事先不知道数组的大小，我想从一个空数组开始，而不是每次我想添加一个移动（通过realloc（size + 1））来调整它的大小。但我想知道，如果设置一个初始尺寸，并且如果我需要，只是将尺寸增加一倍，是否更为理想。性能更好的方法是什么？使用realloc动态数组大小与初始大小C

谢谢！

来源

2013-08-23 user2030118

显然是双倍大小的。 –

倍增效率更高，那是什么'矢量'我认为 –

即使将一些腰部空间？ – user2030118

多次调用realloc将是低效的。因此添加一个内存大小是一个坏主意。将尺寸加倍，当您完成并获得想要存储数据的精确尺寸时，您可以将realloc缩小至该尺寸。这应该照顾浪费的内存。但realloc只有在最后时，你认为你不需要增加了。

根据具体情况和您的实现，如果您认为当分配的内存总量变大时加倍会有点太多，您可以添加检查以增量增加内存。类似于

if (memory_allocated < 100) 
    //realloc to double size 
else 
    //realloc 10 more

上面的数字是任意的，您可以选择更好的数字。但如果将内存加倍是一个巨大的问题，请使用此选项。否则加倍并重新分配到精确是一个足够好的解决方案。

来源

2013-08-23 06:11:11

我会更进一步：不要使用'realloc（）'来缩小数组！无论如何，该内存将需要使用。 – 2013-08-23 06:14:04

@ H2CO3这将取决于实施。我不知道存储的内容是否只是暂时的。假设他缩小了添加的数据，那么在之前的迭代中，加倍的内存可能会成为内存消耗。完成后缩小可以处理内存占用。但是这显然取决于具体的实施。 –

哼，因为'malloc'和'realloc'使用分页，它真的很重要吗？ – DCMaxxx

你可以翻一番。但是如果你关心时间和浪费的空间，你需要知道移动次数的分布。也就是说，有多少时间出现1次移动，2次移动等等。然后，一种方法可能会更清晰。例如，当移动次数为< = 100时加倍，但为大于100时加上20.

最初，将代码写入游戏中，跟踪这些统计数据并相应调整您的方法。

来源

2013-08-23 06:15:06 JackCColeman

-1

没有比赛。每次需要分配更多内存时，请选择任意大小并加倍。该函数调用realloc()为您需要添加的每个结构都会导致您的程序变慢。

realloc()也是昂贵的。每次你调用它时，你都会在堆上使用一块新的内存。 realloc()在成功分配新内存时释放最初分配的块;但是，这会导致堆碎片，并且即使存在大量可用内存，仍有可能无法分配连续内存。

最后，每次调用realloc()时，都会冒内存分配失败的风险。为什么不尽可能少地将风险降至最低？

来源

2013-08-23 06:16:48 verbose

downvoter照顾解释？ – verbose

除了使用realloc来提高分配性能使数组大小加倍外，我还会问你是否真的需要每个Move项的O（1）访问时间。如果没有，你也可以使用一个列表，而不是像：记住

typedef struct Move Move; 
struct Move { 
    /* your stuff here */ 
    Move *next; 
};

有了这个，你可以一个新的移动项目每次创建一个新的时间添加到列表头部或尾部。但是，在这里，您最终需要O（n）个访问时间来随机访问移动项目。

来源

2013-08-23 06:20:35 anselm

但即便如此，您仍可以创建一个“缓存阵列”来存储每个元素的地址。但是，您必须确保每次链接列表更改时更新此缓存。此外，结合2个概念是可行的：建立一个数组链表。如果数据以块的方式添加，现在我可以添加10个条目，然后添加40条，那么添加一个由'next'指针，'count'值或者'大小“值（如果内存块的大小很重要）和一些元素。 – glglgl

是的，我也想过这个解决方案（链表）。我也考虑它 – user2030118

链接列表大部分时间比可调整大小的数组显着更慢，因为引用的位置很差。只有在需要频繁插入中间或前端时才使用链接列表。 –

假设你有一个n个元素的数组，现在它已满。每次您拨打realloc()时，每个元素都将被移至新的空间。

的realloc（大小+ 1）：

的移动总和1+2+...+n = O(n^2)

（即使它开始作为k+k+1...+n，它原来是为O（n^2），其中k是原始空间，你的malloc）

的realloc（尺寸* 2），即使原来的空间只有一个：

的移动之和为n*(1/2+1/4+...+1/(2^logn))，（2^LOGN = N）和金额的上限为2n，那就是说，O(n)。

很明显，当总元素的数量很少时，它们几乎是相同的。但是如果n很大，那么双重效率更高。顺便说一句，当数组满了时，数组的大小加倍，是很多动态数组的一个流行工具。

来源

2013-08-23 06:34:38 vvy

使用realloc动态数组大小与初始大小C

回答

相关问题