快速排序实现

Question

为了学习的目的，我编写了一个快速排序算法的实现。

为了使算法更快，我对算法做了一些修改，即：

• 设置到中间分区边界的两个枢轴(<，=，>)，以避免其他两个变量计算相同的元素
• 分区方法首先检查更少(左分区)或更大(右分区)元素是否存在，如果这两个元素都存在，而不是移动两次枢轴，它只是交换它们；如果不是正常的行为。

我对其进行了基准测试，并将其性能与std::sort进行了比较；当有超过10000000的元素时，使用随机元素的算法要比STD的算法要快，否则，使用更少的元素std：：排序比使用更少的元素std：：排序要快几毫秒(实际基准测试结果见下文)

#include <algorithm>

template<class iterator>
void quickSort(iterator begin, iterator end)
{
    if (end - begin > 1)
    {
        auto lpivot = begin + (end - begin) / 2;
        auto rpivot = lpivot;

        auto pValue = *lpivot;

        auto left_it = lpivot - 1;
        auto right_it = rpivot + 1;

        auto lValue = *left_it;
        auto rValue = *right_it;

        bool isGreater = false;
        bool isLess = false;

        while (left_it != begin-1 || right_it != end)
        {
            if (lValue >= pValue)
            {
                if (lValue == pValue)
                {
                    lpivot--;
                    std::iter_swap(lpivot, left_it);
                }
                else
                    isGreater = true;
            }

            if (rValue <= pValue)
            {
                if (rValue == pValue)
                {
                    rpivot++;
                    std::iter_swap(rpivot, right_it);
                }
                else
                    isLess = true;
            }
            if (isGreater && isLess)
            {
                std::iter_swap(left_it, right_it);
            }
            else if (isGreater)
            {
                if (left_it != lpivot - 1)
                    std::iter_swap(left_it, lpivot - 1);
                std::iter_swap(rpivot - 1, lpivot - 1);
                std::iter_swap(rpivot, rpivot - 1);
                lpivot--;
                rpivot--;
            }
            else if (isLess)
            {
                if (right_it != rpivot + 1)
                    std::iter_swap(right_it, rpivot + 1);
                std::iter_swap(lpivot + 1, rpivot + 1);
                std::iter_swap(lpivot, lpivot + 1);
                lpivot++;
                rpivot++;
            }

            if (left_it != begin - 1)
                left_it--;
            if (right_it != end)
                right_it++;

            lValue = *left_it;
            rValue = *right_it;

            isGreater = false;
            isLess = false;
        }

        quickSort(begin, lpivot);
        quickSort(rpivot + 1, end);
    }
}

我的算法基准

1000000  random integers --------> 80 ms
2000000  random integers --------> 165 ms
3000000  random integers --------> 247 ms
10000000 random integers --------> 780 ms

1000000  binary random integers -> 4 ms
2000000  binary random integers -> 9 ms
3000000  binary random integers -> 14 ms
10000000 binary random integers -> 49 ms

1000000  sorted integers --------> 19 ms
2000000  sorted integers --------> 43 ms
3000000  sorted integers --------> 65 ms
10000000 sorted integers --------> 232 ms

1000000  reversed integers ------> 17 ms
2000000  reversed integers ------> 37 ms
3000000  reversed integers ------> 60 ms
10000000 reversed integers ------> 216 ms

std：：排序基准

1000000  random integers --------> 71 ms
2000000  random integers --------> 160 ms
3000000  random integers --------> 237 ms
10000000 random integers --------> 800 ms

1000000  binary random integers -> 4 ms
2000000  binary random integers -> 9 ms
3000000  binary random integers -> 13 ms
10000000 binary random integers -> 45 ms

1000000  sorted integers --------> 9 ms
2000000  sorted integers --------> 21 ms
3000000  sorted integers --------> 33 ms
10000000 sorted integers --------> 137 ms

