Zapoznanie się poprzez implementację i testowanie z różnymi strukturami asocjacyjnymi (słownikami).
- Implementacja słownika opartego o drzewo binarne.
- Implementacja słownika opartego o funkcję mieszającą (hashmapa - tablica z kubełkami).
- Porównanie efektywności czasowej tych dwóch kolekcji dla co najmniej dwóch różnych operacji.
Po skopiowaniu plików projektu, należy uruchomić skrypt create_configs.sh
aby powstały pliki projektów Make i CodeBlocks.
Na przykład:
cd KatalogNaProjektyAisdi
cp -r /materialy/AISDI/Mapy .
cd Mapy
./create_configs.sh
Katalogi:
- src - katalog zawierający pliki źródłowe klas do zaimplementowania.
- tests - katalog zawierający pliki źródłowe testów jednostkowych.
- Debug - katalog zawierający Makefile'e w trybie Debug i opakowujący je projekt CodeBlocks.
- Release - katalog zawierający Makefile'e w trybie Release i opakowujący je projekt CodeBlocks.
Pliki źródłowe:
- src/TreeMap.h - wydmuszka implementacji struktury drzewa binarnego.
- src/HashMap.h - wydmuszka implementacji hashmapy.
- src/main.cpp - wydmuszka aplikacji do profilowania wybranych struktur.
- tests/TreeMapTests.cpp - testy jednostkowe klasy TreeMap (można dopisywać nowe).
- tests/HashMapTests.cpp - testy jednostkowe klasy HashMap (można dopisywać nowe).
- tests/test_main.cpp - plik wymagany do stworzenia aplikacji wykonującej testy jednostkowe.
- Testy nie są testami czarnej-skrzynki, ale testami "od programisty dla programisty", mającymi pomóc w implementacji. Nie są więc złośliwe, ale jak najbardziej zbliżone do takich, jakie powinny powstać podczas normalnej implementacji. Oznacza to, że można stworzyć kod "złośliwy", zaliczający testy a jednocześnie nie robiący tego co wymagane. Ale prościej będzie skorzystać z pomocy testów i wykonać poprawnie ćwiczenie - Prowadzący będą oceniać kod.
- Wszystkie pliki wolno modyfikować (np. wykomentowywać część testów na czas implementacji jakiejś funkcji). Nie wskazane jest trwałe usunięcie testów - one wychwytują różne sytuacje graniczne, które zapewne będą drobiazgowo weryfikowane przez Prowadzących.
- Dopisywanie własnych testów jest mile widziane.
- Interfejsy klas TreeMap i HashMap przypominają lekko te z biblioteki standardowej C++, ale
tylko w zakresie dotyczącym iteracji (aby ułatwić użycie niektórych operacji
dostępnych w
std::). Z premedytacją pozostałe operacje mają często inną syntaktykę i semantykę - proszę czytać testy, by zapoznać się z ich oczekiwanym zachowaniem. - Warto zweryfikować program testujący narzędziem do wykrywania wycieków pamięci (np.
valgrind). - Wycieki pamięci najlepiej wykrywać badając aplikację wykonującą testy jednostkowe. W ten sposób większość operacji będzie zweryfikowana na obecność wycieków.
- Chcąc profilować konkretną operację na kolekcji, warto wykonać ją wielokrotnie dla np. rosnących wielkości kolekcji, żeby zauważyć różnicę.
- Profilowanie ma sens wyłącznie dla kompilacji zoptymalizowanej (
Release). - Domyślny tryb budowania (np.
make,make allczy konfiguracjaallw CodeBlocks) buduje testy, uruchamia je i tylko gdy one przejdą - buduje aplikację do profilowania. - Niestety CodeBlocks może mieć problemy z parsowaniem wyjścia z testów - wygodniejsze niż przeglądanie widoku błędów "Build messages" powinno być sprawdzenie zawartości okna "Build Log".
- Przełączanie się pomiędzy trybami budowania "Debug" i "Release" wymaga otwarcia dwóch instancji CodeBlocks, ale obydwie wykorzystywać będą te same pliki źródłowe.