Pomoc w optymalizacji kodu

[riddyk]

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.

[Cyfrowy Baron]

Optymalizacji kodu nie dokonuje się od tak. Ten kod jest być może zrozumiały dla Ciebie, ale dla osoby postronnej, jest to ciąg niezrozumiałych znaków.
Kodu wyrwanego z kontekstu nie da się zoptymalizować, gdyż każda optymalizacja wymaga przeprowadzenia testów, a jak przeprowadzić testy na tym fragmencie kodu, który coś robi, tylko nie wiadomo co, z czym jest połączony, do czego służy itd...

Optymalizacja algorytmów zajmuje wiele godzin, a czasami dni. Wiem to z własnego doświadczenia, najpierw tworzę działający algorytm, a potem przez wiele dni się zastanawiam jak go zoptymalizować, a gdy już go zoptymalizuję, to okazuje się, że można go napisać inaczej, lepiej.

---

Co do Twojego kodu. Nie wiadomo, czy umieściłeś ten algorytm w jakimś zdarzeniu, czy też jest to pojedyncza funkcja.
Popełniasz błąd początkujących programistów, umieściłeś cały algorytm w jednej dużej funkcji, zamiast kilku mniejszych odwołujących się do siebie nawzajem.
Nie wiadomo co ta funkcja robi, dlatego też nie wiadomo, czy można ją zoptymalizować - przyspieszyć, ale nie umieszczaj opisu, co ta funkcja ma robić, bo to niczego nie rozjaśni, a tylko skomplikuje.
Przed przystąpieniem do optymalizacji kodu, trzeba stworzyć jego wzór matematyczny, wogóle tworząc ten algorytm powinieneś zacząć od takiego wzoru, wtedy być może od razu działałby lepiej. Mając wzór przekładasz go na język programowania i wtedy widać co można ulepszyć.

Najpopularniejszym (nie jedynym) sposobem na optymalizację kodu jest rekurencja, czyli odwoływanie się definicji lub funkcji do samej siebie. Najlepszym przykładem rekurencji jest ciąg Fiboncciego, dlatego zanim przystąpisz do optymalizacji tego kodu, proponuje poćwiczyć wywołania rekurencyjne, polecam również lekturę porady: Liczby Fibonacciego

[Cyfrowy Baron]

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.

[riddyk]

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 ?

[Cyfrowy Baron]

Wskazówki:

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

[riddyk]

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.

[Cyfrowy Baron]

Programowanie dynamiczne, czytuj tutaj: Programowanie dynamiczne

[Koziol]

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

[Cyfrowy Baron]

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.

[Koziol]

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?

[Cyfrowy Baron]

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...

[riddyk]

// 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ć ?