ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Диаграмма Вороного, поиск ближайшей точки
25 сообщений из 216, страница 5 из 9
  5  все
Диаграмма Вороного, поиск ближайшей точки
    #39130337
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Существуют классические определения асимптотических обозначений, и всё. В любой приличной книге по алгоритмам их можно встретить, и везде они будут написаны в одном и том-же смысле и в очень похожей формулировке. Асимптотика должна зависеть от количества входных экземпляров, от n в нашем случае.

Только мне непонятно как у вас асимптотика построения Диаграммы Вороного получается отрицательной, объясните пожалуйста
...
Рейтинг: 0 / 0
17.12.2015, 02:12
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130391
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
SashaMercuryСуществуют классические определения асимптотических обозначений, и всё. В любой приличной книге по алгоритмам их можно встретить, и везде они будут написаны в одном и том-же смысле и в очень похожей формулировке. Асимптотика должна зависеть от количества входных экземпляров, от n в нашем случае.

Только мне непонятно как у вас асимптотика построения Диаграммы Вороного получается отрицательной, объясните пожалуйста
это я просто так указал интервал: o(n) - некотрые алгоритмы работают за это время, o(n*ln(n)) - крайний предел за который работает нормальный алгоритм. Надо было наверное от o1(n) до o2(n*ln(n))
...
Рейтинг: 0 / 0
17.12.2015, 07:36
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130535
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
kealon(Ruslan)SashaMercuryСуществуют классические определения асимптотических обозначений, и всё. В любой приличной книге по алгоритмам их можно встретить, и везде они будут написаны в одном и том-же смысле и в очень похожей формулировке. Асимптотика должна зависеть от количества входных экземпляров, от n в нашем случае.

Только мне непонятно как у вас асимптотика построения Диаграммы Вороного получается отрицательной, объясните пожалуйста
это я просто так указал интервал: o(n) - некотрые алгоритмы работают за это время, o(n*ln(n)) - крайний предел за который работает нормальный алгоритм. Надо было наверное от o1(n) до o2(n*ln(n))



То есть от O(n= 2 980 .957983014) до ( n*ln(n)= 23 847 .663864116)
разница в скорости 8 раз.

или O(n= 8 886 110 .496494895) до О(n*ln(n)= 142 177 767 .943918322)
разница в 16 раз .

Числа взяты специально , что бы получить целочисленное число
раз сравнения скорости работы алгоритма в зависимости от n.
ln( 2 980.957983014)=8
ln(8 886 110.496494895) =16


Я правильно понял порядок попугаев зависимости скорости от n
когда мы оперируем терминологией О(n, ln(C) ) ?
...
Рейтинг: 0 / 0
17.12.2015, 10:44
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130557
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
Резюмирую:
на значениях порядках n 1000 наши абстрактные алгоритмы могут отличаться
по производительности в 8 раз.
теже алгоритмы на порядках n-миллионы в 16 раз.

Но на прктике мы иногда радуемся 30% приросту производительности
не зависимо от n.

ps все это к вопросу о разрядной сетке измерений алгоритмов
привязанной к теории пределов.
...
Рейтинг: 0 / 0
17.12.2015, 11:03
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130590
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
авторЧисла взяты специально , что бы получить целочисленное число
раз сравнения скорости работы алгоритма в зависимости от n.
ln( 2 980.957983014)=8
ln(8 886 110.496494895) =16


