Почему указатели медленнее в этом случае

Я реализую quadtree. Я повторно реализовал свой первый черновик (полную версию можно увидеть Вот) которые использовали умные указатели и ссылки с версией, использующей необработанные указатели.

Но заполнение нового дерева, по-видимому, в два раза медленнее, почему это так?

Код старых версий:

// 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)),

Можете ли вы сказать мне, в чем причина потери производительности?

(Посмотрите комментарии для дополнительной информации)

2

Решение

Этот код

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,

4

Другие решения

Вам нужны большие тестовые данные, чтобы иметь надежное утверждение.

Вы также хотите сделать это «время сообщения» умножить раз.

После этого вы можете использовать Профилировщик, чтобы определить, что является вашей основной причиной.

Это могут быть проблемы с вашим кэшем процессора (изменение структуры) или что-то более медленное, чем вы сейчас занимаетесь.

2

По вопросам рекламы [email protected]