那些遇到过的问题

使用比较器网络快速排序固定长度阵列

Ros*_*ley 22 c++ arrays sorting template-meta-programming sorting-network

我有一些性能关键代码,涉及在C++中对大约3到10个元素之间的非常短的固定长度数组进行排序(参数在编译时更改).

在我看来,专门针对每个可能的输入大小的静态排序网络可能是一种非常有效的方法:我们进行必要的比较以确定我们所处的情况,然后进行最佳的交换数量以进行排序数组.

要应用此功能,我们使用一些模板魔法来推断数组长度并应用正确的网络:

#include <iostream>
using namespace std;

template< int K >
void static_sort(const double(&array)[K])
{
    cout << "General static sort\n" << endl;
}

template<>
void static_sort<3>(const double(&array)[3])
{
    cout << "Static sort for K=3" << endl;
}


int main()
{

    double  array[3];

    // performance critical code.
    // ...
    static_sort(array);
    // ...

}
Run Code Online (Sandbox Code Playgroud)

显然,编写所有这些代码非常麻烦,所以:

  • 有没有人对是否值得努力有任何意见？
  • 有谁知道这种优化是否存在于任何标准实现中,例如std :: sort？
  • 是否有一个容易实现这种排序网络的代码？
  • 也许有可能使用模板魔法静态生成这样的排序网络.

现在我只使用带有静态模板参数的插入排序(如上所述),希望它会鼓励展开和其他编译时优化.

欢迎你的想法.

