std :: vector и std :: list find_if и max_element performance

Question

Я смущен о выполнении моего кода, протестированного на std::vector и std::list. Есть ли разница между этими двумя, когда дело доходит до find_if и max_element?

Answer 1

В терминах обозначения большой О, обе имеют одинаковые характеристики O (n). (find_if может быть меньше, если элемент обнаружен раньше, но это одинаково верно для обоих контейнеров.)

С точки зрения фактического времени настенных часов вектор будет работать лучше из-за когерентности кеша; все векторные элементы являются последовательными в памяти, поэтому доступ к ним будет лучше использовать кэш ЦП. Элементы связанного списка могут быть разбросаны по всей памяти, и вам также необходимо следить за ссылками на список, которые требуют времени.

Answer 2

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

Как всегда, когда дело доходит до производительности, делайте измерения перед принятием решений.

Answer 3

Для max_element пройдут все элементы как списка, так и массива. Таким образом, оба являются O (n) с точки зрения производительности.

Опять же для find_if обход будет линейным (O (n)) для обеих структур данных.

Я не думаю, что разница между константами по отношению к каждой из них не должна быть большой.