Dynamiczne struktury danych i wydajność
Czas alokacji bloku pamięci nie jest wprost proporcjonalny do jego rozmiaru.
Z tej banalnej obserwacji płynie praktyczny wniosek:
bardziej opłaca się alokować mało dużych bloków pamięci niż wiele
bardzo małych.
Porównajmy dwa dość skrajne przypadki:
w pierwszym dm.cpp
alokujemy pamięć dla każdego z miliona
elementów tablicy osobno,
w drugim md.cpp alokujemy pamięć
od razu dla całej tablicy.
Porównując czasy wykonań dla obu programów otrzymano następujące wyniki:
time ./dm 10
liczba iteracji: 10
real 0m1.278s
user 0m1.210s
sys 0m0.050s
Dla 10 powtórzeń według pierwszego sposobu
oraz
time ./md 100000
liczba iteracji: 100000
real 0m0.768s
user 0m0.150s
sys 0m0.580s
dla 100 tyś. powtórzeń według drugiego sposobu.
Pomiar wykonano pod kontrolą systemu Linux na komputerze
z procesorem Intel Pentium 4 2.4GHz.
Tablica list - przykład
Dana jest grupa osób.
Każda z nich posiada telefon.
Dla uproszczenia przyjmijmy, że każdy numer telefoniczny
ma swój identyfikator 1<= id <= 100000.
Dla celów statystycznych otrzymujemy dane o połączeniach
między tymi osobami.
Chcemy dla każdej osoby zapamiętać z kim
prowadziła rozmowy.
Dla uproszczenia informacja o połączeniu składa się wyłącznie
z dwóch liczb:
n1 n2
gdzie n1 i n2
to identyfikatory osób.
Przykładowy sposób zapamiętania tych danych w tablicy list
tl.cpp.
Struktury drzewiaste (Tylko dla zainteresowanych)
Potrzeba używania łączonych struktur dynamicznych
wynika głównie z zalet wykorzystania struktur drzewiastych
takich jak: drzewa czerwono-czarne, 2-3 drzewa, drzewa AVL
i inne podobne.
Zagadnienia te są dość trudne i zostaną omówione
w przyszłym semestrze na przedmiocie
Projektowanie i Analiza Algorytmów.
Przykładowe zadania
-
Uzupełnij dane o czas połączenia liczony w sekundach.
-
Zaimplementuj tablicę kolejek typu fifo.
-
Dopisz do swojej implementacji:
- dynamiczny stos,
tzn po zapełnieniu całego stosu należy go powiększyć,
tak aby zawsze można było dodać nowy element;
- stos parametryzowany typem przechowywanych elementów.
- Przenieś kod odpowiedzialny za obsługę kolejki
do oddzielnego pliku i stwórz dla niego plik nagłówkowy
z zabezpieczeniem przed wielokrotnym włączaniem.
-
Zamiast tablicy list łączonych stwórz stos list łączonych.
-
Zamiast tablicy list łączonych stwórz kolejkę cykliczną list łączonych.
-
Zamiast zapamiętywać daną rozmowę kilka razy, dodaj w strukturze pole
rozmowy będące sumą czasów rozmów z daną osobą.