Дан куб из 64x64x64 элементов. Как эффективно найти 26 соседей для каждого элемента.

blog newbie, 340 просмотров

-3

Дан куб из 64x64x64 элементов.
У каждого элемента есть координаты x y z от 0,0,0 до 63,63,63 соответственно.
Как за разумное время (~10 минут) найти для каждого элемента 26 соседей (окружающие элементы).

- перебор не подходит - очень долго.

Примечание:
проблема в скорости срабатывания алгоритма. "Тупо перебор" не подходит по скорости.

Примечание:
Напишите алгоритм как вы это собираетесь сделать за пару секунд.
P.S. вы заблуждаетесь насчет скорости ;)

Примечание:
//куб разбит на 512 кластеров (8*8*8) по 512 блоков (8*8*8)

function CalculateNeighbours() //находим соседей
{

for (var clust in structArray) //для каждого кластера
{
for (var block in clust.blockArray) //для каждого блока в кластере
{

//перебираем все блоки
for (var n_clust in structArray)
{
for (var n_block in n_clust.blockArray)
{

//вычисляем одного соседа
if ((n_block.world_x == (block.world_x))&&
(n_block.world_y == (block.world_y - 1))&&
(n_block.world_z == (block.world_z))) block.f = n_block; //записываем соседа

}

}

}

}

}

Примечание:
Rentier, спасибо большое! Выглядит заманчиво, пошел пробовать.

Ответы:

mutant

В чем именно проблема? У соседей координаты отличаются на +-1

Артёмка

64 * 64 * 64 * 26 = 6 815 744
Это пара секунд на среднем компьютере. Где тут проблема со скоростью? Чего-то ты темнишь.

Артёмка

А вообще, покажи свой код, который у тебя работает больше 10 минут.

Rentier

Я так понял, что каждый элемент куба - это элемент соответствующего массива? Тогда, может, можно создать еще 26 массивов, в первом сдвинуть элементы на +1 по х (это будут соседи слева), во втором +1 по у (соседи сзади) и т.д. до -1 по всем трем координатам. Далее в полученный массивах надо отбросить элементы с координатами меньше 0 и больше 63. После этого в первом массиве будет расположен центральный элемент (со своими координатами), а элементы других 26 массивов (с такимиже координатами) будут его соседями.

Артёмка

> Напишите алгоритм как вы это собираетесь сделать за пару секунд.

Артёмка

И пара слов о том, что ты написал. Если я понял твою мысль, ты для каждого элемента пробегаешь по всему кубу, в поисках соседей? Это амба. Ты еще и разбил куб на кластеры и бегаешь по кластеру в поисках соседей. А ты не думал, что сосед может оказаться в другом кластере?

lifecoder

Может, создать четырехмерный массив, и в четвертом измерении в ячейках 1-26 хранить соседей, чтобы не искать их каждый раз?
А вообще, действительно, как-то сложно поставлена задача или ищется решение.. Может, приведете изображение структуры куба, чтобы всем стало намного проще? Сейчас при беглом взгляде абсолютно неясно, чем плохо взятие вышеупомянутого плюс-минус 1 по координатам, с учетом структуры.
Если вы не храните соответствие координат блокам - стоит об этом подумать. Для вашей задачи, допустим, можно сделать так:

15 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.