|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Pertzel Family 2:5020/400 09 Aug 2002 01:06:51
To : Evgenij M. Baldin
Subject : Re: Сортировка комплексных чисел?
--------------------------------------------------------------------------------
Мир Вашему Дому!
"Evgenij M. Baldin" <baldin@Slon.inp.nsk.su> wrote in message
news:aitod0$97el$1@sky.inp.nsk.su...
> поиск всё время в одном наборе (20-50 тыс событий), потом организуется на
> другом массиве данных следующий, но это можно делать параллельльно -
> четыре машины - четыре массива :)
Тогда я бы сделал кластеризацию:
поделил бы квадрат, в который они
попали, на 4 маленьких, каждый из
них, еще на 4, и т.д. Причем,
квадраты бы хранил в структуре
четверичного дерева, в которой
кроме указателей на детей, еще и
записано, сколько в данном квадрате
точек, и если одна -- то и её
координаты, и такие квадраты бы
соответствовали листьям дерева.
(понятно, что если точек нет, то и
делить не надо).
Время на организацию N точек, должно
быть порядка N*log^2(N). Тут надо
поднапрячься и хранить вершины в двух
списках (или др. структурах), одном
отсортированном по одной координате,
а в другом по другой, причем звенья
разных списков, хранящие одну точку,
должны иметь ссылку друг на друга.
При делении квадрата по одной
координате пополам, сначала один
список (отсортированный по этой
координате) разделяется на два,
а потом, за линейное время, и второй,
в зависимости от того, к какому
квадрату оказался приписан "партнер".
Hа этом предварительная стадия
закончена.
Теперь пошел процесс в цикле по
новым точкам:
Взяв новую точку, я нашел бы, деля
на 2 стороны самого большого квадрата,
тот квадрат - лист дерева, в котором
она содержится, взял точку из него.
Время -- порядка log(N).
Теперь, зная отклонение от найденой
точки, я уже не должен просматривать
все точки, а только те, что содержатся
в 4 соседних по стороне квадратах
(а, если повезет, то и не во всех 4).
Тут, если распределение равномерно,
можно не дальше не напрягаться, за
константное в среднем время, рассмотрев
все точки в них, но если нет, то возможно,
придется еще и выбирать порядок перебора.
Идея не моя, но ссылку на литературу
я дать не могу: мне ее когда-то просто
рассказал один араб с которым я
когда-то работал в разработке софтвера
для конструирования микропроцессоров.
--
/\ /\ From the Holy Land, with respect
((ovo)) Vladimir A. Pertsel
():::() news://news.relhum.org
--PVA-------------------------------------------------
An ancestor of mine, by the name of Noah, was once the
commanding admiral of the combined fleets of my planet
--- ifmail v.2.15dev5
* Origin: Sent via Graf's Inn at news://news.relhum.org (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
