Algorytm na ekstremum lokalne (Perl)

[Vigl]

Chciałbym w jak najlepszy sposób znaleźć wszystkie ekstrema funkcji dyskretnej (dane z eksperymentu rozmieszczone w tabeli; [czas, wartość]). Z jakiego algorytmu najlepiej tu skorzystać? Raczkuję w metodach numerycznych, a tu muszę zastosować coś profesjonalnego - zwyczajne porównywanie kolejnych kilku punktów z odpowiednimi "IFami" nie sprawdza się (a w zasadzie, to się sprawdza, ale za mało ). Z czego tu skorzystać? Jakieś numeryczne szukanie pochodnej i przyrównanie jej do zera? A może jest coś lepszego? Rady mile widziane.

[Zordon]

W jakim sensie lepszego? Standardowa metoda przeciez znajdzie wszelkie ekstrema i zrobi to w najlepszej możliwej złożoności. Jeśli powiesz co dokładnie chcesz usprawnić to sprobuję pomóc

[spajder]

Przy takich danych można (i często się to robi) aproksymować funkcje metodą najmniejszych kwadratów do (choć może być inaczej) jakiegoś wielomianu.

W perlu piszesz?

[Vigl]

Heh, oczywiście masz rację i się z Tobą zgadzam, ale powiedz to mojemu supervisorowi. Mam dokonać rzeczy lekko absurdalnej - mam znaleźć dokładnie (lol) tyle samo ekstremów, ile można odczytać z wykresu sporządzonego z tych danych za pomocą e.g. excela (a więc np. ekstrema leżące blisko siebie staną się jednym, a małe piki nie zostaną za ekstremum uznane) - chodzi o usprawnienie i automatyzacje analiz, które przeprowadzają. Nie wiem, co z tym fantem zrobić, bo na moje tłumaczenie, że to jest raczej niemożliwe, by znaleźć uniwersalny warunek ich satysfakcjonujący dostałem tylko: "chłopcze, my tutaj rzeczy niemożliwe robimy na wczoraj, a na cuda to trzeba trochę poczekać" (tak, tak - praktyki). Supervisor zalecił mi poczytanie TA-LIBa, twierdząc, że przez rok zajmował się analizą techniczną i "dla takich ładnych krzywych to na pewno da się zrobić i to dokładnie". Polecał poczytanie o MAPD or smth (średnia krocząca z czymś tam) - swoją drogą ciekawe co to może mieć wspólnego z ekstremami lokalnymi? Spróbuje metodą klasyczną, mam jedynie nadzieję, że zgrabnie to "wkodzę" w tę moją perlową papkę (swoją drogą to przecież też jest przybliżona metoda, tylko dla nieskończenie małych przedziałów iloraz różnicowy przechodzi w pochodną - pozostanie więc jeszcze kwestia dobrania odpowiedniej ilości kroków).

Cóż, popróbuję, ale będę wdzięczny za przybliżenie mi innych metod podejścia do tego problemu. Wiem, że zadanie jest dziwne. Jak kogoś to zaintrygowało, ma czas i nieco cierpliwości dla mojego programistycznego lamerstwa, to chętnie prześle przykładowy plik, na którym pracuję oraz podzielę się stworzonym w pocie czoła dotychczasowym kodem.

-- 12 lipca 2009, 15:12 --

Przy takich danych można (i często się to robi) aproksymować funkcje metodą najmniejszych kwadratów do (choć może być inaczej) jakiegoś wielomianu.

Czyli najpierw opisać dane przybliżonym wzorem, a następnie bawić się w pochodne? Nie wiem czy bym podołał...

W perlu piszesz?

Owszem. W tę środę go poznałem. Sympatyczny.