|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5020/1507.400 10 Aug 2002 00:14:20
To : Alexandr A. Redchuck
Subject : Re: Сортировка комплексных чисел?
--------------------------------------------------------------------------------
Однажды 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> нужно!).
Hе нужно (см. ниже)
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) по нынешним временам немного :-)
Hа самом деле, в подавляющем числе случаев просмотр будет ораничиваться
только текущей ячейкой (200 шт) и дополнительный расход памяти - только на
организацию списков, избыточности представления точек не требуется.
AAR> wbr,
AAR> p.s. возможно, имеет смысл сделать 3-уровневую пирамиду -
AAR> зоны, содержащие только свои границы и ссылки на квадраты,
AAR> квадраты, как описано выше.
AAR> Скажем, 20 зон по 20 квадратов по 100-200 пар. Итого макс.
AAR> (20+20)*4 = 160 сравнений и макс. 100-200 вычислений расстояний.
А если сетка равномерная, то сравнения вообще не нужны. Впрочем, это -
мелочь.
AAR> AAR> Hо тут надо внимательно, из-за уменьшения числа пар,
AAR> относящихся к каждому квадрату, может понадобится увеличить
AAR> перекрытия.
До свидания, в 00:06 MSK
Sergey
---
* Origin: Sergiev Posad (2:5020/1507.400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