А вобще , как я себе это предстваляю
О(n=2 980) и О(ln(n=2 980)=8)
отношение в тактах процессора затраченных на алгоритм
работы с множеством O(n) / O(ln(n)) =372.5 раза
а для n =8 886 110 O(n) / O(ln(n) =5 55 381.875 раз

отношение илюситруется графиком


О(n) по оси Х
О(ln(n)) по оси Y
начиная с точки х=1
...
Рейтинг: 0 / 0
17.12.2015, 11:30
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130641
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Чювачки.

Наша тема in general называется NNS (Nearest neighbor search)
https://en.wikipedia.org/wiki/Nearest_neighbor_search

Правильно ли я понимаю?
...
Рейтинг: 0 / 0
17.12.2015, 12:08
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130686
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ДохтаР, на практике в наши алгортмы а точнее в их реализацию (на малых объёмах N) будет внесена
офигенская константа. Надо об это не забыть.
...
Рейтинг: 0 / 0
17.12.2015, 12:54
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130702
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonДохтаР, на практике в наши алгортмы а точнее в их реализацию (на малых объёмах N) будет внесена
офигенская константа. Надо об это не забыть.

ИМХО
Эта офигенная константа погрешности уже имперически( статистически) заложена
при выборе натурального логарифма в формуле О(ln(n)).
2,718281828 n=1 -2 n=1 =0.718281828
...
Рейтинг: 0 / 0
17.12.2015, 13:06
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130720
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
ДохтаРmaytonДохтаР, на практике в наши алгортмы а точнее в их реализацию (на малых объёмах N) будет внесена
офигенская константа. Надо об это не забыть.

ИМХО
Эта офигенная константа погрешности уже имперически( статистически) заложена
при выборе натурального логарифма в формуле О(ln(n)).
2,718281828 n=1 -2 n=1 =0.718281828


Как минимум для реализации деревьев и прочих алгоритмов
имеющих формулу О(ln(n))

Вопрос почему там натуральный логарифм, а не двоичный,
математичских обоснований для выбора натурального логарифма вместо
двоичного я не нашел.
...
Рейтинг: 0 / 0
17.12.2015, 13:12
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130857
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я говорю о другой поправке. Которая зависит к примеру от cost реализации 1-й
итерации цикла к примеру или от 1 дискового IOPS. Я говорю о реальном затраченном
времени. Об execution time. И об его связи с этими графиками.

Не на бесконечности. А на малых значения.
...
Рейтинг: 0 / 0
17.12.2015, 14:38
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130866
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Чювачки.

Я создал репку для экспериментов. Регайтесь.
...
Рейтинг: 0 / 0
17.12.2015, 14:51
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130867
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
https://sourceforge.net/p/nnsexperiments/code/HEAD/tree/
...
Рейтинг: 0 / 0
17.12.2015, 14:51
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39130966
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonЯ говорю о другой поправке. Которая зависит к примеру от cost реализации 1-й
итерации цикла к примеру или от 1 дискового IOPS. Я говорю о реальном затраченном
времени. Об execution time. И об его связи с этими графиками.

Не на бесконечности. А на малых значения.

Все относительно.

Для кого то 10 000 бесконечность ,
кто делает 10 000 ! ( факториал ) переборов.

а для кого то 10 млн рядовая задача,
кто использует алгоритм О(ln(n)).
...
Рейтинг: 0 / 0
17.12.2015, 16:03
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39132585
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
ДохтаРВопрос почему там натуральный логарифм, а не двоичный,
математичских обоснований для выбора натурального логарифма вместо
двоичного я не нашел.
наверное потому, что ln(a) по основанию b = ln(a)/ ln(b) ?

ДохтаРТо есть от O(n= 2 980.957983014) до ( n*ln(n)= 23 847.663864116)
разница в скорости 8 раз.

или O(n=8 886 110.496494895) до О(n*ln(n)=142 177 767.943918322)
разница в 16 раз .
я кажется специально там индексы поставил около O >> o 1 (n) до o 2 (n*ln(n))
O выражает только масштабируемость нагрузки алгоритма от N

PS: алгоритм Фюррера например O(N*ln(N)), но никто же в здравом уме его не будет на мелких числах применять, медленнее чем столбиком выйдет O(N^2)

mayton Я создал репку для экспериментов. Регайтесь.
Извиняй, напряг со временем совсем, новая работа, в блог занести хоть что-то никак не соберусь
линка на простой инкрементальный алгоритм триангуляции. при правильной подаче данных будет линейно работать, в отличие от оригинала
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
Speed Test in my PC
10000 points
Random construction triangulation sorted time in ms: 62 pure time(47)
Random construction triangulation one-by-one time in ms: 47 pure time(47)
30000 points
Random construction triangulation sorted time in ms: 172 pure time(172)
Random construction triangulation one-by-one time in ms: 312 pure time(312)
50000 points
Random construction triangulation sorted time in ms: 343 pure time(327)
Random construction triangulation one-by-one time in ms: 780 pure time(780)
100000 points
Random construction triangulation sorted time in ms: 967 pure time(936)
Random construction triangulation one-by-one time in ms: 2637 pure time(2637)
CgalTriangulationTest.exe:
Enter number of points for triangulation :10000
Random construction triangulation time in ms: 48
Random construction triangulation one-by-one time in ms: 1134
Enter number of points for triangulation :30000
Random construction triangulation time in ms: 152
Random construction triangulation one-by-one time in ms: 8060
Enter number of points for triangulation :50000
Random construction triangulation time in ms: 271
Random construction triangulation one-by-one time in ms: 17546
Enter number of points for triangulation :100000
Random construction triangulation time in ms: 700
Random construction triangulation one-by-one time in ms: 61943
...
Рейтинг: 0 / 0
20.12.2015, 18:06
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39132967
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonСтранно. Как-то в браузере они бледненько смотряться. Хотя я включал 100% черный цвет для точек.
Браузер "оптимизирует". Если в паинт скопировать - черные точки.
...
Рейтинг: 0 / 0
21.12.2015, 12:31
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39133259
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonСтранно. Как-то в браузере они бледненько смотряться. Хотя я включал 100% черный цвет для точек.
Извини,
Я не специались в парсинге png формата ,
что бы из него координаты точек выдергивать.
:)
...
Рейтинг: 0 / 0
21.12.2015, 15:33
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39133396
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Всё будет чики-пики док. Я приложу CSV с координанами для каждой картинки.

