:: Курилка
расчет фрактала на большой выборке
boba
Автор

Сообщений: 6269
Откуда: Медвежьи озера-
Дата регистрации: 26.03.2001
Вожусь с каталогом землетрясений Японии,
пытаюсь прокатить свои старые методики.
Терплю фиаско.
Размер выборки около 10 миллионов записей
Один из рассчитываемых параметров- коэффициент фрактальности.
Довольно тривиальная штука.
Берем событие и его координаты -широту и долготу.
Задаем некий радиус, скажем 2 километра.
Перебираем все пары событий, чье расстояние укладывается
внутри 2 километов.
Потом другой радиус итд.
Выходная величина -график в двойных лог координатах
число событий от радиуса.
Формула расчета расстояния по сфере содержит
широты , долготы обоих событий в паре, всякие sin, cos, arcos
Пробовал решить запросом таблица каталога открыта дважды.
Ясный пень, индекса на функцию, в которой есть 2 пары координат не сделать.
getdist(jap.lat, jap1.lat, jap.lon, jap1.lon)
Не могу дождаться результата даже для урезанной выборки
в 200 тыс событий.
Сделал вариант перебора
цикл по расстоянию между событиями rr
cntr =0
do while not eof('jap')
do while not eof('jap1')
если расстояние меньше заданного- сумматор
if getdist(jap.lat, jap1.lat, jap.lon, jap1.lon)< rr
cntr= cntr=1
endif
enddo

go top in jap1
enddo
запись результата в файл
strtofile('fract',alltrim(padl(rr,10,' '))+' '+lltrim(padl(cntr,10,' ')),.t.)
конец цикла расстояний
Та же хрень, не могу дождаться результата.
До этого работал с другим каталогом размером примерно 75000 событий.
Получал результаты и тем способом и другим
Программа может быть в любой момент остановлена по escape
и снова запущена с запросом начала цикла расстояний на том, где остановились до этого.
Идеи есть, что делать. Думал, на ФОРТРАНЕ быстрее,
не не быстрее.
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Владимир, нужны ВСЕ совпадения, или можно ограничиться, к примеру, радиусом в 30км, а всё что вне его (для каждой конкретной точки) выбрасывать?
Если так, то однократный перевод в "плоские" координаты xy (на таком расстоянии кривизной поверхности можно спокойно пренебречь), и дополнительный фильтр по "попаданию в квадрат" (т.е. берём все точки с X в интервале (X0-R,X0+R) и Y в интервале (Y0-R,Y0+R)) может существенно сократить объёмы выборки.
Иначе - ну никак ты не выйдешь на меньше чем 50трлн операций "расчёта расстояний"...
Вложенные циклы, но только внутренний не по всем записям, а по тем что "ниже" текущей записи внешнего цикла - ну и инкремент счётчика в нужном слоте расстояния и для точки "внешнего" и для точки "внутреннего" циклов. Т.е. структура таблицы итога, грубо говоря, (координаты, соседи в радиусе 1км, соседи в радиусе 2км, соседи в радиусе 5 км, ...) ну и сколько надо таких "окружностей попадания"...


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
Гулин Федор

Сообщений: 4633
Откуда: Минск
Дата регистрации: 24.10.2002
ох чувствую что это тема для machine learning
но я тут полный 0
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
boba
Автор

Сообщений: 6269
Откуда: Медвежьи озера-
Дата регистрации: 26.03.2001
График рисуется в логарифме.
Отсюда следует, что диапазон радиусов
должен покрывать порядка полтора, иначе не увидишь эффекта.
То сеть хочется диапазон расстояний от пары километров до полу тысячи.
Насчет линеаризации, конечно думал,
но в маленькой Японии, оказывается ,
расстояние между удаленными событиями может доходить
до полутора тысяч километров и больше. То есть,
для далеких событий плохо использовать формулу с постоянной длиной
градуса по широте и долготе.
Программирование, безусловно отучает от математики.
Тут точно должен быть какой-то подход с мозгами,
а я все пишу циклы да запросы.
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
По твоему псевдо-коду:
Можно его уполовинить - вложенный цикл не надо по всем событиям/записям гонять - достаточно только по "оставшимся", т.е. типа
go recno("jap") in jap1
skip && само с собой тоже не надо сравнивать.
scan rest
...
Но это мало поможет - вместо 100 трлн останется 50 трлн "вычислений расстояния".
Замерь сколько у тебя занимает обработка 10 тысяч точек. Просчёт всего массива (10 млн) займёт в 1 млн (один МИЛЛИОН) раз больше времени.
Скажем у меня простейший тест с расстоянием "по пифагору" sqrt(d1^2+d2^2) для 10к точек занимает примерно 17 секунд (и это чисто выражение внутри цикла - никакой больше полезной нагрузки, даже просто счётчик не ведётся, и сама "функция" getdist просто "встроена" в код, без расходов на собственно вызов настоящей функции). Это значит что для 10М точек он займёт примерно 200 суток А если добавить внутрь даже банальные счётчики - сколько расстояний попало в тот или иной интервал - время увеличится раза в 3, т.е. выходим на 1.5 года...

