Testy wydajności algorytmów

Autor podstrony: Krzysztof Zajączkowski

Stronę tą wyświetlono już: 1872 razy

Wyobraź sobie, że masz do dyspozycji kilka różnych algorytmów rozwiązujących ten sam problem. Każdy z tych algorytmów działa lepiej lub gorzej w zależności np. od podanych na wejście danych. Dla przykładu rozważmy dwa warianty prostego algorytmu sprawdzającego, czy dana liczba jest liczbą pierwszą. Celem testu będzie oszacowanie czasu potrzebnego do realizacji tego zadania dla podanej na wejście dużej liczby pierwszej. Implementacja takiego algorytmu umożliwiająca łatwe dodawanie do testu kolejnych implementacji pokazana została na poniższym diagramie UML.

Rys. 1
Diagram UML algorytmu umożliwiającego testowanie wielu implementacji algorytmu sprawdzającego, czy dana liczba jest liczbą pierwszą

Dwa podstawowe interfejsy ITesting oraz IPrimaryNumberCheck mają za zadanie wymusić obsługę w klasach dziedziczących i umożliwić dostęp do metod zadeklarowanych w tychże interfejsach. Implementacje tychże interfejsów wyglądają w moim przypadku tak:

class ITesting{ public: virtual void testing() const = 0; virtual ~ITesting(){} }; class IPrimaryNumberCheck{ public: virtual bool primaryNumberCheck(uint32_t number) const = 0; virtual ~IPrimaryNumberCheck(){} };

Kolejny interfejs IPrimaryCheckTesting scala wyżej opisane interfejsy i obsługuje czysto wirtualną metodę testing. Oto implementacja:

class IPrimaryCheckTesting : public ITesting, IPrimaryNumberCheck { public: virtual void testing() const { uint32_t number = 554277413; QTime timer; timer.start(); qDebug() << "Returned value:" << primaryNumberCheck(number) << "for number" << number; int milliseconds = timer.elapsed(); qDebug() << "Time of testing class" << QString(typeid(*this).name()) << "is equal:" << milliseconds << "[ms]"; } virtual ~IPrimaryCheckTesting(){} };

Nadeszła długo wyczekiwana chwila utworzenia dwóch wersji algorytmu sprawdzającego, czy dana liczba jest liczbą pierwszą:

class PrimaryNumberCheckForce : public IPrimaryCheckTesting{ public: virtual bool primaryNumberCheck(uint32_t number) const{ for(uint32_t i = 2; i < number; i++){ if(number % i == 0) return false; } return true; } }; class PrimaryNumberCheckOptimized : public IPrimaryCheckTesting{ public: virtual bool primaryNumberCheck(uint32_t number) const { if(number == 0 || number == 1) return false; if(number == 2) return true; qreal sqrtNumber = sqrt(number); for(uint32_t i = 3; i < sqrtNumber; i += 2){ if(number % i == 0) return false; } return true; } };

I ostatnia klasa, umożliwiająca proste i przyjemne testowanie:

class TestingClass : public ITesting{ protected: QList<ITesting*> testingInterfaces; public: TestingClass& operator += (ITesting* testingInterface){ testingInterfaces.push_back(testingInterface); return *this; } virtual void testing() const { foreach(const ITesting* testingInterface, testingInterfaces){ testingInterface->testing(); } } };

Jak widać klasa TestingClass dziedziczy po interfejsie ITesting jak również agreguje całą listę tego samego typu interfejsów. Z kolei obsługa operatora += pozwala w łatwy sposób dodawać kolejne interfejsy do testów.

Użycie praktyczne powyższych klas wygląda następująco:

PrimaryNumberCheckForce primaryForce; PrimaryNumberCheckOptimized primaryOptimized; TestingClass testing; testing += &primaryForce; testing += &primaryOptimized; testing.testing();

Natomiast wynik działania:

Returned value: true for number 554277413
Time of testing class "23PrimaryNumberCheckForce" is equal: 2930 [ms]
Returned value: true for number 554277413
Time of testing class "27PrimaryNumberCheckOptimized" is equal: 2 [ms]