Re: Сортировка комплексных чисел?
- From
- Alexandr A. Redchuck ()
- To
- Sergey Andrianov
- Date
- 2002-08-24T01:43:03Z
- Area
- RU.ALGORITHMS
From: "Alexandr A. Redchuck" <real@real.kiev.ua>
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-*) - к его ребру. Т.е.
-+------+------+ точки * окажутся _ближе_, но ты их не проверишь
по "трем соседним квадратам". А если проверять все семь, то чем это
отличается от моих "перекрытий" для предельного случая, когда
размер перекрытия равен размеру квадрата (кроме сильного роста
занимаемой памяти у меня)?
Другое дело, когда точек в каждом квадрате "много" и они размещены
"более-менее равномерно". Тогда в твоем методе может действительно
хватит проверки только максимум трех соседних квадратов (хотя это еще
надо думать). Но тогда у меня может хватит сделать перекрытия
максимум в половину размера квадрата (а по площади это как раз
равно трем квадратам :-).
Тут вышо слишком много слов "может", для точного результата
надо все внимательно делать. Может (:-) лучше всего будет делать
как ты, но с более внимательным выбором соседних квадратов для
дополнительных проверок. Это точно практически не увеличит
объем памяти и в среднем будет лучше по времени, чем большие перекрытия.
AAR>> В любом случае разбиения дадут больше порядка ускорения по сравнению
AAR>> с единым массивом.
SA> Я не понял, что значит "слой".
Ну не "слой", неудачное слово, "слой" это для объема. Зона перекрытия.
SA> Другое дело, если "слой" состоит из некоторого количества квадратов
SA> (например, на 5 квадратов в каждую сторону). Но в этом случае, боюсь,
SA> изначально неоптимально выбран размер квадратов - следовало сделать их
SA> более крупными. В среднем оценка такова, что если количество квадратов
SA> примерно равно корню квадратному из количества точек,
Ну да, я примерно так и раскидывал. Только в исходном письме речь
шла не о 1 миллионе точек, а о 20-50 тысяч. Вот у меня в один квадрат
по 200 точек и попало.
SA> то мы, существенно уменьшая время
SA> поиска, расходуем не слишком много памяти, так что такая оценка кажется
SA> мне
SA> предпочтительной. Т.е., скажем, на 1000000 точек - 1000 квадратов по
А если не миллион, а сто миллионов, то в десять тысяч раз.
Но в задаче упоминались массивы 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)