CYFROWY BARON • PROGRAMOWANIE

Witam, mam bardzo poważny problem, muszę zoptymalizować tak kod żeby wykonywał się co najmniej kilkadziesiąt razy szybciej, postaram się wyjaśnić co się w nim dzieje, problem trochę zahacza o metody numeryczne :

Kod: Zaznacz cały

faktualne+=fdt;         // tutaj obliczam aktualną częstotliwość dla której liczę:

  for ( int i=0; i < syg1.Length; i++)                   // w tej pętli obliczam 1 sygnał którym jest sinu o aktualnej częstotliwości.
{
  syg1[i][1]=sin(2*M_PI*faktualne*(syg1[i][0])*syg1_pot);
}

   double a=0;
   double b=0;
   int e=0;                                   
       for ( int i=0; i<syg2.Length; i++)       //   w tej pętli obliczam odpowiedź układu ( w tym przypadku filtru )
       {
        b=0;
        for ( int j=0; j<tb.Length; j++)         // dla współczynników b
         {
           if (tb[j]!=0)
           if (i >= j)
           b+=tb[j]*syg1[i-j][1];
         }
         e=i;
         a=0;
        for ( int j=0; j<ta.Length; j++)          // i dla  // dla współczynników a
         {
          if (tb[j]!=0)
          if (e>=0)
           a+=ta[j]*syg2[e][1];
          e--;
         }
         syg2[i][1]=b-a;                               
       }

// współczynników a i b jest w sumie 64, przeważnie są zerami

   double smax=0;
   double fmax=0;
   for (int i=gustalenia; i<syg1.Length ;i++)          // w tej pętli obliczam wartości maksymalne dla sinusa
    {                                                                    //   i dla odpowiedzi filtru. Dla sinusa nie mogę przyjąć 1 dlatego, że
      if ( syg1[i][1]>smax) smax=syg1[i][1];           // muszę przyjąć maksymalną wygenerowaną próbkę
      if ( syg2[i][1]>fmax) fmax=syg2[i][1];
    }

   syg3[krok][1]=1.0*(fmax/smax);                     // obliczenie wzmocnienia prościej tego nie da się zrobić.



  bool wgore=0;
  int pprzeg=-1;
  for (int k=syg2.Length-1; k>gustalenia; k--)                // szukam punktu przegięcia sinusojdy
   {                                                                              // ale tylko dla wartości dodatnich
    if ( syg2[k][1]<syg2[k-1][1] )
     {
      wgore=1;
     }

    if ( syg2[k][1]>syg2[k-1][1] && wgore==1 && syg2[k][1]>0)
     {
      pprzeg=k;
      break;
     }

   }




  if ( pprzeg>-1)                                   // jeżeli jest wartość przegięcia to mamy kolejne obliczenia
   {                                                      // przeważnie jej nie ma dla pierwszych 20-30 kroków
    double czasprobki=syg2[pprzeg][0];

     double czaszera=0;
     for (int i=gustalenia; i<syg1.Length-1; i++)                // ustalamy czas pierwszej sinusojdy ( rozpoczęcia sinusa )
      {
        if ( syg1[i][1] <0 && syg1[i+1][1] >=0 )
         {
         czaszera=syg1[i][0];

         break;
         }
      }



      double okres=1.0/faktualne;
      okres*=1.0/syg1_pot;

      for (;;)                                                    // w tej pętli obliczamy ile okresów zmieści się do czasu przegięcia od
       {                                                           // chwili pierwszego sinusa

         if (czaszera<=czasprobki)
         {
          czasprobki-=okres;
         }
          if (czasprobki<0)
          break;
       }


      czasprobki+=okres;
      czasprobki=czasprobki-okres/4;

      syg4[krok][1]=360.0*czasprobki/okres;               // obliczamy przesuniecie fazowe filtra
      if (syg4[krok][1]<0) syg4[krok][1]=0;                  // jezeli jest ujemy to zbijamy do zera

   } else
   {

    syg4[krok][1]=0;                                           // tak samo jak nie ma punktu przebięcia
   }



jakby wykonać to raz to niema żadnego problemu, ale cały algorytm mogę wykonać do 2048 razy za każdym razem z inną częstotliwością, więc trzeba za każdym razem generować sinusa ( można spróbować generować do tak jak dla DFT ), syg1.Legenth może mieć wartość do 16384 ( czyli dość sporo ) mój kod przy maksymalnej ilości wszystkiego wykonuje się w czasie powyżej 4 minut, a wiem że podobny kod realizujący to samo (ten sam algorytm, działanie nie kod) wykonuje się w okolicy 10 sec. Spokojnie mnie zadowoli zejście w okolicy 30 sec.

Chciałbym wszystko upakować w jak najmniejszą liczbę pętli, bo to chyba zabiera najwięcej czasu i generacja sinusa.

