Which is faster: vector traversal or list traversal?
At the interview, they asked: which is faster, traversing a vector or traversing a list with values output to the console? How we bypass it, we did not specify. I replied that there was no difference. Was I right? Explanation: there is a container vector that we run through, for example, with an iterator:
std::vector<int> vector{1, 2, 3};
for (auto it = vector.begin(); it != vector.end(); ++it)
{
qDebug() << *it;
}
There is a list container, which we also run through with an iterator:
std::list<int> values{1, 2, 3};
for (auto it = values.begin(); it != values.end(); ++it)
{
qDebug() << *it;
}
Which of the loops will run faster and why? Which of the cycles will run faster under the other ones ways to bypass these containers? These cycles were not present at the interview, I added them for clarity.
P.S. After this question, then asked: what is a cache? Perhaps the second question has something to do with the first? If the entire vector or list does not get into the cache, will the container crawl time increase?
4 answers
The vector is slightly faster - due to two factors:
There are no pointer transitions, no extra dereferencing
There are no pointer transitions in it - everything lies in one heap, which means that it has a high degree of locality, so there is a high probability that all the contents of the vector will be placed in the processor cache (and if not all because of a very large vector, then in large chunks), i.e. with a significantly higher speed than in the general case in the a list where items can be scattered throughout the memory...
P.S. Since this question has surfaced again :) - we'll measure it.
Millionth list and vector. Sorting - so that there are more random transitions to different memory locations in the list.
list<int> L;
vector<int> V;
int main(int argc, const char * argv[])
{
for(int i = 0; i < 1000000; ++i)
{
int r = rand();
V.push_back(r);
L.push_back(r);
}
L.sort();
sort(V.begin(),V.end());
{
muTimer mu;
long long int sum = 0;
for(int i: V) sum += i;
mu.stop();
cout << "Sum " << sum << " for " << mu.duration() << " mks\n";
}
{
muTimer mu;
long long int sum = 0;
for(int i: L) sum += i;
mu.stop();
cout << "Sum " << sum << " for " << mu.duration() << " mks\n";
}
}
The full code is here. As you can see, the difference is almost 200 times in favor of the vector... So "somewhat faster" is an understatement. :)
For the question "traversing a vector or traversing a list with output values to the console" - the correct answer is "the same, because the traversal time is negligible compared to the time of writing to the console".
As for the iteration and reading time of the elements, the traversal of the list can be significantly slower if its elements are located in memory in an arbitrary order.
The cost of dereferencing pointers to the following list items is negligible compared to the time spent working with list items.
This is an insidious multi-layered question. After receiving it, you can get smart.
From the point of view of mathematics, the speed is asymptotically equal to: O(N). The difference in both cases is determined by the coefficient before N, which depends on the speed of specific operations: dereferencing, reading, output, and so on. The constant can be ignored, but in general it is also there.
From the point of view of accessing elements with hardware in mind, the vector will be faster, because the processor cache optimized for accessing sequential blocks of memory, rather than potentially scattered small elements across the entire memory.
From a practical point of view, accessing the console is a disproportionately slow operation relative to all others, so the speed will be determined by it. Accordingly, the difference between the vector and the list will be negligible.
As a special show-off, we tell you about the possibility of using custom allocators in STL collections, which makes the reasoning about speed invalid, since we can use a device for storing data that does not give an advantage to sequential access. For example, we map memory to a file with a file system without a cache...
At this point, the interviewee loses the desire to talk to sami.
If you look deeper, it turns out that the vector has all the elements stored in a continuous section of memory, and it can fit in the cache. At the same time, the traversal operation itself may be slightly faster for the vector, because there is just a shift. But if you're really interested, do some testing on 10000000 elements, for example.