4
  • 地点
    • 在堆中，碎片化（每个节点的 malloc） - 在几种不同的方面效率低下（缓慢分配，缓慢访问，内存碎片）
    • 在堆中，在一大块中 - 当需要重新分配时，数据结构获得的所有灵活性都会丢失
    • 在堆栈中 - 堆栈的大小往往相当有限，因此根本不建议在其上分配大型结构

它们的最大优势，插入 O(1)，在碎片化内存和数千次调用内存分配器以给我们另外 10 个字节的环境中似乎相当无用。

编辑澄清：
这个问题是在一次采访中被问到的。这不是一个工作场所问题，因此希望从一小组标准算法中盲目地做出正确决定的通常启发式方法是不适用的。

现有的答案和评论提到“malloc 并没有那么慢”，“malloc 部分对抗碎片”。好的，如果我们使用另一种数据结构，例如 C++ 向量的 C 端口（即 - 分配足够大小的顺序内存，如果数据扩展，则重新分配到两倍大的块）所有问题都解决了，但我们失去了快速插入/删除。链表（分配在哪里？）比向量具有巨大优势的任何场景？

4

5 回答 5

7

这听起来像是过早的优化。我认为正确的做法是：

  1. 尽可能使用最简单的实现；
  2. 剖析整个程序。
  3. 如果分析显示列表存在性能问题，请考虑替代实现（包括替代分配器）。
于 2013-04-30T05:59:01.603 回答
4

如果您担心标准分配器不能有效地处理您专门的 10 字节分配，请编写一个自定义分配器，它从标准 ( malloc()) 分配器中获取大量内存并有效地分配小项目。当您在初始大块中耗尽内存时，您不应该重新分配；你应该分配一个新的（额外的）大块并从中分配。您可以决定如何处理释放的内存。您可以简单地忽略发布，直到您在列表处理结束时释放所有大块。或者，您可以通过跟踪大块中释放的内存来使生活复杂化。这总体上减少了内存使用量，但最初编写起来更复杂。

另一方面，您应该意识到过早优化的风险。您是否测量过性能影响？鉴于我对您最近的问题的了解，您可能应该坚持使用malloc()而不是尝试编写自己的分配器（还）。

于 2013-04-30T06:01:37.433 回答
0

这可能不是确切的解决方案，而是另一种方法

  • 自行处理碎片。
    • 分配大内存池
    • 为每个新节点提供来自该节点的内存，直到有空闲内存。
    • 如果使用池，则分配另一个池并使用它来分配新块

然而，这说起来容易做起来难。这样做可能会遇到很多问题。

所以，会建议让这种优化到malloc和相关的功能。

从堆栈分配不是一个可行的选择。你不能malloc从堆栈中。您将不得不在某些函数中预先分配大块缓冲区。在这种情况下，数组比链表好。

于 2013-04-30T06:07:06.307 回答
0

理想情况下，您的链表实现不应使用上述任何一种。应该由调用者分配和销毁内存。想想像 , 等等这样的函数sprintf......fgets它们是否分配了任何内存？不，这是有原因的：简单。想象一下，如果你必须free得到你所得到的一切fgets（或者更糟的是，fscanf）。那不会很痛苦吗？尝试开发您的函数以与标准库保持一致。

声明一个函数可能会有所帮助listnode_alloc，但这只会包装malloc一个listnode_init函数。考虑如何realloc处理NULL输入...

于 2013-04-30T06:07:12.367 回答
0

好吧，内存分配策略可能会因内存碎片、数千个系统调用等而有所不同，这正是使用 O 的原因！;-)

于 2013-04-30T06:36:22.163 回答