C：阵列中的Realloc（再次） [英] C: Realloc in Array (again)

问题描述

您好，

目的是为FindXXXXX和SetCurrentDirectory辅助的RemoveDirectory提供旧式Windows目录漫步的准备。



有问题的变量数组叫做folderTreeArray跟踪这个。



数组的第一个向量表示树级别，第二个文件夹表示文件夹（可能不是全部） ）在该级别找到，第三个是char文件夹名称数组。

Hi there,
The aim is to prepare for an old fashioned Windows directory walk with view to RemoveDirectory aided by FindXXXXfile and SetCurrentDirectory.

The variable array in question is called folderTreeArray keeps track of this.

The first vector of the array represents the tree level, the second the folders (possibly not all) found in that level, the third the char folder name array.

wchar_t *(folderTreeArray)[1000][MAX_PATH - 3];
Globals: BOOL topofTree and int treeLevel

名为RecurseRemovePath（currPathW，folderTreeArray）的递归函数概述如下：



if（topofTree = = TRUE）

{

treeLevel - = 1

下一层并删除刚访问过的目录（folderTreeArray中的第n个目录）。将其设置为{0}并转到下一个目录

}

else

{

treeLevel + = 1;

在oldTreeArray中填充一个新的树级别，即将第一个数组重新分配一个。

}



问题在于realloc的处理。我们只喜欢修复第三个向量。

类似

The recursive function called RecurseRemovePath (currPathW, folderTreeArray) is outlined as follows:

if (topofTree == TRUE)
{
treeLevel -=1
Go down one level and delete directory just visited (the nth directory in folderTreeArray). Set it to {0} and move on to the next directory
}
else
{
treeLevel +=1;
Populate a new tree level in olderTreeArray, i.e realloc the first array by one.
}

Problem is in the treatment of realloc. We only prefer the third vector fixed.
Something like

wchar_t *(temp)[1000][MAX_PATH - 3]= realloc((folderTreeArray)[1000][MAX_PATH - 3], treeLevel * sizeof (wchar_t));

不起作用。 [1000]也看起来效率低下。有什么建议吗？

谢谢

doesn't work. The [1000] also looks inefficient. Any suggestions?
Thanks

推荐答案

你可能需要开发一个支持数组列表语义的更复杂的数据结构。比如，你有太多的元素来证明使用带有单独元素的链表（每个元素中有一个或两个指针）是合理的，并且元素寻址的速度是元素插入成本的关键因素，很少或从未发生过。这是一种非常常见的情况。然后你可以开发一种已知的混合模型。例如，您可以拥有一个元素的链接列表，每个元素代表一个相当大的数组块。在您的数组结构中，您还需要支持两种不同的长度：已分配和实际使用。一般情况下，您的最后一块木板仅部分使用。您可以为您的结构创建一些接受自定义块大小的初始化，根据使用标准，您可以根据实际对象进行更改。



比如，在典型的使用中，你可能有链表元素的数量不超过30-100个元素，这对你的索引算法来说不是一个很大的负担：你将具有O（N）的时间复杂度到达所需的块，但在chuck内部将是直接指针计算，时间复杂度为O（1）。当您的数据增长时，您只需添加另一个链表元素并将数据放入完全填充的最后一个块元素中，然后放入新的块元素中。总的来说，可以在不断增长的数据大小的灵活性和元素寻址的性能之间给予一些合理的权衡。



这只是可能的解决方案之一。我想给你一些混合数据结构的想法。在所有情况下，我都会避免 realloc 。问题不仅在于它的性能，还在于它的代码在你的应用程序外部，因此后果很难预测;它包括不可预测的性能和不可预测的进程内存碎片级别。当你使用固定大小的块时，运行时系统更有可能避免内存大量的内存碎片。



堆优化的问题是一个单独的大问题，但这里只是一些思考的食物：许多软件开发技术基于一些带有内部子分配器的运行时库来管理内存。也就是说，实现不直接通过OS API分配/ deallocaton函数分配堆，而是在更大的块中进行分配，将更小的对象分配给该子分配器。

-SA

It's possible that you just need to develop a more complicated data structure supporting semantic of an "array list". Say, you have too many elements to justify the use of a linked list with a separate element (with one or two pointers in each one), and the speed of addressing of an element is more critical factor then the cost of element insertion, which rarely or never happens. This is a very usual situation. Then you can develop one of the know hybrid model. For example, you can have a linked list of element each representing a fairly big chunk of your array. In your array structure, you will also need to support two different lengths: allocated and actually used. In general case, your last chunk sill be only partially used. You can create some initialization for your structure which accept custom chunk size, which you can vary in actual object depending on the usage criteria.

Say, in typical use, you may have the number of linked list elements not exceeding, say, 30-100 elements, which is not a big burden the your algorithm of the indexing: you will have the time complexity of O(N) for reaching required chunk, but inside chuck it will be direct pointer calculation, with time complexity of O(1). When your data grows, you just add another linked list element and put data in fully filled last chunk element, and then in new chunk element. Overall, can will give you some reasonable trade off between flexibility of the growing size of data and performance of element addressing.

This is only one of possible solution. I wanted to give you just the idea of some hybrid data structure. In all cases, I would avoid realloc. The problem is not just it's performance, but the fact that its code is external to your application, so the consequence are hard to predict; it includes unpredictable performance and unpredictable level of process memory fragmentation. When you go with fixed-size chunks, it's much more likely that runtime system will avoid memory considerable memory fragmentation.

The problem of heap optimization is a separate big problem, but here is just some food for thought: a number of software development technologies manage memory based on some runtime library with internal sub-allocator. That is, the implementation does not allocate heap directly through the OS API allocation/deallocaton function, but do it in larger chunks, leaving allocation to smaller objects to that sub-allocator.

—SA

这篇关于C：阵列中的Realloc（再次）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！