1

我是 C 语言的新手（来自 java），想知道在我的情况下什么是更好的方法。我正在编写一个游戏，在生成移动的函数中，我想返回一些指向结构数组的指针（移动由结构表示）。

因为我事先不知道数组大小是多少，所以我考虑从一个空数组开始，而不是在每次我想添加移动时调整它的大小（通过 realloc(size+1)）。但我想知道只设置初始大小是否更优化，如果需要，只需将大小加倍。什么是更好的方法性能 wize？

谢谢！

4

6 回答 6

2

realloc多次调用将是低效的。所以增加一个内存大小是个坏主意。将大小加倍，当你完成并获得存储数据所需的确切大小时，你可以realloc缩小到该大小。那应该处理浪费的内存。但realloc只有在你认为不再需要增加时才会下降。

根据特定情况和您的实现，如果您认为在分配的总内存变大时加倍有点过多，您可以添加检查以增量添加内存。就像是

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

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

于 2013-08-23T06:11:11.253 回答
2

除了将数组大小加倍realloc以提高分配性能外，我还想问您是否真的需要 O(1) 访问每个 Move 项的时间。如果不是，您也可以使用列表，例如：

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

考虑到这一点，您可以在每次创建新项目时将新的移动项目添加到列表的头部或尾部。但是在这里，您最终会得到 O(n) 访问时间来随机访问 Move 项目。

于 2013-08-23T06:20:35.697 回答
1

你可以加倍。但是如果您担心时间和浪费空间，您需要知道移动次数的分布。也就是说，有多少百分比的时间有 1 个动作，2 个动作等。然后一个方法可能更清楚。比如步数 <= 100 时加倍，大于 100 时加 20。

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

于 2013-08-23T06:15:06.913 回答
1

假设您有一个包含 n 个元素的数组，现在它已满。每次调用realloc()时，每个元素都会被移动到一个新的空间。

重新分配（大小+1）：

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

（即使它以 开头k+k+1...+n，结果也是 O(n^2)，其中 k 是你 malloc 的原始空间）

realloc(size*2) 即使原始空间只有一个：

移动的总和是n*(1/2+1/4+...+1/(2^logn)),(2^logn = n) 并且总和的上限是 2n，也就是说，O(n)。

很明显，当总元素的数量很少时，它们几乎相同。但是如果 n 很大，则双倍更有效。

顺便说一句，当数组已满时，大小翻倍，是许多动态数组的流行实现。

于 2013-08-23T06:34:38.277 回答
0

增加常数会导致每次插入的成本为 O(n)，因此插入 n 个元素的时间复杂度为 O(n²)。

当您将分配增加一个常数因子时，插入单个元素的摊销成本为 O(1)，这意味着插入 n 个元素的成本为 O(n)。您不需要每次都加倍，仅分配 25 % 或 20 % 或最多仅多15 %将过度分配 15 %，并且您仍将获得 O(1) 每次插入的摊销成本。假设为 15%，O(1) 将具有更高的常数因子，但平均而言，现在过度分配比每次缓冲区已满时 100% 增量要少得多。

于 2018-12-28T20:14:04.477 回答
-1

No contest. Choose an arbitrary size and double it each time you need to allocate more memory. The function calls to realloc() for every single struct you need to add would cause your program to be slow.

realloc() is also expensive. Every time you call it, you're going to use a new block of memory on the heap. realloc() does free the originally allocated block when the new memory is successfully allocated; however, this leads to heap fragmentation and you run the risk of running out of contiguous memory to allocate even though there's plenty of free memory.

Finally, every time you call realloc(), you run the risk of the memory allocation failing. Why not minimize the risk by calling it as few times as possible?

于 2013-08-23T06:16:48.617 回答