이 경우 포인터가 더 느린 이유

Question

쿼드 트리를 구현 중입니다. 원시 포인터를 사용하는 버전에서 스마트 포인터와 참조를 사용하는 내 초안 (전체 버전은 here으로 볼 수 있음)을 다시 구현했습니다.

하지만 새로운 나무를 채우는 것이 분명히 최대 2 배 느려지므로이 경우가 어떨까요?

이전 버전의 코드 :

// returns if coordinates fit in the tree 
const bool contains(const double &x, const double &y, const double &w, const double &h) const { 
    return (this->x < x && 
      this->y < y && 
      this->x + this->w > x + w && 
      this->y + this->h > x + h); 
} 
// returns if an element fits in the tree 
const bool contains(const std::shared_ptr<Rectangle> &rect) const { 
    return contains(rect->getX(), rect->getY(), rect->getW(), rect->getH()); 
} 

// inserts an element in the tree 
const bool insert(const std::shared_ptr<Rectangle> &rect) { 
    // if rect is too big for this quadtree 
    if(!contains(rect)) { 
     auto sp = getParent(); 
     if(sp == nullptr) { 
      return false; 
     } 
     return sp->insert(rect); 
    } 
    // if element theoretically fits in subtree 
    else if(rect->getW() < getW()/2 && rect->getH() < getH()/2) { 
     if(!subtrees[0]) { 
      generateSubtrees(); 
     } 
     for(const auto &subtree: subtrees) { 
      if(subtree->contains(rect)) { 
       return subtree->insert(rect); 
      } 
     } 
    } 
    children.insert(children.end(), rect); 
    return true; 
} 

void generateSubtrees() { 
    subtrees[0] = std::make_shared<QuadTree>(getW()/2.0f, getH()/2.0f, getX(),     getY(),     this); 
    subtrees[1] = std::make_shared<QuadTree>(getW()/2.0f, getH()/2.0f, getX() + getW()/2.0f, getY(),     this); 
    subtrees[2] = std::make_shared<QuadTree>(getW()/2.0f, getH()/2.0f, getX(),     getY() + getH()/2.0f, this); 
    subtrees[3] = std::make_shared<QuadTree>(getW()/2.0f, getH()/2.0f, getX() + getW()/2.0f, getY() + getH()/2.0f, this); 

} 

이 버전 트리를 충전 시간은 약이다 1000 요소의 경우 0.001367 초.

그럼 I이 기능을 구현 재 :

는

// Returns if a Rectangle fits in the tree 
const bool contains(const Rectangle *rect) const { 
    return (this->x < rect->x && 
      this->y < rect->y && 
      this->x + this->w > rect->x + rect->w && 
      this->y + this->h > rect->y + rect->h); 
} 

// Inserts an element in the tree 
const bool insert(Rectangle *rect) { 
    if(!contains(rect) && parent == nullptr) { 
     return false; 
    } 
    if(rect->w < this->w/2.0f && rect->w < this->w/2.0f) { 
     if(children[0]==nullptr){ 
      generateSubtrees(); 
     } 
     for(const auto child: children) { 
      if(child->contains(rect)) { 
       return child->insert(rect); 
      } 
     } 
    } 
    elements.push_back(rect); 
    return true; 
} 

// Generate the subtrees 
void generateSubtrees() { 
    children[0] = new Quadtree(w/2.0f, h/2.0f, x,  y,  this); 
    children[1] = new Quadtree(w/2.0f, h/2.0f, x+w/2.0f, y,  this); 
    children[2] = new Quadtree(w/2.0f, h/2.0f, x,  y+w/2.0f, this); 
    children[3] = new Quadtree(w/2.0f, h/2.0f, x+w/2.0f, y+w/2.0f, this); 
} 

1000 요소 버전을 채우는 시간이 소요 CA. 0.00312 초.

아시다시피 포인터를 사용하는 두 번째 버전은 훨씬 느립니다.

PS : 나는

insert(new Quadtree::Rectangle(std::rand()%999, std::rand()%999, 1, 1))와

insert(std::make_shared<Rectangle>(std::rand()%999, std::rand()%999, 1, 1))

과 새와 루프 (버전 2) 오래 된 나무 (버전 1)을 입력합니다.

성능 저하의 원인이 어디에 있는지 알려주실 수 있습니까?

Answer 1

const bool contains(const double &x, const double &y, const double &w, const double &h) const { 
    return (this->x < x && 
      this->y < y && 
      this->x + this->w > x + w && 
      this->y + this->h > x + h); <---- error here 
} 

이 코드

const bool contains(const Rectangle *rect) const { 
    return (this->x < rect->x && 
      this->y < rect->y && 
      this->x + this->w > rect->x + rect->w && 
      this->y + this->h > rect->y + rect->h); 
} 

첫 번째 잘못 x + h 말했다과 동일하지 않습니다이 코드 (자세한 내용은 코멘트를 봐), 그것을 말해야한다 y + h.

Answer 2

신뢰할 수있는 진술을하려면 더 큰 테스트 데이터가 필요합니다.

당신은 또한 '시간 messuring'곱하기 시간을하고 싶습니다.

그런 다음 프로필러를 사용하여 근원이 무엇인지 판단 할 수 있습니다.

CPU 캐시 (구조 변경) 나 현재 수행 속도가 느린 문제 일 수 있습니다.