更新: 我写了一些测试代码来比较'static'插入short和std :: sort.(当我说静态时,我的意思是数组大小是固定的并在编译时推断出来(可能是允许循环展开等).我至少得到20%的NET改进(请注意,生成包含在时间中).平台: clang,OS X 10.9.

代码在这里https://github.com/rosshemsley/static_sorting如果你想将它与你的stdlib实现进行比较.

我还没有为比较器网络分拣机找到一套很好的实现.

小智 12

我最近写了一个小类,它使用Bose-Nelson算法在编译时生成一个排序网络. 

/**
 * A Functor class to create a sort for fixed sized arrays/containers with a
 * compile time generated Bose-Nelson sorting network.
 * \tparam NumElements  The number of elements in the array or container to sort.
 * \tparam T            The element type.
 * \tparam Compare      A comparator functor class that returns true if lhs < rhs.
 */
template <unsigned NumElements, class Compare = void> class StaticSort
{
    template <class A, class C> struct Swap
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            T t = Compare()(v0, v1) ? v0 : v1; // Min
            v1 = Compare()(v0, v1) ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A> struct Swap <A, void>
    {
        template <class T> inline void s(T &v0, T &v1)
        {
            // Explicitly code out the Min and Max to nudge the compiler
            // to generate branchless code.
            T t = v0 < v1 ? v0 : v1; // Min
            v1 = v0 < v1 ? v1 : v0; // Max
            v0 = t;
        }

        inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
    };

    template <class A, class C, int I, int J, int X, int Y> struct PB
    {
        inline PB(A &a)
        {
            enum { L = X >> 1, M = (X & 1 ? Y : Y + 1) >> 1, IAddL = I + L, XSubL = X - L };
            PB<A, C, I, J, L, M> p0(a);
            PB<A, C, IAddL, J + M, XSubL, Y - M> p1(a);
            PB<A, C, IAddL, J, XSubL, M> p2(a);
        }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 1>
    {
        inline PB(A &a) { Swap<A, C> s(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 2>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J); Swap<A, C> s1(a, I - 1, J - 1); }
    };

    template <class A, class C, int I, int J> struct PB <A, C, I, J, 2, 1>
    {
        inline PB(A &a) { Swap<A, C> s0(a, I - 1, J - 1); Swap<A, C> s1(a, I, J - 1); }
    };

    template <class A, class C, int I, int M, bool Stop = false> struct PS
    {
        inline PS(A &a)
        {
            enum { L = M >> 1, IAddL = I + L, MSubL = M - L};
            PS<A, C, I, L, (L <= 1)> ps0(a);
            PS<A, C, IAddL, MSubL, (MSubL <= 1)> ps1(a);
            PB<A, C, I, IAddL, L, MSubL> pb(a);
        }
    };

    template <class A, class C, int I, int M> struct PS <A, C, I, M, true>
    {
        inline PS(A &a) {}
    };

public:
    /**
     * Sorts the array/container arr.
     * \param  arr  The array/container to be sorted.
     */
    template <class Container> inline void operator() (Container &arr) const
    {
        PS<Container, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };

    /**
     * Sorts the array arr.
     * \param  arr  The array to be sorted.
     */
    template <class T> inline void operator() (T *arr) const
    {
        PS<T*, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
    };
};

#include <iostream>
#include <vector>

int main(int argc, const char * argv[])
{
    enum { NumValues = 32 };

    // Arrays
    {
        int rands[NumValues];
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    std::cout << "\n";

    // STL Vector
    {
        std::vector<int> rands(NumValues);
        for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
        std::cout << "Before Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
        StaticSort<NumValues> staticSort;
        staticSort(rands);
        std::cout << "After Sort: \t";
        for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
        std::cout << "\n";
    }

    return 0;
}
Run Code Online (Sandbox Code Playgroud)

基准

下面的基准测试是用clang -O3编写的,并在我2012年中期的macbook air上运行.

排序100万个数组的时间(以毫秒为单位).
大小为2,4,8的数组的毫秒数分别为1.943,8.655,20.246.
C++模板化Bose-Nelson静态排序时序

以下是6个元素的小数组的每种平均时钟数.基准代码和示例可以在这个问题上找到:
最快的固定长度6 int数组 

Direct call to qsort library function   : 342.26
Naive implementation (insertion sort)   : 136.76
Insertion Sort (Daniel Stutzbach)       : 101.37
Insertion Sort Unrolled                 : 110.27
Rank Order                              : 90.88
Rank Order with registers               : 90.29
Sorting Networks (Daniel Stutzbach)     : 93.66
Sorting Networks (Paul R)               : 31.54
Sorting Networks 12 with Fast Swap      : 32.06
Sorting Networks 12 reordered Swap      : 29.74
Reordered Sorting Network w/ fast swap  : 25.28
Templated Sorting Network (this class)  : 25.01
Run Code Online (Sandbox Code Playgroud)

它的性能与6个元素的问题中最快的例子一样快.

用于基准测试的代码可以在这里找到.

Mor*_*enn 9

其他答案很有意思且相当不错,但我相信我可以提供一些额外的答案元素,每点指出:

  • 值得努力吗？好吧,如果你需要对整数的小集合进行排序,并且调整排序网络以尽可能地利用一些指令,那么它可能是值得的.下图显示了int使用不同排序算法对100万个大小为0-14的数组进行排序的结果.如您所见,如果您确实需要,排序网络可以提供显着的加速.

  • std::sort我不知道使用排序网络的标准实现; 当它们没有经过微调时,它们可能比直接插入类型慢.libc ++ std::sort有专门的算法一次排序0到5个值,但它们也没有使用排序网络.我所知道的唯一使用排序网络对几个值进行排序的排序算法是Wikisort.也就是说,将分拣网络应用于合成优化排序库的研究论文表明,排序网络可用于对小型数组进行排序或改进递归排序算法(如快速排序),但前提是它们经过微调以利用特定的硬件指令.

    该访问对齐的排序算法是某种自下而上归并的,显然使用与第一遍SIMD指令实现双调排序网络.显然,对于某些标量类型,算法可能比标准库快一些.

  • 我实际上可以提供这样的信息,原因很简单,我开发了一个C++ 14排序库,它恰好提供了大小为0到32的高效排序网络,实现了上一节中描述的优化.我用它在第一部分生成图表.我仍在研究图书馆的排序网络部分,以提供尺寸最佳,深度优化和交换最优的网络.小型优化分拣网络具有强大的力量,而较大的分拣网络则使用来自文献的结果.

    请注意,库中的排序算法都不直接使用排序网络,但您可以对它们进行调整,以便在为排序算法提供小型std::array或小型固定大小的C阵列时,将选择排序网络:

    using namespace cppsort;

// Sorters are function objects that can be
// adapted with sorter adapters from the
// library
using sorter = small_array_adapter<
    std_sorter,
    sorting_network_sorter
>;

// Now you can use it as a function
sorter sort;

// Instead of a size-agnostic sorting algorithm,
// sort will use an optimal sorting network for
// 5 inputs since the bound of the array can be
// deduced at compile time
int arr[] = { 2, 4, 7, 9, 3 };
sort(arr);
    Run Code Online (Sandbox Code Playgroud)

    如上所述,该库为内置整数提供了高效的排序网络,但如果您需要对其他小型数组进行排序(例如,我的最新基准测试表明它们并不比直接插入排序更好),那么您可能会运气不好即使是long long int).

  • 您可以使用模板元编程来生成任何大小的排序网络,但是没有已知的算法可以生成最佳的排序网络,因此您也可以手动编写最好的排序网络.我不认为通过简单算法生成的那些实际上可以提供可用且有效的网络(Batcher的奇偶排序和成对排序网络可能是唯一可用的)[另一个答案似乎表明生成的网络实际上可以工作].

Aki*_*nen 8

对于N <16,已知最佳或至少最佳长度的比较器网络,因此至少有一个相当好的起点.相当地,因为最佳网络不一定是针对例如SSE或其他矢量算术可实现的最大并行度水平而设计的.

另一点是,对于一些N而言,已经有一些最优网络是针对N + 1稍微更大的最佳网络的简并版本.

来自维基百科:

最多10个输入的最佳深度是已知的,它们分别为0,1,3,3,5,5,6,6,7,7.

这就是说,我追求实现N = {4,6,8和10}的网络,因为深度约束不能通过额外的并行性来模拟(我认为).我还认为,与"众所周知"的排序方法(例如快速排序)相比,在RISC架构中使用SSE寄存器(也使用一些最小/最大指令)或甚至一些相对较大的寄存器设置的能力将提供显着的性能优势.没有指针算术和其他开销.

另外,我会追求使用臭名昭着的循环展开技巧Duff的设备来实现并行网络.

编辑 当已知输入值为正IEEE-754浮点数或双精度数时,还值得一提的是,比较也可以作为整数执行.(float和int必须具有相同的字节顺序)

And*_*rey 3

让我分享一些想法。

有人对这是否值得付出任何意见吗？

不可能给出正确答案。您必须分析您的实际代码才能找到答案。在我的实践中，当涉及到低级分析时，瓶颈总是不在我想象的地方。

有谁知道这种优化是否存在于任何标准实现中，例如 std::sort ？

例如，Visual C++ 实现std::sort对小向量使用插入排序。我不知道使用最佳排序网络的实现。

也许可以使用模板魔术静态生成这样的排序网络

有生成排序网络的算法，例如 Bose-Nelson、Hibbard 和 Batcher 算法。由于 C++ 模板是图灵完备的，因此您可以使用 TMP 来实现它们。但是，这些算法不能保证提供理论上最小数量的比较器，因此您可能需要对最佳网络进行硬编码。

归档时间：

查看次数：

3757 次

最近记录：

8 年，7 月 前
最快的固定长度6 int数组 396
标准排序网络,用于n的小值 13
更多相关链接
相关归档
如何在PHP中从数组创建逗号分隔列表？ 105
数字文字的ULL后缀 67
寻找类似C++ STL的矢量类,但使用堆栈存储 53
G ++错误:/ usr/lib/rpm/redhat/redhat-hardened-cc1:没有这样的文件或目录 39
为什么operator()在C++ 17中为std :: function改变？ 26
eof()不好的做法？ 25
初始化结构中的数组值 11
使用动态嵌套属性键对数组中的对象进行排序 9
Python:将字典键作为按子字典值排序的列表 4
如何根据另一个字符串表定义的顺序对一个字符串表进行排序（Lua） 2
难疑归档
在JavaScript中验证十进制数 - IsNumeric() 2318
带请求正文的HTTP GET 1896
Eclipse Android插件中的"调试证书已过期"错误 1863
如何在Git中检索当前提交的哈希值？ 1788
Python中的switch语句的替换？ 1719
我应该在哪里将<script>标记放在HTML标记中？ 1392
检查值是否是JavaScript中的对象 1194
退出申请不赞成？ 1131
获取插入行的标识的最佳方法是什么？ 1056
Access-Control-Allow-Origin标头如何工作？ 1050