ScanImage019 (4)

1.4 PERSPEKTYWA ma sssss %as3

Tabela 1.1. Testy empiryczne algorytmów scalania i wyszukiwania

Przedstawione poniżej zestawienie czasów rozwiązywania losowych problemów połączeniowych przy użyciu różnych algorytmów' scalania i wyszukiwania jest w zasadzie demonstracją efekty wmości zrównoważonej wersji algorytmu szybkiego scalania. Poprawa jakości uzyskana za sprawą kompresji ścieżek jest mniej ważna. W przedstawionych eksperymentach m oznacza liczbę losowych połączeń generowanych do czasu, aż połączonych zostało n obiektów. Ten proces wymaga zdecydowanie więcej operacji wyszukiwania niż operacji scalania, więc algorytm szybkiego scalania jest znacznie wolniejszy niż szybkiego wyszukiwania. Jednak ani szybkie wyszukiwanie, ani szybkie scalanie nie nadaje się dla dużych n. Czas działania w przypadku metod równoważonych jest ewidentnie proporcjonalny do bo podwaja się wraz z podwojeniem wartości n.

n	m	W	S	Z	K	P
1000	6206	14	25	6	5	3
2500	20236	82	210	13	15	12
5000	41913	304	1172	46	26	25
10000	83857	1216	4577	91	73	50
25000	309802			219	208	216
50000	708701			469	387	497
100000	1545119			1071	1106	1096

Legenda:

W szybkie wyszukiwanie (program 1.1),

S szybkie scalanie (program 1.2),

Z zrównoważone szybkie scalanie (program 1.3),

K zrównow'ażone szybkie scalanie z kompresją ścieżek (zadanie 1.16),

P zrównoważone szybkie scalanie z kompresją ścieżek przez połowienie (program 1.4).

1.4. Perspektywa

Każdy z algorytmów przestawionych w podrozdziale 1.3 był w^f jakimś intuicyjnym sensie ulepszoną wersją poprzedniego, ale przedstawiony przez nas proces ulepszania algorytmów jest sztucznie wygładzony, ponieważ dysponujemy wglądem w całą historię rozwnju algorytmów i mamy dostęp do wyników, nad którymi naukowcy pracowali przez wiele lat (patrz bibliografia). Implementacje są proste, a zadanie jasno określone, więc możemy oceiuać różne algorytmy uruchamiając po prostu testy empiryczne. Możemy ponadto oceniać te testy i przedstawiać porównawcze zestawienia wydajności tych algorytmów' (patrz rozdział 2). Nie wszystkie dziedziny problemów omawiane w tej książce są tak dobrze poznane jak ten. Isinieje ^pewnością wiele skomplikowanych algorytmów', które niełatwo się porównuje, oraz wiele za-łtcmatycznych, które są trudne do rozwiązania. Pragniemy przedstawiać obiektywną na-

21