3

プログラムの最も内側のループに次のコードがあります

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 関数をより効率的にする必要があります。

よろしくお願いします。

編集： ブランチが最も遅い操作のようです（予測ミス？）。

4

7 に答える 7

4

コンパイラがジャンプを短くするのに苦労している場合、これは少し役立つかもしれません:

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;
}
于 2009-09-03T16:34:09.783 に答える
2

各合計を調べずにこれを行う方法は見当たらないため、これは O(n) 問題になります。ただし、データは直線的に配置されるため、Intel/AMD MMX または SSE 命令が役立つ場合があります。Microsoft の組み込み関数の実装については、次のリンクを参照してください。

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

于 2009-09-03T16:17:30.100 に答える
2

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

したがって、私は x86 でアセンブラーと MMX または SSE 命令を使用するか、この命令へのアクセスを提供する (マシン固有の) C++ ライブラリが最善の策であると言う傾向があります。

于 2009-09-03T16:17:52.517 に答える
2

コンパイラがそれらを最適化しない限り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アルゴリズムを使用することがあります。

于 2009-09-03T16:23:54.343 に答える
1

すべてのベクトルを一度に反復してみてください。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
}
于 2009-09-03T16:15:02.147 に答える
1

ループの巻き戻し (および特定の、しかしはるかに複雑な例については、Duff のデバイス) を見てください。これらは、私が思いつくことができる唯一の実際のアルゴリズムの最適化です。

Loop_unwinding

ダフのデバイス

于 2009-09-03T16:39:58.227 に答える
0

a、b、c、d、およびに格納されているデータ (値) に関する追加情報がなければ、これよりもはるかに高速になることはありませんe。どれが最大かを判断するには、すべての合計を検査する必要があります。

N 番目の要素のクエリの場合は少し悪化しますが、幸いなことに、その質問はしませんでした。

于 2009-09-03T16:14:51.977 に答える