列表上的冒泡排序——在计算上花费了太多时间

Question

我创建了一个代码，负责对列表进行冒泡排序。它似乎有效，但需要大量时间来执行。如果有人能告诉我其中有什么问题，我会很高兴，这样我以后就可以避免犯同样的错误

以为可能是auto相关的东西，重写代码也没用。

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)，你的程序几乎只做那个

当然 list 也不是存储 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

这更像是布鲁诺回答的附录，最好尝试将 sort 的实现与实际类型分开，例如

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

列表上的冒泡排序——在计算上花费了太多时间

Bubblesort on List - too much time spent on computing

c++

c++11

bubble-sort

stdlist