ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexandr A. Redchuck                 2:5020/400     24 Aug 2002  01:43:03
 To : Sergey Andrianov
 Subject : Re: Сортировка    комплексных    чисел?
 -------------------------------------------------------------------------------- 
 

 23-Aug-02 21:29 Sergey Andrianov wrote to Alexandr A. Redchuck:
 
 AAR>>>> квадрату массиве (а вот тут и перекрытия понадобились, иначе оказалось
 AAR>>>> бы, что для точки на краю квадрата "истинно" ближайшая может оказаться в
 AAR>>>> другом квадрате).
 SA>>>   Правильно, но после того, как нашли ближайшую точку в своем квадрате
 SA>>> (повторяю, квадраты без перекрытий), сравниваем расстояние до нее с
 SA>>> расстояниями до сторон и углов квадрата (несколько раз можно взять и
 SA>>> корень).
 SA>>> По результатам сравнения в список проверяемых может добавиться до 3-х
 SA>>> дополнительных квадратов (при условии, что в каждом квадрате имеется
 
 [^Y]
 
 AAR>> Мне навскидку тяжело сказать - как лучше. Если возможен вариант,
 AAR>> что в "квадрате" точек нет совсем, то может лучше проверить при нужде
 AAR>> соседние квадраты. Если они гарантированно есть и "не одна", то лучше
 AAR>> проверить некий слой вокруг квадрата (перекртыия), чем проверять
 AAR>> весь квадрат.
 
  Точнее, чем проверять кучу соседних квадратов.
  Тут все от статистики зависит и от размера квадратов.
  Если перекрытий нет и могут быть [почти] пустые квадраты, то просто
 надо проверять соседние квадраты. Кстати, кто сказал, что "до 3-х"?
  |     *|*     |   Если в каждом квадрате имеется, как ты говоришь,
 -+------+------+  минимум одна точка, то проверить придется не три
  |o     |     o|  соседних, может придется до 7 (т.е. не надо всего
  |      |      |  один)
 *|     x|      |   o и * - "опорные" точки.
 -+------+------+   x - это сюда попала точка из "экспериментального"
 *|      |      |   набора.
  |      |      |     Растояния (x-o) близки к диагонали квадрата,
  |o     |     o|   а расстояния (x-*) - к его ребру. Т.е.
 -+------+------+   точки * окажутся _ближе_, но ты их не проверишь
 по "трем соседним квадратам". А если проверять все семь, то чем это
 отличается от моих "перекрытий" для предельного случая, когда
 размер перекрытия равен размеру квадрата (кроме сильного роста
 занимаемой памяти у меня)?
  Другое дело, когда точек в каждом квадрате "много" и они размещены
 "более-менее равномерно". Тогда в твоем методе может действительно
 хватит проверки только максимум трех соседних квадратов (хотя это еще
 надо думать). Hо тогда у меня может хватит сделать перекрытия
 максимум в половину размера квадрата (а по площади это как раз
 равно трем квадратам :-).
  Тут вышо слишком много слов "может", для точного результата
 надо все внимательно делать. Может (:-) лучше всего будет делать
 как ты, но с более внимательным выбором соседних квадратов для
 дополнительных проверок. Это точно практически не увеличит
 объем памяти и в среднем будет лучше по времени, чем большие перекрытия.
 AAR>> В любом случае разбиения дадут больше порядка ускорения по сравнению
 AAR>> с единым массивом.
 
 SA>    Я не понял, что значит "слой".
 
  Hу не "слой", неудачное слово, "слой" это для объема. Зона перекрытия.
 
 SA>    Другое дело, если "слой" состоит из некоторого количества квадратов
 SA> (например, на 5 квадратов в каждую сторону). Hо в этом случае, боюсь,
 SA> изначально неоптимально выбран размер квадратов - следовало сделать их
 SA> более крупными. В среднем оценка такова, что если количество квадратов
 SA> примерно равно корню квадратному из количества точек,
 
  Hу да, я примерно так и раскидывал. Только в исходном письме речь
 шла не о 1 миллионе точек, а о 20-50 тысяч. Вот у меня в один квадрат
 по 200 точек и попало.
 
 SA> то мы, существенно уменьшая время
 SA> поиска, расходуем не слишком много памяти, так что такая оценка кажется
 SA> мне
 SA> предпочтительной. Т.е., скажем, на 1000000 точек - 1000 квадратов по
 
  А если не миллион, а сто миллионов, то в десять тысяч раз.
 Hо в задаче упоминались массивы 20-50K точек.
 
 SA> 1000 точек в каждом - увеличение скорости в 1000 раз.
 
  Если вообще не придется проверять соседние квадраты.
 Если каждый раз придется аж 7 - то не в 1000, а всего в 125. А если
 взять 20000 точек (минимальная граница в исходном письме), то "без
 перекрытий, но с проверками соседей" в лучшем случае ускорение 140 раз,
 в худшем случае (проверка 7 соседей) будет 140/8 ~ 18 раз. Я привел
 _оценку_ минимального ускорения в _худшем_ случае
 
 AAR>> В любом случае разбиения дадут больше порядка ускорения
 
 ________^^^^^^_______________________^^^^^^___
 
 AAR>> по сравнению с единым массивом.
 
 IMHO "больше порядка" вполне нормальная оценка для числа 18,
 так как это еще меньше полутора порядков.
 
 wbr,
 ===
 Геометрия есть умение хорошо рассуждать на плохо выполненном рисунке.
 
 --
 /* Alexandr Redchuck, Kyiv, Ukraine */
 /* real на real тчк kiev тчк ua     */
 
 --- ifmail v.2.15dev5
  * Origin: ReAl at home (2:5020/400)
 
 

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

Тема:    Автор:    Дата:    Re: Сортировка комплексных чисел?   Alexandr A. Redchuck   24 Aug 2002 01:43:03   Re: Сортировка комплексных чисел?   Sergey Andrianov   28 Aug 2002 07:02:04