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

}

用这个版本填充树的时间是 ca。元素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)).

你能告诉我性能损失的原因在哪里吗？

（查看评论以获取更多信息）

4

2 回答 2

4

这段代码

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。

于 2013-09-02T15:08:18.993 回答
2

您需要更大的 Testdata 才能获得可靠的陈述。

您还希望将“时间混乱”倍增。

之后，您可以使用 Profiler 来确定您的根本原因是什么。

这可能是您的 cpu 缓存（结构更改）或您现在正在做的事情较慢的问题。

于 2013-09-02T15:11:13.773 回答