排序10个数字的最快方法?(数字为32位)

(根据@HelloWorld的建议，研究排序网络。)

似乎29个比较/交换网络是进行10个输入排序的最快方法。在这个例子中，我使用了Waksman在1969年发现的JavaScript网络，它应该直接转换成C语言，因为它只是一个if语句、比较和交换的列表。

这里是网络的图形表示，分为独立的阶段。

为了利用并行处理的优势，可以将5-4-3-3 - 4-4-2 -3-2分组改为4-4-4-2 -4-4-3-2分组。

2015-08-24 01:05:16

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

它可以用来为10个数字创建一个非常快速的排序。

/**
 * 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 = 10 };

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

注意，我们没有使用if (compare)交换语句，而是显式地为min和max编写了三元运算符。这有助于推动编译器使用无分支代码。

# #基准

下面的基准测试是用clang -O3编译的，并在我2012年年中的MacBook Air上运行。

###排序随机数据

将它与DarioP的代码进行比较，下面是排序100万个大小为10的32位整型数组所需的毫秒数:

硬编码排序网络10:88.774毫秒模板化玻色-纳尔逊排序10:27.815毫秒

使用这种模板化方法，我们还可以在编译时为其他数量的元素生成排序网络。

排序100万个不同大小的数组的时间(以毫秒为单位)。

大小为2、4、8的数组的毫秒数分别为1.943、8.655、20.246。

感谢格伦·泰特鲍姆的展开插入排序。

下面是6个元素的小数组每次排序的平均时钟。基准测试代码和示例可以在以下问题中找到:

最快的固定长度6 int数组排序

Direct call to qsort library function       : 326.81
Naive implementation (insertion sort)       : 132.98
Insertion Sort (Daniel Stutzbach)           : 104.04
Insertion Sort Unrolled                     : 99.64
Insertion Sort Unrolled (Glenn Teitelbaum)  : 81.55
Rank Order                                  : 44.01
Rank Order with registers                   : 42.40
Sorting Networks (Daniel Stutzbach)         : 88.06
Sorting Networks (Paul R)                   : 31.64
Sorting Networks 12 with Fast Swap          : 29.68
Sorting Networks 12 reordered Swap          : 28.61
Reordered Sorting Network w/ fast swap      : 24.63
Templated Sorting Network (this class)      : 25.37

对于6个元素，它的执行速度和问题中最快的例子一样快。

###排序数据的性能

通常，输入数组可能已经排序或基本排序。在这种情况下，插入排序可能是更好的选择。

您可能希望根据数据选择合适的排序算法。

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

2016-03-24 20:19:15

出于类似于我在这里描述的原因，以下排序函数sort6_iterator()和sort10_iterator_local()应该能很好地执行，其中排序网络是从这里取的:

template<class IterType> 
inline void sort10_iterator(IterType it) 
{
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   auto data##a=*(data+a);
#define DD2(a,b) auto data##a=*(data+a), data##b=*(data+b);
#define CB1(a)   *(data+a)=data##a;
#define CB2(a,b) *(data+a)=data##a;*(data+b)=data##b;
  DD2(1,4) SORT2(1,4) DD2(7,8) SORT2(7,8) DD2(2,3) SORT2(2,3) DD2(5,6) SORT2(5,6) DD2(0,9) SORT2(0,9) 
  SORT2(2,5) SORT2(0,7) SORT2(8,9) SORT2(3,6) 
  SORT2(4,9) SORT2(0,1) 
  SORT2(0,2) CB1(0) SORT2(6,9) CB1(9) SORT2(3,5) SORT2(4,7) SORT2(1,8) 
  SORT2(3,4) SORT2(5,8) SORT2(6,7) SORT2(1,2) 
  SORT2(7,8) CB1(8) SORT2(1,3) CB1(1) SORT2(2,5) SORT2(4,6) 
  SORT2(2,3) CB1(2) SORT2(6,7) CB1(7) SORT2(4,5) 
  SORT2(3,4) CB2(3,4) SORT2(5,6) CB2(5,6) 
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

为了调用这个函数，我给它传递了一个std::vector迭代器。

2017-06-07 01:09:40

当您处理这个固定大小时，请查看排序网络。这些算法有固定的运行时间，并且独立于它们的输入。对于您的用例，您没有某些排序算法所具有的这种开销。

二进制排序就是这种网络的一种实现。这个方法在CPU上使用len(n) <= 32时效果最好。对于更大的输入，你可以考虑使用GPU。

顺便说一下，比较排序算法的一个好页面是这个(尽管它缺少二进制排序):

排序算法动画

2015-08-23 22:26:20

(根据@HelloWorld的建议，研究排序网络。)

似乎29个比较/交换网络是进行10个输入排序的最快方法。在这个例子中，我使用了Waksman在1969年发现的JavaScript网络，它应该直接转换成C语言，因为它只是一个if语句、比较和交换的列表。

这里是网络的图形表示，分为独立的阶段。

为了利用并行处理的优势，可以将5-4-3-3 - 4-4-2 -3-2分组改为4-4-4-2 -4-4-3-2分组。

2015-08-24 01:05:16

使用排序网络，以4为一组进行比较，这样就可以在SIMD寄存器中进行比较。一对打包的最小/最大指令实现了打包比较器函数。对不起，我现在没有时间去找我记得看到过的关于这个的页面，但希望在SIMD或SSE排序网络上搜索会找到一些东西。

x86 SSE确实为4个32位整型的向量提供了打包的32位整型的min和max指令。AVX2 (Haswell及后续版本)具有相同的功能，但用于256b的8个整型向量。还有高效的洗牌指令。

如果你有很多独立的小排序，用向量并行地做4到8个排序是可能的。特别是，如果你随机选择元素(所以要排序的数据在内存中不会连续)，你可以避免打乱，只需要按照你需要的顺序进行比较。10个寄存器保存来自4个(AVX2: 8) 10个整数列表的所有数据，仍然留下6个reg作为临时空间。

如果还需要对相关数据进行排序，则向量排序网络的效率较低。在这种情况下，最有效的方法似乎是使用wrapped -compare来获得更改元素的掩码，并使用该掩码来混合相关数据的(引用)向量。

2015-08-24 01:48:10

排序10个数字的最快方法?(数字为32位)

推荐文章

最新文章

标签