Разрыв производительности между сортировкой списка и вектором структур.C ++

Question

Я написал простой код на C ++ для проверки скорости сортировки данных, представленных в виде списка, а затем вектора.

В случае списка я получаю время в 27 секунд. За вектор я получаю 10 секунд. Почему огромный разрыв в производительности? Разве алгоритмы, используемые для сортировки списка и вектора, не одинаковы? а именно Сортировка слиянием?

РЕДАКТИРОВАТЬ: Я могу ошибаться в последнем пункте. Как я знаю, в учебниках при теоретическом описании алгоритмов сортировки, похоже, используется слово list в смысле std::vector. Я не знаю как чем алгоритмы сортировки векторов будут отличаться от алгоритмов сортировки списков, так что если кто-то сможет уточнить, это будет действительно полезно. Спасибо.

 //In this code we compare the sorting times for lists and vectors.
//Both contain a sequence of structs

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
using namespace std;


struct particle
{
  double x;
  double y;
  double z;
  double w;

    bool operator<(const particle& a) const
    {
        return x < a.x;
    }

};


int main(int argc, char *argv[])
{
  int N=20000000;
  clock_t start,stop;

  vector<particle> myvec(N);
  vector<particle>::iterator cii;
  //Set vector values
  for (cii = myvec.begin(); cii != myvec.end(); ++cii)
  {
    cii->x =1.0*rand()/RAND_MAX;
    cii->y =1.0*rand()/RAND_MAX;
    cii->z =1.0*rand()/RAND_MAX;
    cii->w =1.0*rand()/RAND_MAX;
 }


  list<particle> mylist(N);
  list<particle>::iterator dii;

   //Set list values
  for (cii=myvec.begin(),dii = mylist.begin(); dii != mylist.end() && cii!=myvec.end(); ++dii, ++cii)
  {
      dii->x =cii->x;
      dii->y =cii->y;
          dii->z =cii->z;
      dii->w =cii->w;
 }


  //Sort the vector 

  start=clock();
  sort(myvec.begin(),myvec.end());
  stop=clock();
  cout<<"Time for sorting vector "<<(stop-start)/(double) CLOCKS_PER_SEC<<endl;



  //Sort the list
  start=clock();
  mylist.sort();
  stop=clock();
  cout<<"Time for sorting list "<<(stop-start)/(double) CLOCKS_PER_SEC<<endl;



  return 0;
}

Answer 1

Нет a std::vector не сортируется с использованием сортировки слиянием (в большинстве реализаций; стандарт не определяет алгоритм).

std::list не имеет O (1) произвольного доступа, поэтому он не может использовать алгоритмы, такие как быстрая сортировка *, для которых требуется O (1) произвольный доступ, чтобы быть быстрым (вот почему std::sort не работает на std::list.)

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

И сортировка слиянием обычно медленнее [1] [2] .

См. Также: В чем разница между list.sort и std :: sort?

*: libstdc ++ фактически использует интросорт.
**: libstdc ++ фактически использует вариант сортировки слиянием

Answer 2

Вектор упаковывает вещи в памяти ближе, чем список.Это приводит к более дружественному кэшу шаблону доступа во время сортировки.

Answer 3

Я действительно не программист на C ++, но, насколько я понимаю, std::vector имеет характеристики производительности, отличные от std::list. В частности (как прокомментировал @ Martinho ):

std::vector имеет O (1) произвольный доступ, а std::list - нет.

---

С cplusplus.com (я уверен, что есть менее схематичные ссылки, не стесняйтесь, включите):

Векторы хороши в:

• Доступ к отдельным элементам по их индексу позиции (постоянному времени).
• Перебор элементов в любом порядке (линейное время).
• Добавить и удалить элементы с его конца (постоянное время амортизации).

и

... Преимущества списка контейнеров:

• Эффективная вставка и удаление элементов в любом месте контейнера (постоянное время).
• Эффективные движущиеся элементы и блок элементов внутри контейнера или даже между различными контейнерами (постоянное время).
• Перебор элементов в прямом или обратном порядке (линейное время).

Answer 4

list::sort и std::sort для векторов не используют один и тот же алгоритм.

std::sort использует алгоритм сортировки, который требует итераторов с произвольным доступом, таких как те, которые требуются для std::vector,но не std::list.

list::sort специализируется для списков;он обычно реализует сортировку слиянием, которая не требует произвольного доступа.

Общее количество сравнений составляет O (n log n) для обоих алгоритмов (я говорю, что, не зная точного алгоритма, используемого моим компилятором * 1013)* реализация).Общее число перестановок также равно O (n log n), но для std::sort это означает O (n log n) вызовов для копирования оператора конструктора / присваивания, тогда как для list::sort это операция указателя.Ваша структура слишком мала, чтобы воспользоваться этим преимуществом.Я предполагаю, что как только вы поместите что-то с нетривиальным конструктором копирования в структуру (возможно, достаточно std::string), std::list победит.

РЕДАКТИРОВАТЬ: один элемент std :: string инициализировансо случайным двойным преобразованием в текст, похоже, это точка безубыточности на моем компьютере (x86_64-linux, gcc 4.6.2)

Answer 5

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

Мне было бы любопытно, если бы обмен слайстами <> проходил быстрее, чем список, из-за немного меньших издержек на указатель.