4

我有一个用于 C++ 中背包的动态编程算法。当它被实现为一个函数并访问传递给它的变量时，它需要 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 表的一列。我们从第一列开始，一直到最后一列。ProfitWeights 变量是成对的向量，其中第一个元素是利润，第二个元素是权重。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;
}

这是在 Debian Lenny 上运行 g++-4.3.2 和 -O3 -DNDEBUG 打开的

谢谢

4

1 回答 1

3

在典型实现中，成员函数接收指向实例数据的指针作为隐藏参数 ( this)。因此，对成员数据的访问通常是通过指针来实现的，这可能会导致您看到的速度变慢。

另一方面，除了只看一个版本的代码来猜测之外，很难做更多的事情。

在查看了这两段代码之后，我想我会更像这样编写成员函数：

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 回答