1000000  reversed integers ------> 12 ms
2000000  reversed integers ------> 25 ms
3000000  reversed integers ------> 40 ms
10000000 reversed integers ------> 150 ms

标记代码

int main()
{
    std::vector<int> values;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dist(0, 1000000);
    //std::uniform_int_distribution<> dist(0, 1); //just 0s and 1s array

    std::generate_n(std::back_inserter(values), 10000000, std::bind(dist, gen)); //random

    for (int i = 0; i < 10000000; i++)
    {
        //values.push_back(i);              //sorted array
        //values.push_back(10000000 - i);   //reversed array
    }

    typedef std::chrono::high_resolution_clock Time;
    typedef std::chrono::milliseconds ms;
    typedef std::chrono::duration<float> fsec;
    auto t0 = Time::now();

    //quickSort(values.begin(), values.end());
    //std::sort(values.begin(), values.end());

    auto t1 = Time::now();
    fsec fs = t1 - t0;
    ms d = std::chrono::duration_cast<ms>(fs);
    std::cout << fs.count() << "s\n";
    std::cout << d.count() << "ms\n";

    return 0;
}

更新

我尝试用clang3.8unUbuntu x64对相同的代码进行基准测试，得到了与注释中相同的结果，因此它只是一个带有缓慢的std排序实现的visual studio

(我知道那些箭很烂，它们在那里只是为了清晰)

Answer 1

请注意，文章中的图片都在MatPlotLib许可证下面，因为我已经使用模块绘制了这些图。

我终于完成了基准测试。虽然它们是相当合成的，我相信我核武器的东西，可能会影响到我的能力的基准。

系统设置:英特尔核心i7 2600，8GB ram 1333 the，Ubuntu16.04LTS与最新更新，clang++-5.0-主干，没有性能标志，除了那些通过cmake的发布模式，libc++-主干(我相信最新版本)。

上面的图像用于范围0；100中的元素，生成器：std::random_device (硬件，因为intel cpu和libc++)。

下面是范围0；100‘000，std::mt19937_64中的元素，默认构造。

请注意，由于设置和输入范围的变化，比较两个图像没有多大意义。虽然速度和输入范围之间的关系是非常清楚的，特别是对于std::sort。原因可能是要进行更多的掉期交易。

正如您所见，与libc++'s std::sort相比，您的算法具有算法性能的提高。接近尾声的尖峰是我观看youtube视频，因为基准运行了大约1.5个小时，并且在最后大大减慢了速度。我相信慢下来的原因不是算法，而是std::random_device (它的开销被排除在基准本身之外)，所以如果将来有人想对代码进行基准测试，就不要使用std::random_device生成大数据集！

我在他们的bug跟踪器上读到过，他们的std::sort使用一些复杂的快速排序。要了解更多信息，我建议您看看这个错误报告。

代码审查：

我不擅长算法，所以我将提到代码风格和对通用代码的一些改进。

评论：

是啊，这是个不错的利基。但是，我记不起一个月前我写了什么了，虽然我被认为是一个在我的同龄人中有着相当长时间记忆的人。您至少可以保留一个标记或tex/latex文件与它一起解释。要夸大代码的清晰度是不可能的。

迭代器类别：

对于C++17，我(相信)有7类。std::list可能会有双向类别，而回退到合并排序可能是好的。。我本人还没有检查过，但我的教授同意这一观点。

因此，可以通过更改声明，显式指定“喜欢”随机访问迭代器：

template<class RandomAccessIt>
void quickSort(RandomAccessIt begin, RandomAccessIt end)

它可能会修复来自您可能在当前代码上构建的专门版本的一致性错误。从个人经验来看，我知道要完全符合规格是相当困难的。

小事：

auto pValue = *lpivot;

这可能会增加类型约束。根据我在代码中看到的，您没有修改它。所以应该是：

const auto& pValue = *lpivot;

理解的关键是，对于任何以下形式的功能：

