#c #c 17 #stdvector #stdarray #stdoptional
#c #c 17 #stdvector #stdarray #stdoptional
Вопрос:
У меня есть 2D-среда, в которой я хочу получить для некоторых ячеек окрестности Мура (восточные, западные, северные и восточные ячейки). Иногда ячейка может иметь только 3 или 2 соседей (если мы проверяем с границы или угла сетки).
Выше я хотел бы выделить случай, когда границы нет (мир тора, то, что идет вверх, снова появляется вниз …). В таком случае у каждой ячейки есть ровно 4 соседа.
Поэтому я создал 2 версии этого алгоритма, одну с использованием std ::vector координат, а другую с использованием std ::array необязательных координат (я называю координаты парой коротких целых чисел). См. Ниже :
версия с вектором пар
std::vector<std::pair<uint16_t, uint16_t>>* Environment::getMooreNeighborhood(uint16_t x, uint16_t y) const{
std::vector<std::pair<uint16_t, uint16_t>>* neighborhood = new std::vector<std::pair<uint16_t, uint16_t>>();
std::pair<uint16_t, uint16_t> west_cell(x - 1, y);
std::pair<uint16_t, uint16_t> east_cell(x 1, y);
std::pair<uint16_t, uint16_t> north_cell(x, y - 1);
std::pair<uint16_t, uint16_t> south_cell(x, y 1);
if(this->torus){
if(x == this->width - 1){
east_cell.first = 0;
}
else if(x == 0){
west_cell.first = this->width - 1;
}
if(y == 0){
north_cell.second = this->height - 1;
}
else if(y == this->height - 1){
south_cell.second = 0;
}
neighborhood->push_back(east_cell);
neighborhood->push_back(west_cell);
neighborhood->push_back(south_cell);
neighborhood->push_back(north_cell);
}else{
if(x > 0){
neighborhood->push_back(east_cell);
}
if(x < this->width - 1){
neighborhood->push_back(west_cell);
}
if(y > 0){
neighborhood->push_back(north_cell);
}
if(y < this->height - 1){
neighborhood->push_back(south_cell);
}
}
return neighborhood;
}
версия с массивом необязательных пар
std::array<std::optional<std::pair<uint16_t,uint16_t>>, 4> Environment::getMooreNeighborhood(uint16_t x, uint16_t y) const {
std::array<std::optional<std::pair<uint16_t,uint16_t>>, 4> neighborhood;
std::optional<std::pair<uint16_t, uint16_t>> west_cell;
std::optional<std::pair<uint16_t, uint16_t>> east_cell;
std::optional<std::pair<uint16_t, uint16_t>> north_cell;
std::optional<std::pair<uint16_t, uint16_t>> south_cell;
if(this->torus){
if(x == this->width - 1){
east_cell = std::pair<uint16_t, uint16_t>(0, y);
}
else if(x == 0){
west_cell = std::pair<uint16_t, uint16_t>(this->width - 1, y);
}
if(y == 0){
north_cell = std::pair<uint16_t, uint16_t>(x, this->height - 1);
}
else if(y == this->height - 1){
south_cell = std::pair<uint16_t, uint16_t>(x, 0);
}
}else{
if(x > 0){
east_cell = std::pair<uint16_t, uint16_t>(x - 1, y);
}
if(x < this->width - 1){
west_cell = std::pair<uint16_t, uint16_t>(x 1, y);
}
if(y > 0){
north_cell = std::pair<uint16_t, uint16_t>(x, y - 1);
}
if(y < this->height - 1){
north_cell = std::pair<uint16_t, uint16_t>(x, y 1);
}
}
neighborhood[0] = west_cell;
neighborhood[1] = east_cell;
neighborhood[2] = north_cell;
neighborhood[3] = south_cell;
return neighborhood;
}
Мне приходится выполнять эту операцию очень много раз, и я не хочу стрелять себе в ногу из-за плохой реализации.
Лучше ли один выбор над другим или я абсолютно неправ, и есть другой способ сделать это эффективно?
Комментарии:
1. Предполагая, что после того, как вы нашли соседей, все они обрабатываются одинаково (т. Е. Вас больше не волнует направление), тогда моим инстинктом будет векторный код. Но, как обычно, вам нужно попробовать оба метода и время их.
2. Хотя я замечаю, что вы динамически выделяете вектор, а не динамически выделяете массив, поэтому вы не сравниваете like с like . Мне кажется, это имело бы самое большое значение. Я не вижу причин выделять вектор.
3. @john Я изменил реализацию, чтобы возвращать объект вместо указателя, и я сравнил два метода для данной задачи. Кажется, что у меня лучшая производительность с массивом необязательных пар, чем с вектором. Разница не такая большая, но она все еще есть (3 минуты для одного, 3 минуты 15 для другого). Возможно, потребуется провести дополнительные тесты производительности, чтобы убедиться в этом. Однако я не заметил никаких изменений в потреблении памяти для обоих.
4. Еще одним предложением было бы добавить
neighborhood.reserve(4);в векторный регистр, прежде чем вы начнете добавлять элементы в свой вектор.5. Нет, это другое. 4 в конструкторе означает, что у вас есть вектор размера 4.
reserveне изменяет размер вектора, но предварительно выделяет пространство, поэтому вектор не нужно перераспределять, когда вы начинаете добавлять элементы. Поскольку большую часть времени у вас будет вектор размером 4, и поскольку перераспределение часто является проблемой производительности, использованиеreserve(4)кажется беспроигрышным.