ROZDZIAŁ DWUDZIESTY PIĄTY OPTYMALIACJA NASZYCH PROGRAMÓW, INFORMATYKA, „THE ART OF ASSEMBLY LANGUAGE” ...

[ Pobierz całość w formacie PDF ]
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
WYŁĄCZNOŚĆ DO PUBLIKOWANIA TEGO TŁUMACZENIA
POSIADA
RAG
„THE ART OF ASSEMBLY LANGUAGE
”
tłumaczone by KREMIK
Konsultacje naukowe: NEKRO
wankenob@priv5.onet.pl
nekro@pf.pl
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
ROZDZIAŁ DWUDZIESTY PIĄTY:
OPTYMALIACJA NASZYCH PROGRAMÓW
25.0 WSTĘP
Ponieważ optymalizacja programu jest generalnie jednym z ostatnich kroków w projektowaniu
oprogramowania, jest to tylko przymiarka do omówienia optymalizacji programu w ostatni rozdziale tej książki.
Przeszukując inne teksty, które omawiają ten temat, znajdziemy szeroką gamę opinii na ten temat. Niektóre
teksty i artykuły ignorują zbiór instrukcji całkowicie i koncentrują się na znajdowaniu lepszych algorytmów.
Inne dokumenty zakładają, że już znaleziono najlepszy algorytm i omawiają sposoby wybierania „najlepszej”
sekwencji instrukcji realizujących tą pracę. Inne rozważają architekturę CPU i opisują jak „liczyć cykle” i pary
instrukcji (zwłaszcza na procesorach superskalarnych lub procesorach z potokami) tworząc szybciej wykonujący
się kod. Inne jeszcze rozpatrują architekturę systemu, nie tylko CPU, kiedy próbują zdecydować jak
optymalizować mamy nasz program. Niektórzy autorzy spędzają dużo czasu wyjaśniając, że ich metoda jest
„jedynie słuszną” dla przyspieszenia programu. Inni jeszcze odbiegają od inżynierii oprogramowania i
zaczynają mówić o tym jak czas spędzony nad optymalizacja programu nie jest wart tego z różnych powodów.
Cóż, rozdział ten nie ma zamiaru przedstawiać „jedynie słusznego sposobu”, ani też spędzać wiele czasu na
sprzeczaniu się o pewne techniki optymalizacji. Po prostu przedstawi kilka przykładów, opcji i sugestii.
Ponieważ jesteś sobą po tym rozdziale, czas na Ciebie abyś zaczął podejmować samodzielne decyzje. Miejmy
nadzieję, że rozdział ten dostarczy stosownych informacji dal podejmowania poprawnych decyzji.
25.1 KIEDY OPTYMALIZOWAĆ,KIEDY NIE OPTYMALIZOWAĆ
Proces optymalizacji nie jest tandetny Jeśli projektujemy program a potem stwierdzimy, że jest zbyt
wolny, może będziemy musieli przeprojektować i napisać na nowo główną część tego programu dal uzyskania
akceptowalnej wydajności. W oparciu o powyższe świat dzieli się na dwa obozy – tych , którzy optymizują
wcześnie i tych , którzy optymalizują później. Obie grupy mają dobre argumenty; obie grupy mają jakieś złe
argumenty. Przyjrzymy się obu stronom tych argumentów.
Grupa „optymalizujących później” (OL) używa argumentu 90/10: 90% czasu wykonywania programu
jest spędzanych w 10% kodu. Jeśli próbujemy optymalizować każdy kawałek kodu jaki napisaliśmy (to jest,
optymalizujemy kod zanim dowiemy się ,że musi być zoptymalizowany), 90% wysiłku włożonego pójdzie na
marne. Z drugiej strony, jeśli najpierw piszemy kod w zwykły sposób a potem idziemy w optymalizację,
możemy poprawić wydajność naszego programu przy mniejszym wkładzie pracy. W końcu jeśli zupełnie
usuniemy 90% naszego programu, nasz kod będzie działał tylko 10% szybciej. Z drugiej strony, jeśli zupełnie
usuniemy te 10%, program nasz będzie działał 10 razy szybciej Matematyk oczywiście przemawia za tym aby
zająć się tymi 10%. Grupa OL twierdzi, że powinniśmy napisać kod zwracając tylko uwagę na wydajność (tj.
dać wybór pomiędzy algorytmem O(n
2
) a O(n lg n), wybierając ten drugi). Ponieważ program działa poprawnie
możemy wrócić i skoncentrować wysiłek na tych 10% kodu, który zabiera cały czas.
Argumenty OL są przekonywujące. Optymalizacja jest żmudnym i trudnym problemem. Najczęściej
nie ma jasnego sposobu przyspieszenia sekcji kodu. Jedyny sposób określa, która z różnych opcji jest lepszym w
rzeczywistości kodem i porównać je. Próba zrobienia tego na wejściu programu jest niepraktyczne. Jednakże,
jeśli znajdziemy te 10% kodu i zoptymalizujemy go, zredukujemy nasz e obciążenie o 90% istotnie bardzo
kusząc .Innym dobrym argumentem grupy )L jest to ,że niewielu programistów jest w stanie określić gdzie
najwięcej czasu jest spędzanych w programie. Dlatego też jedynym rzeczywistym sposobem określenia gdzie
program spędza czas jest oprzyrządowanie go i pomierzenie, które funkcje zabierają większość czasu.
Oczywiście musimy mieć działający program zanim to zrobimy. Ponownie, argumentują, że czas spędzony nad
 optymalizacją kodu z wyprzedzeniem jest marnotrawstwem ponieważ prawdopodobnie skończymy na
