0487 - Rozsądna Oszczędność Cz.1

Szybkość działania programu zależy przede wszystkim od przyjętej przez autora metody rozwiązywania problemu (zamiast metoda będziemy raczej mówili ALGORYTM - na poziomie naszych rozważań słowa te znaczą właściwie to samo).

Zaczniemy od przypadku dwóch algorytmów tego samego problemu. Mamy tablicę T, jej elementy to liczby całkowite, i zapisany w niej tekst - jeden element tablicy zawiera jedną liczbę, odpowiadającą wartości znaku w kodzie ASCII ("Bajtek" 8/86). Zmienna N zawiera długość tekstu, tzn. liczbę znaków. Trzeba, nie posługując się pomocniczymi tablicami, usunąć z tekstu wszystkie spację (znaki odstępu), tzn. na wyjściu w tablicy T ma być tekst bez spacji, w zmiennej N jego długość. Przykład (we wszystkich przykładach zamiast kodów liczbowych będę używał znaków).

T:

a

b

c

d

e

N=11

Wynik: T:

a

b

c

d

e

N=5

Zanim przejdziemy do rozwiązania zwróćmy uwagę na różnicę między algorytmem. Algorytm jest to sposób (metoda, recepta) na rozwiązanie zadania. Może być podany w różny sposób, np. opisem słownym, graficznie (np. schematy blokowe), może też być zapisany w jednym z wielu istniejących języków programowania. W tym ostatnim przypadku otrzymujemy program realizujący dany algorytm. Będę unikał podawania gotowych programów, gdyż "wklepanie" gotowego tekstu nie jest specjalnie kształcące. Programista musi umieć zakodować podany, np. słownie, algorytm w języku programowania, który zna. Oczywiście następny krok, to umiejętność układania własnych algorytmów. Przechodzimy do naszego zadania:

Metoda 1: Zaczynając od pierwszego znaku wykonujemy: jeśli znak nie jest spacją, przesuwamy się o jeden znak (na rysunku w prawo); jeśli jest spacją to: przesuwamy wszystkie znaki, które są na prawo od niego o jeden w lewo (znak, który był prawym sąsiadem badanego zajmie jego miejsce), zmniejszamy N o 1. Sprawdzamy, czy teraz znak jest spacją, jeśli tak, przesuwamy wszystkie znaki, które są na prawo o jeden w lewo., itd, itd., dopóki nie pojawi się znak różny od spacji lub nie skończy się tekst. Po napotkaniu znaku innego niż spacja przesuwamy się o jeden znak w prawo, itd, aż do końca tekstu. Gdy dojdziemy do końca tekstu zdanie jest wybrane.

Konia z rzędem temu, kto to zrozumiał bez kłopotów, dlatego proponuje napisać to jeszcze raz, nieco inaczej:

 Ustaw się na pierwszy znak tekstu;
 DOPÓKI nie koniec tekstu
 WYKONUJ:
   JEŚLI znak nie jest spacją przesuń się do następnego znaku
   W PRZECIWNYM PRZYPADKU
   DOPUKI badany znak jest spacją i nie koniec tekstu
   WYKONUJ
     Przesuń wszystkie znaki, leżące na prawo od badanego,
     o jedną pozycję w lewo (prawy sąsiad badanego zajmie jego miejsce),
     zmniejsz N o 1.
   KONIEC DOPUKI badany znak...
 KONIEC DOPUKI nie koniec tekstu
 STOP

Sformułowanie: "DOPÓKI warunek logiczny WYKONUJ" należy rozumieć następująco: sprawdzamy, czy warunek jest spełniony (ma wartość logiczną PRAWDA), jeśli tak, wykonujemy wszystkie instrukcje, aż do odpowiedniego KONIEC DOPÓKI, ponownie sprawdzamy warunek, wykonujemy, itd, aż do momentu gdy warunek będzie miał wartość FAŁSZ. Wtedy przechodzimy do wykonywania czynności występującej po KONIEC DOPÓKI. W sumie nie jest to nic innego, jak opis pętli, której wykonanie sterowane jest wartością warunku. Dwie uwagi: warunek może być niespełniony już w momencie wejścia, i wtedy zawartość pętli nie wykona się ani razu. Dwa: pętle mogą być zagnieżdżone, tzn. (tak jak w naszym algorytmie), jedna z instrukcji wewnątrz pętli może być pętlą. Pętla wewnętrzna musi się skończyć przed końcem pętli zewnętrznej, co pozwala jednoznacznie ustalić, który koniec jest do której pętli, trzeba się tylko uważnie przyjrzeć. W naszym przykładzie występują dodatkowe komentarze ułatwiające identyfikację.

Powyższym przykładem chcę również rozpocząć przekonywanie Was, że w przekazywaniu informacji liczy się nie tylko treść, ale również postać, np. szata graficzna. Prześledźmy teraz na przykładzie działanie naszego algorytmu (gwiazdka wskazuje na badany znak).

*

T:

a

b

c

d

e

N=11

*

T:

a

b

c

d

e

N=10

*

T:

a

b

c

d

e

N=10

*

T:

a

b

c

d

e

N=9

*

T:

a

b

c

d

e

N=9 itd.

