列表中的冒泡排序 - 花费在计算上的时间太长

Question

我已经创建了一个负责在列表上执行bubblesort的代码。它似乎工作，但需要一点时间来执行。如果有人告诉我它有什么问题我会很高兴，所以我可以避免将来犯同样的错误

认为它可能是与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)，你的程序几乎只做了那件事

当然，列表也不是存储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;
    }
}