Может быть проще будет побить все точки на своего рода "соты", и потом уже оперировать именно этими сотами как единым целым (ну помимо координат там ещё "плотность событий" добавится). По крайней мере это (просчёт попадания точки внутрь "соты") будет задачей линейной сложности, а не квадратичной, да и она очень хорошо распараллеливается, в отличие от прямой задачи "посчитать расстояния между всеми парами событий".


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
boba
Автор

Сообщений: 6269
Откуда: Медвежьи озера-
Дата регистрации: 26.03.2001
Игорь, идея насчет сот-возможно недурная
Сейчас попробую что-то изобразить.
Те для всех не заполненных сот
заранее сосчитать расстояние.
А потом разложить события по сотам
и уже определять, кто куда ляжет.
Цикл я описал очень схематично.
Конечно, второй проход по копии таблицы
начинается с записи большей, чем в первом алиасе.
Там много чего есть, но это ни на что не влияет.
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
of63

Сообщений: 25161
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
() А зачем функция расстояния на сфере содержит 4 параметра: getdist(jap.lat, jap1.lat, jap.lon, jap1.lon) ? На идеальной сфере достаточно 2х (разница в широтах и разница в долготах... К тому же, если "синусы" занимают много проц. времени, то можно заранее посчитать это расстояние (с требуемой точностью по градусам и километрам), положить в таблицу (d_шир, d_ дол, расстояние), и потом обращаться к этой таблице с парой разниц...

А нет, фигню сморозил, на высоких широтах другие соотношения с расстоянием...



Исправлено 1 раз(а). Последнее : of63, 19.06.18 15:24
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Олег, какая разница, сразу diff или отдельно два параметра и там уж вычитать - не в этом проблема. Проблема в сложности O(n^2) и том что я не вижу хорошего способа распараллелить такого рода алгоритм (вложенные циклы по всему множеству исходных данных). Т.е. в лучшем случае придётся просто в разных потоках/процессах обрабатывать подмножество + полное множество.


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
of63

Сообщений: 25161
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
надо посчитать расстояние во всех возможных парах в множестве 10^7 элементов? Это ... на первом элементе 10^7, плюс на втором меньше на 1... примерно квадрат вроде... Т.е надо измерить 10^14 расстояний. За желаемое время, например, 14 сут = 10^6 сек надо каждое измерение провести за 10^-8 сек, НЕРЕАЛЬНО. Если использовать 10^3 процессов, то 10^-5 сек тоже нереально. Надо как-то отсекать заранее лишние пары... И то, если много точнк соберутся в Японии, то измерений будет все равно много... надо ботнетсеть компов )

Типа, сначала составляем таблицу всех возможных пар (в пределе 10^14 пар, на фоксе не получится, вероятно), но включаем в нее только пары с разницей по долготе менее столько то градусов для низких широт, и с большЕй разницей для верхних. также не включаем в таблицу с большой разницей по широте. А потом уже измеряем расстояние для каждой пары... Т.е. сначала отсеять явно лишние пары.



Исправлено 2 раз(а). Последнее : of63, 19.06.18 17:14
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Владимир, задача сформулирована нечетко, поэтому что-нибудь конкретное посоветовать трудно, но по некоторым фразам создается впечатление, что делается что-то вроде свертки. Поэтому, может вот это чем-нибудь поможет:

en.wikipedia.org

Кстати, на питоне есть очень мощная библиотека для подобных вычислений:

www.tensorflow.org
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
of63

Сообщений: 25161
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
И какая точность измерения требуется (и точность отсчетов какая). Может некоторые измерения уже, в пределах точности, были сосчитаны. ИК правильно сказал, распределение точек надо знать, и требуемая погрешность. Если задача вообще решаема, вернее, что она может показать в землетрясениях... Почему время не участвует в расчетах...
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
_vit

Сообщений: 5173
Дата регистрации: 29.07.2002
of63
Т.е. сначала отсеять явно лишние пары.

Если я правильно понял то лишних пар нет ибо на выходе надо получить график количества событий в зависимости от радиуса

boba
Выходная величина -график в двойных лог координатах
число событий от радиуса.
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
of63

Сообщений: 25161
Откуда: Н.Новгород
Дата регистрации: 13.02.2008
Говорит, что:
> График рисуется в логарифме. Отсюда следует, что диапазон радиусов должен покрывать порядка полтора, иначе не увидишь эффекта. То сеть хочется диапазон расстояний от пары километров до полу тысячи.

500 км что-ли...
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
_vit

Сообщений: 5173
Дата регистрации: 29.07.2002
По сути исходные данные есть ч/б векторная графика. Только не в декартовой а в сферической системе координат.
Возможно подойдут какие то функции выделения региона интереса и сжатия изображения из готовых библиотек.
Ratings: 0 negative/0 positive
Re: расчет фрактала на большой выборке
boba
Автор

Сообщений: 6269
Откуда: Медвежьи озера-
Дата регистрации: 26.03.2001
Предложение Игоря пока рулит.
Правда времена не малые.
До расчета фрактала расчет матрицы 200
на 400 шел 13 часов на рабочей персоналке.
Посмотрел на результаты, крупновато,
нужно 400 * 600
Пока не знаю, на сколько потянет расчет графика фрактальности
по таким матрицам.
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 45 (Гостей: 45)

© 2000-2024 Fox Club 
Яндекс.Метрика