optymalizacji tych 90%, które nie zmieniają niczego.
Są jednak bardzo dobre kontr argumenty do powyższych. Po pierwsze, kiedy większość OL zaczyna
mówić o zasadzie 90/10, jest to bezgraniczna sugestia, że te 10% kodu pojawi się jako jeden duży fragment w
środku naszego programu .Dobry programista, podobnie jak dobry chirurg, może zlokalizować tą złośliwą
masę, wyciąć ją i zastąpić czymś dużo szybszym, a zatem zwiększyć szybkość programu niewielkim wysiłkiem.
Niestety, nie jest to częsty przypadek w świecie rzeczywistym. W prawdziwych programach, te 10% kodu ,
które zabiera 90% czasu wykonania jest często porozrzucany po całym naszym programie. Będziemy mieli 1%
tu, 0,5% tam, „gigantyczne” 2,5% w jednej funkcji i tak dalej. Gorzej jeszcze, optymalizacja 1% kodu wewnątrz
jednej funkcji często wymaga aby zmodyfikować również jakiś inny kod. Na przykład, przepisując funkcję
(1%), przyspieszając ją trochę, wymagana jest zmiana sposobu przekazywania parametrów do tej funkcji. Może
to wymagać przepisania kilku sekcji kodu na zewnątrz, tych wolnych 10%. Wiec często kończy się na
przepisaniu dużo więcej niż tylko 10% kodu aby przyspieszyć te 10 % zajmujące 90% czasu.
Inny problem z zasadą 90/10 jest taki, że dział na procentach, i zmienia procenty podczas optymalizacji.
Na przykład przypuśćmy, że zlokalizowaliśmy funkcję pożerającą 90% czasu wykonania. Przypuśćmy, że Pan
Super Programista i ty daliście sobie radę z przyspieszeniem tego podprogramu dwukrotnie. Nasz program
pobierać bezie około 55% czasu wykonania przed optymalizacją. Jeśli potroimy szybkość podprogramu ,
program pobiera 40% całkowitego czasu wykonania. Jeśli spowodujemy ,że ta funkcja będzie działała dziewięć
razy szybciej , program działał będzie teraz w 20% czasu oryginalnego, tj. pięć razy szybciej.
Przypuśćmy, że możemy pobrać funkcję działającą dziewięć razy szybciej. Załóżmy, że zasada 90/10
już nie ma zastosowania do naszego programu. 50% czasu wykonania jest spędzanych w 10% kodu, 50% w
pozostałych 90% kodu. I jeśli poradziliśmy sobie z przyspieszeniem tej jednej funkcji 0 900%, jest bardzo
nieprawdopodobne abyśmy musieli wykluczyć dużo więcej z niego. Czy jest warte zachodu nie traktowanie
poważnie tych pozostałych 90% kodu? Zakładamy ,że jest. W końcu, możemy poprawić wydajność naszego
programu o 25% jeśli podwoimy szybkość tego pozostałego kodu. Odnotujmy, że jednak mamy tylko 25%
wydajność zwiększoną po optymalizacji 10%. Mając zoptymalizowane najpierw 90%, będziemy mieli 5%
poprawę wydajności; prawie nic. Pomimo to ujrzymy sytuację gdzie zasada 90/10 wyraźnie nie ma
zastosowania i zobaczymy przypadki gdzie optymalizacja tych 90% może stworzyć znaczną poprawę
wydajności. Grupa OL uśmiechnie się i powie „hmm, to jest korzyść późnej optymalizacji, możemy
optymalizować stopniowo i pobierać poprawną ilość optymalizacji jaką potrzebujemy”.
Grupa wczesnej optymalizacji (OE) używa słabości w arytmetyce procentów do wskazania, że
prawdopodobnie zakończymy optymalizację dużej części naszego programu tak czy inaczej. Więc dlaczego nie
obsłużyć wszystkiego tego w pierwszej kolejności w naszym projekcie? Duży problem ze strategią OL jest taki,
że często kończymy projektowanie i pisanie programu dwukrotnie – raz aby uczynić go funkcjonalnym, drugi
raz czyniąc go praktycznym. W końcu jeśli mamy zamiar przepisać i tak 90%, dlaczego nie napisać go szybciej
za pierwszym razem? Ludzie z OE również wskazują ,ze chociaż programiści notorycznie błądzą przy ustalaniu
gzie program spędza większość czasu, są pewne oczywiste miejsca gdzie wiadomo iż wystąpią problemy z
wydajnością. Dlaczego czekać do odkrycia tej oczywistości? Dlaczego nie obsłużyć takich obszarów problemu
wcześniej co pozwoli spędzić mniej czasu na mierzeniu i optymalizacji tego kodu?
Podobnie jak wiele innych argumentów w Inżynierii Oprogramowania, te dwa obozy stały się zupełnie
spolaryzowane i stają się zwolennikami całkowicie czystego podejścia w jednym z kierunków (albo OE albo
OL). Podobnie jak wiele innych argumentów w Informatyce, prawda leży gdzieś pomiędzy tymi dwoma
ekstremami Każdy projekt gdzie programista przystępuje do projektowania perfekcyjnego programu bez
martwienia się o wydajność dopóki koniec jest przesądzony. .Większość programistów w tym scenariuszu pisze
strasznie wolny kod. Dlaczego? Ponieważ łatwiej jest zrobić to a potem zawsze mogą „rozwiązać problem
wydajności podczas fazy optymalizacji.” W wyniku tego, 90% części programu jest często tak wolnych , że
nawet jeśli czas pozostałych 10% zostałby zredukowany do zera program byłby jeszcze zbyt wolny. Z drugiej
strony, grupa OE próbuje dogonić w pisaniu najlepszego z możliwych kodu opuszczając warunki graniczne , a
produkt może nigdy nie zaskoczyć,
Jest jeden niezaprzeczalny fakt, który faworyzuje argumentację OL – kod optymalizowany jest trudny
do zrozumienia i pielęgnacji. Co więcej, często zawiera błędy, które nie są obecne w kodzie
niezoptymalizowanym. Ponieważ kod niepoprawny jest nieakceptowany, nawet jeśli działa szybciej, bardzo
dobrym argumentem przeciw wczesnej optymalizacji jest fakt, ze testowanie, debuggowanie i zapewnienie
jakości przedstawia dużą część cyklu rozwoju programu. Wczesna optymalizacja może tworzyć wiele
dodatkowych błędów programowych, które gubimy obojętnie kiedy ,zachowując przez nie optymalizowanie
później w cyklu rozwoju.
Poprawnym czasem do optymalizacji programu jest, cóż, odpowiedni czas. Niestety „odpowiedni czas”
różni się w programie. Jednakże, pierwszym krokiem jest rozwój wydajności programu wymaganej wraz z
innymi specyfikacjami programu. System analizy powinien rozwinąć docelowy czas reakcji dla wszystkich
interakcji użytkownika i przetwarzania. Podczas rozwoju i testowania, programiści maja cel do wypełnienia ,
więc nie mogą lenić się i czekać na fazę optymalizacji przed napisaniem kodu, wykonującego się rozsądnie. Z
drugiej strony mają również na celowniku to, że chociaż kod działa dosyć szybko, nie muszą marnować czasu,
lub czynić swój kod mniej pielęgnacyjnym; mogą pójść dalej i pracować nad resztą programu. Oczywiście,
system analizy może źle ocenić wymagania wydajności, ale nie zdarza się to często w dobrze zaprojektowanym
systemie.
Inną okolicznością jest to kiedy co wykonać. Jest kilka typów optymalizacji jakie możemy zastosować.
Na przykład. Możemy przestawić instrukcje unikając hazardu dublujących szybkość kawałka kodu. Lub
możemy wybrać różne algorytmy, które możemy uruchomi dwa razy szybciej. Jednym wielkim problem z
optymalizacją jest taki, że nie jest to proces pojedynczy a wiele typów optymalizacji jest lepiej wykonać później
niż wcześniej lub vice versa. Na przykład, wybór dobrego algorytmu jest tym co powinniśmy zrobić wcześniej.
Jeśli zdecydujemy się użyć lepszego algorytmu po implementacji kiepskiego, wiele pracy na kodzie
implementującym stary algorytm jest stracone. Podobnie szeregowanie instrukcji jest jedną z ostatnich
optymalizacji jakie powinniśmy zrobić. Każda zmiana kodu po przestawieniu instrukcji dla wydajności, może
wymusić spędzenie później wiele na czasu na przestawianiu ich ponownie. Najwyraźniej najniższy poziom
optymalizacji (tj. zależny od CPU lub parametrów systemu) powinien być optymalizowany później. Odwrotnie,
poziom najwyższy optymalizacji (tj. wybór algorytmu) powinien być optymalizowany szybciej. We wszystkich
przypadkach powinniśmy mieć docelowe wartości wydajności na myśli podczas rozwijania kodu.
25.2 JAK ZNALEŻĆ WOLNY KOD W NASZYM PROGRAMIE?
Chociaż są problemy z zasada 90/10, koncepcja jest w zasadzie solidna – programy mają w zwyczaju
spędzać duża ilość swojego czasu wykonania tylko w małym procencie kodu. Wyraźnie powinniśmy
zoptymalizować najpierw najwolniejszą część kodu. Jedyny problem to ten jak znaleźć ten najwolniejszy kod
programu?
Są cztery powszechne techniki programistyczne używane do znajdowania „gorących miejsc” (miejsc
gdzie programy spędzają większość swojego czasu). Pierwsza to metoda prób i błędów. Druga to optymalizacja
wszystkiego. Trzecią jest analiza programu. Czwartą jest użycie profilu lub innego systemowego narzędzia
monitorowania wydajności różnych części programu. Po zlokalizowaniu gorących miejsc programista może
próbować zanalizować tą część programu.
Technika prób i błędów jest ,niestety, najpopularniejszą strategią. Programista przyspiesza różne części
programu poprzez uczynienie świadomego odgadywania gdzie spędza się większość czasu. Jeśli programista
odgadnie prawidłowo, program będzie działał dużo szybciej po optymalizacji. Eksperymentujący programiści
często używają tej techniki szczęśliwie szybko lokalizując i optymalizując program. Jeśli programista odgadnie
prawidłowo, technika ta minimalizuje ilość czasu spędzonego na znajdowaniu gorących miejsc w programie.
Niestety większość programistów źle odgaduje i kończy na optymalizowaniu złych części kodów. Taki wysiłek
często idzie na marne ponieważ optymalizacja złych 10% nie poprawi zdecydowanie wydajności. Jednym z
podstawowych powodów błędności tej techniki jest to ,że jest często pierwszym wyborem niedoświadczonych
programistów , którzy nie mogą łatwo rozpoznać wolnego kodu. Niestety, są oni nieświadomi innych technik,
więc zamiast próbować podejścia strukturalnego, zaczynają stosować (często) odgadywanie nieświadome.
Innym sposobem zlokalizowania i optymalizacji wolnej części programu jest optymalizacja
wszystkiego. Oczywiście technika ta nie działa dobrze dla dużych programów, ale dla krótkich części kodu
działa stosunkowo dobrze. Później w tym tekście będzie dostarczony krótkiego przykładu problemu
optymalizacji i będzie stosował tą technikę optymalizacji programu. Oczywiście, dla dużego programu lub
podprogramów może nie być podejściem mało opłacalnym. Jednakże gdzie właściwie można zachować czas
podczas optymalizacji naszego programu (lub przynajmniej części programu) ponieważ nie będziemy musieli
uważnie analizować i mierzyć wydajności naszego kodu. Poprzez optymalizację wszystkiego, jesteśmy pewni
optymalizacji wolnego kodu.
Metoda analizy jest najtrudniejszą z tych czterech. Przy tej metodzie studiujemy nasz kod i określamy
gdzie program spędza większość czasu w oparciu o dane jakich oczekujemy od procesu. Teoretycznie , jest to
najlepsza technika. W praktyce, istoty ludzkie generalnie wykazują dystans dla takiej pracy analitycznej. Jako
taka, analiza jest często niepoprawna lub zbyt długa do ukończenia. Co więcej, niewielu programistów ma duże
doświadczenie w studiowaniu swoich kodów dla określenia gdzie spędza on większość swojego czasu, więc
często są bezradni przy lokalizowaniu gorących miejsc przez studiowanie swoich listingów kiedy pojawia się
potrzeba.
Pomimo problemów z analizą programów, jest to pierwsza technika jakiej powinniśmy zawsze używać,
kiedy próbujemy optymalizować program.. Prawie wszystkie programy spędzają większość swojego czasu
wykonania w ciele pętli lub rekurencyjnym wywołaniu funkcji.. Dlatego też powinniśmy spróbować
zlokalizować wszystkie rekurencyjne wywołania funkcji (zwłaszcza pętle zagnieżdżone) w naszych
programach. Jest bardzo duże prawdopodobieństwo, że program będzie spędzał większość swojego czasu w
jednym z tych dwóch obszarach programu. Takie miejsca są do rozważenia w pierwszej kolejności kiedy
optymalizujemy nasze programy.
Chociaż metoda analityczna dostarcza dobrego sposobu zlokalizowania wolnego kodu w programie,
analizowanie programu jest wolnym, nużącym i nudnym procesem. Jest bardzo łatwo zupełnie zgubić
najbardziej czasochłonna część programu, zwłaszcza w pośredniej obecności wywołania funkcji rekurencyjnej.
Nawet zlokalizowanie czasochłonnych pętli zagnieżdżonych jest często trudne. Na przykład możemy nie
uświadamiać sobie, kiedy szukamy pętli wewnątrz procedury, że jest zagnieżdżona pętla z racji faktu, że kod
wywołujący wykonuje pętlę kiedy wywołujemy procedurę. Teoretycznie, metoda analityczna powinna zawsze
działać. W praktyce, jest to tylko nieznaczny sukces ,kiedy omylni ludzie robią analizę. Niemniej jednak, pewne
gorące miejsca są łatwe do odnalezienia poprzez analizę programu, więc naszym pierwszym krokiem, kiedy
optymalizujemy program jest analiza.
Ponieważ programiści są notorycznie słabi przy analizie programów w celu znalezienia
gorących miejsc, można spróbować zautomatyzować ten proces. Jest to dokładnie to co profiler może zrobić dla
nas. Profiler jest małym programikiem, który mierzy jak długo nasz kod spędza w jakiejś części programu.
Profiler zazwyczaj działa poprzez cykliczne przerywanie naszego kodu i odnotowywanie adresu powrotnego.
Profiler buduje histogram przerwań adresów przerwań (generalnie zaokrągla do określonej przez użytkownika
wartości). Poprzez studiowanie tego , możemy określić gdzie program spędza większość czasu .Powie to nam
jaką część kodu musimy zoptymalizować. Oczywiście, stosując ta technikę, będziemy potrzebowali programu
profilera. Borland, Microsoft i kilku innych producentów dostarcza profilerów i innych narzędzi
optymalizujących.
25.3 CZY OPTYMALIZACJA JST KONIECZNA?
Z wyjątkiem zabawy i edukacji, nigdy nie powinniśmy próbować podejścia do projektu z postawą, że
musimy uzyskać maksymalną wydajność naszego kodu. Lata temu, była to ważna postawa ponieważ było to to
co pozwalało uzyskiwać przyzwoite działanie na wolnych maszynach tej ery. Redukując czas działania
programu z dziesięciu minut do dziesięciu sekund, uczyniono poważny krok dla poprawy wydajności . Z drugiej
strony przyspieszenie programu pobierającego 0,1 sekundy do punktu w którym działa on w milisekundę jest
często bezcelowe. Zmarnujemy dużo wysiłku poprawiając wydajność, mimo to tylko kilka osób odnotuje
różnice.
Nie mówię, że przyspieszenie programu z 0,1 sekundy do 0,001 sekundy nie jest nigdy warte zachodu.
Jeśli piszemy program do zbierania danych, który wymaga wykonania odczytu co milisekundę, a może tylko
obsłużyć dziesięć odczytów na sekundę jako obecnie zapisanych. Co więcej, nawet jeśli nasz program działu
już dość szybko, są powody dlaczego chcielibyśmy uczynić go dwa razy szybszym. Na przykład przypuśćmy, że
ktoś może używać naszego programu w środowisku wielozadaniowym. Jeśli zmodyfikujemy nasz program do
dwukrotnie szybszego, użytkownik będzie mógł uruchomić inny program wraz z naszym i nie zauważyć
obniżenia wydajności.
Jednakże, sprawą do zapamiętania jest to, że musimy napisać oprogramowanie, które jest dosyć
szybkie. Ponieważ program tworzy wyniki natychmiastowe (lub prawie bliskie natychmiastowych) istnieje
potrzeba uczynienie jego uruchomienia szybszym. Ponieważ optymalizacja jest procesem kosztownym i
skłonnym do błędów, chcemy unikać jej jak to tylko możliwe. Pisanie programów, które działają szybciej niż
dosyć szybki jest marnowaniem czasu. Jednakże, jak widać wyraźnie z dzisiejszych rozdętych aplikacji, nie jest
to rzeczywisty, większość tworzonych kodów programistycznych jest zbyt wolnych, nie zbyt szybkich.
Popularnym podawanym powodem dla tworzenia nie zoptymalizowanego kodu jest złożoność sprzętu. Wielu
programistów i menadżerów czuje ze maszyny wyższej klasy dla których projektują oprogramowanie dzisiaj,
będą maszynami średniej klasy za dwa lata, kiedy udostępnią końcową wersją oprogramowania .Więc jeśli
zaprojektują oprogramowanie działające na dzisiejszych bardzo szybkich maszynach, będą się wykonywały
średniej klasy maszynach kiedy udostępnią oprogramowanie
Są z tym związane dwa problemy. Po pierwsze system operacyjny działający na tych maszynach za
dwa lata pożre znaczną część zasobów maszyny (wliczając w to cykle CPU) Ciekawe jest, że dzisiejsze są sto
razy szybsze niż oryginalny 8088, a mimo to wiele aplikacji działa wolniej niż gdyby działał na oryginalnym
PC.. Prawda , dzisiejsze oprogramowanie dostarcza wiele cech poza te z oryginalnego PC, ale jest cała masa
argumentów – klienci domagają się cech takich jak wiele okienek, GUI, menu rozwijane itd., które
wykorzystują cykle CPU. Nie możemy zakładać, ze nowsze maszyny będą dostarczały dodatkowych cykli
zegarowych, więc nasz wolny kod będzie działał szybciej. OS lub interfejs użytkownika naszego programu
zakończy zjedzenie tych dodatkowych dostępnych cykli zegarowych.
Tak więc pierwszym krokiem jest realistyczne określenie żądanej wydajności naszego programu. Potem
musimy napisać program spełniający ten cel wydajności. Kiedy rozminiemy się z żądana wydajnością, wtedy
jest czas na optymalizację programu. Jednakże nie powinniśmy marnować dodatkowego czasu optymalizując
kod ponieważ nasz program napotyka lub przekracza specyfikację wydajności.
25.4 TRZY TYPY OPTYMALZACJI
Są trzy formy optymalizacji jakie może zastosować, kiedy poprawiamy wydajność programu.
Wybierają one lepszy algorytm (optymalizacja wysokiego poziomu), implementację lepszego algorytmu
(poziom optymalizacji średniego poziomu) i „zliczanie cykli” (optymalizacja niskiego poziomu). Każda
technika ma swoje miejsce i, generalnie, stosujemy je w różnych miejscach w procesie projektowania.
Wybór lepszego algorytmu jest najbardziej nagłośnioną technika optymalizacji. Niestety jest to
technika używana najmniej często. Jest łatwa dla kogoś głoszącego, że powinniśmy zawsze znajdować lepszy
algorytm jeśli potrzebujemy większej szybkości; ale znalezienie tego algorytmu jest trochę trudniejsze. Po
pierwsze, zdefiniujmy algorytm zmiany ponieważ używamy zasadniczo różnych technik do rozwiązania
problemu. Na przykład, przełączając z algorytmu „sortowania bąbelkowego” do algorytmu „szybkiego
sortowania” jest dobrym przykładem algorytmu zmiany, Generalnie, chociaż nie zawsze, zmiany algorytmów
oznaczają, że używamy programu z lepsza funkcją Big-Oh. Na przykład, kiedy przełączamy z sortowania
bąbelkowego do szybkiego sortowania, zmieniamy algorytm z czasem działania O(n
2
) na algorytm z
oczekiwanym czasem działania O(n lg n).
Musimy pamiętać o ograniczeniach funkcji Big-Oh kiedy porównujemy algorytmy. Wartość dla n musi
być wystarczająco duża do zamaskowania efektu ukrytej stałej. Co więcej, analizy Big-Oh są zazwyczaj
najgorsze i mogą nie wpływać na nasz program. Na przykład jeśli życzymy sobie posortować tablicę, która jest
„prawie” posortowana najpierw, algorytm sortowania bąbelkowego jest zazwyczaj szybszy niż algorytm
szybkiego sortowania, bez względu na wartość dla n. Dla danej, która jest prawie posortowana, sortowanie
bąbelkowego działa prawie w czasie O(n) podczas gdy algorytm szybkiego sortowania działa w czasie O(n
2
).
Drugą rzeczą do zapamiętania jest stałość. Jeśli dwa algorytmy mają taką samą funkcję Big-Oh, nie
możemy określić żadnej różnicy pomiędzy dwoma analizami Big-Oh. To nie znaczy, że będą one pobierały taką
samą ilość czasu działania. Nie zapomnijmy, że w analizie Big-Oh odrzucamy wszystkie nisko poziomowe
warunki i stałe mnożne. Trochę bardziej pomocny jest zapis asymptotyczny w tym przypadku.
Uzyskanie rzeczywiście poprawy wydajności wymaga zmiany algorytmu naszego programu. Jednakże,
zmiana algorytmu O(n lg n) na algorytm O(n
2
) jest często trudniejsze jeśli rozwiązanie już nie istnieje.
Przypuszczalnie , dobrze zaprojektowany program nie będzie zawierał oczywistych algorytmów, które możemy
dramatycznie poprawić (jeśli są , nie były dobrze zaprojektowane).Dlatego też, próby znalezienia lepszego
algorytmu może nie zakończyć się powodzeniem. Niemniej jednak jest to zawsze pierwszy krok jaki
powinniśmy wykonać ponieważ kolejne kroki działają na takim algorytmie jaki mamy. Jeśli wykonujemy te
inne kroki na złym algorytmie a potem, później odkryjemy lepszy algorytm, będziemy musieli powtarzać, te
czasochłonne kroki ponownie przy nowym algorytmie.
Są dwa kroki odkrywania nowych algorytmów: badanie i rozwój. Pierwszy krok służy temu aby
zobaczyć czy możemy znaleźć lepsze rozwiązanie w istniejącej literaturze. Ewentualnie, drugi krok jest po to
aby zobaczyć czy możemy odkryć lepszy algorytm w naszym własnym. Kluczem do tego jest zabudżetowanie
właściwej ilości czasu dla tych dwóch działań badanie jest luźnym procesem . Zawsze możemy przeczytać
więcej książek lub artykułów. Więc musimy zadecydować jak wiele czasu mamy zamiar spędzić szukając
istniejącego rozwiązania. Może to być kilka godzin, dni m, tygodni lub miesięcy. Jakkolwiek jest to opłacalne.
Potem możemy udać się do biblioteki (lub półki z książkami) i poszukać lepszego rozwiązania. Gdy tylko
wygasa nasz czas, czas porzucić podejście badawcze chyba, że jesteśmy pewni, że zmierzamy we właściwym
kierunku w materiałach jakie studiujemy. Jeśli tak zabudżetujemy trochę więcej czasu i zobaczmy jak to działa.
W tym samym miejscu jednak musimy zadecydować czy prawdopodobnie nie można znaleźć lepszego
rozwiązania i czy jest czas aby rozwinąć nowe w naszym własnym.
Podczas poszukiwania lepszego rozwiązania powinniśmy studiować dokładnie artykuły, teksty itp.
Chociaż przestudiowaliśmy ważne testy. Kiedy prawdą jest ,że większość z tego co wystudiowaliśmy nie będzie
miało zastosowania do problemu, nauczymy się o rzeczach, które będą użyteczne w przyszłych projektach. Co
więcej, podczas gdy ktoś może nie uzyskać potrzebnego rozwiązania, może wykonać pracę , która idzie w tym
samym kierunku co nasza i może dostarczyć takich samych dobrych pomysłów, jeśli nie podstawowych dla
naszego własnego rozwiązania. Jednakże, zawsze musimy pamiętać, że zadaniem inżynierów jest dostarczenie
wydajnych rozwiązań problemu. Jeśli marnujemy zbyt dużo czasu szukając rozwiązań, które mogą się nigdzie
nie pojawić w literaturze, spowodujemy kosztowne przedłużenie naszego projektu. Trzeba wiedzieć, kiedy jest
czas aby „odłożyć go” i zając się resztą projektu.
Rozwijanie nowego algorytmu jako naszego własnego jest również luźne. Możemy spędzić resztę życia
próbując znaleźć wydajne rozwiązanie dla trudnego do rozwiązania problemu. Ponownie więc musimy
zabudżetować czas w związku z tym dla tego projektu. Spędzajmy czas mądrze próbując rozwijać lepsze
[ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • tejsza.htw.pl

    •