Влияние на производительность при использовании объектов в с ++ - PullRequest
Новая
       18

Влияние на производительность при использовании объектов в с ++

4 голосов
/ 05 февраля 2010

У меня есть алгоритм динамического программирования для рюкзака на 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

Спасибо

1 Ответ

3 голосов
/ 05 февраля 2010

В типичной реализации функция-член получает указатель на данные экземпляра в качестве скрытого параметра (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];
}
...