performance of array vs. map

Question

I have to loop over a subset of elements in a large array where each element point to another one (problem coming from the detection of connected component in a large graph).

My algo is going as follows: 1. consider 1st element 2. consider next element as the one pointed by the previous element. 3. loop until no new element is discover 4. consider next element not already consider in 1-3, get back to 1. Note that the number of elements to consider is much smaller than the total number of elements.

For what I see now, I can either:

//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

or

//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

I know that accessing keys in map is O(log N) while it's only constant for arrays, but I don't know if malloc is not more costly at the creation while it also requires more memory?

Answer 1

When in doubt, measure the performance of both alternatives. That's the only way to know for sure which approach will be fastest for your application.

That said, a one-time large malloc is generally not terribly expensive. Also, although the map is O(log N), the big-O conceals a relatively large constant factor, at least for the std::map implementation, in my experience. I would not be surprised to find that the array approach is faster in this case, but again the only way to know for sure is to measure.

Keep in mind too that although the map does not have a large up-front memory allocation, it has many small allocations over the lifetime of the object (every time you insert a new element, you get another allocation, and every time you remove an element, you get another free). If you have very many of these, that can fragment your heap, which may negatively impact performance depending on what else your application might be doing at the same time.