数百万UINT64 RGBZ图形像素的最快排序算法

发布时间：2020-12-14 02:10:14 所属栏目：Windows 来源：网络整理

导读：我使用来自.RAW文件的RGB数据对1000万uint64_ts进行??排序,并且在qsort中花费了79％的C程序时间.我正在寻找这种特定数据类型的更快排序. 作为RAW图形数据,数字是非常随机的,并且~80％是唯一的.不需要对排序数据进行部分排序或运行. uint64_t内的4 uint16_ts

我使用来自.RAW文件的RGB数据对1000万uint64_ts进行??排序,并且在qsort中花费了79％的C程序时间.我正在寻找这种特定数据类型的更快排序.

作为RAW图形数据,数字是非常随机的,并且~80％是唯一的.不需要对排序数据进行部分排序或运行. uint64_t内的4 uint16_ts是R,G,B和零(可能是一个小的计数< = ~20). 我有最简单的比较函数,我可以想到使用无符号long longs(你不能只减去它们)：

qsort(hpidx,num_pix,sizeof(uint64_t),comp_uint64); 
...
int comp_uint64(const void *a,const void *b)  {
    if(*((uint64_t *)a) > *((uint64_t *)b))  return(+1);
    if(*((uint64_t *)a) < *((uint64_t *)b))  return(-1);
    return(0);
}  // End Comp_uint64().

StackExchange上有一个非常有趣的“Programming Puzzles& Code Golf”,但他们使用了浮点数.然后有QSort,RecQuick,堆,stooge,树,基数……

swenson / sort看起来很有趣,但对我的数据类型uint64_t没有(明显的)支持.而“快速排序”时间是最好的.有些消息称,系统qsort可以是任何东西,不一定是“快速排序”.

C类绕过void指针的通用转换并实现了对C的性能的极大改进.必须有一种优化的方法,以经线速度通过64位处理器猛击U8.

系统/编译器信息：

我目前正在使用GCC和Strawberry Perl

gcc version 4.9.2 (x86_64-posix-sjlj,built by strawberryperl.com
Intel 2700K Sandy Bridge CPU,32GB DDR3
windows 7/64 pro

gcc -D__USE_MINGW_ANSI_STDIO -O4 -ffast-math -m64 -Ofast -march=corei7-avx -mtune=corei7 -Ic:/bin/xxHash-master -Lc:/bin/xxHash-master c:/bin/stddev.c -o c:/bin/stddev.g6.exe

第一次尝试更好的qsort,QSORT()！

试图使用Michael Tokarev的内联qsort.

“可以用了”？来自qsort.h文档

-----------------------------
* Several ready-to-use examples:
 *
 * Sorting array of integers:
 * void int_qsort(int *arr,unsigned n) {
 * #define int_lt(a,b) ((*a)<(*b))
 *   QSORT(int,arr,n,int_lt);
--------------------------------

Change from type "int" to "uint64_t"
compile error on TYPE???

    c:/bin/bpbfct.c:586:8: error: expected expression before 'uint64_t'
      QSORT(uint64_t,hpidx,islt);

我找不到一个真实的,编译的,有效的示例程序,只是用“一般概念”来评论

#define QSORT_TYPE uint64_t 
#define islt(a,b) ((*a)<(*b))

uint64_t *QSORT_BASE; 
int QSORT_NELT;

hpidx=(uint64_t *) calloc(num_pix+2,sizeof(uint64_t));  // Hash . PIDX
QSORT_BASE = hpidx;
QSORT_NELT = num_pix;  // QSORT_LT is function QSORT_LT()
QSORT(uint64_t,islt);  
//QSORT(uint64_t *,QSORT_LT);  // QSORT_LT mal-defined?
//qsort(hpidx,comp_uint64); // << WORKS

“即用型”示例使用int,char *和struct elt的类型. uint64_t不是一个类型??试试很久

QSORT(long long,islt); 
c:/bin/bpbfct.c:586:8: error: expected expression before 'long'
 QSORT(long long,islt);

下一次尝试：RADIXSORT：

结果：RADIX_SORT是根本的！

I:br3pf.249465>grep "Event" bb12.log | grep -i Sort       
 << 1.40 sec average
4) Time=1.411 sec    = 49.61%,Event RADIX_SORT,hits=1
4) Time=1.396 sec    = 49.13%,hits=1
4) Time=1.392 sec    = 49.15%,hits=1
16) Time=1.414 sec    = 49.12%,hits=1

I:br3pf.249465>grep "Event" bb11.log | grep -i Sort 
 << 5.525 sec average  = 3.95 time slower
4) Time=5.538 sec    = 86.34%,Event QSort,hits=1
4) Time=5.519 sec    = 79.41%,hits=1
4) Time=5.519 sec    = 79.02%,hits=1
4) Time=5.563 sec    = 79.49%,hits=1
4) Time=5.684 sec    = 79.83%,hits=1
4) Time=5.509 sec    = 79.30%,hits=1

