Kiedy chcemy skorzystać z dodatkowej pamięci, nie wiedząc z góry ile nam jej będzie potrzeba i uzależniając jej ilość od danych, których wartości nie są znane, wygodnie jest używać mechanizmu dynamicznej alokacji pamięci. Podstawy alokacji dynamicznej pamięci zostały omówione w rozdziale Pamięć dynamiczna.
Bardzo wygodną strukturą danych są listy, czyli struktury, które umożliwiają tworzenie ciągów danych w taki sposób, że każda dana pamięta gdzie się znajduje kolejna.
Zanim zdefiniujemy listy, zastanówmy się, dlaczego trudno jest zrealizować następujący pomysł sortujący dane w tablicy. Ponieważ umiemy szybko wyszukiwać w posortowanym ciągu miejsce, w które należy wstawić daną wartość tak, aby nie popsuć posortowania, więc można sobie wyobrazić następujący szybki algorytm sortujący.
Dane: ciąg \(\alpha=\langle a_1,\ldots,a_n\rangle\) elementów z dziedziny A oraz relacja ≤ liniowo porządkująca dziedzinę A.
Cel: Posortować ciąg \(\alpha\), czyli tak poprzestawiać jego elementy, żeby następowały po sobie w kolejności niemalejącej.
Szukamy zatem takiego ciągu \(\beta=b_1,\ldots,b_n\), żeby był on permutacją ciągu \(\alpha\) oraz żeby \(\forall 1\le k <n: b_i\le b_{i+1}\).
Rozszerzmy ciąg \(\beta\) z lewej strony o element \(b_0=-\infty\), czyli załóżmy, że ciąg \(\beta\) zaczyna się od minus nieskończoności, pełniącej rolę strażnika.
Rozwiązanie:
Niech \(\beta_1=\langle -\infty,a_1 \rangle\) będzie dwuelementowym ciągiem złożonym ze strażnika oraz z pierwszego elementu ciągu a.
for i:=2 to n do {ciąg \(\beta_{i-1}\) składa się z posortowanych elementów \(b_0,a_1,...,a_{i-1}\)} begin znajdź taki indeks j, żeby \(1\le j<i\) oraz żeby \(b_{j-1}\le a_i \le b_j\) wstaw \(a_i\) między \(b_{j-1},\) a \(b_j\) end
Ten algorytm w pseudokodzie nie jest wcale tak łatwy do efektywnego zaimplementowania. Przyjrzyjmy się dziedzinie algorytmicznej, w której jest określony. Aby go zrealizować potrzebne są dwie operacje: znajdowania indeksu, pod który powinien trafić kolejny element ciągu a oraz wstawienia elementu we wskazane miejsce ciągu: "wepchnięcia" go między dwa istniejące elementy.
Spróbujmy przymierzyć się do zaimplementowania podanego algorytmu, przy założeniu, że właściwy ciąg \(a\) jest reprezentowany w tablicy A[1..n].
Pierwsza operacja – znajdowania stosownego indeksu – jest dość prosta: wystarczy zastosować algorytm wyszukiwania binarnego i jako efekt uboczny dostaniemy indeks j, po którym należy wstawić nasz element. Podany poniżej algorytm wyszukiwania binarnego znajduje indeks ostatniego wystąpienia elementu mniejszego lub równego A[i] – jest to miejsce, w którym element A[i] powinien się pojawić. Przedstawiony algorytm jest nieco zmodyfikowanym algorytmem wyszukiwania binarnego. Strażnik \(-\infty\) na pozycji 0 pełni swą rolę, gdy wstawiany element jest najmniejszy z dotychczasowych – zawsze wtedy wstawiamy nowy element za jakimś już istniejącym. Dzięki niemu nasz algorytm stanie się jednorodny: zawsze wstawiany element będzie znajdował swoje miejsce po jakimś już istniejącym. Tu rolę zmiennej n pełni i, ponieważ algorytm uruchamiamy wielokrotnie dla kolejnych wartości i:
A[0]:=-nieskonczonosc; l:=0; p:=i-1; {szukamy elementu PO którym chcemy wstawić A[i], zatem ostatniego, który jest mniejszy lub równy A[i]} while l < p do \(\{Sort(A[1..i-1) \land (1\le l\le p < i) \land (\forall p< k <i: A[k]> A[i]) \land (\forall 1\le k <i: A[k]\le A[i] \rightarrow k\le l)\}\) begin s:=(l+p+1) div 2; if A[i] >= A[s] then l:=s else p:=s+1 end;
Wychodzimy z pętli przy l=p, więc nasz niezmiennik gwarantuje to, że na prawo od p i na lewo od i (z wyłączeniem p oraz i) są elementy większe od A[i], zaś do l włącznie są mniejsze lub równe A[i]. Element A[i] należy zatem wstawić pomiędzy A[l] a A[l+1]. Tylko jak to zrobić? Tablica nie może tak nagle spuchnąć i zrobić sobie jedno dodatkowe miejsce gdzieś w środku na ten nowy element. To, co można zrobić, to tylko przesunąć mozolnie wszystkie elementy od j na prawo o jedną pozycję w prawo i dopiero wtedy, gdy zrobi się wolne miejsce na A[i], wstawić tam tę wartość.
Ćwiczenie:
Zaprogramuj tę część algorytmu.
Rozwiązanie:
v:=A[i]; for k:=i-1 downto p do A[k+1]:=A[k]; A[p]:=v
Tyle, że samo przesuwanie zajmie nam w średnim przypadku i/2 obrotów pętli, a cały algorytm będzie kwadratowy ze względu na n. Zatem to, co zarobiliśmy w pierwszej fazie, tracimy w drugiej, kiedy okazuje się, że operacja wciśnięcia nowego elementu do ciągu jest kosztowna. Na dobrą sprawę można powiedzieć, że niepotrzebnie robiliśmy pierwszą fazę; można było od razu zacząć od przesuwania elementów kończąc na pierwszym mniejszym lub równym A[i] i tam go wstawić. Taki algorytm nazywa się algorytmem sortowania przez proste wstawianie i jest całkiem dobrym algorytmem dla niewielkich danych, ale o złożoności kwadratowej – zarówno pesymistycznej, jak i średniej.
Widzimy więc, że w tablicach wyszukiwanie w ciągu posortowanym jest tanią operacją, natomiast wstawianie nowego elementu w środek ciągu – kosztowną. Poznamy teraz strukturę danych, reprezentującą ciągi, dla której będzie dokładnie na odwrót: wyszukiwanie będzie stosunkowo kosztowne, za to wstawianie tanie. Struktura ta będzie miała dodatkową cechę odróżniającą ją od tablic: długość reprezentowanego ciągu nie będzie musiała być z góry ustalona. Jest to niezwykle ważna cecha, gdyż w przypadku tablic musimy zazwyczaj przewidzieć zawczasu, jaka będzie długość ciągu i zadeklarować tablicę stosownego rozmiaru, być może godząc się na nieoszczędność pamięci, jeśli całej tablicy nie wykorzystamy.
Zbiór list \(L(A)\) nad pewnym zbiorem A definiujemy, jako najmniejszy zbiór spełniający następujące warunki:
Do reprezentacji list użyjemy zmiennych dynamicznych. Są one bardzo wygodne, gdyż można je alokować w czasie wykonywania programu i na tyle elastyczne, że umożliwiają łatwe dokonywanie wszystkich interesujących nas operacji. Zatem w składni Pascala można typ listowy zdefiniować następująco. Niech typA reprezentuje zbiór A.
type lista = ^elementlisty; elementlisty=record w: typA; nast: lista; end;
Przyjmijmy do końca tego wykładu, że typA=Integer. Będziemy więc mieli do czynienia z listami liczb całkowitych.
Powyższa definicja może nieco niepokoić. Definiujemy typ lista odwołując się do elementu listy, o którym za chwilę się dowiadujemy, że w jego definicji występuje z powrotem lista. Nastąpiło tu złamanie starej arystotelesowskiej zasady, że wolno definiować nowe pojęcia tylko za pomocą aksjomatów (czyli pojęć pierwotnych) lub pojęć już zdefiniowanych. Na szczęście wszystko jest w porządku, jeśli zdamy sobie sprawę z tego, że typ wskaźnikowy jest tak naprawdę adresem – adresem zaalokowanej zmiennej pokazującej na obiekt danego typu. Zatem typ lista jest adresem komórki o dwóch polach: pierwsze z nich zawiera wartość reprezentowaną przez typA, a drugie adres. Tak też tego rodzaju definicje traktuje kompilator Pascala i nie ma problemu z kompilacją takiego pseudozapętlenia definicji.
Lista jest zatem reprezentowana, jako wskaźnik do rekordu o dwóch polach: w pierwszym polu jest reprezentowany element danego typu, a w drugim wskaźnik do następnego elementu listy. Wyróżnioną wartością wskaźnika jest nil, który tu oznacza pustą listę. Przeważnie lista kończy się nilem. Inne możliwości, to
Ponadto warto zauważyć, że listy mogą się zbiegać i dla dwóch różnych początków mieć tę samą końcówkę.
Spróbujmy podać teraz parę rozwiązań podstawowych zadań związanych z przetwarzaniem list.
Zadanie 1.
Stwierdź, czy w liście znajduje się element o wartości x.
Rozwiązanie 1:
function jest_rek(l:lista; x:typA):Boolean; {przyjmuje wartość true wtedy i tylko wtedy, gdy w liście l znajduje się wartość x} begin if l=nil then jest_rek :=false else if l^.w = x then jest_rek := true else jest_rek := jest_rek(l^.nast,x) end;
Warto skomentować to rozwiązanie. Zauważmy, że na początku sprawdzamy, czy lista l aby nie jest pusta. Jest to konieczne, gdyż próba odwołania się do jakiegokolwiek pola listy pustej powoduje błąd i przerwanie programu – dla pustej listy wywołanie tej funkcji dałoby właśnie taki efekt. Początkowy test niepustości listy jest zalecany jako standardowy przy pracy z listami.
Reszta jest już w miarę prosta: jeśli lista jest niepusta, to szukana wartość jest albo w pierwszym elemencie, albo w ogonie listy; ten pierwszy przypadek badamy wprost, ten drugi – korzystając z rekurencji.
Od razu może ustalmy, że takie rekurencyjne rozwiązanie tego typu problemów nie jest zalecane. W ogóle w imperatywnych językach nadużywanie rekursji w przypadku prostych list jest niewskazane. Dodatkowe koszty organizacji rekurencji nie usprawiedliwiają zysku, jaki płynie z prostoty rozwiązania. Przedstawiamy zatem kolejną wersję – iteracyjną – rozwiązującą ten sam problem:
Rozwiązanie 2:
function jest_iter(l:lista; x:typA):Boolean; {podaje wartość true wtedy i tylko wtedy, gdy w liście l znajduje się wartość x} begin if l=nil then jest_iter :=false else begin while (l^.nast<>nil) and (l^.w <> x) do {aż do l wyłącznie nie ma x} l := l^.nast; jest_iter := l^.w = x end end;
Ćwiczenie. Udowodnij poprawność podanego kodu.
Ten kod wymaga znowu paru komentarzy.
Po pierwsze zauważmy, że kiedy przechodzimy wewnątrz funkcji ze wskaźnikiem l po liście, nie jesteśmy sie w stanie cofnąć. Niby nie mamy po co, ale czy nie tracimy dowiązania do początku listy? Otóż nie! Zawdzięczamy to wywołaniu parametru l przez wartość – działamy na jego kopii, zatem procedura wywołująca funkcję jest_iter po jej zakończeniu będzie miała oryginalną wartość l.
Po drugie, można by zapytać, po co tak się męczyć z następnikiem: czy nie wystarczy iść do przodu aż albo znajdziemy x, albo l stanie się równe nil? Innymi słowy chodziłoby tu o taką wersję naszej funkcji:
function jest_iter_leniwie (l:lista; x:typA):Boolean; {podaje wartość true wtedy i tylko wtedy, gdy w liście l znajduje się wartość x} begin while (l<>nil) and (l^.w <> x) do l := l^.nast; {aż do l wyłącznie nie ma x} jest_iter_leniwie := l <> nil {Zwróćmy uwagę na inny warunek ustalający wartość funkcji} end;
W wersji tej oszczędzamy sobie początkowego sprawdzenia nila – robi się to przy okazji testowania warunku wejścia do pętli – oraz być może dwukrotnego sprawdzenia czy wartość elementu listy równa się x (w poprzedniej wersji zawsze tak się działo, jeśli x wystąpił w liście!). Rozwiązanie to też jest poprawne, ale tym razem warunkowo – aby takie było, musi być włączona opcja tzw. leniwego sprawdzania złożonych warunków logicznych.
Przypomnijmy: leniwe wyliczanie polega na tym, że kompilator gdy tylko jest w stanie przewidzieć wynik formuły logicznej, przerywa jej dalsze obliczanie. Dzieje się tak w szczególności, gdy w koniunkcji jednym (i to nieostatnim) z czynników logicznych jest fałsz, lub – analogicznie – gdy w przypadku alternatywy jednym ze składników logicznych jest prawda. Musimy sobie zdać sprawę z tego, że logika wyrażeń logicznych w językach programowania jest trójwartościowa: poza prawdą lub fałszem mamy jeszcze wartość trzecią – nazwijmy ją niewiadomoco – gdy warunku nie udało się obliczyć, np. z powodu błędu. Jeżeli w logice wyrażeń komputerowych oznaczymy prawdę przez 1, fałsz przez 0, a niewiadomoco przez ?, to zakładamy, że działają tu następujące prawa dla alternatywy i koniunkcji:
\(1 \land ? = ?, ?\land 1 = ?, 0\land ? = 0, ? \land 0 = ?// 1 \lor ? = 1, ?\lor 1 = ?, 0\lor ? = ?, ? \lor 0 = ?\)
oraz prawo negacji
\(\neg ? = ?\)
Innymi słowy: jeśli zdąży się wyliczyć wartość ?, to niezależnie od reszty formuły wynikiem wyrażenia będzie ?. Jeśli natomiast w koniunkcji napotkamy 0 przed ? lub w alternatywie 1 przez ?, to formuła wyliczy się do klasycznej wartości logicznej – odpowiednio 0 lub 1. Zapamiętajmy:
Ani alternatywa, ani koniunkcja w leniwej logice trójwartościowej nie są przemienne!
Ćwiczenie
Czy błąd jest jedyną sytuacją, której warto przypisać wartość '?'.
Odpowiedź:
Nie, analogiczny efekt uzyskamy, gdy w czasie wyliczania warunku logicznego program się zapętli (np. wywołując funkcję logiczną). Proszę sprawdzić, że podane reguły logiczne dotyczące operatora ? są sensowne semantycznie w przypadku zapętlenia.
Leniwa logika pojawia się jako domniemana w pewnych językach programowania, np. w C, Javie. Jednak w Pascalu leniwego wyliczania nie ma w standardzie, więc musimy zachować szczególną ostrożność przy korzystaniu z tego narzędzia i mieć absolutną pewność, że opcja leniwego wyliczania wartości logicznych jest dostępna i włączona, gdy z niej korzystamy. Poprzednia wersja algorytmu, choć może nieco bardziej chropawa, była bezpieczna: w każdej realizacji Pascala zadziała. Jeżeli nie ma wyraźnych powodów, aby postępować inaczej, należy preferować rozwiązania zgodne ze standardem.
Zadanie 2
Wstaw do posortowanej listy l nowy element o wartości x, zachowując posortowanie l.
Rozwiązanie 1
Aby wstawić nową wartość do posortowanej listy, musimy znaleźć element ZA którym ją wstawimy (trzeba mu będzie zmienić pole nast). Pamiętajmy jednak, że po pierwsze o tym, że już pora wstawiać dowiadujemy się będąc już w jego następniku, bo dopiero następnik tego elementu bedzie większy lub równy wstawianej wartości. Po drugie nie zawsze tak element istnieje.
Ćwiczenie
Kiedy do posortowanej listy nie wstawiamy za jakimś elementem?
Rozwiązanie
Wtedy gdy wstawiany element jest najmniejszy z występujących na liście (w szczególności, gdy lista l jest pusta).
Napiszmy najpierw procedurę, z której często będziemy korzystali i która wstawia do listy element o wartości x za elementem wskazywany przez zmienną wsk. Zauważymy przy okazji wspomnianą na początku wykładu różnicę między wstawianiem do tablicy, a wstawianiem we wskazane miejsce wewnątrz listy. Zakładamy tu, że element wsk istnieje (czyli jest różny od nil).
procedure wstawZA(wsk:lista; x:typA); {wstawiamy wartość x do listy za element wskazywany przez wsk} var pom:lista; begin new(pom); pom^.nast:=wsk^.nast; pom^.w := x; wsk^.nat:=pom end;
Teraz zasadnicza procedura wstawiająca.
procedure wstaw_sort (var l:lista; x:typA); {do posortowanej listy l wstawia wartość x. Parametr l musi być przekazany przez zmienną, gdyż wartość l może się zmienić w przypadku wstawiania najmniejszej wartości do listy – lista będzie miała inny początek} var akt,next: lista; {akt – aktualny, next – następnik akt} begin if' l<>nil then begin {tu nietypowo akurat łatwiej jest napisać kod począwszy od ,,trudniejszego<i> przypadku, gdy lista jest niepusta}</i> akt := l; next := akt^.nast; if (next = nil) and (l^.w<x) then wstawZA(l,x) else begin while (next^.nast<>nil) and (next^.w<x) do begin akt:=next; next:=akt^.nast end; if x<=next^.w then wstawZA(akt,x) else {przerwaliśmy pętlę ze względu na koniec listy i nasza wartość powinna być wstawiona na koniec} wstawZA(next,x) end else {lista jest pusta lub pierwszy element listy jest większy lub równy x} begin akt:=l; {w szczególności może być nil} new(l); l^.w := x; l^.nast := akt end {Zauważmy, że ten sam kod dotyczy pustej listy, jak i przypadku, gdy naszą wartość wstawiamy na początku listy} else wstawZA(l,x) end;
Trzeba przyznać, że kod wyszedł dość obskurny – tutaj kłopot sprawiły nam dwie rzeczy: szczególne przypadki listy pustej i jednoelementowej oraz to, że trzeba było cały czas iść dwoma wskaźnikami, pilnując żeby ten z przodu nie stał się nilem, a zarazem badając jego wartość. Oczywiście użycie leniwego wyliczania tę część by uprościło, ale trzymajmy się na razie standardu.
Poznamy teraz technikę, za pomocą której przynajmniej pierwszy ze wspomnianych kłopotów zniknie.
Ponieważ pewne zamieszanie w jednorodności algorytmu wynikało z potencjalnej pustości listy, więc spróbujmy tak zadziałać, żeby ciąg pusty był reprezentowany przez niepustą listę. Wprowadzimy zatem dodatkowy element na początku listy, atrapę, której jedynym zadaniem będzie posiadanie pola nast – po to, aby było za czym wstawiać nowy element, nawet na początku listy. Tworzenie pustego ciągu wartości zamiast wyglądać tak:
l:= <b>nil</b>
będzie wyglądać tak:
new(l); l^.nast:=nil
Pole w atrapy nie ma znaczenia, więc go nawet nie inicjalizujemy.
Zobaczmy, jak uprości się teraz nasz kod wstawiania do posortowanej listy z atrapą.
procedure wstaw_sort_z_atrapa (l:lista; x:typA); {do posortowanej listy l, zaczynającej się od atrapy, wstawia wartość x. Parametr l nie musi tym razem być przekazany przez zmienną, gdyż wartość l, będąca dowiązaniem do atrapy nie może się zmienić: nawet w przypadku wstawiania najmniejszej wartości do listy – lista będzie miała tę samą atrapę, jako początek} var next: lista; {rolę zmiennej akt może pełnić parametr l} begin next:=l^.nast; if next=nil then {lista pusta} wstawza(l,x) else begin while (next^.w<x) and (next^.nast<>nil) do begin l:=next; next:=l^.nast <b>end</b>; if' x>next^.w then wstawza(next,x) else wstawZA(l,x) end end;
I już!
Co robić, jeśli ktoś nam daje listę bez atrapy? Cóż – zawsze możemy taką atrapę sobie dodać, a potem zlikwidować:
procedure wstaw_sort (var l:lista; x:typ); {robi to samo na normalnej liście, sama sobie dodając atrapę} var atrapa: lista; begin new(atrapa); atrapa^.nast:=l; wstaw_sort_z_atrapa(atrapa, x); l:=atrapa^.nast; dispose(atrapa) end;
Atrapy są na tyle wygodne, że często lepiej się umówić, że listy po prostu reprezentujemy z atrapami. Ale nie przesadzajmy: traktujmy atrapy jako jedną z technik naszego repertuaru i używajmy ich wtedy, gdy są rzeczywiście pożyteczne.
Przyjrzyjmy się korzyściom i stratom wynikającym ze stosowania atrap. Podstawowa korzyść polega na tym, że uzyskujemy często krótszy i klarowniejszy – bardziej jednorodny kod. Złożoność czasowa praktycznie jest taka sama. Pamięciowa – tu jest gorzej: gdy mamy wiele krótkich list, z którymi jednocześnie pracujemy, wówczas dodatkowy rekord może stanowić pewne obciążenie pamięciowe i to jest podstawowa strata, którą trzeba wziąć pod uwagę.