阵列与地图的表现

Question

我必须循环遍历大型数组中的元素子集,其中每个元素指向另一个元素(来自大图中连接组件的检测的问题).

我的算法如下: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

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

Answer 1

如有疑问,请衡量两种替代品的性能. 这是确定哪种方法对您的应用程序来说最快的唯一方法.

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

请记住,尽管地图没有大量的前期内存分配,但它在对象的生命周期内有许多小的分配(每次插入新元素时,都会得到另一个分配,并且每次删除元素,你得到另一个免费).如果你有很多这些,那么可能会破坏你的堆,这可能会对性能产生负面影响,具体取决于你的应用程序可能在同一时间做什么.