2

我必须遍历一个大数组中的元素子集，其中每个元素指向另一个元素（问题来自于大图中连接组件的检测）。

我的算法如下： 1. 考虑第一个元素 2. 将下一个元素视为前一个元素指向的元素。3. 循环直到没有发现新元素 4. 考虑下一个元素在 1-3 中尚未考虑，回到 1。注意要考虑的元素数量远小于元素的总数。

对于我现在所看到的，我可以：

//create a map of all element, init all values to 0, set to 1 when consider
map<int,int> is_set; // is_set.size() will be equal to N

或者

//create a (too) large array (total size), init to 0 the elements to consider
int* is_set = (int*)malloc(total_size * sizeof(int)); // is_set length will be total_size>>N

我知道访问 map 中的键是 O(log N)，而它只是数组的常量，但我不知道 malloc 在创建时是否成本更高，同时它还需要更多内存？

4

3 回答 3

9

如有疑问，请衡量两种备选方案的性能。 这是确定哪种方法对您的应用程序最快的唯一方法。

也就是说，一次性的大型 malloc 通常不会非常昂贵。此外，虽然地图是 O(log N)，但根据我的经验，大 O 隐藏了一个相对较大的常数因子，至少对于std::map实现而言。我不会惊讶地发现在这种情况下数组方法更快，但再次确定的唯一方法是测量。

还要记住，虽然映射没有大量的前期内存分配，但它在对象的生命周期内有许多小的分配（每次插入新元素时，都会获得另一个分配，每次删除一个元素，你会得到另一个免费的）。如果你有很多这样的东西，那可能会使你的堆碎片化，这可能会对性能产生负面影响，具体取决于你的应用程序可能同时在做什么。

于 2012-05-03T16:46:53.777 回答
3

如果索引搜索满足您的需求（例如由常规 C 样式数组提供），则可能std::map不适合您。相反，std::vector如果您需要动态运行时分配，或者std::array如果您的集合是固定大小的，并且您只需要最快的边界安全替代 C 样式指针，请考虑使用。

您可以在上一篇文章中找到更多信息。

于 2012-05-03T17:07:19.627 回答
1

我知道访问 map 中的键是 O(log N)，而它只是数组的常量，但我不知道 malloc 在创建时是否成本更高，同时它还需要更多内存？

地图中的每个条目都是动态分配的，因此如果动态分配是一个问题，那么地图中的问题将是一个更大的问题。至于数据结构，您可以使用位图而不是普通的 int 数组。这将在具有 32bitint的架构中将数组的大小减少 32 倍，在大多数情况下，将索引映射到数组的额外成本将远小于额外内存的成本，因为结构更紧凑并且可以容纳更少的缓存行。

还有其他需要考虑的事情，例如集合中元素的密度是否很小。如果条目很少（即图形稀疏），那么任何一个选项都可以。作为最后一个选项，您可以通过使用向量来手动实现映射pair<int,int>并缩短它们，然后使用二进制搜索。这将减少分配的数量，在排序中产生一些额外的成本，并提供比地图更紧凑的 O(log N) 解决方案。不过，我会尝试使用位掩码。

于 2012-05-03T16:47:37.750 回答