[c++] Sprawdzanie efektywności algorytmu

Witam.
W tym semestrze na stuydiach mam przedmiot Analiza Algorytmów i poznajemy wiele ciekawych rzeczy z tym związanych. Chciałem się zatem dowiedzieć w jaki sposób mógłbym sobie to sprawdzić w C++? Np. policzę złożoność obliczeniową jakiegoś algorytmu i wyjdzie mi n^2, ale chciałbym móc to zaobserwować w rzeczywistości.

Więc:

1. czy istnieje jakaś metoda aby zmierzyć ile się wykonuje operacja dominująca na jakimś kompie? (np. porównywanie elementów tablicy)

2. (powiązane z 1) czy są jakieś programy/klasy, które pozwalają np. na ustawienie zegara, wykonanie instrukcji, odczytanie zegara? (oczywiście chodzi mi o taki zegra, który mógłby liczyc w milisekundach)

Pozdro.

funckja clock zwraca Tobie czas w ms:

t_clock start = clock();
/* testowany algorytm */
cout << "czas : " << clock() - start;

oczywiscie jest to czas na danej maszynie zeby wynik byl widoczny na lepszym sprzecie najlepij wykonac algorytm w petli np powtorzyc go przynajmniej 1000 krotnie i dopiero pozniej porownac z czasem koncowym jeszcze lepsza ocena jest potwarzac ta petle 1000 krotna i wyliczac czas sredni pozniej to daje Tobie jakas zblizona ocene porownianai wydajnosci jednego algorytmu z drugim w ms oczywiscie

zawsze mozesz wygenerowac kod w asmie i liczyc cykle :]

z tym liczeniem cyklów to bym się wstrzymał - na nowoczesnych procesorach wygląda to nieco inaczej niż na 486, a liczba czynników, które wpływają na liczbę cykli dla danej instrukcji jest aktualnie całkiem spora.

Słyszałem o takiej funkcji jak GetThreadTimes. Może być pomocna.

Znalazłęm idealne rozwiązanie.
Program nazywa się Rational i obsługuję Javę i C++. Jest naprawdę super, więc jeśłi ktoś się interesuje przyśpieszaniem kodu to niech go sobie ściągnie. Na stronce IBM'a jest 30 dniowy trail.

Pozdrawiam.

eh nie jestem sam..

też mam napisać program do badania wpływu selekcji na wpływ algorytmów ewolucyjnych

na sam start generuję pewną pulę osobników (pula rodzicielska)
chcę się nią posługiwać w dwojaki sposób:
-osobniki zapisane w sposób zmiennoprzecinkowy - dla oceny ich przystosowania
-te same osobniki zapisane birnarnie (w tablicy) - dla umożliwienia przeprowadzania na nich operacji takich jak krzyżowanie,mutacja....

i tu pojawia się problem
napisałem prostą funkcję rekurencyjną do konwersji z systemu dziesiątkowego na binarny
ale każdy osobnik ma być przedstawiony za pomocą 10 bitów i gdy mój osobnik dajmy na to ma wartość 18 (10010) to przedstawiany jest w tej tablicy jako 1001000000, gdzie nie jest to prawdą
w jaki sposób przesunąć bity we właściwe miejsca tabeli???

a może masz inny pomysł może niepotrzebnie babram się z tymi tablicami

z góry thx

p.s. potrzebuje tego do pracy inżynierskiej na zajęciach c++ tylko lizneliśmy (jestem z MT)... a nową trzytomową symfonię mam od tygodnia
może miałbyś coś dla mnie... pliz

Może podasz tu kod tej funkcji, żebyśmy wiedzieli jak tworzysz tablice bitów?

zdziszek napisał(a)

program do badania wpływu selekcji na wpływ algorytmów ewolucyjnych
Możesz troche jaśniej to opisać?

zdziszek napisał(a)

napisałem prostą funkcję rekurencyjną do konwersji z systemu dziesiątkowego na binarny
po co, przecież masz już funkcje atoi, itoa.

Tu masz link do dobrej stronki o algorytmach genetycznych

A tak w ogóle algorytmy ewolucyjne są dobre do problemów, gdzie funkcja przystosowania ma wiele cech do zbadania, tak aby były różne kombinacje. Jeżeli cecha osobnika ma być tylko jedna (a ty piszesz, że ma to byś po prostu liczba zmiennoprzecinkowa) to algorytm bedzie słabo wydajny, porównując z innymi metodami. Budując algorytm, szukający jednej cechy (np. szukanie maksimum lokalne funkcji, czyli badanie jedenej cechy - wartości funkcji w punkcie, która ma być najwyższa) operacja krzyżowania musi wyglądać w ten spodób:
Krzyżowanie genów polega na wymianie cech, koro cecha jest jedna, to jedynym rozsądnym rozwiązaniem podczas tworzenia genu dziecka jest wylosować wartość(ceche) z pomiędzy wartości rodziców, lub policzyć wartość w połowie pomiędzy wartościami rodziców. Tak więc zamiana tych wartości na bity, losowanie ich czy co tam innego nie ma sensu. Nie ważne na ilu bitach przedstawisz w genie ceche, gdy będzie to tylko jedna cecha.