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

#c++ #оптимизация #vector #std_list

На собеседовании спросили: что быстрее, обход вектора или обход списка с выводом
значений в консоль? Каким образом обходим, не уточнили. Я ответил, что разницы нет.
Был ли я прав?
Пояснение: имеется контейнер вектор, по которому мы пробегаемся, например, итератором:

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. После этого вопроса затем спросили: что такое кэш? Возможно, второй вопрос как-то
связан с первым? Если весь вектор или список не попадает в кэш, то время обхода контейнера
увеличится?
    

Ответы

Ответ 1

Вектор несколько быстрее - за счет двух факторов:


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


P.S. Раз уж этот вопрос всплыл заново :) - измерим.

Миллионный список и вектор. Сортировка - чтоб в списке побольше случайных переходов
в разные места памяти было.

list L;
vector 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";
    }

}


Полный код - здесь. Как видим, разница практически в 200 раз в пользу вектора...
Так что "несколько быстрее" - это я преуменьшил :)


Ответ 2

Для вопроса "обход вектора или обход списка с выводом значений в консоль" -  правильный
ответ это "одинаково, т.к. время обхода пренебрежимо мало по сравнению со временем
записи в консоль".

Что касается времени итерации и чтения элементов, то обход списка может быть значительно
медленнее если его элементы расположены в памяти в произвольном порядке. 

Расходы на разыменование указателей на следующие элементы списка незначительны по
сравнению со временем на работу с элементами списка.


Ответ 3

Это коварный многослойный вопрос. Получив его, можно поумничать.


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


В этот момент у собеседующего пропадает желание с сами разговаривать.


Ответ 4

Если глянуть глубже, получится что у вектора все элементы хранятся в непрерывном
участке памяти, и он может поместиться в кэш. При этом сама операция обхода может быть
немного быстрее у вектора, т.к. там просто сдвиг. Но если вам действительно интересно,
проведите тестирование на 10000000 элементах, например.