<分区>
我正在实现一个四叉树。我重新实现了我的初稿(完整版可以看 here )，它使用了智能指针和使用原始指针的版本的引用。
但是填充新树显然要慢两倍，这是为什么？
旧版本代码:
// 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);
}
用这个版本填充树的时间大约是。 0.001367 1000 的秒数元素。
然后我重新实现了这个功能:
// 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填充这个版本的时间元素需要大约。 0.00312秒。
如您所见，使用指针的第二个版本要慢得多。
PS:我用
循环填充旧树(版本 1) insert(std::make_shared<Rectangle>(std::rand()%999, std::rand()%999, 1, 1))
和新版本(版本 2)
insert(new Quadtree::Rectangle(std::rand()%999, std::rand()%999, 1, 1)) .
你能告诉我性能损失的原因在哪里吗？
(查看评论以获取更多信息)