logo标签列表

使用哪种排序方法：快速排序、桶排序、基数排序等等，对于小型数据对来说哪个更好？（C++）

c++sortingperformancebenchmarking
4
我需要优化一些代码，该代码对一个vector<pair<int，float>>进行排序，其中的pair需要按照float值进行排序。这个vector的长度在0到5之间。我已经在Google上搜索并阅读了有关C ++排序方法的内容，但找不到任何针对小数据集的基准测试。对于系统来说，尽可能快速非常重要，因为它用于实时斑点跟踪系统。
此致， Pollux
基数排序只能用于整数。 - kennytm
2
你如何创建这些向量？你不能将它们创建为已排序的吗？ - sbi
2
IEEE754浮点数具有一个有趣的属性，当像整数一样处理时，它们处于相同的数值顺序中，这是因为符号位和偏置指数。 - matja
1
@matja：只要你排除掉NaN。 - MSalters
如果您正在对执行此排序的同一处理器进行blob/background分区，则忘掉它吧！输入图像上的4或8路blob连接算法将完全淹没排序时间。考虑：在64x64传感器上，您必须查看4096个像素值并做出blob/background决策。相比之下，要对5个值进行O(N^2)冒泡排序，您需要进行大约20次比较。将20与4096进行比较，并告诉我您将在哪里因循环而受到更严重的伤害。 - John R. Strohm
8个回答
6
插入排序总是比冒泡排序好吗？ - Nikko
@Nikko，一般来说插入排序会是更好的选择。然而，如果你实现冒泡排序的内部循环正确（优化），我认为在这样小的数据集上不会有任何性能差异。 - Nick Dandoulakis
5

阅读基准测试的内容毫无意义。你可以阅读并比较算法的复杂度（Big-O），因为它只取决于算法本身，但基准测试取决于太多因素。

你需要使用你所用的工具，在对应用户应用的环境中进行基准测试。

3
对于您提到的数据（0-5），请使用STL sort 方法进行排序。（历史上基于qsort） stable_sort -- 如果您想保留重复项的顺序，请使用此方法。（历史上基于归并排序）
3

您需要对这段代码进行优化的特定原因是什么？对于n==5，几乎任何排序算法都可以。甚至Bogosort也应该有合理的运行时间，因为数据中只有 5! == 120 种可能的排列方式。您是否分析了您的算法以找出其中的瓶颈？

2
首先，过早地进行优化是万恶之源。也就是说，首先对代码进行基准测试，并确保排序确实是耗费大量时间的部分。如果你的关键性能代码的另一部分占用了80%的执行时间，那么优化这部分将会获得明显的性能提升。
考虑到你有5个元素，这个观点几乎没有意义。除了乱序排序，你使用的任何算法都应该具有几乎恒定的执行时间，除非你每秒运行几百次或更多。
其次，如果你仍想优化搜索，如果你确定你始终只有5个元素，则最佳方法是硬编码比较（可以通过数学证明，该方法在最坏情况下提供最少的执行操作）。如果你的元素少于5个，同样适用这种方法，但如果元素超过7个，算法编写和执行将变得困难，逻辑也会变得复杂，使你的代码难以维护。
如果你需要帮助编写最优硬编码算法本身，请告诉我（尽管我认为你应该在网上找到实现和理论）。
如果你并不总是有五个数字（或者由于某种原因想避免硬编码比较算法），可以使用库提供的排序。这个页面得出结论，stl排序在时间（而不仅仅是执行操作数）方面是最优的。我不知道用于搜索的实现方式。
小小的抱怨： “恒定执行时间”并不意味着快速，它只是恒定的，因此如果它“几乎是恒定的”，那么这并不一定是好事，如果您重复执行几百次，它也不会变得不那么恒定。 - Thomas Padron-McCarthy
1
我不会相信那个显示STL排序最优的页面。首先，我找不到所有使用排序的源代码。有一个名为d_sort.h的文件缺失，我猜它是和那本书一起提供的。其次，我有一个单轴递归快速排序比std::sort快得多。此外，有一个双轴快速排序（不是我创建的）击败了我的快速排序和std::sort。话虽如此，std::sort还是相当快的，但是对于研究需要保持警惕并仔细审查它们以了解它们的执行方式。 - Justin Peel
2

如果你想要对5个元素进行排序，可以使用一组有点复杂的if语句来实现最快的排序。但是，如果你希望排序稍微慢一点，但不会带来太多麻烦，那么可以使用排序网络。使用此网站，输入5个数字以获取优化的排序网络。它甚至展示了如何并行处理某些部分，尽管这似乎有点过度，因为只有5个输入。它将需要9次比较，这非常好。你也需要使用一组if语句来实现排序网络，但是在我之前提到的有点复杂的if语句和真正最优的排序网络之间的区别在于交换的数量：排序网络并不最小化交换的数量。

1

如果你确信（也就是说，你已经进行了测量），这是一个瓶颈并且需要优化，而STL中的任何排序算法都不够快（你也已经测量过了），那么也许你知道更多可以使用的东西？标准排序算法是通用的，并且适用于任何数据集：不同数量的元素，不同范围的值等等。如果你真的需要性能，诀窍通常是使用额外的信息来制定更专业的算法。

在这里，你已经说了一件事情：有0-5个元素需要排序，正如Nick D在他的回答中所说，也许使用硬编码的if语句而不是通用排序算法的循环或递归可能会更快。

但也许还有更多？例如，浮点值是否有任何限制？

大家好！非常感谢这个有用的信息！ - pollux
0

这里有一个排序4个元素的例程，使用最优数量的比较。我本来想发布5个元素的，但stackoverflow限制帖子长度为30000个字符。

