Влияние на производительность при использовании объектов в C++
-
18-09-2019 - |
Вопрос
У меня есть алгоритм динамического программирования для Knapsack на 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 Lenny с включенными g++-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];
}