2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Быстрый поиск элементов массива
Сообщение25.09.2014, 21:29 


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

 Профиль  
                  
 
 Re: Быстрый поиск элементов массива
Сообщение25.09.2014, 23:06 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Быстрый поиск элементов массива
Сообщение26.09.2014, 06:36 


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

 Профиль  
                  
 
 Re: Быстрый поиск элементов массива
Сообщение26.09.2014, 09:15 


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

 Профиль  
                  
 
 Re: Быстрый поиск элементов массива
Сообщение26.09.2014, 10:06 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
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. Если брать такую фиксированную структуру, то вам даже координаты хранить не надо, только пары чисел на нужных строках, а номера строк и будут координатами.

 Профиль  
                  
 
 Re: Быстрый поиск элементов массива
Сообщение26.09.2014, 14:08 


11/04/13
72
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 операций, чего требуется избежать.

 Профиль  
                  
 
 Re: Быстрый поиск элементов массива
Сообщение26.09.2014, 15:15 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
Alex345 в сообщении #912276 писал(а):
Но даже если бы число это было одинаково, нужно было бы их попарно скомпоновать. А это N*N операций, чего требуется избежать.
Нет конечно. Если у вас два массива, один из которых просто смещен относительно другого и меньше по размерам, то вам надо просто перебрать один раз элементы первого массива и выбрать из второго соответствующие элементы, итого N операций. Если оба массива разом не помещаются в оперативную память - тогда да, придется что-то придумывать.

 Профиль  
                  
 
 Re: Быстрый поиск элементов массива
Сообщение26.09.2014, 17:50 


01/12/11

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group