我们可以通过将可用节点的集合保存在自己的结构中来避免对存储分配器的多次调用。
这个思想可以应用于二叉搜索树数据结构。
作者说：“一次分配所有节点可以大大减少树的空间需求，从而减少大约三分之一的运行时间。 ”
我很好奇这个技巧如何减少空间需求。我的意思是如果我们要构建一个有四个节点的二叉搜索树，我们需要为这四个节点分配内存，无论我们是一个一个分配节点还是一次性分配所有节点。
问问题
232 次
2 回答
2
众所周知，内存分配器不擅长分配非常小的对象。在过去十年中，情况有所改善，但书中的技巧仍然适用。
大多数分配器在分配给您的块中保留附加信息，以便它们可以正确释放内存。例如C的/对或mallocC ++的/对需要将实际内存块的长度信息保存在某处；通常，这些数据在返回给您的地址之前的四个字节中结束。freenew[]delete[]
这意味着每次分配至少会浪费四个额外的字节。如果您的树节点占用 12 个字节（两个指针各占 4 个字节，数字占 4 个字节），则将为每个节点分配 16 个字节 - 增加 33.3%。
内存分配器还需要执行额外的簿记。每次从堆中取出一个块时，分配器都必须考虑它。
最后，你的树使用的内存越多，在处理当前节点时，相邻节点在缓存中被获取的机会就越小，因为内存中到下一个节点的距离。
于 2012-08-17T04:51:05.283 回答
1
这与 Java 如何处理字符串有关。而当你连接到一个字符串时，你实际上是在使用 3 个字符串对象：旧字符串、新段和新结果。最终垃圾收集器清理干净，但在这种情况下（我的字符串示例和您的程序二进制搜索） - 您正在以一种浪费的方式增加内存空间。至少我是这么理解的。
于 2012-08-17T04:37:52.160 回答