Re: Сортировка комплексных чисел?

From

Alexandr A. Redchuck ()

To

"Evgenij M. Baldin"

Date

2002-08-08T23:15:58Z

Area

RU.ALGORITHMS

From: "Alexandr A. Redchuck" <real@real.kiev.ua>

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 вычислений расстояний.
Но тут надо внимательно, из-за уменьшения числа пар,
относящихся к каждому квадрату, может понадобится увеличить
перекрытия.

--
/* Alexandr Redchuck, Kyiv, Ukraine */
/* real на real тчк kiev тчк ua     */

--- ifmail v.2.15dev5
 * Origin: ReAl at home (2:5020/400)