首页 文章

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

提问于
浏览
205

我正在解决一个问题,它涉及非常快速地排序10个数字(int32) . 我的应用程序需要尽可能快地对10个数字进行数百万次排序 . 我正在对数十亿个元素的数据集进行采样,每次我需要从中挑选10个数字(简化)并对它们进行排序(并从排序的10个元素列表中得出结论) .

目前我正在使用插入排序但我想我可以实现一个非常快速的自定义排序算法,针对我的10个数字的特定问题,这将超过插入排序 .

有没有人知道如何处理这个问题?

10 回答

  • 8

    插入排序平均需要29,6个比较来排序10个输入,最佳情况为9,最差情况为45(给定输入的顺序相反) .

    {9,6,1}炮弹将平均需要25.5个比较来排序10个输入 . 最好的情况是14次比较,最差的是34次,并且对反向输入进行排序需要22次 .

    因此,使用shellsort而不是插入排序可以将平均情况减少14% . 尽管最佳情况增加了56%,但最坏情况下减少了24%,这对于保持最坏情况性能得到控制的应用非常重要 . 相反的情况减少了51% .

    由于您似乎熟悉插入排序,因此您可以将算法实现为{9,6}的排序网络,然后在插入排序({1})之后执行:

    i[0] with i[9]    // {9}
    
    i[0] with i[6]    // {6}
    i[1] with i[7]    // {6}
    i[2] with i[8]    // {6}
    i[3] with i[9]    // {6}
    
    i[0 ... 9]        // insertion sort
    
  • 5

    由于类似于我描述here的原因,以下排序函数 sort6_iterator()sort10_iterator_local() 应该运行良好,其中排序网络取自here

    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 迭代器 .

  • 87

    (跟进HelloWorld的建议,研究排序网络 . )

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

    function sortNet10(data) {	// ten-input sorting network by Waksman, 1969
        var swap;
        if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
        if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
        if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
        if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
        if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
        if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
        if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
        if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
        if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
        if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
        if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
        if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
        if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
        if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
        if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
        if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
        if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
        if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
        if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
        if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
        if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
        if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
        if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
        if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
        if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
        if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
        if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
        if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
        if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
        return(data);
    }
    
    alert(sortNet10([5,7,1,8,4,3,6,9,2,0]));
    

    这是网络的图形表示,分为独立的阶段 .

    10-input sorting network (Waksman, 1969)

    为了利用并行处理,可以将5-4-3-4-4-4-3-2分组改为4-4-4-4-4-4-3-2分组 .

    10-input sorting network (Waksman, 1969) re-grouped

  • 25

    使用具有4个组比较的排序网络,因此您可以在SIMD寄存器中执行此操作 . 一对压缩的最小/最大指令实现了压缩比较器功能 . 抱歉,我现在没有时间寻找一个我记得看过这个页面的页面,但希望在SIMD或SSE排序网络上搜索会有所改变 .

    对于四个32位整数的向量,x86 SSE确实具有打包的32位整数最小和最大指令 . AVX2(Haswell和更高版本)具有相同的但是对于具有8个整数的256b向量 . 还有有效的随机指示 .

    如果你有很多独立的小分类,可能可以使用向量并行进行4或8种分类 . ESP . 如果你随机选择元素(所以要分类的数据无论如何都不会在内存中连续),你可以避免随机播放,只需按照你需要的顺序进行比较 . 10个寄存器用于保存4个(AVX2:8)10个整数列表中的所有数据,但仍有6个reg用于暂存空间 .

    如果您还需要对关联数据进行排序,则向量排序网络效率较低 . 在这种情况下,最有效的方法似乎是使用packed-compare来获取哪些元素已更改的掩码,并使用该掩码来混合(引用)关联数据的向量 .

  • 33

    那么展开的无分支选择排序怎么样?

    #include <iostream>
    #include <algorithm>
    #include <random>
    
    //return the index of the minimum element in array a
    int min(const int * const a) {
      int m = a[0];
      int indx = 0;
      #define TEST(i) (m > a[i]) && (m = a[i], indx = i ); 
      //see http://stackoverflow.com/a/7074042/2140449
      TEST(1);
      TEST(2);
      TEST(3);
      TEST(4);
      TEST(5);
      TEST(6);
      TEST(7);
      TEST(8);
      TEST(9);
      #undef TEST
      return indx;
    }
    
    void sort( int * const a ){
      int work[10];
      int indx;
      #define GET(i) indx = min(a); work[i] = a[indx]; a[indx] = 2147483647; 
      //get the minimum, copy it to work and set it at max_int in a
      GET(0);
      GET(1);
      GET(2);
      GET(3);
      GET(4);
      GET(5);
      GET(6);
      GET(7);
      GET(8);
      GET(9);
      #undef GET
      #define COPY(i) a[i] = work[i];
      //copy back to a
      COPY(0);
      COPY(1);
      COPY(2);
      COPY(3);
      COPY(4);
      COPY(5);
      COPY(6);
      COPY(7);
      COPY(8);
      COPY(9);
      #undef COPY
    }
    
    int main() {
      //generating and printing a random array
      int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
      std::random_device rd;
      std::mt19937 g(rd());
      std::shuffle( a, a+10, g);
      for (int i = 0; i < 10; i++) {
        std::cout << a[i] << ' ';
      }
      std::cout << std::endl;
    
      //sorting and printing again
      sort(a);
      for (int i = 0; i < 10; i++) {
        std::cout << a[i] << ' ';
      } 
    
      return 0;
    }
    

    http://coliru.stacked-crooked.com/a/71e18bc4f7fa18c6

    唯一相关的行是前两个 #define .

    它使用两个列表并完全重新检查第一个十次,这将是一个糟糕实现的选择排序,但它避免了分支和可变长度循环,这可以补偿现代处理器和如此小的数据集 .


    基准

    我对排序网络进行了基准测试,我的代码似乎更慢 . 但是我试图删除展开和副本 . 运行此代码:

    #include <iostream>
    #include <algorithm>
    #include <random>
    #include <chrono>
    
    int min(const int * const a, int i) {
      int m = a[i];
      int indx = i++;
      for ( ; i<10; i++) 
        //see http://stackoverflow.com/a/7074042/2140449
        (m > a[i]) && (m = a[i], indx = i ); 
      return indx;
    }
    
    void sort( int * const a ){
      for (int i = 0; i<9; i++)
        std::swap(a[i], a[min(a,i)]); //search only forward
    }
    
    
    void sortNet10(int * const data) {  // ten-input sorting network by Waksman, 1969
        int swap;
        if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
        if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
        if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
        if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
        if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
        if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
        if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
        if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
        if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
        if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
        if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
        if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
        if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
        if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
        if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
        if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
        if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
        if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
        if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
        if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
        if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
        if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
        if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
        if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
        if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
        if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
        if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
        if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
        if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
    }
    
    
    std::chrono::duration<double> benchmark( void(*func)(int * const), const int seed ) {
      std::mt19937 g(seed);
      int a[10] = {10,11,12,13,14,15,16,17,18,19};
      std::chrono::high_resolution_clock::time_point t1, t2; 
      t1 = std::chrono::high_resolution_clock::now();
      for (long i = 0; i < 1e7; i++) {
        std::shuffle( a, a+10, g);
        func(a);
      }
      t2 = std::chrono::high_resolution_clock::now();
      return std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);
    }
    
    int main() {
      std::random_device rd;
      for (int i = 0; i < 10; i++) {
        const int seed = rd();
        std::cout << "seed = " << seed << std::endl;
        std::cout << "sortNet10: " << benchmark(sortNet10, seed).count() << std::endl;
        std::cout << "sort:      " << benchmark(sort,      seed).count() << std::endl;
      }
      return 0;
    }
    

    与分拣网络相比,我一直得到 better result for the branch-less selection sort .

    $ gcc -v
    gcc version 5.2.0 (GCC) 
    $ g++ -std=c++11 -Ofast sort.cpp && ./a.out
    seed = -1727396418
    sortNet10: 2.24137
    sort:      2.21828
    seed = 2003959850
    sortNet10: 2.23914
    sort:      2.21641
    seed = 1994540383
    sortNet10: 2.23782
    sort:      2.21778
    seed = 1258259982
    sortNet10: 2.25199
    sort:      2.21801
    seed = 1821086932
    sortNet10: 2.25535
    sort:      2.2173
    seed = 412262735
    sortNet10: 2.24489
    sort:      2.21776
    seed = 1059795817
    sortNet10: 2.29226
    sort:      2.21777
    seed = -188551272
    sortNet10: 2.23803
    sort:      2.22996
    seed = 1043757247
    sortNet10: 2.2503
    sort:      2.23604
    seed = -268332483
    sortNet10: 2.24455
    sort:      2.24304
    
  • 3

    问题并不是说这是某种基于Web的应用程序 . 引起我注意的一件事是:

    我正在对数十亿个元素的数据集进行采样,每次我需要从中挑选10个数字(简化)并对它们进行排序(并从排序的10个元素列表中得出结论) .

    作为一名软件和硬件工程师,这对我来说绝对是尖叫 . 我不知道你需要从排序的数字集中得出什么样的结论或数据的来源,但我知道在"sort-and-analyze"这些"sort-and-analyze"之间的某个地方进行处理几乎是微不足道的 . 当问题非常适合这种类型的解决方案时,我就是've done FPGA-assisted DNA sequencing work in the past. It is nearly impossible to beat the massive processing power of FPGA' .

    在某种程度上,唯一的限制因素是您可以多快地将数据转换为FPGA以及如何将数据转换为FPGA很快你就可以把它拿出来 .

    作为参考,我设计了一个高性能的实时图像处理器,以每秒约3亿像素的速率接收32位RGB图像数据 . 在从另一端出来之前,数据通过FIR滤波器,矩阵乘法器,查找表,空间边缘检测块和许多其他操作流式传输 . 所有这一切都在一个相对较小的Xilinx Virtex2 FPGA上,内部时钟频率从大约33MHz到如果我没记错,400MHz . 哦,是的,它还有一个DDR2控制器实现并运行了两组DDR2内存 .

    FPGA可以在每个时钟转换时输出一个10位32位数,同时工作在数百MHz . 当数据填满处理管道时,操作开始时会有短暂的延迟 . 之后,您应该能够每个时钟获得一个结果 . 或者更多,如果可以通过复制排序和分析管道来并行化处理 . 原则上,解决方案几乎是微不足道的 .

    重点是:如果应用程序不受PC限制,并且数据流和处理与FPGA解决方案“兼容”(独立或作为机器中的协处理器卡),那么您无法继续使用无论算法如何,用任何语言编写的软件都能够达到可达到的性能水平 .

    EDIT:

    只是快速搜索并找到了一篇可能对你有用的论文 . 看起来它可以追溯到2012年 . 今天你可以做得更好(甚至当时) . 这里是:

    Sorting Networks on FPGAs

  • 209

    我最近写了一个little class,它使用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;
    }
    

    请注意,我们为min和max明确编写了三元运算符,而不是 if (compare) swap 语句 . 这有助于推动编译器使用无分支代码 .

    基准

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

    对随机数据进行排序

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

    Hardcoded Sort Net 10 : 88.774 ms
    Templated Bose-Nelson sort 10 : 27.815毫秒

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

    分类100万个不同大小的数组的时间(以毫秒为单位) .
    大小为2,4,8的数组的毫秒数分别为1.943,8.655,20.246 .

    C++ Templated Bose-Nelson Static Sort timings

    对于展开的插入排序,Glenn Teitelbaum的积分 .

    以下是6个元素的小数组的每种平均时钟数 . 可以在此问题中找到基准代码和示例:
    Fastest sort of fixed length 6 int array

    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个元素的问题中最快的例子一样快 .

    用于排序已排序数据的性能

    通常,输入数组可能已经排序或大部分排序 .
    在这种情况下,插入排序可能是更好的选择 .

    enter image description here

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

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

  • 0

    你可以完全展开 insertion sort

    为了使这更容易,递归 template 可以使用没有函数开销 . 由于它已经是 templateint 也可以是 template 参数 . 这也使得编码阵列大小不是十分微不足道的 .

    请注意,要排序 int x[10] ,调用是 insert_sort<int, 9>::sort(x); ,因为该类使用最后一项的索引 . 这可以包装,但这将是更多的代码来阅读 .

    template <class T, int NUM>
    class insert_sort;
    
    template <class T>
    class insert_sort<T,0>
    // stop template recursion
    // sorting 1 item is a no-op
    {
    public:
        static void place(T *x) {}
        static void sort(T * x) {}
    };
    
    template <class T, int NUM>
    class insert_sort
    // use template recursion to do insertion sort
    // NUM is the index of the last item, eg. for x[10] call <9>
    {
    public:
        static void place(T *x)
        {
            T t1=x[NUM-1];
            T t2=x[NUM];
            if (t1 > t2)
            {
                x[NUM-1]=t2;
                x[NUM]=t1;
                insert_sort<T,NUM-1>::place(x);
            }
        }
        static void sort(T * x)
        {
            insert_sort<T,NUM-1>::sort(x); // sort everything before
            place(x);                    // put this item in
        }
    };
    

    在我的测试中,这比排序网络示例更快 .

  • 20

    处理此固定大小时,请查看Sorting Networks . 这些算法具有固定的运行时,并且与其输入无关 . 对于您的用例,您没有某些排序算法所具有的开销 .

    Bitonic sort是此类网络的实现 . 这个最适合在CPU上使用len(n)<= 32 . 在更大的输入上,您可以考虑转向GPU . https://en.wikipedia.org/wiki/Sorting_network

    顺便说一句,这是一个比较排序算法的好页面(尽管它缺少 bitonic sort .

    http://www.sorting-algorithms.com

  • 0

    尽管网络排序在小型阵列上具有很快的快速成功率,但如果经过适当优化,有时您无法击败插入排序 . 例如,具有2个元素的批量插入:

    {
        final int a=in[0]<in[1]?in[0]:in[1];
        final int b=in[0]<in[1]?in[1]:in[0];
        in[0]=a;
        in[1]=b;
    }
    for(int x=2;x<10;x+=2)
    {
        final int a=in[x]<in[x+1]?in[x]:in[x+1];
        final int b=in[x]<in[x+1]?in[x+1]:in[x];
        int y= x-1;
    
        while(y>=0&&in[y]>b)
        {
            in[y+2]= in[y];
            --y;
        }
        in[y+2]=b;
        while(y>=0&&in[y]>a)
        {
            in[y+1]= in[y];
            --y;
        }
        in[y+1]=a;
    }
    

相关问题