どのように素早くベクトルの和の最大要素を見つけるか？

Question

は、私はそれはいくつかの巧妙なアルゴリズムになるかどうか気にしない（これは最も興味深いものになるだろう）、または

struct V { 
    float val [200]; // 0 <= val[i] <= 1 
}; 

V a[600]; 
V b[250]; 
V c[250]; 
V d[350]; 
V e[350]; 

// ... init values in a,b,c,d,e ... 

int findmax(int ai, int bi, int ci, int di, int ei) { 
    float best_val = 0.0; 
    int best_ii = -1; 

    for (int ii = 0; ii < 200; ii++) { 
    float act_val = 
     a[ai].val[ii] + 
     b[bi].val[ii] + 
     c[ci].val[ii] + 
     d[ci].val[ii] + 
     e[ci].val[ii]; 

    if (act_val > best_val) { 
     best_val = act_val; 
     best_ii = ii; 
    } 
    } 

    return best_ii; 
} 

私のプログラムの最も内側のループに次のコードを持っているいくつかのC++のトリックや組み込み関数やアセンブラ。しかし、findmax関数をより効率的にする必要があります。

事前に大変感謝しています。

編集： 枝が最も遅い操作（誤予測？）であるようです。

Answer 1

まあ、私は、アルゴリズムの最適化のための明白な部屋を見ません。理論的には、最大に達することができないことが明らかになるまで、5つのベクトルの合計を計算することしかできませんでしたが、これは5つの数値を加算するだけのオーバーヘッドにつながります。複数のスレッドを使用してスレッドに範囲を割り当てることもできますが、非常に短い作業項目が200個しかない場合はスレッド作成のオーバーヘッドについて考える必要があります。

私は、x86上でAssemblerとMMXまたはSSE命令を使用するか、おそらくこの命令へのアクセスを提供するライブラリ（マシン固有のC++）を使用することが最善の策だと言います。

Answer 2

あなたは本当にa、b、c、d、およびeに格納されたデータ（値）に関する追加情報なしにそのはるかに速くよりも取得することはできません。どの合計が最大かを判断するためには、合計を調べなければなりません。

N番目の要素のクエリでは少し悪くなりますが、幸いなことに、それを聞かなかったのです。

Answer 3

すべてのベクトルを一度に繰り返してみてください。ここでは、2つのベクトルの例です：

for (float *ap = a[ai].val, *bp = b[bi].val; ap - a[ai].val < 200; ap++, bp ++) { 
    float act_val = *ap + *bp; 
    // check for max and return if necessary 
} 

Answer 4

私はこのO（n）の問題を作り、それぞれの合計を検討せずにこれを行うにはどのような方法が表示されません。しかし、データが線形にレイアウトされているため、Intel/AMD MMXまたはSSE命令が役立ちます。組み込み関数のMicrosoftの実装のために、このリンクを参照してください：

http://msdn.microsoft.com/en-us/library/y0dh78ez(VS.71).aspx

Answer 5

コンパイラがそれらを最適化しない限り、ループ内のa[ai]などを計算すると、findmaxの間固定されているとしたら、少し時間がかかります。その光の中で、あなたのような何かを試してみてください：コードを改善する

int findmax(int ai, int bi, int ci, int di, int ei) { 
    float best_val = std::numeric_limits<float>::min(); 
    int  best_ii = 0; 
    const V& a(a[ai]); 
    const V& b(b[bi]); 
    const V& c(c[ci]); 
    const V& d(d[di]); 
    const V& e(e[ei]); 

    for (int ii = 0; ii < 200; ++ii) { 
     float act_val = a.val[ii] + b.val[ii] + c.val[ii] + 
         d.val[ii] + e.val[ii]; 

     if (act_val > best_val) { 
      best_val = act_val; 
      best_ii = ii; 
     } 
    } 

    return best_ii; 
} 

他の手段は、異なる（しかし、はるかに高速）findmaxアルゴリズムにつながる、データが表される方法を変更することがあります。

Answer 6

コンパイラが困難短いジャンプをカットをしている場合、これは少し役立つかもしれない：和テーブルを生成

int findmax(int ai, int bi, int ci, int di, int ei) { 
    float best_val = 0.0; 
    int best_ii = -1; 

    float* a_it = &a[ai].val[0] 
    float* b_it = &b[bi].val[0] 
    float* c_it = &c[ci].val[0] 
    float* d_it = &d[di].val[0] // assume typo ci->di 
    float* e_it = &e[ei].val[0] // assume typo ci->ei 

    for (int ii = 0; ii < 200; ii++) { 
    float act_val = *(a_it++) + *(b_it++) + *(c_it++) + *(d_it++) + *(e_it++); 
    best_val = (act_val <= best_val) ? best_val : act_val; // becomes _fsel 
    best_ii = (act_val <= best_val) ? best_ii : ii; // becomes _fsel 
    } 

    return best_ii; 
} 

は、私は少しでこれを投稿しますキャッシュミスの面でより速いかもしれません。

int findmax(int ai, int bi, int ci, int di, int ei) { 
    float best_val = 0.0; 
    int best_ii = -1; 

    float* its[] = {&a[ai].val[0], &a[bi].val[0], &a[ci].val[0], &a[di].val[0], &a[ei].val[0] }; 

    V sums; 
    for (int ii = 0; ii < 200; ii++) { 
    sums.val[ii] = * (++its[0]); 
    } 

    for (int iter = 1 ; iter < 5; ++iter) { 
     for (int ii = 0; ii < 200; ii++) { 
     sums.val[ii] += * (++its[iter]); 
     } 
    } 
    } 
    for (int ii = 0; ii < 200; ii++) { 
    best_val = (sums.val[ii] <= best_val) ? best_val : sums.val[ii]; // becomes _fsel 
    best_ii = (sums.val[ii] <= best_val) ? best_ii : ii; // becomes _fsel 
    } 
    return best_ii; 
} 

Answer 7

ループ巻き戻し（特定の、しかしはるかに複雑な例のDuffのデバイス）を見てください。それらが私が思い付く唯一の本当のアルゴリズムの最適化です。

Loop_unwinding

Duff's_device