比开箱即用的任何类型的qsort快3.94倍！

而且,更重要的是,有一些实际的,有效的代码,而不仅仅是一些Guru所需要的80％,他们假设你知道他们所知道的一切,并且可以填写其他20％.

很棒的解决方案！谢谢Louis Ricci！

解决方法

我会使用Radix Sort和8bit基数.对于64位值,优化良好的基数排序将不得不在列表上迭代9次(一次用于预先计算计数和偏移量,8次用于64位/ 8位). 9 * N时间和2 * N空间(使用阴影阵列).

这是优化的基数排序的样子.

typedef union {
    struct {
        uint32_t c8[256];
        uint32_t c7[256];
        uint32_t c6[256];
        uint32_t c5[256];
        uint32_t c4[256];
        uint32_t c3[256];
        uint32_t c2[256];
        uint32_t c1[256];
    };
    uint32_t counts[256 * 8];
} rscounts_t;

uint64_t * radixSort(uint64_t * array,uint32_t size) {
    rscounts_t counts;
    memset(&counts,256 * 8 * sizeof(uint32_t));
    uint64_t * cpy = (uint64_t *)malloc(size * sizeof(uint64_t));
    uint32_t o8=0,o7=0,o6=0,o5=0,o4=0,o3=0,o2=0,o1=0;
    uint32_t t8,t7,t6,t5,t4,t3,t2,t1;
    uint32_t x;
    // calculate counts
    for(x = 0; x < size; x++) {
        t8 = array[x] & 0xff;
        t7 = (array[x] >> 8) & 0xff;
        t6 = (array[x] >> 16) & 0xff;
        t5 = (array[x] >> 24) & 0xff;
        t4 = (array[x] >> 32) & 0xff;
        t3 = (array[x] >> 40) & 0xff;
        t2 = (array[x] >> 48) & 0xff;
        t1 = (array[x] >> 56) & 0xff;
        counts.c8[t8]++;
        counts.c7[t7]++;
        counts.c6[t6]++;
        counts.c5[t5]++;
        counts.c4[t4]++;
        counts.c3[t3]++;
        counts.c2[t2]++;
        counts.c1[t1]++;
    }
    // convert counts to offsets
    for(x = 0; x < 256; x++) {
        t8 = o8 + counts.c8[x];
        t7 = o7 + counts.c7[x];
        t6 = o6 + counts.c6[x];
        t5 = o5 + counts.c5[x];
        t4 = o4 + counts.c4[x];
        t3 = o3 + counts.c3[x];
        t2 = o2 + counts.c2[x];
        t1 = o1 + counts.c1[x];
        counts.c8[x] = o8;
        counts.c7[x] = o7;
        counts.c6[x] = o6;
        counts.c5[x] = o5;
        counts.c4[x] = o4;
        counts.c3[x] = o3;
        counts.c2[x] = o2;
        counts.c1[x] = o1;
        o8 = t8; 
        o7 = t7; 
        o6 = t6; 
        o5 = t5; 
        o4 = t4; 
        o3 = t3; 
        o2 = t2; 
        o1 = t1;
    }
    // radix
    for(x = 0; x < size; x++) {
        t8 = array[x] & 0xff;
        cpy[counts.c8[t8]] = array[x];
        counts.c8[t8]++;
    }
    for(x = 0; x < size; x++) {
        t7 = (cpy[x] >> 8) & 0xff;
        array[counts.c7[t7]] = cpy[x];
        counts.c7[t7]++;
    }
    for(x = 0; x < size; x++) {
        t6 = (array[x] >> 16) & 0xff;
        cpy[counts.c6[t6]] = array[x];
        counts.c6[t6]++;
    }
    for(x = 0; x < size; x++) {
        t5 = (cpy[x] >> 24) & 0xff;
        array[counts.c5[t5]] = cpy[x];
        counts.c5[t5]++;
    }
    for(x = 0; x < size; x++) {
        t4 = (array[x] >> 32) & 0xff;
        cpy[counts.c4[t4]] = array[x];
        counts.c4[t4]++;
    }
    for(x = 0; x < size; x++) {
        t3 = (cpy[x] >> 40) & 0xff;
        array[counts.c3[t3]] = cpy[x];
        counts.c3[t3]++;
    }
    for(x = 0; x < size; x++) {
        t2 = (array[x] >> 48) & 0xff;
        cpy[counts.c2[t2]] = array[x];
        counts.c2[t2]++;
    }
    for(x = 0; x < size; x++) {
        t1 = (cpy[x] >> 56) & 0xff;
        array[counts.c1[t1]] = cpy[x];
        counts.c1[t1]++;
    }
    free(cpy);
    return array;
}

编辑此实现基于JavaScript版本Fastest way to sort 32bit signed integer arrays in JavaScript?

这是C基数排序http://ideone.com/JHI0d9的IDEONE

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!