实际上这是否是最快的取决于你的CPU指令缓存能承受多少压力，所以在真实程序中进行基准测试！

/// Generated sort function for 4 arguments.
template <class T>
void DirectSort(T& a0, T& a1, T& a2, T& a3) {
    if (a0 < a1) {
        if (a0 < a2) {
            if (a0 < a3) {
                if (a1 < a2) {
                    if (a1 < a3) {
                        if (a3 < a2) {
                            {
                                T tmp(a2);
                                a2 = a3;
                                a3 = tmp;
                            }
                        }
                    }
                    else { // a1 >= a3
                        {
                            T tmp(a1);
                            a1 = a3;
                            a3 = a2;
                            a2 = tmp;
                        }
                        // a2 >= a3
                    }
                }
                else { // a1 >= a2
                    if (a1 < a3) {
                        {
                            T tmp(a1);
                            a1 = a2;
                            a2 = tmp;
                        }
                        // a2 < a3
                    }
                    else { // a1 >= a3
                        if (a2 < a3) {
                            {
                                T tmp(a1);
                                a1 = a2;
                                a2 = a3;
                                a3 = tmp;
                            }
                        }
                        else { // a2 >= a3
                            {
                                T tmp(a1);
                                a1 = a3;
                                a3 = tmp;
                            }
                        }
                    }
                }
            }
            else { // a0 >= a3
                if (a1 < a2) {
                    {
                        T tmp(a0);
                        a0 = a3;
                        a3 = a2;
                        a2 = a1;
                        a1 = tmp;
                    }
                    // a1 >= a3
                    // a2 >= a3
                }
                else { // a1 >= a2
                    {
                        T tmp(a0);
                        a0 = a3;
                        a3 = a1;
                        a1 = tmp;
                    }
                    // a1 >= a3
                    // a2 >= a3
                }
            }
        }
        else { // a0 >= a2
            if (a0 < a3) {
                // a1 >= a2
                if (a1 < a3) {
                    {
                        T tmp(a0);
                        a0 = a2;
                        a2 = a1;
                        a1 = tmp;
                    }
                    // a2 < a3
                }
                else { // a1 >= a3
                    {
                        T tmp(a0);
                        a0 = a2;
                        a2 = a3;
                        a3 = a1;
                        a1 = tmp;
                    }
                    // a2 < a3
                }
            }
            else { // a0 >= a3
                // a1 >= a2
                // a1 >= a3
                if (a2 < a3) {
                    {
                        T tmp(a0);
                        a0 = a2;
                        a2 = tmp;
                    }
                    {
                        T tmp(a1);
                        a1 = a3;
                        a3 = tmp;
                    }
                }
                else { // a2 >= a3
                    {
                        T tmp(a0);
                        a0 = a3;
                        a3 = a1;
                        a1 = a2;
                        a2 = tmp;
                    }
                }
            }
        }
    }
    else { // a0 >= a1
        if (a0 < a2) {
            if (a0 < a3) {
                {
                    T tmp(a0);
                    a0 = a1;
                    a1 = tmp;
                }
                // a1 < a2
                // a1 < a3
                if (a3 < a2) {
                    {
                        T tmp(a2);
                        a2 = a3;
                        a3 = tmp;
                    }
                }
            }
            else { // a0 >= a3
                // a1 < a2
                if (a1 < a3) {
                    {
                        T tmp(a0);
                        a0 = a1;
                        a1 = a3;
                        a3 = a2;
                        a2 = tmp;
                    }
                    // a2 >= a3
                }
                else { // a1 >= a3
                    {
                        T tmp(a0);
                        a0 = a3;
                        a3 = a2;
                        a2 = tmp;
                    }
                    // a2 >= a3
                }
            }
        }
        else { // a0 >= a2
            if (a0 < a3) {
                if (a1 < a2) {
                    {
                        T tmp(a0);
                        a0 = a1;
                        a1 = a2;
                        a2 = tmp;
                    }
                    // a1 < a3
                    // a2 < a3
                }
                else { // a1 >= a2
                    {
                        T tmp(a0);
                        a0 = a2;
                        a2 = tmp;
                    }
                    // a1 < a3
                    // a2 < a3
                }
            }
            else { // a0 >= a3
                if (a1 < a2) {
                    if (a1 < a3) {
                        if (a2 < a3) {
                            {
                                T tmp(a0);
                                a0 = a1;
                                a1 = a2;
                                a2 = a3;
                                a3 = tmp;
                            }
                        }
                        else { // a2 >= a3
                            {
                                T tmp(a0);
                                a0 = a1;
                                a1 = a3;
                                a3 = tmp;
                            }
                        }
                    }
                    else { // a1 >= a3
                        {
                            T tmp(a0);
                            a0 = a3;
                            a3 = tmp;
                        }
                        // a2 >= a3
                    }
                }
                else { // a1 >= a2
                    if (a1 < a3) {
                        {
                            T tmp(a0);
                            a0 = a2;
                            a2 = a3;
                            a3 = tmp;
                        }
                        // a2 < a3
                    }
                    else { // a1 >= a3
                        if (a2 < a3) {
                            {
                                T tmp(a0);
                                a0 = a2;
                                a2 = a1;
                                a1 = a3;
                                a3 = tmp;
                            }
                        }
                        else { // a2 >= a3
                            {
                                T tmp(a0);
                                a0 = a3;
                                a3 = tmp;
                            }
                            {
                                T tmp(a1);
                                a1 = a2;
                                a2 = tmp;
                            }
                        }
                    }
                }
            }
        }
    }
} // DirectSort - 4 arguments.
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接