|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Goldobin 2:5020/400 22 Jul 2003 11:16:04
To : Anatoly Saveliev
Subject : Re: Поиск ближайшей точки (сабж слетел)
--------------------------------------------------------------------------------
Hi!
> > ... и они распределены равномерно по плоскости. Hо в этом случае гораздо
> > эффективнее регулярная сетка.
>
> лучше вложенная, она же квадродерево - о чем ниже; и лучше не
> регулярная, а делить по медиане на прямоугольники для баланса
регулярная позволяет единственной операцией list =
array[round(x/K)][round(y/K)] получить сразу список допустим 2-3 точек из
миллиона, которые могут быть ближайшей к искомой, если она лежит в данной
ячейке. А нерегулярные подразумевают несколько итераций спуска по дереву.
Для случая именно равномерного распределения регулярная получается лучше.
> > > Точно так же сортируются (по левому краю) и проекции
>
> > а вот в более сложных случаях, чем описано выше, это может привести к
> > затратам большим, чем даже простой перебор. Как мы будем искать при
такой
> > сортировке? Ищем бинарным поиском ближайшую по X точку к искомой,
вычисляем
>
> неверно, просто ищем дихотомией левую границу в сортированном массиве
> проекций на X (с некоторым epsilon), после чего линейный перебор до
> правой границы. поскольку в epsilon окрестности искомой точки ожидается
> 2*epsilon/Range(x)*N точек, а скорость поиска O(log(N)), то процесс идет
во-первых откуда брать эпсилон? мы же ищем не примерно ближайшую, а
ближайшую. И что зачит быстро? допустим равномерно распределены N точек в
квадрате MxM, среднее расстояние между точками что-то в районе sqr(N)/M, то
есть брать эпсилон нужно в районе sqr(N) и перебирать тогда придется порядка
тысячи значений для миллиона точек? В случае же вот этих всяких сложных
алгоритмов с деревьями - около двадцати (logN). Разница существенная.
> быстро, а приведенный ниже пример к данному методу контрпримером не
> является, поскольку му переберем примерно 3 точки - центральную, над
> ней, и под ней.
как это? ближайшая находится допустим слева, в центре точки нет, около
центра (чуть левее) та, к которой мы ищем ближайшую.
> округления, после чего оставил только QSort, но будучи университетским
> человеком изучил реальные характеристики поиска при реальных данных - и
> с удивлением обнаружил, что матожтдание числа перебираемых точек
> примерно 6, а максимум обычно не превышает 200, поэтому с практической
> точки зрения скорость можно считать линейной.
6 из скольки? из 100000? не верю :) так может получиться если только точки
распределить равномерно в вытянутом вдоль X узком прямоугольнике. ты уверен,
что ищешь именно "ближайшую", а не "любую из точек в заданном
квадрате/окружности/etc"?
Bye.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
