4

C++でのKnapsackの動的計画法アルゴリズムがあります。関数として実装され、渡された変数にアクセスすると、特定のインスタンスで実行するのに22秒かかりました。これをクラスKnapsackInstanceのメンバー関数にして、そのクラスのデータメンバーである変数を使用させると、実行に37秒かかり始めました。私の知る限り、メンバー関数へのアクセスのみがvtableを通過するため、何が起こっているのかを説明するのに迷っています。

これが関数のコードです

int KnapsackInstance::dpSolve() {
 int i; // Current item number
 int d; // Current weight
 int * tbl; // Array of size weightLeft
 int toret;
 tbl = new int[weightLeft+1];
 if (!tbl) return -1;
 memset(tbl, 0, (weightLeft+1)*sizeof(int));
 for (i = 1; i <= numItems; ++i) {
  for (d = weightLeft; d >= 0; --d) {
   if (profitsWeights.at(i-1).second <= d) {
    /* Either add this item or don't */
    int v1 = profitsWeights.at(i-1).first + tbl[d-profitsWeights.at(i-1).second];
    int v2 = tbl[d];
    tbl[d] = (v1 < v2 ? v2 : v1);
   }
  }
 }
 toret = tbl[weightLeft];
 delete[] tbl;
 return toret;
}

tblは、DPテーブルの1つの列です。最初の列から始めて、最後の列まで進みます。ProfitsWeights変数はペアのベクトルであり、最初の要素は利益で、2番目の要素は重みです。toretは返す値です。

これが元の関数のコードです：-

int dpSolve(vector<pair<int, int> > profitsWeights, int weightLeft, int numItems) {
 int i; // Current item number
 int d; // Current weight
 int * tbl; // Array of size weightLeft
 int toret;
 tbl = new int[weightLeft+1];
 if (!tbl) return -1;
 memset(tbl, 0, (weightLeft+1)*sizeof(int));
 for (i = 1; i <= numItems; ++i) {
  for (d = weightLeft; d >= 0; --d) {
   if (profitsWeights.at(i-1).second <= d) {
    /* Either add this item or don't */
    int v1 = profitsWeights.at(i-1).first + tbl[d-profitsWeights.at(i-1).second];
    int v2 = tbl[d];
    tbl[d] = (v1 < v2 ? v2 : v1);
   }
  }
 }
 toret = tbl[weightLeft];
 delete[] tbl;
 return toret;
}

これは、g++-4.3.2および-O3-DNDEBUGがオンになっているDebianLennyで実行されました。

ありがとう

4

1 に答える 1

3

一般的な実装では、メンバー関数はインスタンスデータへのポインターを非表示のパラメーター（this）として受け取ります。そのため、メンバーデータへのアクセスは通常、ポインターを介して行われます。これにより、表示される速度が低下する可能性があります。

一方、1つのバージョンのコードだけを見て推測する以上のことを行うのは困難です。

両方のコードを見た後、私はメンバー関数を次のように書くと思います。

int KnapsackInstance::dpSolve() {
    std::vector<int> tbl(weightLeft+1, 0);
    std::vector<pair<int, int> > weights(profitWeights);
    int v1;

    for (int i = 0; i <numItems; ++i) 
        for (int d = weightLeft; d >= 0; --d)
            if ((weights[i+1].second <= d) && 
                ((v1 = weights[i].first + tbl[d-weights[i-1].second])>tbl[d]))
                    tbl[d] = v1;
    return tbl[weightLeft];
}
于 2010-02-04T21:14:14.953 に答える