В контексте статьи это наверное даже смешно ;-) Но мир настолько разнообразен, что даже в такой ситуации обработка рядов порой приносит ощутимую пользу с точки зрения научного знания... Попросту говоря, "искали то не знаю что", а там и правда что-то интересное обнаружилось ;-)
> Если шум аддитивный и стационарный, то особых сложностей с оптимальным приемом нет.
ФШ по определению нестационарный. Матожидание модуля формально рассчитанной АКФ никогда, даже на бесконечно больших лагах, до нуля не спадает.
Пример двух ФШ сигналов и их АКФ. Конечные модельные реализации
Два ФШ сигнала
Их АКФ. Незначительный спад объясняется конечной длиной рядов.
Поэтому сама идея понятна, но напрямую неприменима. Если я правильно понимаю, то корреляционная матрица R шума у нас будет вырожденной?
А модифицировать этот подход так, чтобы оно худо-бедно работало и в варианте с ФШ, у меня мозгов не хватает. Я не прошу строгие формулы (для нестационарных процессов их наверное вообще не бывает?). Но хотя бы какие-то полуэмпирические алгоритмы возможны? Типа того, что мы
приспособили
идея в том, что мы берем обычную формулу для рядов без NaN и подмухлевываем ее таким образом, чтобы вычисляемая оценка оказалась несмещенной, даже если в сигналах есть NaN-ы. Ну и чтобы формула сходилась к классической по мере уменьшения количества Nan до нуля. В общем случая задача, разумеется, некорректная. Но для многих практических случаев алгоритмы вполне работают. PDF статьи тут.
для различных расчетов при наличии Nan-значений в сигналах.
> что из сигнала является шумом, а что полезным сигналом который подлежит исследованию.
Если б мы это знали!
То есть, в отдельных случаях - да, вполне себе знаем. Например, есть приливный сигнал, он теоретически считается, поэтому наблюдая отклик на этот сигнал на выходе черного ящика, можно довольно много узнать про наш этот ЧЯ (=геофизическую среду).
Но очень много задач относится к поисковым. То есть мы не знаем, как выглядит этот полезный сигнал, а скорее гадаем. И, обнаружив подозрительный паттерн, затем прикладываем его к разным гипотезам: согласуется ли? А если да, то какие будут оценки вот у этих параметров вот у этой модели?
Но в целом это действительно немного напоминает поиск сигналов от инопланетного разума. С той разницей, что мы почти уверены в существовании огромного количества всевозможных сигналов, возникающих по ходу разных процессов в Земле. Некоторые из них настолько сильны, что С/Ш изначально >>1, и тогда проблем нет. Накопление не нужно вообще. Но такие явления уже в основном все изучены и известны. Сейчас фронт смещается к порогу С/Ш=1, и даже хотелось бы немного ниже забраться. Проблема в том, что даже на уровне С/Ш=1 мы не можем ничего сказать про сигнал без его накопления, так как априорные данные и про С, и про Ш очень скудны.
Откуда и вытекает вопрос про подавление ФШ накоплением...
> Насколько я могу себе представить даже АЧХ вот того интегратора через который проходит шум и динамика ее изменений может представлять интерес.
Да, именно так.
То есть у вас же нет специально сформированного аналогово сигнала который несет цифровую информацию, зачем же вам битовая скорость по Шеннону
Собственно битовая скорость - да, не нужна. Но вопрос в сущности очень близкий (и там, и там мы фактически давим шум избыточным кодом, в простейшем случае - накоплением, и оцениваем необходимую степень избыточности). А поскольку у меня паранойя, то когда я вижу толпу специалистов из соседней области, то в воспаленном воображении сразу начинаешь подозревать: а вдруг они эту задачу уже решили?!
> я могу только предположить что давить тогда надо не накоплением, а как-то иначе.
Но как?
Вот у нас (в геодинамическом мониторинге) есть измеренный многолетний ряд. Навскидку это ФШ. Есть версия, что там присутствует полезный сигнал. Причем мы даже не знаем, какой именно. Есть только гипотеза, что он с какими-то вариациями повторяется время от времени (например, во время землетрясений). Дальше мы накладываем несколько эпох и надеемся, что ФШ при этом подавится (он же случайный), а сигнал останется. И вот дальше возникает вопрос: а во сколько раз мы подавили ФШ? На сколько процентов результат накопления - это искомый сигнал, а на сколько - остаток от неподавленного ФШ?
Я, конечно, пытаюсь на него отвечать численным моделированием. Но если честно, мне это больше напоминает
анекдот про профессора с обезьяной
Удивительно, но не нашел в сети
полной версии этого анекдота
Впрочем, возможно ее и не было никогда - а дополнения самостоятельно приросли к базовой версии в нашей компании?
Короче, у нас его рассказывали вот так:
Диссертант исследует творческие способности обезьян. В пустой комнате пальма с бананом (ствол обмотан скользкой пленкой, залезть нельзя), в одном углу стул, в другом углу палка. Впускают обезьяну. Она прыгает (не достала), трясет пальму (не падает), берет палку (не достает), кидает палку (не попадает), пододвигает стул (не достает), берт палку и со стула сбивает банан. Обезьяне дают премиальный банан и уводят, аспирант готовится запустить следующую особь.
Тут приходит профессор (шеф), и говорит: а давайте я проверю Вашу методику? Аспирант соглашается, пускает его в комнату, показывает лабораторное оборудование. Вот говорит, надо достать приманку. Профессор прыгает (не достал), трясет пальму (не падает). Профессор в задумчивости: да, хороший эксперимент, тут и правда надо подумать!
Аспирант уходит за обезьяной, но там какие-то накладки, и вынужденно возвращается только вечером, так как его срочно зовут в учебный корпус: профессор куда-то пропал, и надо за него провести семинар. По дороге проходит мимо своей лаборатории. Там в комнате профессор с криками "Чего там думать, РАБОТАТЬ надо!" уже полдня остервенело трясет пальму...
А мне все-таки хочется хоть немного понятной теории от умных людей...
> Еще вопрос почему вы выбрали именно этот частотный диапазон с этим шумом, этот шум же убывает, что мешает передвинуться вправо, чтобы просто уйти от него?
Да это не я выбрал ;-) Помните
такой лозунг
Берегите природу, мать вашу!
так вот, это она, родимая. Вся геофизика - это
один сплошной фликкер-шум.
Подробнее, например, вот в этой статье 1997г (текста нет, но по ссылке можно найти версию на английском языке). Или вот коротенькая статья 2003г с текстом. Ну или вот этот талмуд 1996 года (наш текст там смотреть не стоит, основное луче глянуть в статьях, а вот за обзором приглашаю в талмуд. Текст там есть).
И еще довольно много материалов по теме в моей папке на Я-диске.
Короче, здесь частотный диапазон выбираем не мы (с) ;-)
Так что я рад за
связистов, которым не надо ждать милостей от природы (с)
хотя по моим представлениям, ФШ открыли именно в радиофизике, и для аналоговых устройств он там до сих пор актуален
> алгоритм который адаптивно запрещает к использованию частоты на которых обнаружены помехи,
В том-то и дело, что у ФШ не выделенных частот. Это абсолютно случайный процесс, НО с автокорреляцией. Почему с ним и сложно бороться.
Простейший пример: берем БШ, затем интегрируем. Получаем т.н. процесс с независимыми случайными приращениями. Кстати, у него степенной параметр спектра как раз 2.0. Теперь подаем этот шум в канал связи... Есть идеи, как изменятся приведенные в статье формулы?
А фликкер-шум в канал не хотите? Да еще с показателем степени ближе к 2...
И вот уже горькими слезами плачут все формулы. Так как для подавления такого шума избыточность кода должна быть гораздо выше. Ведь фликкерный (=автокоррелированный) шум не давится накоплением, как корень из N.
А серьезный вопрос в том, во сколько именно раз выше? Точнее, как это отношение зависит от степенного параметра над частотой (=степенного параметра спектра шума)?
У меня не хватает мозгов эту формулу вывести. Хотя бы асимптотику. И найти ее нигде не могу. Есть только смутное подозрение, что когда степенной параметр приближается к 2, это отношение стремится к бесконечности.
Вы не думал в эту сторону? Или может в литературе что-то встречали?
P.S. Кстати, корни проблемы ложных корреляций растут отсюда же...
@firegurafiku, спасибо! Скачал, глянул пока очень бегло... кажется, это как раз то, что нужно!
Не исключено, что в университете в курсе векторного и тензорного анализа до тензоров просто не дошли.
Кстати, да. Я хотя и не был отличником, но учиться приходилось серьезно,
чтобы стипендии не лишиться.
Так как жил я в основном на нее. Ну и на "летнюю халяву", естественно. Был самый конец СССР, тогда геологи охотно брали студентов-физиков в свои партии. Это давало приличные деньги и массу впечатлений, ну и жизненного опыта заодно ;-) И профессионального, кстати, тоже.
У меня до сих пор тетрадки с конспектами остались. А в некоторые я порой даже заглядываю, так как в интернете (как ни странно) до сих пор далеко не все можно найти. Но вот тензоров я у себя в тетрадках не обнаружил. Так что вполне возможно, что действительно мы по ним очень кратко прошлись.
досконально разбираться в тензорах нужно только на некоторых специальностях теоретической физики.
Как оказалось в моем случае - не только теоретической ;-) Я вот вообще специализируюсь по временным рядам в геофизике... много лет занимался статобработкой, и горя не знал. Однако же механика сплошных сред, как выяснилось, все это время караулила за углом ;-)
@igaraja, спасибо! Кажется, теперь начал понимать. Текст статьи не рассчитан на мимокрокодилов (строго говоря, автор и не должен об этом думать). Поэтому я и протупил.
Я просто сам всегда компилирую с оптимизацией скорости, поэтому в моем случае память для сложной константной структуры при вызове функции не аллоцируется вообще никогда. Ни на куче, ни в стеке. Поэтому меня и удивило, что аллокация в стеке - это достоинство. Я просто не сразу сообразил, что речь в статье идет про сравнение плохого варианта с еще более худшим ;-)))
UPD. Уточнил в дизассемблере. На самом деле иногда все-таки аллоцируется. Если функция просто устроена, и мне не требуется многократный доступ к отдельным полям структуры в разных местах функции, то мой компилятор тоже может разместить ее в стеке (вероятно, чтобы не прыгать по дальним адресам памяти?). Возможно, в противном случае работа с ней через стек становится чересчур накладной? Если, конечно, я правильно в дизассемблере разобрался. Но если в двух словах, то, наверно, в моем случае так: пока я не напишу указания в явном виде, компилятор все это решает на свое усмотрение.
Вообще, похоже, что тема не так проста, как кажется. Попробую при случае покопать ассемблерный код ;-) Проблема в том, что при разных опциях компилятора и в зависимости от ключевых слов, которыми я сопровождаю объявление этой структуры, ассемблерный код получается абсолютно различный. Двух одинаковых байт не найти ;-) Создатели компилятора явно не предполагали, что юзер туда в этот код полезет копаться ;-))))
P.S.
Наверно, эту статью вообще не следовало читать человеку, который и так уже использует максимально эффективный для вычислений язык, и поэтому лишь мимоходом интересуется Julia... Простите, что залез в чужой монастырь :-(((
Неизменяемые структуры могут быть не такие удобными в плане интерфейса их использования. Но их преимуществом является размещение «на стеке»
Я тут крокодил мимо, и, наверно, поэтому не смог разобраться: а в чем преимущество-то? Разве это не должно зависеть от того, как используется структура? Например, если у меня есть глобальная неизменяемая структура, при чем тут стек-то?
> Вы же пытаетесь показать, что умение строить грамотные SQL запросы - это вообще краеугольный камень программирования и без этого там нечего делать... Хотя по факту это нужно далеко не всегда и не всем...
Да, квантор всеобщности в статье явно лишний.
> Почему нужно сначала изучить SQL;
Да-да. Обязательно!
Расскажите геофизикам, которые хранят гигабайтные данные в собственных специфических базах, или сейсмологам, ориентированным на Mseed,что их жизнь пуста и бессмысленна без знания SQL. И почему в их программах (где действительно используются очень нетривиальные алгоритмы, сильно выходящие за пределы обычных курсов) этот самый SQL является тем краеугольным камнем, без которого нет смысла даже и начинать. Да половина из тех, кто всю жизнь успешно и эффективно работает с этими данными, и пишет для этого не только собственные программы, но зачастую и алгоритмы (которые нормальному фронтэндеру в страшном сне не приснятся), даже такого слова не слышали ;-)
См. предпоследнюю строку, где функция даже не вызывается, а заменяется вычисленным во время компиляции значением..
$-)
Да, конечно ;-) Но это все-таки довольно простой случай. А мне хочется понять, что произойдет по мере накопления сложности? Есть подозрение, что на каком-то уровне сложности (например, если в вычислениях задействовано много функций, и не все они "чистые", ну или еще почему-то), компилятор перестанет воспринимать задачу в целом, и вместо полной оптимизации ограничится локальными улучшениями кода. Гипотезасостоит в том, что при записи одного и того же алгоритма через циклы и через рекурсию в последнем случае этот момент наступит раньше.
Но, это именно мое "подозрение" и "гипотеза". А вот как оно реально работает - я бы сам очень хотел узнать.
Дисклеймер
Главное - это не забывать, что в действительности все не так, как на самом деле (с). На заре моей компьютерной молодости это было моим девизом ;-)
UPD
Я этой фразой много лет пользовался, не зная, кто автор (дело было еще до интернета). А недавно открыл, что это Станислав Ежи Лец. Хорошо топтать плечи гигантов! ;-)
Но тогда получается, что оптимизация рекурсивного алгоритма - это на порядок более сложная задача для компилятора, чем даже оптимизация цикла?!
> Почему?
Я не специалист по компиляторам, поэтому никаких серьезных обоснований у меня нет. Просто есть такое впечатление, основанное на том, что в цикле все прописано в явном виде, а рекурсию надо распознавать и раскручивать. Взять, например , количество итераций: многие формы записи цикла позволяют его определить сразу при входе в цикл. При итеративной записи даже в самом простейшем случае компилятору придется задуматься. А еще, если в коде есть этот самый call, то это уже получается межпроцедурная оптимизация, что по идее сложнее. Особенно когда этих вложенных вызовов несколько...
В общем, определенные причины так думать у меня есть, но не более того. Для получения обоснованного ответа надо вызывать чистильщика обращаться к специалисту по компиляторам. Такому, как уже упомянутый здесь уважаемый @xortator. Ну или может еще кто-то откликнется?
> Например, массивный оператор не обязан внутри себя выполняться последовательно
Кстати, да! Что резко расширяет свободу компилятора оптимизизировать или распараллеливаать вычисления,
> и это подрывает его операционную связь как с циклическим, так и с рекурсивным алгоритмом.
Но тогда получается, что оптимизация рекурсивного алгоритма - это на порядок более сложная задача для компилятора, чем даже оптимизация цикла?!
> А для компилятора в принципе что цикл, что рекурсия – один фиг.
Если моя гипотеза выше (в прошлой фразе) верна, то совсем даже нет. Как только мы начинаем оптимизацию, будет две больших разницы?
> Другое дело, что компилятор Фортрана гораздо больше ориентирован на оптимизацию циклов, чем рекурсивных вызовов, по чисто прагматической причине.
А вот тут я бы не подписался безоговорочно. С одной стороны, спору нет: циклы конечно встречаются чаще и оптимизировать их важнее. Но может быть, есть и вторая сторона медали, что оптимизировать циклы банально проще?
> Если убрать множественные рекурсивные вызовы, дурящие голову компилятору Фортрана, и оставить одномерный массив такого же размера (...) то тогда компилятор понимает, что рекурсия является хвостовой, и время работы всех трёх программ оказывается равно между собой.
Вот в этом-то и проблема. В реальной жизни часто встречаются всякие прибамбасы, которые могут кому угодно запудрить мозги. Моя гипотеза - что обычно компилятору сложнее разобраться в рекурсивной записи, чем в нерекурсивной. Или нет?
Недавно здесь на Хабре был замечательный цикл статей про оптимизирующие компиляторы от уважаемого @xortator. В том числе, там довольно подробно рассматривались циклы и их "размотка". Если вдруг этот мудрый человек нас сейчас слышит, было бы очень интересно узнать его мнение по этим вопросам.. Пожалуйста...
Мне конечно сложно оценивать, так как я и мои друзья правда "...привыкли представлять себе массивный оператор таким образом". Но на мой субъективный вкус, тройной цикл в программе m2 все-таки попонятнее, чем нанизанные if - else в m3. Поэтому было бы очень интересно узнать: а как оценивается этот код с точки зрения человека, привыкшего к рекурсивной форме выражения мыслей?
> Но проблема в том, что gfortran не понимает, что здесь рекурсия хвостовая.
Давайте все-таки разделим два эти вопроса? Или даже точнее три:
1) Читаемость и понятность кода с точки зрения типичного программиста 2) Способность конкретного компилятора эффективно оптимизировать рекурсивные вызовы 3) Насколько пострадает задача (1), если мы будем вынуждены искусственно помогать компилятору
справиться с (2)?
допустим, он такое умеет
Мое субъективное мнение: 1) Циклы все же понятнее (Но! это зависит от "воспитания" и предыдущего опыта); 2) Компилятору наверное проще оптимизировать цикл, чем рекурсию? 3) Если такая задача становится актуальной, значит выбран не самый подходящий для данного случая язык программирования
Ну и конечно, наилучшим решением задач (1) и (3) я по-прежнему считаю массивные операторы. А задачу (2) компилятору в этом случае вообще не нужно решать ;-).
> Пишете здравицу за циклы, а приводите в пример массивный оператор.
Я бы тут с Вами не согласился. В моем представлении, массивный оператор - это именно форма записи цикла. Во всяком случае, абсолютно все знакомые мне программисты (причем не только пишущие на фортране!) воспринимают его именно так.
Я не сомневаюсь, что рекурсией его записать тоже можно. Вот только удобно ли? А главное, зачем? Напишите, для примера, рекурсию для двух-трехмерного массива - и сравните, какой код
Я бы сам с удовольствием написал, но вряд ли сумею реализовать рекурсию оптимально. Поэтому мне правда интересно посмотреть на по-настоящему неплохую реализацию
Я уж не говорю, что если вдруг компилятор окажется недостаточно умным, и вдруг все-таки реализует рекурсию через call, то на одной только передаче параметров (которая в фортране реализована максимально эффективно!) мы сразу проиграем не проценты, а много крат.
А распознать ее ему будет очень непросто, так как массивный оператор (=цикл) может оказаться гораздо более хитрым, чем приведенные выше тривиальные примеры. В том неидеальном мире, где я живу, я вот сплошь и рядом использую, например, массивный оператор where для отсечения Nan-значений. В комбинации с другими массивными операторами в не очень простых выражениях (и это мы еще про сечения массивов не вспомнили).
И если циклами я это все еще могу более-менее расписать, то аналогичный код на рекурсии - даже не представляю, сколько сил и времени может отнять. Его же надо не только написать, но еще и отладить. Я конечно верю, что специалисту все это - раз плюнуть. Но мы же сейчас говорим о
среднестатистическом программисте?
У которого, разумеется, есть в том числе и какой-то практический опыт с рекурсией. Лично у меня в таком стиле работа с файловой системой закручена. Ну и плюс к этому еще 500 тысяч строк лично написанного кода в продакте (работающих прямо сейчас). На основании чего я все-таки наберусь наглости выдвинуть свою кандидатуру на должность этого самого "среднего" программиста. Для которого цикл: а) на порядок естественнее и понятнее, и б) при решении реальных задач позволяет писать гораздо более эффективный код
> На самом деле call это и есть jmp только с дополнительной нагрузкой (а icall, это расширенный ijmp).
Именно что!
Я не могу сейчас сгенерировать пример кода, чтобы проверить, распознает ли компилятор рекурсию,
и заменит ли циклом
дело даже не в том, что нет времени, но у меня компилятор 2008 года, так что ответ про современные компиляторы мы все равно не получим
Но когда-то давно я в учебных целях экспериментировал с рекурсивными вызовами в фортране. И машинный код при любом уровне оптимизации получался гораздо хуже. Собственно, не потому ли на протяжении всей моей жизни перемалыватели чисел пишутся на тех языках, где базовая структура - цикл? А рекурсия представляет собой скорее синтаксический сахар полезную нишевую фичу для особых задач, чем базовый элемент языка, без которого все остальное рассыпается вдребезги пополам?
> Но это и к циклам относится в той же самой мере.
Вот как раз на циклы все современные компиляторы натасканы круче некуда. Если эффективность не стоит на последнем месте, конечно. В том же фортране никому и в страшном сне не придет в голову заменять массивный оператор a=f(b), или a=b+c, где a, b и c- многомерные массивы, а f -
элементная функция
т.е. каждый элемент массива a = результат применения функции f к соответствующему элементу массива и b
на рекурсию. Мало того, что далеко не всякий фортранист с этим справится, так еще и машинный код с 99.9999%-ной гарантией получится в разы менее эффективным.
Да, ГСЧ в современном Exctll явно лучше, чем в фортране 2008 года. Но в моем случае E+9 - это, конечно, не период повторяемости ГСЧ, а период возникновения определенных аномалий в моем сигнале. Причем это не точный период, а плавающий. И вот он на порядки меньше
периода повторяемости самого ГСЧ (около E+18)
RANDOM_NUMBER
Intrinsic Subroutine: Returns one pseudorandom number or an array of such numbers.
CALL RANDOM_NUMBER (harvest)
harvest
(Output) Must be of type real. It can be a scalar or an array variable. It is set to contain pseudorandom numbers from the uniform distribution within the range 0 <= x < 1.
The seed for the pseudorandom number generator used by RANDOM_NUMBER can be set or queried with RANDOM_SEED. If RANDOM_SEED is not used, the processor sets the seed for RANDOM_NUMBER to a processor-dependent value.
The RANDOM_NUMBER generator uses two separate congruential generators together to produce a period of approximately 10**18, and produces real pseudorandom results with a uniform distribution in (0,1). It accepts two integer seeds, the first of which is reduced to the range [1, 2147483562]. The second seed is reduced to the range [1, 2147483398]. This means that the generator effectively uses two 31-bit seeds.
For more information on the algorithm, see the following:
Communications of the ACM vol 31 num 6 June 1988, titled: Efficient and Portable Combined Random Number Generators by Pierre L'ecuyer.
Springer-Verlag New York, N. Y. 2nd ed. 1987, titled: A Guide to Simulation by Bratley, P., Fox, B. L., and Schrage, L. E.
В общем, некая неслучайность присутствует. И при решении некоторых задач это может быть неприятно.
И второй нюанс: если нам нужна выборка большого объема, то мы точно не будем работать в Excell. А значит и обращаться к его ГСЧ не сможем (технически это возможно, но скорость будет несоразмерна задаче). А вот какие ГСЧ используются сейчас в стандартных библиотеках, это вопрос. В моем случае (компиляторы Интел, 2008 год) плюсы и фортран к одному и тому же ГСЧ обращались. Как сейчас - не знаю (компилятор пока не могу обновить), но шанс столкнуться с подобным багом вполне реален. На что собственно и намекает довольно свежая хабровская статья уважаемого @red-cat-fat, которую я упомянул в первом комменте
> У вас тяжелый случай... сигнал неизвестен.
Спасибо за понимание ;-)
В контексте статьи это наверное даже смешно ;-) Но мир настолько разнообразен, что даже в такой ситуации обработка рядов порой приносит ощутимую пользу с точки зрения научного знания... Попросту говоря, "искали то не знаю что", а там и правда что-то интересное обнаружилось ;-)
> Если шум аддитивный и стационарный, то особых сложностей с оптимальным приемом нет.
ФШ по определению нестационарный. Матожидание модуля формально рассчитанной АКФ никогда, даже на бесконечно больших лагах, до нуля не спадает.
Пример двух ФШ сигналов и их АКФ. Конечные модельные реализации
Поэтому сама идея понятна, но напрямую неприменима. Если я правильно понимаю, то корреляционная матрица R шума у нас будет вырожденной?
А модифицировать этот подход так, чтобы оно худо-бедно работало и в варианте с ФШ, у меня мозгов не хватает. Я не прошу строгие формулы (для нестационарных процессов их наверное вообще не бывает?). Но хотя бы какие-то полуэмпирические алгоритмы возможны? Типа того, что мы
приспособили
идея в том, что мы берем обычную формулу для рядов без NaN и подмухлевываем ее таким образом, чтобы вычисляемая оценка оказалась несмещенной, даже если в сигналах есть NaN-ы. Ну и чтобы формула сходилась к классической по мере уменьшения количества Nan до нуля. В общем случая задача, разумеется, некорректная. Но для многих практических случаев алгоритмы вполне работают. PDF статьи тут.
для различных расчетов при наличии Nan-значений в сигналах.
> что из сигнала является шумом, а что полезным сигналом который подлежит исследованию.
Если б мы это знали!
То есть, в отдельных случаях - да, вполне себе знаем. Например, есть приливный сигнал, он теоретически считается, поэтому наблюдая отклик на этот сигнал на выходе черного ящика, можно довольно много узнать про наш этот ЧЯ (=геофизическую среду).
Но очень много задач относится к поисковым. То есть мы не знаем, как выглядит этот полезный сигнал, а скорее гадаем. И, обнаружив подозрительный паттерн, затем прикладываем его к разным гипотезам: согласуется ли? А если да, то какие будут оценки вот у этих параметров вот у этой модели?
Но в целом это действительно немного напоминает поиск сигналов от инопланетного разума. С той разницей, что мы почти уверены в существовании огромного количества всевозможных сигналов, возникающих по ходу разных процессов в Земле. Некоторые из них настолько сильны, что С/Ш изначально >>1, и тогда проблем нет. Накопление не нужно вообще. Но такие явления уже в основном все изучены и известны. Сейчас фронт смещается к порогу С/Ш=1, и даже хотелось бы немного ниже забраться. Проблема в том, что даже на уровне С/Ш=1 мы не можем ничего сказать про сигнал без его накопления, так как априорные данные и про С, и про Ш очень скудны.
Откуда и вытекает вопрос про подавление ФШ накоплением...
> Насколько я могу себе представить даже АЧХ вот того интегратора через который проходит шум и динамика ее изменений может представлять интерес.
Да, именно так.
То есть у вас же нет специально сформированного аналогово сигнала который несет цифровую информацию, зачем же вам битовая скорость по Шеннону
Собственно битовая скорость - да, не нужна. Но вопрос в сущности очень близкий (и там, и там мы фактически давим шум избыточным кодом, в простейшем случае - накоплением, и оцениваем необходимую степень избыточности). А поскольку у меня паранойя, то когда я вижу толпу специалистов из соседней области, то в воспаленном воображении сразу начинаешь подозревать: а вдруг они эту задачу уже решили?!
Ну вот я и лезу к ним со своими вопросами...
> я могу только предположить что давить тогда надо не накоплением, а как-то иначе.
Но как?
Вот у нас (в геодинамическом мониторинге) есть измеренный многолетний ряд. Навскидку это ФШ. Есть версия, что там присутствует полезный сигнал. Причем мы даже не знаем, какой именно. Есть только гипотеза, что он с какими-то вариациями повторяется время от времени (например, во время землетрясений). Дальше мы накладываем несколько эпох и надеемся, что ФШ при этом подавится (он же случайный), а сигнал останется. И вот дальше возникает вопрос: а во сколько раз мы подавили ФШ? На сколько процентов результат накопления - это искомый сигнал, а на сколько - остаток от неподавленного ФШ?
Я, конечно, пытаюсь на него отвечать численным моделированием. Но если честно, мне это больше напоминает
анекдот про профессора с обезьяной
Удивительно, но не нашел в сети
полной версии этого анекдота
Впрочем, возможно ее и не было никогда - а дополнения самостоятельно приросли к базовой версии в нашей компании?
Короче, у нас его рассказывали вот так:
Диссертант исследует творческие способности обезьян. В пустой комнате пальма с бананом (ствол обмотан скользкой пленкой, залезть нельзя), в одном углу стул, в другом углу палка. Впускают обезьяну. Она прыгает (не достала), трясет пальму (не падает), берет палку (не достает), кидает палку (не попадает), пододвигает стул (не достает), берт палку и со стула сбивает банан. Обезьяне дают премиальный банан и уводят, аспирант готовится запустить следующую особь.
Тут приходит профессор (шеф), и говорит: а давайте я проверю Вашу методику? Аспирант соглашается, пускает его в комнату, показывает лабораторное оборудование. Вот говорит, надо достать приманку. Профессор прыгает (не достал), трясет пальму (не падает). Профессор в задумчивости: да, хороший эксперимент, тут и правда надо подумать!
Аспирант уходит за обезьяной, но там какие-то накладки, и вынужденно возвращается только вечером, так как его срочно зовут в учебный корпус: профессор куда-то пропал, и надо за него провести семинар. По дороге проходит мимо своей лаборатории. Там в комнате профессор с криками "Чего там думать, РАБОТАТЬ надо!" уже полдня остервенело трясет пальму...
А мне все-таки хочется хоть немного понятной теории от умных людей...
> Еще вопрос почему вы выбрали именно этот частотный диапазон с этим шумом, этот шум же убывает, что мешает передвинуться вправо, чтобы просто уйти от него?
Да это не я выбрал ;-) Помните
такой лозунг
Берегите природу, мать вашу!
так вот, это она, родимая. Вся геофизика - это
один сплошной фликкер-шум.
Подробнее, например, вот в этой статье 1997г (текста нет, но по ссылке можно найти версию на английском языке). Или вот коротенькая статья 2003г с текстом. Ну или вот этот талмуд 1996 года (наш текст там смотреть не стоит, основное луче глянуть в статьях, а вот за обзором приглашаю в талмуд. Текст там есть).
И еще довольно много материалов по теме в моей папке на Я-диске.
Короче, здесь частотный диапазон выбираем не мы (с) ;-)
Так что я рад за
связистов, которым не надо ждать милостей от природы (с)
хотя по моим представлениям, ФШ открыли именно в радиофизике, и для аналоговых устройств он там до сих пор актуален
но вот у нас так не получится :-(
> алгоритм который адаптивно запрещает к использованию частоты на которых обнаружены помехи,
В том-то и дело, что у ФШ не выделенных частот.
Это абсолютно случайный процесс, НО с автокорреляцией.
Почему с ним и сложно бороться.
Простейший пример: берем БШ, затем интегрируем. Получаем т.н. процесс с независимыми случайными приращениями. Кстати, у него степенной параметр спектра как раз 2.0. Теперь подаем этот шум в канал связи... Есть идеи, как изменятся приведенные в статье формулы?
:
> средней мощности гауссового шума N
Везунчики вы! :-)
А фликкер-шум в канал не хотите? Да еще с показателем степени ближе к 2...
И вот уже горькими слезами плачут все формулы. Так как для подавления такого шума избыточность кода должна быть гораздо выше. Ведь фликкерный (=автокоррелированный) шум не давится накоплением, как корень из N.
А серьезный вопрос в том, во сколько именно раз выше?
Точнее, как это отношение зависит от степенного параметра над частотой (=степенного параметра спектра шума)?
У меня не хватает мозгов эту формулу вывести. Хотя бы асимптотику. И найти ее нигде не могу. Есть только смутное подозрение, что когда степенной параметр приближается к 2, это отношение стремится к бесконечности.
Вы не думал в эту сторону? Или может в литературе что-то встречали?
P.S. Кстати, корни проблемы ложных корреляций растут отсюда же...
@firegurafiku, спасибо! Скачал, глянул пока очень бегло... кажется, это как раз то, что нужно!
Не исключено, что в университете в курсе векторного и тензорного анализа до тензоров просто не дошли.
Кстати, да. Я хотя и не был отличником, но учиться приходилось серьезно,
чтобы стипендии не лишиться.
Так как жил я в основном на нее. Ну и на "летнюю халяву", естественно. Был самый конец СССР, тогда геологи охотно брали студентов-физиков в свои партии. Это давало приличные деньги и массу впечатлений, ну и жизненного опыта заодно ;-)
И профессионального, кстати, тоже.
У меня до сих пор тетрадки с конспектами остались. А в некоторые я порой даже заглядываю, так как в интернете (как ни странно) до сих пор далеко не все можно найти. Но вот тензоров я у себя в тетрадках не обнаружил. Так что вполне возможно, что действительно мы по ним очень кратко прошлись.
досконально разбираться в тензорах нужно только на некоторых специальностях теоретической физики.
Как оказалось в моем случае - не только теоретической ;-) Я вот вообще специализируюсь по временным рядам в геофизике... много лет занимался статобработкой, и горя не знал. Однако же механика сплошных сред, как выяснилось, все это время караулила за углом ;-)
@igaraja, спасибо! Кажется, теперь начал понимать. Текст статьи не рассчитан на мимокрокодилов (строго говоря, автор и не должен об этом думать). Поэтому я и протупил.
Я просто сам всегда компилирую с оптимизацией скорости, поэтому в моем случае память для сложной константной структуры при вызове функции не аллоцируется вообще никогда. Ни на куче, ни в стеке. Поэтому меня и удивило, что аллокация в стеке - это достоинство. Я просто не сразу сообразил, что речь в статье идет про сравнение плохого варианта с еще более худшим ;-)))
UPD. Уточнил в дизассемблере. На самом деле иногда все-таки аллоцируется. Если функция просто устроена, и мне не требуется многократный доступ к отдельным полям структуры в разных местах функции, то мой компилятор тоже может разместить ее в стеке (вероятно, чтобы не прыгать по дальним адресам памяти?). Возможно, в противном случае работа с ней через стек становится чересчур накладной? Если, конечно, я правильно в дизассемблере разобрался. Но если в двух словах, то, наверно, в моем случае так: пока я не напишу указания в явном виде, компилятор все это решает на свое усмотрение.
Вообще, похоже, что тема не так проста, как кажется. Попробую при случае покопать ассемблерный код ;-) Проблема в том, что при разных опциях компилятора и в зависимости от ключевых слов, которыми я сопровождаю объявление этой структуры, ассемблерный код получается абсолютно различный. Двух одинаковых байт не найти ;-) Создатели компилятора явно не предполагали, что юзер туда в этот код полезет копаться ;-))))
P.S.
Наверно, эту статью вообще не следовало читать человеку, который и так уже использует максимально эффективный для вычислений язык, и поэтому лишь мимоходом интересуется Julia... Простите, что залез в чужой монастырь :-(((
Неизменяемые структуры могут быть не такие удобными в плане интерфейса их использования. Но их преимуществом является размещение «на стеке»
Я тут крокодил мимо, и, наверно, поэтому не смог разобраться: а в чем преимущество-то? Разве это не должно зависеть от того, как используется структура? Например, если у меня есть глобальная неизменяемая структура, при чем тут стек-то?
> Вы же пытаетесь показать, что умение строить грамотные SQL запросы - это вообще краеугольный камень программирования и без этого там нечего делать...
Хотя по факту это нужно далеко не всегда и не всем...
Да, квантор всеобщности в статье явно лишний.
> Почему нужно сначала изучить SQL;
Да-да. Обязательно!
Расскажите геофизикам, которые хранят гигабайтные данные в собственных специфических базах, или сейсмологам, ориентированным на Mseed,что их жизнь пуста и бессмысленна без знания SQL. И почему в их программах (где действительно используются очень нетривиальные алгоритмы, сильно выходящие за пределы обычных курсов) этот самый SQL является тем краеугольным камнем, без которого нет смысла даже и начинать. Да половина из тех, кто всю жизнь успешно и эффективно работает с этими данными, и пишет для этого не только собственные программы, но зачастую и алгоритмы (которые нормальному фронтэндеру в страшном сне не приснятся), даже такого слова не слышали ;-)
Надеюсь, тут не нужно намекать, почему?
;-)
См. предпоследнюю строку, где функция даже не вызывается, а заменяется вычисленным во время компиляции значением..
$-)
Да, конечно ;-) Но это все-таки довольно простой случай. А мне хочется понять, что произойдет по мере накопления сложности? Есть подозрение, что на каком-то уровне сложности (например, если в вычислениях задействовано много функций, и не все они "чистые", ну или еще почему-то), компилятор перестанет воспринимать задачу в целом, и вместо полной оптимизации ограничится локальными улучшениями кода. Гипотеза состоит в том, что при записи одного и того же алгоритма через циклы и через рекурсию в последнем случае этот момент наступит раньше.
Но, это именно мое "подозрение" и "гипотеза". А вот как оно реально работает - я бы сам очень хотел узнать.
Дисклеймер
Главное - это не забывать, что в действительности все не так, как на самом деле (с). На заре моей компьютерной молодости это было моим девизом ;-)
UPD
Я этой фразой много лет пользовался, не зная, кто автор (дело было еще до интернета). А недавно открыл, что это Станислав Ежи Лец. Хорошо топтать плечи гигантов! ;-)
> Почему?
Я не специалист по компиляторам, поэтому никаких серьезных обоснований у меня нет. Просто есть такое впечатление, основанное на том, что в цикле все прописано в явном виде, а рекурсию надо распознавать и раскручивать. Взять, например , количество итераций: многие формы записи цикла позволяют его определить сразу при входе в цикл. При итеративной записи даже в самом простейшем случае компилятору придется задуматься. А еще, если в коде есть этот самый call, то это уже получается межпроцедурная оптимизация, что по идее сложнее. Особенно когда этих вложенных вызовов несколько...
В общем, определенные причины так думать у меня есть, но не более того. Для получения обоснованного ответа надо
вызывать чистильщикаобращаться к специалисту по компиляторам. Такому, как уже упомянутый здесь уважаемый @xortator. Ну или может еще кто-то откликнется?> Например, массивный оператор не обязан внутри себя выполняться последовательно
Кстати, да! Что резко расширяет свободу компилятора оптимизизировать или распараллеливаать вычисления,
> и это подрывает его операционную связь как с циклическим, так и с рекурсивным алгоритмом.
Но тогда получается, что оптимизация рекурсивного алгоритма - это на порядок более сложная задача для компилятора, чем даже оптимизация цикла?!
> А для компилятора в принципе что цикл, что рекурсия – один фиг.
Если моя гипотеза выше (в прошлой фразе) верна, то совсем даже нет. Как только мы начинаем оптимизацию, будет две больших разницы?
> Другое дело, что компилятор Фортрана гораздо больше ориентирован на оптимизацию циклов, чем рекурсивных вызовов, по чисто прагматической причине.
А вот тут я бы не подписался безоговорочно. С одной стороны, спору нет: циклы конечно встречаются чаще и оптимизировать их важнее. Но может быть, есть и вторая сторона медали, что оптимизировать циклы банально проще?
> Если убрать множественные рекурсивные вызовы, дурящие голову компилятору Фортрана, и оставить одномерный массив такого же размера (...) то тогда компилятор понимает, что рекурсия является хвостовой, и время работы всех трёх программ оказывается равно между собой.
Вот в этом-то и проблема. В реальной жизни часто встречаются всякие прибамбасы, которые могут кому угодно запудрить мозги. Моя гипотеза - что обычно компилятору сложнее разобраться в рекурсивной записи, чем в нерекурсивной. Или нет?
Недавно здесь на Хабре был замечательный цикл статей про оптимизирующие компиляторы от уважаемого @xortator. В том числе, там довольно подробно рассматривались циклы и их "размотка". Если вдруг этот мудрый человек нас сейчас слышит, было бы очень интересно узнать его мнение по этим вопросам.. Пожалуйста...
> Вот три программы, о которых Вы говорили:
Спасибо, действительно интересно!
Мне конечно сложно оценивать, так как я и мои друзья правда "...привыкли представлять себе массивный оператор таким образом". Но на мой субъективный вкус, тройной цикл в программе m2 все-таки попонятнее, чем нанизанные if - else в m3. Поэтому было бы очень интересно узнать: а как оценивается этот код с точки зрения человека, привыкшего к рекурсивной форме выражения мыслей?
> Но проблема в том, что gfortran не понимает, что здесь рекурсия хвостовая.
Давайте все-таки разделим два эти вопроса? Или даже точнее три:
1) Читаемость и понятность кода с точки зрения типичного программиста
2) Способность конкретного компилятора эффективно оптимизировать рекурсивные вызовы
3) Насколько пострадает задача (1), если мы будем вынуждены искусственно помогать компилятору
справиться с (2)?
допустим, он такое умеет
Мое субъективное мнение:
1) Циклы все же понятнее (Но! это зависит от "воспитания" и предыдущего опыта);
2) Компилятору наверное проще оптимизировать цикл, чем рекурсию?
3) Если такая задача становится актуальной, значит выбран не самый подходящий для данного случая язык программирования
Ну и конечно, наилучшим решением задач (1) и (3) я по-прежнему считаю массивные операторы. А задачу (2) компилятору в этом случае вообще не нужно решать ;-).
> Пишете здравицу за циклы, а приводите в пример массивный оператор.
Я бы тут с Вами не согласился. В моем представлении, массивный оператор - это именно форма записи цикла. Во всяком случае, абсолютно все знакомые мне программисты (причем не только пишущие на фортране!) воспринимают его именно так.
Я не сомневаюсь, что рекурсией его записать тоже можно. Вот только удобно ли? А главное, зачем? Напишите, для примера, рекурсию для двух-трехмерного массива - и сравните, какой код
легче понять среднестатистическому программеру/математику?
Я бы сам с удовольствием написал, но вряд ли сумею реализовать рекурсию оптимально. Поэтому мне правда интересно посмотреть на по-настоящему неплохую реализацию
Я уж не говорю, что если вдруг компилятор окажется недостаточно умным, и вдруг все-таки реализует рекурсию через call, то на одной только передаче параметров (которая в фортране реализована максимально эффективно!) мы сразу проиграем не проценты, а много крат.
А распознать ее ему будет очень непросто, так как массивный оператор (=цикл) может оказаться гораздо более хитрым, чем приведенные выше тривиальные примеры. В том неидеальном мире, где я живу, я вот сплошь и рядом использую, например, массивный оператор where для отсечения Nan-значений. В комбинации с другими массивными операторами в не очень простых выражениях (и это мы еще про сечения массивов не вспомнили).
И если циклами я это все еще могу более-менее расписать, то аналогичный код на рекурсии - даже не представляю, сколько сил и времени может отнять. Его же надо не только написать, но еще и отладить. Я конечно верю, что специалисту все это - раз плюнуть. Но мы же сейчас говорим о
среднестатистическом программисте?
У которого, разумеется, есть в том числе и какой-то практический опыт с рекурсией. Лично у меня в таком стиле работа с файловой системой закручена. Ну и плюс к этому еще 500 тысяч строк лично написанного кода в продакте (работающих прямо сейчас). На основании чего я все-таки наберусь наглости выдвинуть свою кандидатуру на должность этого самого "среднего" программиста. Для которого цикл:
а) на порядок естественнее и понятнее, и
б) при решении реальных задач позволяет писать гораздо более эффективный код
А в остальном Вы, конечно же, правы.
> На самом деле call это и есть jmp только с дополнительной нагрузкой (а icall, это расширенный ijmp).
Именно что!
Я не могу сейчас сгенерировать пример кода, чтобы проверить, распознает ли компилятор рекурсию,
и заменит ли циклом
дело даже не в том, что нет времени, но у меня компилятор 2008 года, так что ответ про современные компиляторы мы все равно не получим
Но когда-то давно я в учебных целях экспериментировал с рекурсивными вызовами в фортране. И машинный код при любом уровне оптимизации получался гораздо хуже. Собственно, не потому ли на протяжении всей моей жизни перемалыватели чисел пишутся на тех языках, где базовая структура - цикл? А рекурсия представляет собой скорее
синтаксический сахарполезную нишевую фичу для особых задач, чем базовый элемент языка, без которого все остальное рассыпается вдребезги пополам?> Но это и к циклам относится в той же самой мере.
Вот как раз на циклы все современные компиляторы натасканы круче некуда. Если эффективность не стоит на последнем месте, конечно. В том же фортране никому и в страшном сне не придет в голову заменять массивный оператор a=f(b), или a=b+c, где a, b и c- многомерные массивы, а f -
элементная функция
т.е. каждый элемент массива a = результат применения функции f к соответствующему элементу массива и b
на рекурсию. Мало того, что далеко не всякий фортранист с этим справится, так еще и машинный код с 99.9999%-ной гарантией получится в разы менее эффективным.
Да, ГСЧ в современном Exctll явно лучше, чем в фортране 2008 года. Но в моем случае E+9 - это, конечно, не период повторяемости ГСЧ, а период возникновения определенных аномалий в моем сигнале. Причем это не точный период, а плавающий. И вот он на порядки меньше
периода повторяемости самого ГСЧ (около E+18)
RANDOM_NUMBER
Intrinsic Subroutine: Returns one pseudorandom number or an array of such numbers.
CALL RANDOM_NUMBER (harvest)
harvest
(Output) Must be of type real. It can be a scalar or an array variable. It is set to contain pseudorandom numbers from the uniform distribution within the range 0 <= x < 1.
The seed for the pseudorandom number generator used by RANDOM_NUMBER can be set or queried with RANDOM_SEED. If RANDOM_SEED is not used, the processor sets the seed for RANDOM_NUMBER to a processor-dependent value.
The RANDOM_NUMBER generator uses two separate congruential generators together to produce a period of approximately 10**18, and produces real pseudorandom results with a uniform distribution in (0,1). It accepts two integer seeds, the first of which is reduced to the range [1, 2147483562]. The second seed is reduced to the range [1, 2147483398]. This means that the generator effectively uses two 31-bit seeds.
For more information on the algorithm, see the following:
Communications of the ACM vol 31 num 6 June 1988, titled: Efficient and Portable Combined Random Number Generators by Pierre L'ecuyer.
Springer-Verlag New York, N. Y. 2nd ed. 1987, titled: A Guide to Simulation by Bratley, P., Fox, B. L., and Schrage, L. E.
В общем, некая неслучайность присутствует. И при решении некоторых задач это может быть неприятно.
И второй нюанс: если нам нужна выборка большого объема, то мы точно не будем работать в Excell. А значит и обращаться к его ГСЧ не сможем (технически это возможно, но скорость будет несоразмерна задаче). А вот какие ГСЧ используются сейчас в стандартных библиотеках, это вопрос. В моем случае (компиляторы Интел, 2008 год) плюсы и фортран к одному и тому же ГСЧ обращались. Как сейчас - не знаю (компилятор пока не могу обновить), но шанс столкнуться с подобным багом вполне реален. На что собственно и намекает довольно свежая хабровская статья уважаемого @red-cat-fat, которую я упомянул в первом комменте