Быстрый поиск элементов массива

[Alex345]

Есть два частично заполненных трёхмерных массива. Массивы не ограничены по размерности (т.е. индексы могут иметь любые целочисленные значения).
Заполненные элементы массива заданы в виде текстового файла, где каждая строка представляет собой один его элемент, первые три столбца - три индекса, а четвертый столбец - собственно числовое значение этого элемента.
Требуется для каждого элемента одного такого массива найти элемент с такими же индексами из другого массива и всех его ближайших соседей (коих будет шесть). Как это сделать наибыстрейшим образом?
Понятно, что можно для каждого элемента одного массива перебором найти все требуемые семь элементов другого, но это потребует порядка N1*N2 операций (если количество элементов в массивах N1 и N2).
Как сделать это быстрее?
У массивов есть особенность: один получен из другого заполнением всех пустых граничных элементов, находящихся не далее одной ячейки по одному индексу.

[venco]

Если массивы сильно прореженые, то имеет смысл хранить их в ассоциативном контейнере, с ключом - тройкой координат. Поиск либо $\ln n$ (если контейнер отсортированный), или вообще константа, если использовать хэш ключа.
А поиск соседних элементов проще делать шестью поисками элемента с конкретными координатами.

[Alex345]

Массивы ближе к сферическим (эллипсоидным) и один от другого отличается дополнительным (квази) сферическим (эллипсоидным) поверхностным слоем.

[upgrade]

поиск повторов - это очень часто решаемая задача при обработке данных.

[rockclimber]

Alex345 в сообщении #912039 писал(а):

Требуется для каждого элемента одного такого массива найти элемент с такими же индексами из другого массива и всех его ближайших соседей (коих будет шесть). Как это сделать наибыстрейшим образом?

Может, имеет смысл хранить числа парами? То есть простейшая структура будет: координата по x, координата по y, координата по z, число массива 1, число массива 2. Тогда число из второго массива искать не надо вообще (если вы просто перебираете все числа первого массива по очереди), а место хранения соседних чисел в файле можно будет быстро вычислить, если у вас будет фискированная структура файла. Например, для массива 10 х 10 х 10 создаете файл размером 1000 строк. Если надо найти соседей числа $(3, 4, 5)$, это будут строки 245, 445, 335, 355, 344, 346.

-- 26.09.2014, 11:08 --

P. S. Если брать такую фиксированную структуру, то вам даже координаты хранить не надо, только пары чисел на нужных строках, а номера строк и будут координатами.

[Alex345]

rockclimber в сообщении #912187 писал(а):

Alex345 в сообщении #912039 писал(а):

Требуется для каждого элемента одного такого массива найти элемент с такими же индексами из другого массива и всех его ближайших соседей (коих будет шесть). Как это сделать наибыстрейшим образом?

Может, имеет смысл хранить числа парами? То есть простейшая структура будет: координата по x, координата по y, координата по z, число массива 1, число массива 2. Тогда число из второго массива искать не надо вообще (если вы просто перебираете все числа первого массива по очереди), а место хранения соседних чисел в файле можно будет быстро вычислить, если у вас будет фискированная структура файла. Например, для массива 10 х 10 х 10 создаете файл размером 1000 строк. Если надо найти соседей числа $(3, 4, 5)$, это будут строки 245, 445, 335, 355, 344, 346.

-- 26.09.2014, 11:08 --

P. S. Если брать такую фиксированную структуру, то вам даже координаты хранить не надо, только пары чисел на нужных строках, а номера строк и будут координатами.

Проблема в том, что число элементов одного массива не совпадает с числом элементов другого, поэтому хранить их попарно не получится.
Но даже если бы число это было одинаково, нужно было бы их попарно скомпоновать. А это N*N операций, чего требуется избежать.

[rockclimber]

Alex345 в сообщении #912276 писал(а):

Но даже если бы число это было одинаково, нужно было бы их попарно скомпоновать. А это N*N операций, чего требуется избежать.

Нет конечно. Если у вас два массива, один из которых просто смещен относительно другого и меньше по размерам, то вам надо просто перебрать один раз элементы первого массива и выбрать из второго соответствующие элементы, итого N операций. Если оба массива разом не помещаются в оперативную память - тогда да, придется что-то придумывать.

[Skeptic]

Отсортировать по ключу (координатам) только второй массив. Элементы первого массива перебираются последовательно.