对性能的影响在c中使用对象时++
-
18-09-2019 - |
题
我有背包在C的动态规划算法++。当它被作为一个函数,并传递到它访问的变量来实现,它正在采取22秒在特定实例上运行。当我做了我的课KnapsackInstance的成员函数,把它使用了这个类的数据成员变量,它开始采取37秒运行。据我所知,只有存取成员函数经过虚函数表,所以我不知所措地解释一下可能发生的。
这里的函数的代码
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表中的一列。我们从第一列开始,继续,直到最后一列。所述profitsWeights变量是对一个向量,第一个元件,它的是利润和所述第二权重。 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莱尼与克运行++ - 4.3.2和-O3 -DNDEBUG接通
由于
解决方案
在一个典型的实现中,成员函数接收的指针实例数据作为隐藏参数(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];
}
不隶属于 StackOverflow