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

From

Sergey Andrianov (2:5020/1507.400)

To

Alexandr A. Redchuck

Date

2002-08-10T00:14:20Z

Area

RU.ALGORITHMS

Здравствуй, Alexandr!

Однажды 08-Aug-02  в 23:15   Alexandr A. Redchuck (via gate)
написал       "Evgenij M. Baldin"    по поводу
-=-   Re: Сортировка    комплексных    чисел?  -=-


EB>> У меня есть наборы пар чисел (4 набора по 20-50 тыс после
EB>> предварительного отбора), получаемых совершенно случайным образом.
AAR>  Я так надеюсь, опроный массив ("матрица коррекции") меняется гораздо
AAR> реже массива сырых данных...

AAR>  Тогда я попробовал бы так: "опорный" набор режем на квадраты,
AAR> штук так на 200. Получаем толпу структур вида

AAR> * x0, x1, y0, y1; - координаты границ
AAR> * массив опорных точек, находящихся в пределах x0-dx, x1+dx, y0-dy,
AAR>   y1+dy, где dx, dy - полуширина перекрытий.
AAR>   т.е. часть опорных точек попадет в 2 или 4 массива (обязательно
AAR>   нужно!).
       Не нужно (см. ниже)
AAR> В зависимости от размера перекрытий в каждый массив попадет по
AAR> 200-500 пар.

AAR> Взяв очередную "сырую" пару сначала проверяем в какой квадрат она
AAR> попала, потом проверяем расстояния до точек в соответствующему этому
AAR> квадрату массиве (а вот тут и перекрытия понадобились, иначе оказалось
AAR> бы, что для точки на краю квадрата "истинно" ближайшая может оказаться в
AAR> другом квадрате).
   Правильно, но после того, как нашли ближайшую точку в своем квадрате (повторяю, квадраты без перекрытий), сравниваем расстояние до нее с расстояниями до сторон и углов квадрата (несколько раз можно взять и корень). По результатам сравнения в список проверяемых может добавиться до 3-х дополнительных квадратов (при условии, что в каждом квадрате имеется минимум одна точка. Если это условие слишком сильное, организуем очередь из квадратов - кандидатов на рассмотрение, пока не найдем искомую точку.
AAR> Итого для каждой входной точки имеем максимум 200*4=800 сравнений чисел
AAR> на больше/меньше (попадание в квадрат) и вычисление расстояний (в смысле,
AAR> квадратов расстояний, как тут уже тебе напомнили :-) максимум для
AAR> 200-500 пар, т.е. ускорение на 2 порядка.
AAR> Правда, ценой увеличения, может даже раза в 2-3, объема памяти,
AAR> занимаемого опорными данными (из-за перекрытий), но даже
AAR> 1M*sizeof(double) по нынешним временам немного :-)
   На самом деле, в подавляющем числе случаев просмотр будет ораничиваться только текущей ячейкой (200 шт) и дополнительный расход памяти - только на организацию списков, избыточности представления точек не требуется.
AAR> wbr,
AAR> p.s. возможно, имеет смысл сделать 3-уровневую пирамиду -
AAR> зоны, содержащие только свои границы и ссылки на квадраты,
AAR> квадраты, как описано выше.
AAR> Скажем, 20 зон по 20 квадратов по 100-200 пар. Итого макс.
AAR> (20+20)*4 = 160 сравнений и макс. 100-200 вычислений расстояний.
   А если сетка равномерная, то сравнения вообще не нужны. Впрочем, это - мелочь.
AAR> AAR> Но тут надо внимательно, из-за уменьшения числа пар,
AAR> относящихся к каждому квадрату, может понадобится увеличить
AAR> перекрытия.


                  До свидания,  в  00:06 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)