|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexandr A. Redchuck 2:5020/400 08 Aug 2002 23:15:58
To : "Evgenij M. Baldin"
Subject : Re: Сортировка комплексных чисел?
--------------------------------------------------------------------------------
8-Aug-02 14:26 Evgenij M. Baldin wrote to Andrey Belyaev:
EB> У меня есть наборы пар чисел (4 набора по 20-50 тыс после
EB> предварительного отбора), получаемых совершенно случайным образом.
Я так надеюсь, опроный массив ("матрица коррекции") меняется гораздо
реже массива сырых данных...
Тогда я попробовал бы так: "опорный" набор режем на квадраты,
штук так на 200. Получаем толпу структур вида
* x0, x1, y0, y1; - координаты границ
* массив опорных точек, находящихся в пределах x0-dx, x1+dx, y0-dy,
y1+dy, где dx, dy - полуширина перекрытий.
т.е. часть опорных точек попадет в 2 или 4 массива (обязательно
нужно!).
В зависимости от размера перекрытий в каждый массив попадет по
200-500 пар.
Взяв очередную "сырую" пару сначала проверяем в какой квадрат она
попала, потом проверяем расстояния до точек в соответствующему этому
квадрату массиве (а вот тут и перекрытия понадобились, иначе оказалось
бы, что для точки на краю квадрата "истинно" ближайшая может оказаться в
другом квадрате).
Итого для каждой входной точки имеем максимум 200*4=800 сравнений чисел
на больше/меньше (попадание в квадрат) и вычисление расстояний (в смысле,
квадратов расстояний, как тут уже тебе напомнили :-) максимум для
200-500 пар, т.е. ускорение на 2 порядка.
Правда, ценой увеличения, может даже раза в 2-3, объема памяти,
занимаемого опорными данными (из-за перекрытий), но даже
1M*sizeof(double) по нынешним временам немного :-)
wbr,
p.s. возможно, имеет смысл сделать 3-уровневую пирамиду -
зоны, содержащие только свои границы и ссылки на квадраты,
квадраты, как описано выше.
Скажем, 20 зон по 20 квадратов по 100-200 пар. Итого макс.
(20+20)*4 = 160 сравнений и макс. 100-200 вычислений расстояний.
Hо тут надо внимательно, из-за уменьшения числа пар,
относящихся к каждому квадрату, может понадобится увеличить
перекрытия.
--
/* Alexandr Redchuck, Kyiv, Ukraine */
/* real на real тчк kiev тчк ua */
--- ifmail v.2.15dev5
* Origin: ReAl at home (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