template <typename T>
void foo(T value);

如果它是rvalue，T将删除它的引用。证明。因此，代码实际上是复制构建pValue，这可能非常昂贵。

标杆方法：

虽然基准代码可以很好地衡量性能，但我认为当您开始压缩性能时，它不会满足您的要求。同时，在每个阶段记录你的想法将是一个非常好的方法。简而言之，所有的软件工程实践都应该在这里应用，加上基准：

• 总是有底线的。它通常是代码最快的版本。如果您没有针对某物来度量代码，则不会使它变得更快。
• 设置多个情况。我不认为每个人都希望总是对ints排序，可能会出现编译错误、未定义的行为等等。
• 原始运行时不是最好的东西。如果您阅读我所链接的bug报告，用户会提到原始运行时不是可移植的，而且严重依赖于环境。我的声音可能没有任何意义，但我同意他/她的看法。更好的衡量标准是吞吐量、数据读写。我相信所有的东西都可以通过使用google基准库来捕捉。

用于基准测试的

代码：

我的基准测试v2的修改版本。

main()中的代码：

std::size_t counter = 0;
auto quicksort_bench = [&counter](std::vector<int>& v)
{
    quickSort(v.begin(), v.end());
    std::cout << v.front() << ' ' << counter++ << '\n'; //just to tell compiler to not optimize the code away
};

auto stdsort_bench = [&counter](std::vector<int>& v)
{
    std::sort(v.begin(), v.end());
    std::cout << v.front() << ' ' << counter++ << '\n'; //ditto
};

auto checked_bench = shino::benchmarker(generator{}, quicksort_bench, stdsort_bench);

for (std::size_t i = 1000; i <= 1'000'000; i += 100)
{
    checked_bench.time(i, 3); //3 means runcount for the same dataset
}

checked_bench.save_as<std::chrono::microseconds>("./benchmarks/metafile.txt",
                      {"custom quicksort.txt", "standard sort.txt"});

生成器编写起来有点棘手，因为它不会导致速度减慢，并且不会耗尽内存：

class generator
{
    std::unique_ptr<shino::random_int_generator<>> gen;
public:
    using input_type = std::size_t;

    generator():
            gen(std::make_unique<shino::random_int_generator<>>(0, 100)) //replaced with 0, 100'000 on second run
    {}

    generator(generator&& other):
            gen(std::move(other.gen))
    {}

    std::tuple<std::vector<int>> operator()(input_type input)
    {
        static std::vector<int> v(input);
        if (v.size() != input)
        {
            v.resize(input);
            (*gen)(v.begin(), v.end());
        }

        return v;
    }
};

输入的生成发生在“关键部分”之外，因此不应该影响基准测试。此外，缺省值是std::random_device，这也是基准测试运行这么长时间的原因。

还有一个python脚本来绘制图，我认为这是不相关的，因为它根本不修改数据。

Answer 2

我认为这个小小的改变将提高大型数据集的性能。

原创

if (lValue >= pValue) // == is redundant changeto <
   {
    if (lValue == pValue)
       {
        lpivot--;
        std::iter_swap(lpivot, left_it);
       }
    else
       isGreater = true;
   }

   if (rValue <= pValue) // == is redundant changeto >
      {
       if (rValue == pValue)
          {
           rpivot++;
           std::iter_swap(rpivot, right_it);
          }
       else
          isLess = true;
   }

变到

if (!(lValue < pValue)) // leaving == and >
   {
    if (lValue == pValue)
       {
        lpivot--;
        std::iter_swap(lpivot, left_it);
       }
    else
       isGreater = true;
   }

if (!(rValue > pValue)) // leaving == and <
   {
    if (rValue == pValue)
       {
        rpivot++;
        std::iter_swap(rpivot, right_it);
       }
    else
       isLess = true;
   }

我将考虑如何提高排序数据的性能。

编辑:更改！(.)致(！(.))