13

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

std::vector<int> vector{1, 2, 3};
for (auto it = vector.begin(); it != vector.end(); ++it)
{
    qDebug() << *it;
}

имеется контейнер список, по которому мы также пробегаемся итератором:

std::list<int> values{1, 2, 3};
for (auto it = values.begin(); it != values.end(); ++it)
{
    qDebug() << *it;
}

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

P.S. После этого вопроса затем спросили: что такое кэш? Возможно, второй вопрос как-то связан с первым? Если весь вектор или список не попадает в кэш, то время обхода контейнера увеличится?

4 ответа 4

18

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

  1. в нем нет переходов по указателям, нет лишних разыменований

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

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

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

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";
    }

}

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

4
  • спасибо за прояснение! 26 июл 2017 в 16:34
  • Так подправьте ответ, заменив несколько на пару порядков (заранее плюсую)
    – avp
    20 янв 2019 в 9:56
  • @avp Не могу :) - потому что я ее получал не то чтобы искусственно, но... Например, при малых размерах разница будет не столь существенной. Или если убрать сортировку (которая просто перемешивает местоположения элементов в списке) - то разница сразу падает до примерно в 30 раз. Так что оставим неопределенное "несколько" :)
    – Harry
    20 янв 2019 в 10:05
  • @Harry, сортировка вектора вытесняет из кеша элементы списка и сама прогревает кеш в пользу вектора. В результате вектор тестируется на кешированной памяти. Список тестируется на не кешированной памяти. Это объясняет колебания в производительности. Корректнее прогревать кеши повторяя суммирование несколько раз, но время измерять только в последний. 20 дек 2021 в 14:26
11

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

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

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

6

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

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

  2. С точки зрения доступа к элементам с учётом аппаратуры быстрее будет вектор, потому что кэш процессора оптимизирован для доступа к последовательным блокам памяти, а не потенциально разбросанным по всей памяти небольшим элементам.

  3. С практической точки зрения доступ к консоли — несоразмеримо медленная операция относительно всех остальных, поэтому скорость будет определяться ей. Соответственно, разница между вектором и списком будет пренебрежимо мала.

  4. В качестве особенного выпендрёжа рассказываем про возможность использования кастомных аллокаторов у коллекций STL, что делает рассуждения о скорости невалидными, так как мы можем для хранения данных использовать устройство, которое не даёт преимущества последовательному доступу. Скажем, делаем маппинг памяти на файл с файловой системой без кэша...

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

0
3

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

1
  • спасибо, что прояснили. да, попробую потестировать 26 июл 2017 в 16:35

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.