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 回答