Auswirkungen auf die Leistung, wenn Objekte in C ++

Question

Ich habe einen dynamischen Programmieralgorithmus für Knapsack in C ++. Wenn es als eine Funktion von und Zugreifen auf Variablen implementiert wurde in sie übergeben, es nahm 22 Sekunden auf einer bestimmten Instanz zu laufen. Als ich es die Member-Funktion meiner Klasse KnapsackInstance und hatte es Variablen verwenden, die Datenelemente der Klasse waren, begann es 37 Sekunden unter auszuführen. Soweit ich weiß, nur Funktionen Mitglied Zugriff auf die VTable geht durch so ich ratlos bin zu erklären, was passiert sein könnte.

Hier ist der Code der Funktion

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 ist eine Spalte der DP-Tabelle. Wir gehen von der ersten Spalte und gehen bis zur letzten Spalte. Die profitsWeights Variable ist ein Vektor von Paaren, das erste Element davon ist der Gewinn und die zweite das Gewicht. Toret ist der Wert zurückzukehren.

Hier ist der Code der ursprünglichen Funktion: -

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;
}

Dieses wurde auf Debian Lenny mit g ++ laufen - 4.3.2 und O3 -DNDEBUG eingeschaltet

Danke

Answer 1

In einer typischen Implementierung wird eine Elementfunktion empfängt einen Zeiger auf den Instanzdaten als verborgener Parameter (this). Als solcher Zugriff auf Mitgliederdaten ist in der Regel über einen Zeiger, der für die Verlangsamung ausmachen können Sie sehen.

Auf der anderen Seite ist es schwer, mehr zu tun, als mit nur einer Version der Codes erraten, zu betrachten.

Nachdem an beiden Teilen des Codes suchen, denke ich, dass ich die Member-Funktion wie diese mehr schreiben würde:

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];
}