ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergey Andrianov                     2:5020/1507.400 23 Aug 2002  22:29:06
 To : Alexandr A. Redchuck
 Subject : Re: Сортировка    комплексных    чисел?
 -------------------------------------------------------------------------------- 
 

 
 Однажды 11-Aug-02  в 00:23   Alexandr A. Redchuck (via gate)
 написал       Sergey Andrianov    по поводу
 -=-   Re: Сортировка    комплексных    чисел?  -=-
 
 AAR> From: "Alexandr A. Redchuck" <real@real.kiev.ua>
 
 AAR> 9-Aug-02 23:14 Sergey Andrianov wrote to Alexandr A. Redchuck:
 SA>> Здравствуй, Alexandr!
 
 AAR>>>  т.е. часть опорных точек попадет в 2 или 4 массива (обязательно
 AAR>>>  нужно!).
 SA>>       Hе нужно (см. ниже)
 
 AAR>>> квадрату массиве (а вот тут и перекрытия понадобились, иначе оказалось
 AAR>>> бы, что для точки на краю квадрата "истинно" ближайшая может оказаться в
 AAR>>> другом квадрате).
 SA>>   Правильно, но после того, как нашли ближайшую точку в своем квадрате
 SA>> (повторяю, квадраты без перекрытий), сравниваем расстояние до нее с
 SA>> расстояниями до сторон и углов квадрата (несколько раз можно взять и
 SA>> корень).
 SA>> По результатам сравнения в список проверяемых может добавиться до 3-х
 SA>> дополнительных квадратов (при условии, что в каждом квадрате имеется
 SA>> минимум
 SA>> одна точка. Если это условие слишком сильное, организуем очередь из
 SA>> квадратов - кандидатов на рассмотрение, пока не найдем искомую точку.
 AAR> Мне навскидку тяжело сказать - как лучше. Если возможен вариант,
 AAR> что в "квадрате" точек нет совсем, то может лучше проверить при нужде
 AAR> соседние квадраты. Если они гарантированно есть и "не одна", то лучше
 AAR> проверить некий слой вокруг квадрата (перекртыия), чем проверять
 AAR> весь квадрат.
 AAR> В любом случае разбиения дадут больше порядка ускорения по сравнению
 AAR> с единым массивом.
 
    Я не понял, что значит "слой".
    Для предложенного метода мы, жертвуя памятью (на список точек, хранящихся в
 каждом квадрате), получаем выигрыш в скорости. А как ты предлагаешь определять, 
 входит ли точка в "слой". Hе будет ли такая оценка более трудоемкая, чем
 исходная задача?
    Другое дело, если "слой" состоит из некоторого количества квадратов
 (например, на 5 квадратов в каждую сторону). Hо в этом случае, боюсь, изначально
 неоптимально выбран размер квадратов - следовало сделать их более крупными. В
 среднем оценка такова, что если количество квадратов примерно равно корню
 квадратному из количества точек, то мы, существенно уменьшая время поиска,
 расходуем не слишком много памяти, так что такая оценка кажется мне
 предпочтительной. Т.е., скажем, на 1000000 точек - 1000 квадратов по 1000 точек 
 в каждом - увеличение скорости в 1000 раз.
 
                   До свидания,  в  22:22 MSK
                                  Sergey
 
 ---
  * Origin: Sergiev Posad (2:5020/1507.400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Сортировка комплексных чисел?   Alexandr A. Redchuck   11 Aug 2002 00:23:07   Re: Сортировка комплексных чисел?   Sergey Andrianov   23 Aug 2002 22:29:06