расчет фрактала на большой выборке | |
---|---|
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 и снова запущена с запросом начала цикла расстояний на том, где остановились до этого. Идеи есть, что делать. Думал, на ФОРТРАНЕ быстрее, не не быстрее. |
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 |
Re: расчет фрактала на большой выборке | |
---|---|
Гулин Федор Сообщений: 4633 Откуда: Минск Дата регистрации: 24.10.2002 |
ох чувствую что это тема для machine learning
но я тут полный 0 |
Re: расчет фрактала на большой выборке | |
---|---|
boba Автор Сообщений: 6269 Откуда: Медвежьи озера- Дата регистрации: 26.03.2001 |
График рисуется в логарифме.
Отсюда следует, что диапазон радиусов должен покрывать порядка полтора, иначе не увидишь эффекта. То сеть хочется диапазон расстояний от пары километров до полу тысячи. Насчет линеаризации, конечно думал, но в маленькой Японии, оказывается , расстояние между удаленными событиями может доходить до полутора тысяч километров и больше. То есть, для далеких событий плохо использовать формулу с постоянной длиной градуса по широте и долготе. Программирование, безусловно отучает от математики. Тут точно должен быть какой-то подход с мозгами, а я все пишу циклы да запросы. |
Re: расчет фрактала на большой выборке | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
По твоему псевдо-коду:
Можно его уполовинить - вложенный цикл не надо по всем событиям/записям гонять - достаточно только по "оставшимся", т.е. типа
Замерь сколько у тебя занимает обработка 10 тысяч точек. Просчёт всего массива (10 млн) займёт в 1 млн (один МИЛЛИОН) раз больше времени. Скажем у меня простейший тест с расстоянием "по пифагору" sqrt(d1^2+d2^2) для 10к точек занимает примерно 17 секунд (и это чисто выражение внутри цикла - никакой больше полезной нагрузки, даже просто счётчик не ведётся, и сама "функция" getdist просто "встроена" в код, без расходов на собственно вызов настоящей функции). Это значит что для 10М точек он займёт примерно 200 суток А если добавить внутрь даже банальные счётчики - сколько расстояний попало в тот или иной интервал - время увеличится раза в 3, т.е. выходим на 1.5 года... Может быть проще будет побить все точки на своего рода "соты", и потом уже оперировать именно этими сотами как единым целым (ну помимо координат там ещё "плотность событий" добавится). По крайней мере это (просчёт попадания точки внутрь "соты") будет задачей линейной сложности, а не квадратичной, да и она очень хорошо распараллеливается, в отличие от прямой задачи "посчитать расстояния между всеми парами событий". ------------------ WBR, Igor |
Re: расчет фрактала на большой выборке | |
---|---|
boba Автор Сообщений: 6269 Откуда: Медвежьи озера- Дата регистрации: 26.03.2001 |
Игорь, идея насчет сот-возможно недурная
Сейчас попробую что-то изобразить. Те для всех не заполненных сот заранее сосчитать расстояние. А потом разложить события по сотам и уже определять, кто куда ляжет. Цикл я описал очень схематично. Конечно, второй проход по копии таблицы начинается с записи большей, чем в первом алиасе. Там много чего есть, но это ни на что не влияет. |
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 |
Re: расчет фрактала на большой выборке | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Олег, какая разница, сразу diff или отдельно два параметра и там уж вычитать - не в этом проблема. Проблема в сложности O(n^2) и том что я не вижу хорошего способа распараллелить такого рода алгоритм (вложенные циклы по всему множеству исходных данных). Т.е. в лучшем случае придётся просто в разных потоках/процессах обрабатывать подмножество + полное множество.
------------------ WBR, Igor |
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 |
Re: расчет фрактала на большой выборке | |
---|---|
leonid Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Владимир, задача сформулирована нечетко, поэтому что-нибудь конкретное посоветовать трудно, но по некоторым фразам создается впечатление, что делается что-то вроде свертки. Поэтому, может вот это чем-нибудь поможет:
en.wikipedia.org Кстати, на питоне есть очень мощная библиотека для подобных вычислений: www.tensorflow.org |
Re: расчет фрактала на большой выборке | |
---|---|
of63 Сообщений: 25161 Откуда: Н.Новгород Дата регистрации: 13.02.2008 |
И какая точность измерения требуется (и точность отсчетов какая). Может некоторые измерения уже, в пределах точности, были сосчитаны. ИК правильно сказал, распределение точек надо знать, и требуемая погрешность. Если задача вообще решаема, вернее, что она может показать в землетрясениях... Почему время не участвует в расчетах...
|
Re: расчет фрактала на большой выборке | |
---|---|
_vit Сообщений: 5173 Дата регистрации: 29.07.2002 |
Если я правильно понял то лишних пар нет ибо на выходе надо получить график количества событий в зависимости от радиуса
|
Re: расчет фрактала на большой выборке | |
---|---|
of63 Сообщений: 25161 Откуда: Н.Новгород Дата регистрации: 13.02.2008 |
Говорит, что:
> График рисуется в логарифме. Отсюда следует, что диапазон радиусов должен покрывать порядка полтора, иначе не увидишь эффекта. То сеть хочется диапазон расстояний от пары километров до полу тысячи. 500 км что-ли... |
Re: расчет фрактала на большой выборке | |
---|---|
_vit Сообщений: 5173 Дата регистрации: 29.07.2002 |
По сути исходные данные есть ч/б векторная графика. Только не в декартовой а в сферической системе координат.
Возможно подойдут какие то функции выделения региона интереса и сжатия изображения из готовых библиотек. |
Re: расчет фрактала на большой выборке | |
---|---|
boba Автор Сообщений: 6269 Откуда: Медвежьи озера- Дата регистрации: 26.03.2001 |
Предложение Игоря пока рулит.
Правда времена не малые. До расчета фрактала расчет матрицы 200 на 400 шел 13 часов на рабочей персоналке. Посмотрел на результаты, крупновато, нужно 400 * 600 Пока не знаю, на сколько потянет расчет графика фрактальности по таким матрицам. |
© 2000-2024 Fox Club  |