最快的固定長度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
提交
取消