Próbowałem coś z tym kodem zrobić, zmniejszyć liczbę pętli, ale za cholerę nie mogę się w tym bałaganie połapać. Naprodukowałeś tych zmiennych, że już nie wiadomo, która jest do czego.
Ten algorytm to koszmar programisty. Nie będzie działał sprawnie dopóki nie zmniejszysz liczby pętli i zmiennych, za dużo zagłębień jednych pętli w drugich. Powinieneś wiedzieć że jeżeli wewnątrz jednej pętli umieszczasz dwie inne, to z tych dwóch najpierw jedna musi wykonać się do końca, a potem druga zaczyna działanie. Jeżeli istnieje taka możliwość to należy tak przerobić ten kod, żeby pętle wykonywały się jednocześni, czyli trzeba każdą z tych umieścić w oddzielnym wątku, czyli aplikacja wielowątkowa. Jeżeli jednak cały algorytm jest skonstruowany w ten sposób, że najpierw jedna pętla musi zakończyć działanie, żeby zwrócić jakieś wartości i dopiero druga może rozpocząć pracę - to nie ma co tutaj optymalizować - trzeba cały kod wyrzucić, przemyśleć cała koncepcję i stworzyć nowy kod, w oparciu o jakiś sensowny wzór.

Algorytm dostałem na piśmie czyli co poklei trzeba zrobić (słownie). I to jest chyba są rzeczy w tym algorytmie, które muszą się wykonać przed innymi, a znowu inne mogą już wykonywać się razem, spróbuje coś z tym zrobić.

A jakieś inne wskazówki przy optymalizacji kodu ?

Wskazówki:

1. wywołanie rekurencyjne
2. wywołanie dynamiczne

wiem co to jest rekurencja,

a wywołania dynamiczne ? można coś szerzej? // w momencie rozpoczęcia pierwszego i kolejnego kroku, parametry się nie zmieniają, tablice są tworzone dynamicznie, podczas pierwszego kroku i są sztywne przez przejście wszystkich kroków.

Programowanie dynamiczne, czytuj tutaj: Programowanie dynamiczne

Hmmm... również przyłączam się do prośby. Mógł byś pokazać jakiś przykładowy program zrobiony metodą dynamiczną?
Bo nie jestem do końca pewnie czy chodzi tu o to co mam na myśli czyli np dynamiczne tworzone zmienne.

Pozdrawiam

Przykład dla algorytmu dla Liczb Fibonacciego:

Implementacja rekurencyjna (bezużyteczna, gdyż czas obliczania liczby F_n jest wykładniczy. Czas potrzebny do obliczenia liczby F_n+1 jest około 1,6 razy dłuższy od czasu potrzebnego do obliczenia liczby F_n.

Kod: Zaznacz cały

int F(int i)
{
if(i < 1) return 0;
if(i == 1) return 1;
return F(i - 1) + F(i - 2);
}


Programowanie dynamiczne, zapisując obliczone wartości w tablicy statycznej unika się obliczania tych samych wartości:

Kod: Zaznacz cały

int F(int i)
{
static int znane_F[max_N];
if(znane_F[i] != 0) return znane_F[i];
int t = i;
if(i < 0) return 0;
if(i > 1) t = F(i - 1) + F(i - 2);
return znane_F[i] = t;
}


To by było na tyle, nie będę wyjaśniał kodu, odsyłam do literatury tematu.

A sprytne rozwiązanie można powiedzieć ze to taki "bufor" w którym zapisujemy już obliczone wartości.

A czy do dynamicznego programowania zalicza się również dynamiczne generowanie formularzy ? Bo znalazłem na googlu tę metodę do zmniejszania obiętości programu. Jest to opłacalne?

Mylisz pojęcia, dynamiczne znaczy tworzone na bieżąco wg. potrzeb, jedno nie ma z drugim nic wspólnego poza pojęciem dynamiczne, ale dynamo od roweru też działa dynamicznie...

// Z dynamo mogę się kłócić.

ok, co do optymalizacji to chyba dobrym sposobem jest wyciągnięcie przed pętle tego co można. Analogicznie tak jak wyciągnięcie przed nawias stałych.

Edit:

próbując optymalizacji kodu, doszedłem do wnioski, że najbardziej procesożernym procesem jest generacja tablicy z funkcją sinus. (część rzeczy upakowałem w jedną pętle).

Teraz opiszę sposób jak generuję się funkcję sinus do algorytmu DFT ( dyskretna transformata Fouriera ).

Działamy na pewnej ilości próbek N.
Generujemy tablicę N elementową. Dzielimy 360* na N kawałków, o stałym kroku dfi ( swoją drogą. przydały by się takie greckie literki, z boku do kliknięcia zamiast emotikon ). Dla każdego kąta obliczamy sinus i zapisujemy do tablicy.
W każdym kroku algorytmu działamy na innej częstotliwości ( zależy to od kilku czynników, lecz o stałym kroku df ) i potrzebujemy inną funkcję sinus. W 1 kroku nasz funkcja sinus tworzymy korzystając kolejno z każdego elementu wygenerowanego w tablicy. W 2 kroku korzystamy już z co 2 wartości z tablicy w ten sposób dostaniemy w tym samym oknie czasowym 2 okresy sinusoidy. W 3 kroku z co 3 wartości z tablicy i dostajemy 3 okresy funkcji.

Sęk w tym że ja nie mogę skorzystać z takiego algorytmu bo muszę generować funkcję sinus z pewną częstotliwością w pewnym oknie czasowym, i nie zawsze w całym oknie czasowym zmieści się cały okres sinusa. Też kolejne częstotliwości są inne niż z tego jakie wynikają z tego algorytmu DFT. Myślę że bardzo dobrym rozwiązaniem jest skorzystać z tablicy z wartościami sinusa niż w każdym kroku tworzyć ją na nowo. Jakieś pomysły jak to wykorzystać ?