精华内容
参与话题
问答
  • 双调排序

    2017-09-19 13:34:41
    前言今天一次偶然的机会学习到了双调排序,还是感觉很有趣的,这种排序算法可以达到O(n(logn)(logn))的时间复杂度,更重要的是这种算法很好地支持了并发计算。 循环对S1,S2再使用相同的方法,直到S1与S2只有1...

    前言

    今天一次偶然的机会学习到了双调排序,还是感觉很有趣的,这种排序算法可以达到O(n(logn)(logn))的时间复杂度,更重要的是这种算法很好地支持了并发计算。
    这里写图片描述
    这里写图片描述
    循环对S1,S2再使用相同的方法,直到S1与S2只有1元素,再重新整合起来即可。但是我们需要先使用某种方法先让数列成为一个双调序列。
    具体的方法是:从小到大聚合
    显然当数列只有一个元素时,就已经是一个特殊的双调序列了,我们此时把这些只含单个元素的数列相邻不重叠的两两比较形成:递增、递减、递增、递减•••交替出现的数列。
    然后我们再把这个数列相邻不重叠4个为一组。组内依次为递增、递减、递增、递减•••
    然后再把相邻两个双调子数列合并成同一个,最后只就剩下左边递增、右边递减的双调数列。再把这两个大的子序列整合起来就是一个有序数列啦.

    举例:

    A={5,2,1,7,3,8,6,4}:
    第一步,将A里面的相邻两个元素两两比较,两个数为一组,各组内有序,各组为升序、降序交替。
    A={2,5,7,1,3,8,6,4}
    第二步:在第一步的基础上,两个组各并为一个大组,大组内有序,大组与大组之间升序、降序交替出现。
    前两个小组组成一个大组:A’={2,5,7,1}
    后两个小组组成一个大组:B’={3,8,6,4}
    我们让A’升序,B’降序。
    首先:
    A’={2,5,7,1}
    A’已经是一个双调序列了,先增后减。
    那么我们把A’的前一半记做:A’L={2,5},后一半记做:A’R={7,1}
    则对于A’来说:
    S1={min(2,7),min(5,1)}={2,1}
    我们再将S1分成两部分:S1’L={1},S1’R={2}
    那么对于S1={2,1}:
    它的S1={min(2,1)}={1},S2={max(2,1)}={2};
    所以S1={2,1}最后成为{1,2}内部升序。
    S2={max(2,7),max(5,1)}={7,5}
    那么对于S2={7,5}:
    它的S1={min(7,5)}={5},S2={max(7,5)}={7}
    所以S2={7,5}最终变换为{5,7}
    此时A’L=S1,S2={1,2},{,5,7}=>{1,2,5,7} 前面一个组已经升序。

    再看后面一个组B:需要成为降序
    B’={3,8,6,4},
    把B’分成两边:B’L={3,8},B’R={6,4}
    则S1={max(3,6),max(8,4)}={6,8}
    S2={min(3,6),min(8,4)}={3,4}
    对于S1再进行双调排序,同时排序为降序:S1={8,6}
    同理:S2={4,3}
    所以B’=S1,S2={8,6,4,3}
    所以A=A’,B’={1,2,5,7,8,6,4,3}
    此时A已经是一个双调序列了,两个大组,第一大组A’先增,第二个大组B’后减。
    再将两个大组合成一个更大的组A’,B’让它递增。可以发现A’B’就是构成了A本身。
    A={1,2,5,7,8,6,4,3}
    左边:L={1,2,5,7}
    右边:R={8,6,4,3}
    S1={1,2,4,3} =>{1,2,4,3}=>{1,2,3,4}
    S2={8,6,5,7}=>{5,6,8,7}=>{5,6,7,8}
    最后:A=S1,S2={1,2,3,4,5,6,7,8}

    为什么说它很好支持并发呢?
    由上面,我们可以知道,当一个序列是双调时,生成出S1,S2后。S1与S2已经是分离开来了,S2的任何元素都大于S1的任何元素。所以在S1,S2内部的排序中,可以使用两个线程分别处理其中的一个,并发的执行。

    处理数列长度不是2的幂情况

    上面的性质利用的是 数列长度为2的幂的特殊双调序列的性质,当长度不为2的幂可以使用很大的标志数填充原序列,直到序列的长度为2的幂,只取前原长度个数即是原序列的排序。

    代码:

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <malloc.h>
    #include <iostream>
    using namespace std;
    
    #define DBMAX   ((unsigned short)((1 << (15 - _DOFF)) - 1))
    
    //定义Double 可以表示的最大值.用于填充。注意并不float max.因为 传入的参数可能会取值到float max。
    
    void print(float *d, int l, int r, int epoch = 0)
    {
        printf("epoch %d:\n", epoch);
        for (int i = l; i < r; i++)
        {
            printf("%f  ", d[i]);
        }
        printf("\n");
    }
    
    void biSort(float * d, int l, int r, int order = 0)
    //order=0升序,order=1降序
    //l是左起点,r是右结束点的后一个[l,r),左开右闭
    //该函数将d[l]~d[r-1]的元素按序order进行双调排序
    {
        int rr = r;
        int ll = l;
        int n = r - l;//真实的长度
        int step = 0;
        int sec = 1;
        while (sec < n)
        {
            sec = sec * 2;//分区数,对于组内,先分成sec组
            step = n / sec;//每组含有step个元素
                            //step会越来越小,其实就是越来越是相邻的数据进行比较
            for (int ii = 0; ii < sec; ii+=2)
                //每个区进行处理
            {
                l = ll + ii*step;
                r = l + step;
                if (order == 0)
                    //升序处理
                {
                    for (int i = 0; i < step; i++)
                    {
                        if (d[i + l] != d[i + l] || d[i + l + step] != d[i + l + step])
                            //sqrt(-1),处理纯虚数
                        {
                            continue;
                        }
                        float min = d[i + l]<d[i + step + l] ? d[i + l] : d[i + step + l];
                        float max = d[i + l]>d[i + step + l] ? d[i + l] : d[i + step + l] ;
                        d[i + l] = min;//小的放s1
                        d[i + l + step] = max;//大的放s2
                    }
                }
                else
                    //降序处理
                {
                    for (int i = 0; i < step; i++)
                        //递减序列
                    {
                        if (d[i + l] != d[i + l] || d[i + l + step] != d[i + l + step])
                            //sqrt(-1),处理是否是虚数
                        {
                            continue;
                        }
                        float min = d[i + l]<d[i + step + l] ? d[i + l] : d[i + step + l];
                        float max = d[i + l]>d[i + step + l] ? d[i + l] : d[i + step + l];
                        d[i + l] = max;
                        d[i + l + step] = min;
                    }
                }
    
            }
        }
    
    }
    void semiSort(float * data, int l, int r)
    {
        int num = r - l;
        int expnum = pow(2.0,int( log2(num*1.0)+0.5));
        float *dd=data;
        if (num!=expnum)
        {
            dd = (float*)malloc(expnum*sizeof(float));
            for (int i = 0; i<expnum; i++)
            {
                if (i<num)
                {
                    dd[i] = data[i+l];
                }
                else
                {
                    dd[i] = DBMAX;
                }
            }
    
        }
        //以上在进行必要的填充
        int batch = expnum;//expect number ,把目前的元素分成几组进行双调排序
        char flag = 0;//用于标记降序和升序
        int Cnt = 0;
        while (batch>1)
        {
            batch = batch / 2;//每一次迭代,组数都会减半。
            int num_of_each_batch = expnum / batch;//每一组的元素个数
            for (int j = 0; j < batch; j++)
            {
                int start; 
                int end;
                if (dd == data)
                    //没有动态分配的则需要偏移
                {
                    start = l + j*num_of_each_batch;
                }
                else
                {
                    start = j*num_of_each_batch;    
                }
                end = start + num_of_each_batch;
                biSort(dd, start, end, flag);//调用biSort进行双调排序
    
                print(dd, 0, expnum, Cnt += 1);
                flag = !flag;//升序和降序的符号相反
            }
        }
        if (dd!=data)
        {
            for (int i = l; i < r;i++)
            {
                data[i] = dd[i-l];
            }
            free(dd);
        }
    }
    void segmentedBitonicSort(float* data, int* seg_id, int* seg_start, int n, int m)
    //分段
    {
    
        for (int i = 0; i < m; i++)
        {
            int l = seg_start[i];
            int r = seg_start[i + 1];
            semiSort(data, l, r);
        }
    }
    
    int main()
    {
        float data[] = { 5, 2, 1, 7, 3, 8, 6, sqrt(-1) };
        int seg_id[] = { 0, 0, 0,0,0,0,0,0};
        int seg_start[] = { 0, 8 };
        int n = 8;
        int m = 1;
        int l = 0;
        int r = sizeof(data) / sizeof(float);
        segmentedBitonicSort(data, seg_id, seg_start, n, m);
        //print(data, l, r);
        //float d[] = { 0.4, 0.6, 0.5 };
        //semiSort(d, 0, 3);
        //print(d,0,3);
        system("pause");
        return 0;
    }
    

    并没使用递归,可以处理输入为sqrt(-1)

    展开全文
  • 双调排序详解

    2018-09-25 17:03:40
    双调排序的详解,还是比较容易看懂的,可用于cuda并行算法(png)
  • 分段双调排序

    2018-06-10 20:39:43
    今天在https://blog.csdn.net/u014226072/article/details/56840243上看到一个关于分段双调排序的问题....用C/C++ 编写一个分段双调排序(Bitonic sort)函数,对每一段内部的浮点数进行排序,但不要改变段...

    今天在"https://blog.csdn.net/u014226072/article/details/56840243"上看到一个关于分段双调排序的问题. 抄录如下:

    问题说明:

    ***********************

    给出分成m段的n个浮点数,输入数据已按段号有序,但每段内部无序。用C/C++ 编写一个分段双调排序(Bitonic sort)函数,对每一段内部的浮点数进行排序,但不要改变段间的位置。

    接口方式:

    ***********************

    void segmentedBitonicSort(float* data, int*seg_id, int* seg_start, int n, int m);

    输入数据中,data包含需要分段排序的n个float值,seg_id给出data中n个元素各 自所在的 段编号。seg_start共有m+1个元素,前m个分别给 出0..m-1共m个段的起 始位置,seg_start[m]保证等于n。

    seg_id中的元素保证单调不下降,即对任意的i<j,seg_id[i]<=seg_id[j]。 seg_id所有元 素均在0到m-1范围内。

    输出结果覆盖data,保证每一段内排序,但不改变段间元素的顺序。

    注意:

    ***********************

    1、必须使用双调排序算法进行排序。

    2、可以直接使用从网上下载的双调排序代码,但须注明出处。

    样例输入:

    ***********************

    float data[5]={0.8, 0.2, 0.4, 0.6, 0.5};

    int seg_id[5]={0,   0,  1,   1,   1}

    int seg_start[3]={0,2,5};

    int n=5;

    int m=2;

    样例输出:

    ***********************

    float data[5]={0.2, 0.8, 0.4, 0.5, 0.6};

    加分挑战(非必需):

    ***********************

    1、不递归:segmentedBitonicSort函数及其所调用的任何其他函数都不得直接或间接地进行递归。

    2、不调用函数:segmentedBitonicSort不调用除标准库函数外的任何其他函数。

    3、内存高效:segmentedBitonicSort及其所调用的任何其他函数都不得进行动态内存分配,包括malloc、new和静态定义的STL容器。

    4、可并行:segmentedBitonicSort涉及到的所有时间复杂度O(n)以上的代码都写 在for循 环中,而且每个这样的for循环内部的循环顺序可 以任意改变,不影响程 序结果。注:自己测试时可以用rand()决定循环顺序。

    5、不需内存:segmentedBitonicSort不调用任何函数(包括C/C++标准库函数), 不使用全局变量,所有局部变量都是int、float或指针类 型,C++程序不使用new关键字。

    6、绝对鲁棒:在输入数据中包含NaN时(例如sqrt(-1.f)),保证除NaN以外 的数 据正确排序,NaN的个数保持不变。

    你的程序每满足以上的一个条件都可以获得额外的加分。

    为此, 我们先了解一下双调排序. 下图来自于:

    https://www.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_overview.html


    双调排序是一种基于比较的可并行的排序算法. 

    第一点, 如果一个序列前半部分和后半部分都单调, 那么称它为一个双调序列. (图中红色部分是前半部分, 递增. 蓝色部分递减)
    第二点, 对一个双调序列, 依次比较两个单调部分的对应位置的元素, 视比较结果交换位置. 可以得到两个序列(s1和s2). 
    第三点, 这两个序列都是双调序列, 并且前一个双调序列的每个元素都小于后一个双调序列. 
    第四点, 此时, 对于整个数组来说, 前部分小于(同理也可以是大于)后半部分. 那么我们可以递归地使用这种拆分双调序列的方法, 直到序列长度为1, 这时, 整个数组将是有序的. 
    ------
    但是我们需要排序的数组并不一定一开始就是双调序列的, 所以要应用这个排序方法还需要换个思考方式. 
    - 注意, 长度为1的序列可以看作是单调的, 那么, 长度为2的序列一定是双调序列. 
    - 双调序列可以排序, 所以我们先给这些长度为2的双调序列排序. 

    - 排序的时候, 如果排序的方式我们选择递增和递减交替. 排序结束时, 我们将得到长度为4的双调序列. 


    好了, 问题已经解决了. 我们终将得到长度为n的双调序列, 也就是把原数组变成了双调序列. 当然, 值得一提的是, 这种方法只能给长度为2的整数次幂的数组排序, 对于一个任意的数组, 需要用一个较大的值填充至长度为2^n之后才能用这种方法. 

    不严格的时间复杂度分析: 容易看出, 给一个双调序列排序的时间复杂度是nlogn(一共logn轮比较), 而为了使原数组变成双调序列, 我们要进行logn轮, 每轮n/len个长度为len的排序, 其中在第i轮时, len=logi. 所以有一个很明显的上界O(n*logn*logn). 但是这是串行分析的结果. 事实上在并行条件下可以大大加速. 


    具体到这道题, 一个很容易想到的思路是把seg_id当作第一关键字, data当作第二关键字, 把整个数组补齐到2^n后整体排序. 据此, 可以很容易写出满足不递归, 不调用函数, 可并行, 绝对鲁棒的代码. 目前我还想不到如何不动态分配内存. 关于绝对鲁棒, 我是采用手动设置nan大于任何数字来避免因nan而出现排序错乱的问题的. 


    但是这里还可以再有一点改进, 我们可以分别给每一段排序. 这样可以把时间复杂度从O(n*log^2n)降为近似O(m * n/m * log^2(n/m)). 所需额外空间也更少. 

    最终代码如下:

    #include <cstdio>
    #include <stdlib.h>
    #include <time.h>
    #include <assert.h>
    #include <cmath>
    #include <iostream>
    
    #define SEGN 50
    #define SEGLEN 50
    
    #define nan (std::sqrt(-1.f))
    
    //#define debug
    
    void seg3(float* data, int* seg_id, int* seg_start, int n, int m) 
    {
        //#ifdef debug
        printf("seg3:\nn = %d, m = %d\n", n, m);
        for (int i = 0; i < n; i++) std::cout << data[i] << ", ";
        printf("\n");
        for (int i = 0; i < n; i++) printf("%d, ", seg_id[i]);
        printf("\n");
        for (int i = 0; i <= m; i++) printf("%d, ", seg_start[i]);
        printf("\n");
        //#endif
        
        for (int seg = 0; seg < m; seg++) {
            int curlen = seg_start[seg + 1] - seg_start[seg];
            int pow = 0;
            int tempn = curlen;
            while (tempn) {
                tempn >>= 1;
                pow++;
            }
            tempn = (1 << pow);
            if (tempn == (curlen << 1)) {
                tempn >>= 1;
            }
            int endid = seg_start[seg] + tempn;
            float* datab;
            int* segb;
            if (endid > n) {
                datab = (float*)malloc(sizeof(float) * (endid - n));
                segb = (int*)malloc(sizeof(int) * (endid - n));
                for (int i = 0; i < endid - n; i++) {
                    segb[i] = m;
                }
            }
            else {
                datab = data + seg_start[seg + 1];
                segb = seg_id + seg_start[seg + 1];
            }
            // sort begin
            for (int s = 2; s <= tempn; s *= 2) {
                for (int itr = 0; itr < tempn; itr += s * 2) {
                    // mergeup(arr+i, s)
                    // float* arr = data + i;
                    int offset = itr + seg_start[seg];
                    int len = s;
                    // begin
                    int step = len / 2, i, j, k, temp;
                    float tempf;
                    while (step > 0) {
                        for (i = 0; i < len; i += step * 2) {
                            for (j = i, k = 0; k < step; j++, k++) {
                                // if arr[j] > arr[j + step], swap
                                int* seg_add_j = offset + j < n ? seg_id + offset + j : segb + offset + j - n;
                                int* seg_add_js = offset + j + step < n ? seg_id + offset + j + step : segb + offset + j + step - n;
                                float* data_add_j = offset + j < n ? data + offset + j : datab + offset + j - n;
                                float* data_add_js = offset + j + step < n ? data + offset + j + step : datab + offset + j + step - n;
                                bool swap = false;
                                
                                if (*seg_add_j > *seg_add_js) {
                                    swap = true;
                                }
                                else if (*seg_add_j == *seg_add_js) {  
                                    if (*data_add_j > *data_add_js) {
                                        swap = true;
                                    }
                                    else if (!(*data_add_j > 0) && !(*data_add_j <= 0)) {
                                        // *data_add_j = nan
                                        swap = true;
                                    }
                                }
                                
                                if (swap) {
                                    temp = *seg_add_j;
                                    *seg_add_j = *seg_add_js;
                                    *seg_add_js = temp;
                                    tempf = *data_add_j;
                                    *data_add_j = *data_add_js;
                                    *data_add_js = tempf;
                                }
                            }
                        }
                        step >>= 1;
                    }
                    //mergedown(arr+i+s,s)
                    //arr = data + i + s;
                    if (s == tempn) continue;
                    offset = itr + len + seg_start[seg];
                    step = len / 2;
                    // begin
                    while (step > 0) {
                        for (i = 0; i < len; i += step * 2) {
                            for (j = i, k = 0; k < step; j++, k++) {
                                // if arr[j] < arr[j + step], swap
                                int* seg_add_j = offset + j < n ? seg_id + offset + j : segb + offset + j - n;
                                int* seg_add_js = offset + j + step < n ? seg_id + offset + j + step : segb + offset + j + step - n;
                                float* data_add_j = offset + j < n ? data + offset + j : datab + offset + j - n;
                                float* data_add_js = offset + j + step < n ? data + offset + j + step : datab + offset + j + step - n;
                                
                                bool swap = false;
                                if (*seg_add_j < *seg_add_js) {
                                    swap = true;
                                }
                                else if (*seg_add_j == *seg_add_js) {  
                                    if (*data_add_j < *data_add_js) {
                                        swap = true;
                                    }
                                    else if (!(*data_add_js > 0) && !(*data_add_js <= 0)) {
                                        // *data_add_js = nan
                                        swap = true;
                                    }
                                }
                                
                                if (swap) {
                                    temp = *seg_add_j;
                                    *seg_add_j = *seg_add_js;
                                    *seg_add_js = temp;
                                    tempf = *data_add_j;
                                    *data_add_j = *data_add_js;
                                    *data_add_js = tempf;
                                }
                            }
                        }
                        step >>= 1;
                    }
                }
            }
            if (endid > n) {
                free(datab);
                free(segb); 
            }
        }
    }
    
    int main() {
        #ifdef debug
        float data[] = {1.08344, 2.6747, nan, 1.94815, 1.11102, 0.289917, 0.64205,
        6.59573, 0.00369898, 12.7636, 1.56606, 0.0572074, 0.380153, nan, 2.96348,
        3.89681, nan, 2.27465, 1.71466, 3.69074, 0.351484};
      int seg_id[] = {0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4};
      int seg_start[] = {0, 5, 7, 11, 16, 21};
      int n = 21;
      int m = 5;
      seg3(data, seg_id, seg_start, n, m);
            for (int j = 0; j < n; j++) {
                std::cout << data[j] << ' ';
            }
            std::cout << std::endl;
            //
            bool wrong = false;
            for (int j = 1; j < n; j++) {
                if (seg_id[j] < seg_id[j - 1]) {
                    wrong = true;
                    break;
                }
                
                if (!(seg_id[j] > seg_id[j - 1] || (!(data[j] < data[j - 1])))) {
                    std::cout << "j :" << j << std::endl;
                    std::cout << data[j] << ' ' << data[j-1] << std::endl;
                    std::cout << seg_id[j] << ' ' << seg_id[j-1] << std::endl;
                    wrong = true;
                    break;
                }
            }
            if (wrong) std::cerr << "wrong^" << std::endl;
        #else
        srand((unsigned)time(NULL));
        // test 
        float* data;
        int* seg_id;
        int* seg_start;
        int n;
        int m;
        for (int i = 0; i < 10; i++) {
            m = rand() % SEGN + 5;
            seg_start = (int*)malloc(sizeof(int) * (m + 1));
            seg_start[0] = 0;
            for (int j = 1; j <= m; j++) {
                seg_start[j] = rand() % SEGLEN + 1 + seg_start[j-1];
            }
            n = seg_start[m];
            seg_id = (int*)malloc(sizeof(int)*n);
            data = (float*)malloc(sizeof(float)*n);
            for (int j = 1; j <= m; j++) {
                for (int k = seg_start[j - 1]; k < seg_start[j]; k++) {
                    seg_id[k] = j - 1;
                }
            }
            for (int j = 0; j < n; j++) {
                float tempf = 1.0 * rand() / rand();
                if (tempf < 0.6 && tempf > 0.4) {
                    data[j] = std::sqrt(-1.f);
                    //data[j] = 0.5;
                }
                else {
                    data[j] = tempf;
                }
            }
            // 
            seg3(data, seg_id, seg_start, n, m);
            //
            for (int j = 1; j < n; j++) {
                assert(seg_id[j] >= seg_id[j - 1]);
                assert(seg_id[j] > seg_id[j - 1] || (!(data[j] < data[j - 1])));
            }
            free(seg_start);
            free(seg_id);
            free(data);
        }
        #endif
        return 0;
    }



    后来我又找到两篇文章, 实现了不用动态分配内存的任意长度数组双调排序, 以后有时间试试把它改为不调用函数的形式. 
    https://blog.csdn.net/ljiabin/article/details/8631374
    https://blog.csdn.net/lqmiku/article/details/78834178


    Ref:
    https://blog.csdn.net/u014226072/article/details/56840243
    https://www.cs.rutgers.edu/~venugopa/parallel_summer2012/bitonic_overview.html

    展开全文
  • cuda双调排序

    千次阅读 2015-03-28 17:36:36
    #include "cuda_runtime.h" #include "device_launch_parameters.h" #include "device_functions.h" #include #include #include #define SHARED_SIZE_LIMIT 1024U #define UMUL(a, b) __umul24((a), (b)) ...
    #include "cuda_runtime.h"
    #include "device_launch_parameters.h"
    #include "device_functions.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include<assert.h>
    #define SHARED_SIZE_LIMIT 1024U
    #define    UMUL(a, b) __umul24((a), (b))
    #define UMAD(a, b, c) ( UMUL((a), (b)) + (c) )
    typedef unsigned int uint;
    
    __device__ inline void Comparator(
        uint &keyA,
        uint &valA,
        uint &keyB,
        uint &valB,
        uint dir
    )
    {
        uint t;
    
        if ((keyA > keyB) == dir)
        {
            t = keyA;
            keyA = keyB;
            keyB = t;
            t = valA;
            valA = valB;
            valB = t;
        }
    }
    __global__ void bitonicSortShared(
        uint *d_DstKey,
        uint *d_DstVal,
        uint *d_SrcKey,
        uint *d_SrcVal,
        uint arrayLength,
        uint dir
    )
    {
        //Shared memory storage for one or more short vectors
        __shared__ uint s_key[SHARED_SIZE_LIMIT];
        __shared__ uint s_val[SHARED_SIZE_LIMIT];
    
        //Offset to the beginning of subbatch and load data
        d_SrcKey += blockIdx.x * SHARED_SIZE_LIMIT + threadIdx.x;
        d_SrcVal += blockIdx.x * SHARED_SIZE_LIMIT + threadIdx.x;
        d_DstKey += blockIdx.x * SHARED_SIZE_LIMIT + threadIdx.x;
        d_DstVal += blockIdx.x * SHARED_SIZE_LIMIT + threadIdx.x;
        s_key[threadIdx.x +                       0] = d_SrcKey[                      0];
        s_val[threadIdx.x +                       0] = d_SrcVal[                      0];
        s_key[threadIdx.x + (SHARED_SIZE_LIMIT / 2)] = d_SrcKey[(SHARED_SIZE_LIMIT / 2)];
        s_val[threadIdx.x + (SHARED_SIZE_LIMIT / 2)] = d_SrcVal[(SHARED_SIZE_LIMIT / 2)];
    
        for (uint size = 2; size < arrayLength; size <<= 1)
        {
            //Bitonic merge
            uint ddd = dir ^ ((threadIdx.x & (size / 2)) != 0);
    
            for (uint stride = size / 2; stride > 0; stride >>= 1)
            {
                __syncthreads();
                uint pos = 2 * threadIdx.x - (threadIdx.x & (stride - 1));
                Comparator(
                    s_key[pos +      0], s_val[pos +      0],
                    s_key[pos + stride], s_val[pos + stride],
                    ddd
                );
            }
        }
    
        //ddd == dir for the last bitonic merge step
        {
            for (uint stride = arrayLength / 2; stride > 0; stride >>= 1)
            {
                __syncthreads();
                uint pos = 2 * threadIdx.x - (threadIdx.x & (stride - 1));
                Comparator(
                    s_key[pos +      0], s_val[pos +      0],
                    s_key[pos + stride], s_val[pos + stride],
                    dir
                );
            }
        }
    
        __syncthreads();
        d_DstKey[                      0] = s_key[threadIdx.x +                       0];
        d_DstVal[                      0] = s_val[threadIdx.x +                       0];
        d_DstKey[(SHARED_SIZE_LIMIT / 2)] = s_key[threadIdx.x + (SHARED_SIZE_LIMIT / 2)];
        d_DstVal[(SHARED_SIZE_LIMIT / 2)] = s_val[threadIdx.x + (SHARED_SIZE_LIMIT / 2)];
    }
    
    
    
    
    // Bitonic sort kernel for large arrays (not fitting into shared memory)
    
    //Bottom-level bitonic sort
    //Almost the same as bitonicSortShared with the exception of
    //even / odd subarrays being sorted in opposite directions
    //Bitonic merge accepts both
    //Ascending | descending or descending | ascending sorted pairs
    __global__ void bitonicSortShared1(
        uint *d_DstKey,
        uint *d_DstVal,
        uint *d_SrcKey,
        uint *d_SrcVal
    )
    {
        //Shared memory storage for current subarray
        __shared__ uint s_key[SHARED_SIZE_LIMIT];
        __shared__ uint s_val[SHARED_SIZE_LIMIT];
    
        //Offset to the beginning of subarray and load data
        d_SrcKey += blockIdx.x * SHARED_SIZE_LIMIT + threadIdx.x;
        d_SrcVal += blockIdx.x * SHARED_SIZE_LIMIT + threadIdx.x;
        d_DstKey += blockIdx.x * SHARED_SIZE_LIMIT + threadIdx.x;
        d_DstVal += blockIdx.x * SHARED_SIZE_LIMIT + threadIdx.x;
        s_key[threadIdx.x +                       0] = d_SrcKey[                      0];
        s_val[threadIdx.x +                       0] = d_SrcVal[                      0];
        s_key[threadIdx.x + (SHARED_SIZE_LIMIT / 2)] = d_SrcKey[(SHARED_SIZE_LIMIT / 2)];
        s_val[threadIdx.x + (SHARED_SIZE_LIMIT / 2)] = d_SrcVal[(SHARED_SIZE_LIMIT / 2)];
    
        for (uint size = 2; size < SHARED_SIZE_LIMIT; size <<= 1)
        {
            //Bitonic merge
            uint ddd = (threadIdx.x & (size / 2)) != 0;
    
            for (uint stride = size / 2; stride > 0; stride >>= 1)
            {
                __syncthreads();
                uint pos = 2 * threadIdx.x - (threadIdx.x & (stride - 1));
                Comparator(
                    s_key[pos +      0], s_val[pos +      0],
                    s_key[pos + stride], s_val[pos + stride],
                    ddd
                );
            }
        }
    
        //Odd / even arrays of SHARED_SIZE_LIMIT elements
        //sorted in opposite directions
        uint ddd = blockIdx.x & 1;
        {
            for (uint stride = SHARED_SIZE_LIMIT / 2; stride > 0; stride >>= 1)
            {
                __syncthreads();
                uint pos = 2 * threadIdx.x - (threadIdx.x & (stride - 1));
                Comparator(
                    s_key[pos +      0], s_val[pos +      0],
                    s_key[pos + stride], s_val[pos + stride],
                    ddd
                );
            }
        }
    
    
        __syncthreads();
        d_DstKey[                      0] = s_key[threadIdx.x +                       0];
        d_DstVal[                      0] = s_val[threadIdx.x +                       0];
        d_DstKey[(SHARED_SIZE_LIMIT / 2)] = s_key[threadIdx.x + (SHARED_SIZE_LIMIT / 2)];
        d_DstVal[(SHARED_SIZE_LIMIT / 2)] = s_val[threadIdx.x + (SHARED_SIZE_LIMIT / 2)];
    }
    
    //Bitonic merge iteration for stride >= SHARED_SIZE_LIMIT
    __global__ void bitonicMergeGlobal(
        uint *d_DstKey,
        uint *d_DstVal,
        uint *d_SrcKey,
        uint *d_SrcVal,
        uint arrayLength,
        uint size,
        uint stride,
        uint dir
    )
    {
        uint global_comparatorI = blockIdx.x * blockDim.x + threadIdx.x;
        uint        comparatorI = global_comparatorI & (arrayLength / 2 - 1);
    
        //Bitonic merge
        uint ddd = dir ^ ((comparatorI & (size / 2)) != 0);
        uint pos = 2 * global_comparatorI - (global_comparatorI & (stride - 1));
    
        uint keyA = d_SrcKey[pos +      0];
        uint valA = d_SrcVal[pos +      0];
        uint keyB = d_SrcKey[pos + stride];
        uint valB = d_SrcVal[pos + stride];
    
        Comparator(
            keyA, valA,
            keyB, valB,
            ddd
        );
    
        d_DstKey[pos +      0] = keyA;
        d_DstVal[pos +      0] = valA;
        d_DstKey[pos + stride] = keyB;
        d_DstVal[pos + stride] = valB;
    }
    
    //Combined bitonic merge steps for
    //size > SHARED_SIZE_LIMIT and stride = [1 .. SHARED_SIZE_LIMIT / 2]
    __global__ void bitonicMergeShared(
        uint *d_DstKey,
        uint *d_DstVal,
        uint *d_SrcKey,
        uint *d_SrcVal,
        uint arrayLength,
        uint size,
        uint dir
    )
    {
        //Shared memory storage for current subarray
        __shared__ uint s_key[SHARED_SIZE_LIMIT];
        __shared__ uint s_val[SHARED_SIZE_LIMIT];
    
        d_SrcKey += blockIdx.x * SHARED_SIZE_LIMIT + threadIdx.x;
        d_SrcVal += blockIdx.x * SHARED_SIZE_LIMIT + threadIdx.x;
        d_DstKey += blockIdx.x * SHARED_SIZE_LIMIT + threadIdx.x;
        d_DstVal += blockIdx.x * SHARED_SIZE_LIMIT + threadIdx.x;
        s_key[threadIdx.x +                       0] = d_SrcKey[                      0];
        s_val[threadIdx.x +                       0] = d_SrcVal[                      0];
        s_key[threadIdx.x + (SHARED_SIZE_LIMIT / 2)] = d_SrcKey[(SHARED_SIZE_LIMIT / 2)];
        s_val[threadIdx.x + (SHARED_SIZE_LIMIT / 2)] = d_SrcVal[(SHARED_SIZE_LIMIT / 2)];
    
        //Bitonic merge
        uint comparatorI = UMAD(blockIdx.x, blockDim.x, threadIdx.x) & ((arrayLength / 2) - 1);
        uint ddd = dir ^ ((comparatorI & (size / 2)) != 0);
    
        for (uint stride = SHARED_SIZE_LIMIT / 2; stride > 0; stride >>= 1)
        {
            __syncthreads();
            uint pos = 2 * threadIdx.x - (threadIdx.x & (stride - 1));
            Comparator(
                s_key[pos +      0], s_val[pos +      0],
                s_key[pos + stride], s_val[pos + stride],
                ddd
            );
        }
    
        __syncthreads();
        d_DstKey[                      0] = s_key[threadIdx.x +                       0];
        d_DstVal[                      0] = s_val[threadIdx.x +                       0];
        d_DstKey[(SHARED_SIZE_LIMIT / 2)] = s_key[threadIdx.x + (SHARED_SIZE_LIMIT / 2)];
        d_DstVal[(SHARED_SIZE_LIMIT / 2)] = s_val[threadIdx.x + (SHARED_SIZE_LIMIT / 2)];
    }
    
    
    
    
    // Interface function
    
    //Helper function (also used by odd-even merge sort)
    extern "C" uint factorRadix2(uint *log2L, uint L)
    {
        if (!L)
        {
            *log2L = 0;
            return 0;
        }
        else
        {
            for (*log2L = 0; (L & 1) == 0; L >>= 1, *log2L++);
    
            return L;
        }
    }
    
    extern "C" uint bitonicSort(
        uint *d_DstKey,
        uint *d_DstVal,
        uint *d_SrcKey,
        uint *d_SrcVal,
        uint batchSize,
        uint arrayLength,
        uint dir
    )
    {
        //Nothing to sort
        if (arrayLength < 2)
            return 0;
    
        //Only power-of-two array lengths are supported by this implementation
        uint log2L;
        uint factorizationRemainder = factorRadix2(&log2L, arrayLength);
        assert(factorizationRemainder == 1);
    
        dir = (dir != 0);
    
        uint  blockCount = batchSize * arrayLength / SHARED_SIZE_LIMIT;
        uint threadCount = SHARED_SIZE_LIMIT / 2;
    
        if (arrayLength <= SHARED_SIZE_LIMIT)
        {
            assert((batchSize * arrayLength) % SHARED_SIZE_LIMIT == 0);
            bitonicSortShared<<<blockCount, threadCount>>>(d_DstKey, d_DstVal, d_SrcKey, d_SrcVal, arrayLength, dir);
        }
        else
        {
            bitonicSortShared1<<<blockCount, threadCount>>>(d_DstKey, d_DstVal, d_SrcKey, d_SrcVal);
    
            for (uint size = 2 * SHARED_SIZE_LIMIT; size <= arrayLength; size <<= 1)
                for (unsigned stride = size / 2; stride > 0; stride >>= 1)
                    if (stride >= SHARED_SIZE_LIMIT)
                    {
                        bitonicMergeGlobal<<<(batchSize * arrayLength) / 512, 256>>>(d_DstKey, d_DstVal, d_DstKey, d_DstVal, arrayLength, size, stride, dir);
                    }
                    else
                    {
                        bitonicMergeShared<<<blockCount, threadCount>>>(d_DstKey, d_DstVal, d_DstKey, d_DstVal, arrayLength, size, dir);
                        break;
                    }
        }
    
        return threadCount;
    }
    int main(){
    const uint             N = 1048576;
        const uint           DIR = 0;
        const uint     numValues = 65536;
    
    uint *h_InputKey, *h_InputVal, *h_OutputKeyGPU, *h_OutputValGPU;
        uint *d_InputKey, *d_InputVal,    *d_OutputKey,    *d_OutputVal;
    h_InputKey     = (uint *)malloc(N * sizeof(uint));
        h_InputVal     = (uint *)malloc(N * sizeof(uint));
        h_OutputKeyGPU = (uint *)malloc(N * sizeof(uint));
        h_OutputValGPU = (uint *)malloc(N * sizeof(uint));
    
    	   for (uint i = 0; i < N; i++)
        {
            h_InputKey[i] = rand() % numValues;
            h_InputVal[i] = i;
        }
    	 cudaMalloc((void **)&d_InputKey,  N * sizeof(uint));
     cudaMalloc((void **)&d_InputVal,  N * sizeof(uint));
     cudaMalloc((void **)&d_OutputKey, N * sizeof(uint));
     cudaMalloc((void **)&d_OutputVal, N * sizeof(uint));
     cudaMemcpy(d_InputKey, h_InputKey, N * sizeof(uint), cudaMemcpyHostToDevice);
     cudaMemcpy(d_InputVal, h_InputVal, N * sizeof(uint), cudaMemcpyHostToDevice);
    	   
    	   int flag = 1;
    	   for(uint arrayLength = 64;arrayLength<=N;arrayLength*=2){
    		   cudaDeviceSynchronize();
    		   bitonicSort(d_OutputKey,d_OutputVal,d_InputKey,d_InputVal,
    			   N/arrayLength,arrayLength,DIR);
    		   cudaDeviceSynchronize();
    	   }
    	    cudaMemcpy(h_OutputKeyGPU, d_OutputKey, N * sizeof(uint), cudaMemcpyDeviceToHost);
    		cudaMemcpy(h_OutputValGPU, d_OutputVal, N * sizeof(uint), cudaMemcpyDeviceToHost);
    		for(int i=0;i<N;i++){
    		printf("%d %d\n",h_OutputKeyGPU[i],h_OutputValGPU[i]);
    		}
    		 cudaFree(d_OutputVal);
             cudaFree(d_OutputKey);
             cudaFree(d_InputVal);
             cudaFree(d_InputKey);
    		 free(h_OutputValGPU);
    		 free(h_OutputKeyGPU);
    		 free(h_InputVal);
    		 free(h_InputKey);
    		 system("pause");
    		 return 0;
    }

    展开全文
  • 说说双调排序

    千次阅读 2013-11-10 19:23:03
     双调排序(Bitonic Sort)属于排序网络(Sorting Network)的一种,它是一种可以并行计算的排序算法。  要理解双调排序,首先需要理解双调序列,双调序列定义如下:  如果序列满足以下两个条件之一,则称之为...

    一、简介

        双调排序(Bitonic Sort)属于排序网络(Sorting Network)的一种,它是一种可以并行计算的排序算法。

        要理解双调排序,首先需要理解双调序列,双调序列定义如下:

        如果序列<a0, a1, …, an-1>满足以下两个条件之一,则称之为双调序列:™

        存在一个0≤k≤n-1,使得<a0, a1, …, ak-1>为升序序列,<ak, ak+1, …, an-1>为降序序列;或存在一个标号的循环移位,使得条件1)满足。

        如果n为偶数,且<a0, a1, …, an/2-1>为升序序列,<an/2, an/2+1, …, an-1>为降序序列,则以下两个序列都是双调序列

        S1=<min(a0, an/2), min(a1, an/2+1), …, min(an/2-1, an-1)>

        S2=<max(a0, an/2), max(a1, an/2+1), …, max(an/2-1, an-1)>

        双调排序主要思想:

        1、首先不断的二分,直到每组只剩下一个元素,然后开始归并。

        2、双调排序归并时以不大于n的最大2的幂次方2^k为界限,把2^k~n的元素分别与0~(n-2^k)的元素比较,然后再分别在0~2^k和2^k~n这两段上应用比较网络。

        3、双调排序难以理解的地方就在于这个归并的过程,假设我们要把长度为n的序列a升序排列,由于二分时是把前n/2的序列降序排列后n/2的序列升序排列的,而n-2^k < n/2,所以前n-2^k 和后n-2^k个元素都大于中间的元素,当前n-2^k个元素和后n-2^k个元素比较时,会把序列中最大的n-2^k个元素放到最后n-2^k个位置上,也就是说比较后,2^k~n的元素都比0~2^k的元素大,这样在分别对这两段用同样的方法归并,最终得到完整的升序序列。

        以6个元素的序列为例,当前3个元素已经降序排好,后3个元素已经升序排好(递归到底时是从1个元素开始返回的,所以对6个元素归并时前后3个元素已经排好序),这个以4(不大于6的最大2的幂次方)为界限,分别让第1个和第5个、第2个和第6个元素比较,使得这6个元素中最大的两个处于第5、6个位置上,然后再分别对前4个和后2个元素按此方法归并,最终递归完成排序。

    二、算法实现

    //双调归并过程
    template <typename T>
    void BitonicMerge(T* pFirst,T* pLast,bool bDirection)
    {
    	T* pTemp = pFirst;
    	if(pFirst < pLast)
    	{
    		int nLength = pLast - pFirst + 1;                   //计算数组长度
    		int nMid = 1;
    		while(nMid < nLength)                               //计算小于数组长度的2的最大幂次方值k
    			nMid = nMid << 1;
    		nMid = nMid >> 1;
    		for(int i=0;i< nLength - nMid;i++)                  //对元素0~n-k和元素k~n进行比较,根据升序降序标志bDirection对元素进行交换
    		{
    			if((*(pTemp+i) > *(pTemp+i+nMid)) == bDirection)
    			{
    				Swap(*(pTemp+i),*(pTemp+i+nMid));
    			}
    		}
    		BitonicMerge(pFirst,pFirst+nMid-1,bDirection);      //递归对数组前后两部分元素进行双调递归
    		BitonicMerge(pFirst+nMid,pLast,bDirection);
    	}
    }
    
    
    //Bitonic排序(双调排序):属于排序网络(Sorting Network)的一种,它是一种可以并行计算的排序算法。
    //首先,双调序列是指序列要么先单调递增然后再单调递减,要么先单调递减然后又单调递增。
    //通过对要排序的数组构造双调序列,然后递归进行双调归并即可完成对数组的排序
    template <typename T>
    bool BitonicSort(T* pFirst,T* pLast,bool bDirection,Compare pFun)
    {
    	bool bIsReverse = false;
    	T* pTemp = NULL;
    	if((pFirst == NULL) || (pLast == NULL))
    	{
    		cout<<"Input parameters error!"<<endl;
    		return false;
    	}
    	if(pFirst > pLast)
    	{
    		bIsReverse = true;
    		pTemp = pFirst;
    		pFirst = pLast;
    		pLast = pTemp;
    	}
    	if(pFirst < pLast)
    	{
    		int nNum = pLast - pFirst + 1;                         //计算数组长度
    		int nMid = nNum / 2;                                   //计算中间元素索引值
    		BitonicSort(pFirst,pFirst+nMid-1,!bDirection);         //对数组前半部分递归进行分裂
    		BitonicSort(pFirst+nMid,pLast,bDirection);             //对数组后半部分递归进行分裂
    		BitonicMerge(pFirst,pLast,bDirection);                 //双调归并过程
    	}
    	if(bIsReverse)
    	{
    		while(pFirst < pLast)
    		{
    			Swap(*pFirst,*pLast);
    			++pFirst;
    			--pLast;
    		}
    	}
    	return true;
    }

        其他排序算法及数据结构的具体实现详见GitHub:https://github.com/daiyl0320/IntroductionToAlgorithms

    展开全文
  • 归并排序与双调排序

    2019-03-25 23:04:28
    归并排序 采用分治法的策略, 1)将原始序列分成2个子序列,然后继续对每个序列递归划分,直到得到的子序列长度为1为止。 50 11 13 20 | 29 78 56 31 50 11 | 13 20 | 29 78 | 56 31 50 | 11 | 13 | 20 | 29 | 78 | ...
  • 分段双调排序实现

    千次阅读 2017-02-25 00:52:20
    问题说明: ...用C/C++ 编写一个分段双调排序(Bitonic sort)函数,对每一段内部的浮点数进行排序,但 不要改变段间的位置。 接口方式: *********************** void segmentedBitonicSort(flo
  • Python之双调排序

    2019-10-16 09:39:03
    双调序列 双调序列(Bitonic Sequence)是指由一个非严格增序列X和非严格减序列Y构成的序列,比如序列(23,10,8,3,5,7,11,78)。 定义:一个序列a1,a2,…,an是双调序列(Bitonic Sequence),如果: (1)存在一个ak(1≤k≤...
  • 双调排序是data-independent的排序, 即比较顺序与数据无关的排序方法, 特别适合做并行计算,例如用GPU、fpga来计算。
  • 并行排序 Bitonic Sort(双调排序)

    千次阅读 2018-01-02 20:28:14
    双调排序是data-independent的排序, 即比较顺序与数据无关的排序方法, 特别适合做并行计算,例如用GPU、fpga来计算。 1、双调序列 在了解双调排序算法之前,我们先来看看什么是双调序列。  (1)先单调递增后...
  • 双调排序的简单实现

    千次阅读 2014-06-06 15:11:45
    先在这里记录一下代码!原理将来再补吧!  这个算法算是有一个致命的弱点吧!那就是如果元素的个数达不到2^n个的话,要填充!#include using namespace std; void SortDown(int , int);...void MergeUp(int, int);...
  • Bitonic Sequences 首先来介绍一下什么叫做双调序列,我认为,这个序列是一个先增再减的序列(或者先减再增),判断方法是这样滴,首先,将序列第一个元素和最后一个...好了,这就是双调排序的基础,下面我们来看一下...
  • 奇偶排序 奇偶排序是排序方法的一种,...双调排序 所谓双调序列(Bitonic Sequence)是指由一个非严格增序列X和非严格减序列Y构成的序列,比如序列(23,10,8,3,5,7,11,78)。 定义:一个序列a1,a2,…,an是双调序列(B
  • Bitonic sort(双调排序)

    千次阅读 2017-07-02 10:05:33
    怎么保证Bitonic sort算法保证了排序的正确性?希望有同样疑问的你看到这篇文章会有所启示~
  • Bitonic Sort(双调排序

    千次阅读 2012-08-29 00:03:18
    #include #include using namespace std; class bitonic_sorter{ public: bitonic_sorter(int a[], int len); void sort(bool dir=true); void sort_for_arbitray_length(bool di
  • 串行的BitonicSort双调排序

    千次阅读 2011-12-20 22:04:53
    而BitonicSort双调排序是一个非常适合并行化的排序算法,其在《算法导论》的排序网络一章对其基本原理做了描述与证明。有兴趣大家可以看看。  作为个人的一个学习总结,这里只是对其性质做些简单介绍,以及它算法...
  • C++实现分段双调排序算法

    千次阅读 2015-10-14 22:12:40
    C++实现分段双调排序算法 //问题说明: // //给出分成m段 的n个浮点数,输入数据已按段号有序,但每段内部 无序。用C/C++ //编写一个分段双调排序(Bitonic sort)函数,对每一段内部的浮点数进行排序,但 //不要...
  • 1.双调序列 假设序列A是一个单调递增序列,B是一个单调di'j递减序列,那么由A与B拼接而成的序列C就是一个双调序列。如图1: 接下来我们要介绍的一个概念是双调分裂操作: 1)将数列的前半部分的各个元素(i值从0...
  • 双调排序(Bitonic sort)学习

    千次阅读 2018-09-22 11:35:46
    之前的时候参加浙大的考核,学习了一下双调排序,正好现在在学习CUDA编程,因此把之前的学习成果整理一下。 问题说明:  ***********************  给出分成m段 的n个浮点数,输入数据已按段号有序,但每段内部 ...
  • 双调合并排序(Bitonic mergesort)是一个并行排序算法。它也用作建立一个排序网络的一种构造方法。这个算法是由Ken Batcher提出来的。基于它生成的排序网络包含了个比较操作和的延时,这里的n是要排序的元素个数。 ...
  • 双调排序的基本概念有两个:双调序列和 Batcher 定理。 双调序列:双调序列是由两个单调性相反的非严格单调序列构成的序列(非严格指的是可以出现重复元素,或者NaN不参与排序)。比如(23, 10, 8, 3, 5, 7, 7, 8)。...
  • 写一个分段双调排序算法

    千次阅读 2015-03-31 08:50:11
    根据主函数中的测试用例输出结果为: Timeuse= 0.000003 0.2 0.8 0.4 0.5 0.6 0.1 0.2  实现了分段排序 1.void segmentedBitonicSort(float* data, ...对每一段用 双调排序算法 进行排序 利用step遍历数组中的每个元
  • __device__ void swap(int& a, int& b) { int t = a; a = b; b = t; } ...__global__ void sort(int* a, int flag_j, int flag_i, int count) ... unsigned int tid = blockIdx.x * blockDim.x + threadIdx.x;...
  • 双调排序思想及实现; 什么是双调排序双调排序怎么实现; 本文阅读建议用时:26min
  • 1. Batcher比较器  Batcher比较器是指如果在两个输入端给定输入x,y,再在两个输出端输出... 所谓双调序列(Bitonic Sequence)是指由一个非严格增序列X和非严格减序列Y(其中X的最小元素正好是Y的最大元素)构成的...

空空如也

1 2 3 4 5
收藏数 100
精华内容 40
关键字:

双调排序