多重房地产是否比巨大的马里奥更贵？

Question

我使用动态数组来表示最小堆。有一个循环可以移除最小值，并将随机元素添加到最小堆中，直到出现某种情况。虽然我不知道在运行时堆的长度会如何变化(有很大的随机性)，但我知道上限，即1000万。我有两个选择：

1)使用malloc声明一个小数组，然后当堆中的元素数超过该长度时调用realloc。

2)使用malloc声明1,000万条目数组。这避免了调用realloc。

问题

备选方案2是否比备选案文1更有效？

我用我的代码对此进行了测试，从使用2开始，运行时减少了20%，这是因为代码中的随机性。在前面声明一个带有malloc的大型10-5千万条目数组有什么缺点吗？

Answer 1

如果你能腾出内存来做大的预先分配，并且它提供了一个有价值的性能提升，那么一定要这么做。

如果您坚持使用realloc，那么您可能会发现，每次增加一倍的大小而不是增加固定的数量，可以在性能和有效的内存使用之间进行很好的权衡。

Answer 2

并不是说当您使用realloc时，内存将从相同的place.It中扩展，也可能会发生内存在另一个区域中被替换的情况。

因此，使用realloc可能会导致复制以前的内存恰克( chuck )。

另外，考虑到系统调用可能需要一些开销，所以最好只调用malloc一次。

Answer 3

缺点是，如果您没有使用所有的空间，您将占用大量的内存，这可能是必要的。如果您确切地知道您需要多少字节，那么由于系统调用开销，一次分配将更有效，然后将其一片片地分配。通常，您可能有一个上限，但不知道确切的数字。花时间打开空间来处理上界可能需要1秒。但是，如果这个特定的情况只有上界的一半，那么可能需要.75秒一段一段地分配。因此，这取决于你认为你会得到多近的上限。