C ++에서 객체를 사용할 때 성능에 영향을 미칩니다

Question

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 테이블의 한 열입니다. 첫 번째 열에서 시작하여 마지막 열까지 계속됩니다. Profitseights 변수는 쌍의 벡터이며, 첫 번째 요소는 이익이고 두 번째 요소는 가중치입니다. 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;
}

이것은 G ++ -4.3.2와 -o3 -dndebug로 Debian Lenny에서 실행되었습니다.

감사

Answer 1

일반적인 구현에서 멤버 함수는 인스턴스 데이터에 대한 포인터를 숨겨진 매개 변수로 수신합니다 (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];
}