metodyka testowania implementacji drzew czerwono czarnych na bazie tablicy

Kod nieprzetestowany albo nie działa w ogóle, albo nie działa poprawnie - i tak było w przypadku tej implementacji drzew czerwono-czarnych. Dlatego napisałem specjalny kod do przetestowania. Metodyka jaką przyjąłem polega na testowaniu porównawczym. Trzy takie same programy, oparte jednak na innych implementacjach drzew czerwono-czarnych, muszą dać takie same wyniki.

W celu przetestowania zaprojektowałem 15 procedur. Każda procedura, w przybliżeniu, testuje kolejną metodę z tej implementacji, a także analogiczne metody z implementacji w std::set i QMap.

Kolejność wywoływania procedur jest losowa, a także losowa jest kolejność wybierania implementacji, co powinno wykluczyć błędy ujawniające się tylko przy określonej kolejności, np. po wywołaniu metody sort, która kompletnie reorganizuje ułożenie węzłów w pamięci. Oczywiście niektóra kolejność wywoływania procedur jest błędna z założenia, np. po wywołaniu metod: insert, remove, nie można wywoływać metod z przedrostkiem sort, a na pustym drzwie nie można w ogóle wywoływać metod wyszukujących. Test został zabezpieczny przed wywołaniem niedozwolonej kolejności.

Przy okazji testowania wykonywany jest benchmark. Testowane są trzy implementacje std::set, QMap i RBTree. Program testowy zawiera trzy timery, każdy timer mierzy czas wykonywania operacji jednej implementacji. Z pomiarów czasu wynika, że implementacja na tablicy jest najszybsza.

Test przyjmuje aż 19 parametrów parametrów. Można określić przy pomocy tych parametrów maksymalną i minimalną ilość elementów w drzewie, zarodek liczb losowych i prawdopodobieństwo testowania poszczególnych procedur. Dzięki dużemu zwiększeniu jednego z parametrów można uzyskać benczmark jednej konkretnej cechy. Jednak skrypt test00.sh przyjmuje dla uproszczenia tylko jeden parametr, a mianowicie zarodek liczb losowych, po czym samodzielnie kompiluje i uruchamia test z rozsądnymi parametrami. W systemie (linux) muszą być tylko odpowiednie biblioteki i w miarę nowa wersja kompilatora g++ z obslugą standardu C++x11.

Test, o ile nie wykryje błędu, trwa w nieskończoność, należy go przerwać przy pomocy kombinacji klawiszy ctrl+c po wyczerapniu cierpliwości. Jeśli test wykryje błąd, wtedy wyświetli stosowny komunikati i zakończy się procedurą abort(). Jeśli uruchomisz u siebie test, będę Ci wdzięczny. Jeśli test zakończy się błędem, koniecznie poinformuj mnie o tym i przyślij mi zarodek liczb losowych z jakim uruchomiłeś test. Jeśli użyłeś innych parametrów niż domyślne w skrypcie test00.sh, to też wyślij je do mnie w razie błędu.

Przykład użycia:
./test00.sh 123

Przy czym liczbę 123 oczywiscie zastąp jakąś swoją, losową liczbą.

Kod testujący drzewo czerwno czarne (pobierz i zapisz jako test00.cpp)

Skrypt powłoki shell do zautomatyzowania testu (pobierz i zapisz jako test00.sh)