Кстате... нафига ты самозобанился? Вот мозохист
...
Рейтинг: 0 / 0
21.12.2015, 16:23
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39138331
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonВсё будет чики-пики док. Я приложу CSV с координанами для каждой картинки.

Кстате... нафига ты самозобанился? Вот мозохист


проверить свои предположения что без форума живется гораздо
лучше чем с ним.

А где координаты, которые будем тестить и сравнивать ?
...
Рейтинг: 0 / 0
25.12.2015, 16:56
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39226357
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
Вообще то для решения таких задач используется 2х мерный индекс. Его прямое назначение за log(N) операций выбирать точки в заданном прямоугольнике (и не обязательно точки). Для поиска ближайших точек к заданной делается несколько итераций начиная с малой окрестности и увеличивая радиус поиска вдвое, пока не будет найдено хоть что-то. Такие индексы реализованы во всех ГИС. Имею свою довольно простую реализацию 2х мерного индекса.
Если не отвечу - пишите сюда nikichale@yahoo.com
...
Рейтинг: 0 / 0
28.04.2016, 09:56
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39226417
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Кривую Мортона можно использовать. Для разложения 2D -> 1D
...
Рейтинг: 0 / 0
28.04.2016, 10:58
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39226550
nikichale
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nikichale
Гость
ну да, типа замешиваешь побитно X и Y координаты и получаешь из двух чисел одно. Потом упорядочиваешь массив из таких XY для всех точек. Потом сложнее, для поиска точек в квадрате нужно просканировать 4 интервала в этом массиве.
...
Рейтинг: 0 / 0
28.04.2016, 12:37
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39228774
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
nikichaleВообще то для решения таких задач используется 2х мерный индекс. Его прямое назначение за log(N) операций выбирать точки в заданном прямоугольнике (и не обязательно точки). Для поиска ближайших точек к заданной делается несколько итераций начиная с малой окрестности и увеличивая радиус поиска вдвое, пока не будет найдено хоть что-то. Такие индексы реализованы во всех ГИС. Имею свою довольно простую реализацию 2х мерного индекса.
Если не отвечу - пишите сюда nikichale@yahoo.com

Вы не говорите о сложности построения данного индекса и о побочных эффектах. Приведите пожалуйста пример вашей простой реализации
...
Рейтинг: 0 / 0
04.05.2016, 04:22
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39228775
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Откуда такая информация про все ГИС ?
...
Рейтинг: 0 / 0
04.05.2016, 04:23
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39228781
Фотография iv_an_ru
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iv_an_ru
Участник
SashaMercuryОткуда такая информация про все ГИС ?Ну в общем-то без четревьев или R-дерева производительность ГИС будет абсолютно удрючающей, так что во всех взрослых системах это действительно есть.
...
Рейтинг: 0 / 0
04.05.2016, 05:56
| Ответить | Цитировать | Написать  
Диаграмма Вороного, поиск ближайшей точки
    #39228782
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
iv_an_ruSashaMercuryОткуда такая информация про все ГИС ?Ну в общем-то без четревьев или R-дерева производительность ГИС будет абсолютно удрючающей, так что во всех взрослых системах это действительно есть.

Как я понял, nikichale не имел ввиду R-деревья
...
Рейтинг: 0 / 0
04.05.2016, 05:59
| Ответить | Цитировать | Написать  
25 сообщений из 216, страница 5 из 9
  5  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Диаграмма Вороного, поиск ближайшей точки
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39228774&tid=1340722]:
 0ms
get settings:
 6ms
get forum list:
 18ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 131ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 81ms
get tp. blocked users:
 1ms
others: 224ms
total:  479ms
созд. / загр.: 479ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]