Страницы

Поиск по вопросам

суббота, 6 октября 2018 г.

Что быстрее: обход вектора или обход списка?

На собеседовании спросили: что быстрее, обход вектора или обход списка с выводом значений в консоль? Каким образом обходим, не уточнили. Я ответил, что разницы нет. Был ли я прав? Пояснение: имеется контейнер вектор, по которому мы пробегаемся, например, итератором:
std::vector vector{1, 2, 3}; for (auto it = vector.begin(); it != vector.end(); ++it) { qDebug() << *it; }
имеется контейнер список, по которому мы также пробегаемся итератором:
std::list values{1, 2, 3}; for (auto it = values.begin(); it != values.end(); ++it) { qDebug() << *it; }
Какой из циклов будет работать быстрее и почему? Какой из циклов будет работать быстрее при других способах обхода этих контейнеров? Этих циклов не было на собеседовании, я их добавил для наглядности.
P.S. После этого вопроса затем спросили: что такое кэш? Возможно, второй вопрос как-то связан с первым? Если весь вектор или список не попадает в кэш, то время обхода контейнера увеличится?


Ответ

Вектор несколько быстрее - за счет двух факторов:
в нем нет переходов по указателям, нет лишних разыменований в нем нет переходов по указателям - все лежит одной кучей, а значит, с высокой степенью локальности, так что высока вероятность, что все содержимое вектора разместится в кеше процессора (а если и не все из-за очень большого вектора - то большими кусками), т.е. с существенно более высокой скоростью, чем в общем случае в списке, где элементы могут быть разбросаны по всей памяти...

Комментариев нет:

Отправить комментарий