Mam nadzieję, że dalej poradzicie sobie sami. Chciałby żebyście dokładnie zrozumieli działanie algorytmu, gdyż zaraz będziemy go dalej analizować. Może również warto go zaprogramować - oczywiście zamiast gwiazdki trzeba użyć zmiennej określającej położenie w tablicy badanego znaku.

Analizę algorytmu najłatwiej zacząć od przypadków końcowych. Popatrzmy co się stanie gdy nasz tekst będzie się składał z samych spacji: w pierwszym kroku na nowe miejsce zostaje przepisanych N-1 znaków, w drugim N-2, następnie N-3, ..., w przedostatnim 2 znaki w ostatnim 1. Czyli w sumie będzie N-1+N-2+N-3+ ... +2+1 operacji przepisywania znaku. Wartość tej sumy wynosi N*(N-1)/2=(N²-N)/2, czyli jest proporcjonalna do kwadratu ilości znaków w tekście. Jakie to ma znaczenie? Popatrzmy na kilka wartości N i N²:

N    10      100       1000       10000       20000
N2  100    10000    1000000    10000000    40000000

Oczywiście nie liczby są najważniejsze, tylko szybkość, z jaką wzrasta liczba operacji potrzebnych do otrzymania rozwiązania - jeśli tekst wydłużymy 10 razy to czas działania programu trzeba pomnożyć przez sto!!. Co prawda wybraliśmy przypadek najmniej korzystny, ale dla wielu, dużo bardziej prawdopodobnych danych, koszt wykonania algorytmu również jest proporcjonalny do kwadratu ilości znaków w tekście, czyli bardzo znaczny.

Jak w takiej sytuacji napisać szybko działający program? Żadne kombinacje i drobne usprawnienia nie pomogą nam wiele, gdyż już niewielki wzrost rozmiaru danych zniweluje osiągnięty efekt. Jedyną rozsądną metodą jest znalezienie tańszego algorytmu. Spróbujmy nasze zadanie rozwiązać inaczej:

Metoda 2: (Będziemy w niej korzystali z dwóch wskaźników: w1, w2)

 Ustaw wskaźnik w1, w2, na początku tekstu;
 Przesuń w1, w2 aż do pierwszej spacji;
 DOPÓKI nie koniec tekstu
 WYKONUJ
   Przesuń w2 o jeden znak w przód;
   JEŚLI w2 wskazuje spację nie rób nic
   W PRZECIWNYM WYPADKU
     Przepisz wskazywany przez w2 znak na miesce
     wskazywane przez w1 i przesuń w1 o jeden znak
     w przód, oraz zmniejsz N o 1;
 KONIEC DOPÓKI
 STOP

+

T:

a

b

c

d

e

N=11

*

+

T:

a

b

c

d

e

N=11

*

+

T:

a

a

b

c

d

e

N=10

*

+

T:

a

a

b

c

d

e

N=10

*

+

T:

a

a

b

c

d

e

N=10

*

+

T:

a

a

b

c

d

e

N=10

*

+

T:

a

a

b

c

d

e

N=9 itd...

*

(Jak widać przepisując znak w lewo nie musimy wpisywać w jego miejsce spacji, za to po zakończeniu algorytmu w końcowej części tablicy pozostaje część starego tekstu - na pozostałych większych niż ostateczna wartość N).

W tym algorytmie spacje nie są przepisywane w ogóle, każdy z pozostałych znaków jest przepisywany tylko raz - od razu na właściwe miejsce. Wniosek: liczba operacji przepisania znaku nigdy nie będzie większa niż liczba znaków w tekście. Postęp jest ogromny. Dla danych wielkości N koszt wykonania algorytmu jest rzędu N operacji, a nie jak poprzednio N² - popatrzcie jeszcze raz na tabelkę wartości N i N²!

Przedstawione zadanie nie ma wielkiego znaczenia praktycznego*) jednak problem, który ilustruje jest problemem typowym i ma ogromne znaczenie. Praktycznymi wnioskami wynikającymi z zaprezentowanego materiału zajmiemy się za miesiąc, w drugiej części tego artykułu...

Na zakończenie obiecane w poprzednim miesiącu wyjaśnienia. Czy wartość zmiennej całkowitej A% jest parzysta:

 POM% = A%/2
 IF POM%*2 = A% THEN PRINT "Wartość A% jest parzysta".

Konwersja z systemu dziesiętnego na szesnastkowy przebiega analogicznie do opisanej (Bajtek 13/86) konwersji z dziesiętnego na dwójkowy. Dzielimy liczbę dziesiętną przez podstawę systemu - w tym przypadku przez 16. Otrzymujemy iloraz i resztę, która jest wartością z przedziału 0-15. Reszta jest pierwszą od prawej cyfrą wynikowej liczby szesnastkowej, iloraz ponownie dzielimy przez 16 itd.

*) Można sobie wyobrazić wiele mutacji podanego algorytmu, najprostsza to usuwanie znaków innych niż spacja. Inne mogą działać nie na poziomie przepisywania znaków , lecz całych bloków informacji, gdy część bloków usuwamy, a reszta musi tworzyć spójną całość.

Andrzej Pilaszek, Bajtek 04/1987r.