Bubblesort в списке - слишком много времени тратится на вычисления

Question

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

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

void Sorting::bubblesort(std::list<int>::iterator start, std::list<int>::iterator stop)
{
    int k = 0;
    int temp;
    std::list<int>::iterator j_1 ;
    for (auto i = start; i != stop; i++)
    {
        for (auto j = std::next(start, 1); j != std::prev(stop, k); j++)
        {
            j_1= std::prev(j, 1);
            if (*j_1 > *j)
            {
                temp = *j_1;
                *j_1 = *j;
                *j = temp;
            }
        }
        k++;
    }
}

Проверено на 1000 элементах - 9 032 с (измерено с помощью std :: chrono)

Answer 1

сделать

void bubblesort(std::list<int>::iterator start, std::list<int>::iterator stop)
{
    std::list<int>::iterator k = stop;
    int temp;
    std::list<int>::iterator j_1 ;
    for (auto i = start; i != stop; i++)
    {
        for (auto j = std::next(start, 1); j != k; j++)
        {
            j_1= std::prev(j, 1);
            if (*j_1 > *j)
            {
                temp = *j_1;
                *j_1 = *j;
                *j = temp;
            }
        }
        k--;
    }
}

для непрерывного пересчета std::prev(stop, k) все время, ваша программа делает почти только то, что

Конечно, список также не самая лучшая коллекция для хранения int и сортировки их

---

Полный пример:

#include <list>
#include <iostream>
#include <chrono>
#include <ctime>

void bubblesort(std::list<int>::iterator start, std::list<int>::iterator stop)
{
#ifdef YOU
    int k = 0;
#else
    std::list<int>::iterator k = stop;
#endif
    int temp;
    std::list<int>::iterator j_1 ;
    for (auto i = start; i != stop; i++)
    {
        for (auto j = std::next(start, 1);
#ifdef YOU
             j != std::prev(stop, k);
#else
             j != k;
#endif
             j++)
        {
            j_1= std::prev(j, 1);
            if (*j_1 > *j)
            {
                temp = *j_1;
                *j_1 = *j;
                *j = temp;
            }
        }
#ifdef YOU
        k++;
#else
        k--;
#endif
    }
}

int main()
{
  std::list<int> l;

  for (int i = 0; i != 1000; ++i)
    l.push_front(i);

#ifdef DEBUG
  for (auto i : l)
    std::cout << i << ' ';
  std::cout << std::endl;
#endif


  std::chrono::time_point<std::chrono::system_clock> start, end;  

  start = std::chrono::system_clock::now();
  bubblesort(l.begin(), l.end());
  end = std::chrono::system_clock::now();
  std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() / 1000.0
    << " sec" << std::endl;

#ifdef DEBUG
  for (auto i : l)
    std::cout << i << ' ';
  std::cout << std::endl;
#endif
}

Компиляция и исполнение:

pi@raspberrypi:/tmp $ g++  b.cc
pi@raspberrypi:/tmp $ ./a.out
0.183 sec
pi@raspberrypi:/tmp $ g++ -DYOU b.cc
pi@raspberrypi:/tmp $ ./a.out
3.98 sec
pi@raspberrypi:/tmp $ 
pi@raspberrypi:/tmp $ g++ -O3 b.cc
pi@raspberrypi:/tmp $ ./a.out
0.004 sec
pi@raspberrypi:/tmp $ g++ -O3 -DYOU b.cc
pi@raspberrypi:/tmp $ ./a.out
0.413 sec

Обратите внимание также на преимущество компиляции в O3 ...

Answer 2

Это скорее дополнение к ответу Бруно, лучше попытаться разорвать реализацию сортировки отдельно от реальных типов, например

template <class InIt>
void bubblesort(InIt start, InIt stop)
{
    InIt k = stop, j_1;
    for (auto i = start; i != stop; ++i)
    {
        for (auto j = std::next(start, 1); j != k; ++j)
        {
            j_1 = std::prev(j, 1);
            if (*j_1 > *j)
            {
                /*auto temp = *j;
                *j = *j_1;
                *j_1 = temp;*/
                std::swap(*j,*j_1); 
                // - no real performance difference on GCC with -O2.
            }
        }
        --k;
    }
}