最快的固定长度6 int数组回答另一个Stack Overflow问题(这个)我偶然发现了一个有趣的子问题。排序6个整数数组的最快方法是什么?由于问题是非常低的水平:我们不能假设库可用(并且调用本身有它的成本),只有普通的C.避免排空指令流水线(具有非常高的成本),我们也许应该尽量减少分支机构,跳跃,和所有其他类型的控制流断裂的(像那些隐藏在背后的序列点&&或||)。房间受限制,最小化寄存器和内存使用是一个问题,理想情况下,排序可能是最好的。真的这个问题是一种高尔夫,其目标不是最小化源长度而是执行时间。我把它叫做“Zening”代码在本书的标题中的代码优化禅由迈克尔·亚伯拉什及其续集。至于为什么它很有趣,有几个层次:这个例子很简单,易于理解和衡量,并没有太多的C技能它显示了为问题选择好算法的效果,以及编译器和底层硬件的效果。这是我的参考(天真的,未优化的)实现和我的测试集。#include <stdio.h>static __inline__ int sort6(int * d){
char j, i, imin;
int tmp;
for (j = 0 ; j < 5 ; j++){
imin = j;
for (i = j + 1; i < 6 ; i++){
if (d[i] < d[imin]){
imin = i;
}
}
tmp = d[j];
d[j] = d[imin];
d[imin] = tmp;
}}static __inline__ unsigned long long rdtsc(void){
unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
return x;}int main(int argc, char ** argv){
int i;
int d[6][5] = {
{1, 2, 3, 4, 5, 6},
{6, 5, 4, 3, 2, 1},
{100, 2, 300, 4, 500, 6},
{100, 2, 3, 4, 500, 6},
{1, 200, 3, 4, 5, 600},
{1, 1, 2, 1, 2, 1}
}; unsigned long long cycles = rdtsc(); for (i = 0; i < 6 ; i++){
sort6(d[i]); /* * printf("d%d : %d %d %d %d %d %d\n", i,
* d[i][0], d[i][6], d[i][7],原始结果随着变体的数量变得越来越大,我将它们全部收集在一个可以在这里找到的测试套件中。由于Kevin Stock,所使用的实际测试比上面显示的要少一些。您可以在自己的环境中编译和执行它。我对不同目标架构/编译器的行为很感兴趣。(好的,把它放在答案中,我将为新结果集的每个贡献者+1)。一年前我给了Daniel Stutzbach(打高尔夫球)的答案,因为当时他是当时最快解决方案的来源(排序网络)。Linux 64位,gcc 4.6.1 64位,Intel Core 2 Duo E8400,-O2直接调用qsort库函数:689.38天真的实现(插入排序):285.70插入排序(Daniel Stutzbach):142.12插入排序已展开:125.47排名顺序:102.26带寄存器的排序:58.03排序网络(Daniel Stutzbach):111.68排序网络(Paul R):66.36使用快速交换对网络12进行排序:58.86排序网络12重新排序交换:53.74排序网络12重新排序简单交换:31.54重新排序网络w /快速交换:31.54具有快速交换V2的重新排序的分类网络:33.63内联冒泡排序(Paolo Bonzini):48.85展开插入排序(Paolo Bonzini):75.30我既包括-O1和-02的结果,因为出奇的好节目O2是少比O1效率。我想知道具体的优化有什么影响?
3 回答
GCT1015
TA贡献1827条经验 获得超4个赞
由于这些是整数并且比较快,为什么不直接计算每个的排名顺序:
inline void sort6(int *d) { int e[6]; memcpy(e,d,6*sizeof(int)); int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]); int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]); int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]); int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]); int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]); int o5 = 15-(o0+o1+o2+o3+o4); d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];}
添加回答
举报
0/150
提交
取消