[ Pobierz całość w formacie PDF ]
.Jeśli dopuszczalne liczby wejściowe są ograniczone z góry, możemy odrazu stwierdzić, ile czasu zajmie wykonywanie naszego kodu.Jeśli te wartościzależą od czynników zewnętrznych (na przykład liczby rekordów zwróconychprzez plik wsadowy uruchamiany na noc czy liczby nazwisk na liście klientów),być może powinniśmy skoncentrować się raczej na maksymalnym akcepto-wanym czasie działania lub na maksymalnym dopuszczalnym poziomie wyko-rzystania pamięci.WSKAZ�WKA NR 45Należy szacować rzędy wielkości algorytmów.Istnieją pewne techniki, które można z powodzeniem wykorzystywać do rozwią-zywania potencjalnych problemów.Jeśli złożoność naszego algorytmu wynosiO(n2), warto podjąć próbę zastosowania techniki dziel i zwyciężaj , aby obniżyćtę złożoność do O(n lg(n)).Jeśli nie jesteśmy pewni, ile czasu potrzeba na wykonanie naszego kodu lubile pamięci wykorzysta nasz kod, wystarczy to sprawdzić, przeprowadzająceksperymenty przy różnej liczbie rekordów wejściowych (lub różnych warto-ściach dowolnego innego parametru, który prawdopodobnie będzie miał wpływna czas działania algorytmu).Warto następnie nanieść wyniki na wykres.Kształt tak tworzonego wykresu dość szybko powinien nam zasugerować fak-tyczną złożoność.Czy mamy do czynienia z krzywą rosnącą, prostą, czy możekrzywą dążącą do jakiejś wartości stałej (przy rosnącej ilości danych wejścio-wych)? Trzy lub cztery pomiary powinny wystarczyć.Warto też testować rozwiązania stosowane w samym kodzie.Dla odpowiedniomałych wartości n prosta pętla o złożoności O(n2) może działać dużo szybciej odskomplikowanej pętli o złożoności O(n lg(n)), szczególnie jeśli algorytm O(n lg(n))zawiera kosztowną pętlę wewnętrzną.Opisana teoria nie powinna przesłaniać nam praktycznych aspektów szybkościalgorytmów.Wzrost czasu wykonywania może sprawiać wrażenie liniowego dlastosunkowo niedużych zbiorów danych wejściowych.Wystarczy jednak użyć tegosamego kodu do przetworzenia milionów rekordów, aby czas działania wydłużyłsię do tego stopnia, że wydajność całego systemu będzie nie do zaakceptowania. 198 u� Rozdział 6.Kiedy kodujemy&Jeśli testujemy procedurę sortującą, która operuje na losowych kluczach wej-ściowych, możemy być pozytywnie zaskoczeni czasem działania w razie napo-tkania już uporządkowanych danych.Pragmatyczni programiści starają się pa-miętać zarówno o podstawach teoretycznych, jak i ich wymiarze praktycznym.Po przeprowadzeniu wszystkich tych szacunków jedynym naprawdę istotnymwnioskiem jest szybkość naszego kodu wykonywanego w środowisku produkcyj-nym na prawdziwych danych2.W ten sposób dochodzimy do kolejnej wskazówki.WSKAZ�WKA NR 46Należy testować swoje szacunki.Jeśli uzyskanie precyzyjnych szacunków jest zbyt trudne, warto użyć mecha-nizmów profilowania kodu do określenia liczby wykonań poszczególnych kro-ków algorytmu i nanieść te wartości na wykres uwzględniający ilość danychwejściowych.Najlepsze nie zawsze jest najlepszePragmatyzm musimy wykazywać także na etapie doboru właściwych algoryt-mów najszybszy algorytm nie we wszystkich przypadkach jest najlepszy.Dla niewielkiego zbioru wejściowego proste sortowanie przez wstawianie będzierównie efektywne jak sortowanie szybkie, a jednocześnie będzie łatwiejsze dozaimplementowania i przetestowania.Warto też zachować daleko idącą ostroż-ność, jeśli interesujący algorytm wiąże się z dużymi kosztami na etapie ini-cjalizacji.W przypadku niedużych zbiorów wejściowych czas samej inicjalizacjimoże przekroczyć czas właściwego działania algorytmu (w takim przypadkunależy szukać innych rozwiązań).Ważne jest także unikanie pochopnych decyzji o optymalizacji.Zawsze wartoupewnić się, że interesujący nas algorytm rzeczywiście jest wąskim gardłem, za-nim zdecydujemy się poświęcić swój cenny czas na doskonalenie tego algorytmu.Pokrewne podrozdziałyl� Szacowanie w rozdziale 2.Wyzwanial� Każdy programista powinien wiedzieć, jak należy projektować i analizo-wać algorytmy.Robert Sedgewick napisał serię książek wprowadzającychte zagadnienia w wyjątkowo przejrzysty sposób ([Sed83, SF96, Sed92]2Podczas testowania algorytmów sortowania użytych na potrzeby ćwiczeń dla tego pod-rozdziału na komputerze Pentium z 64 MB pamięci operacyjnej autorzy wyczerpalidostępną pamięć fizyczną już przy sortowaniu siedmiu milionów liczb metodą sortowaniapozycyjnego.Kiedy algorytm sortowania zaczął korzystać z przestrzeni wymiany, jegowydajność uległa dodatkowemu, dramatycznemu pogorszeniu. Szybkość algorytmu t� 199i inne).Zachęcamy do włączenia którejś z tych pozycji do własnej biblio-teki oraz jej uważną lekturę.l� Czytelnicy, którzy szukają bardziej wyczerpujących materiałów na tentemat, powinni sięgnąć po książki Sztuka programowania Donalda Knu-tha, w których szczegółowo przeanalizowano najróżniejsze algorytmy[Knu97a, Knu97b, Knu98].l� W ćwiczeniu 34.przyjrzymy się problemowi sortowania tablic długich liczbcałkowitych.Jaki wpływ na szybkość działania algorytmu mają bardziejzłożone klucze? Jaki wpływ na łączną wydajność algorytmu mają kosz-towne operacje porównywania kluczy? Czy struktura klucza wpływa naefektywność algorytmów sortujących, czy też jeden algorytm zawsze jestnajszybszy?wiczenia34.Opracowaliśmy kilka prostych funkcji sortujących, których kod można po- Patrzodpowiedz 34.brać z naszej witryny internetowej (www.pragmaticprogrammer.com).Za-w dodatku B.chęcamy do uruchomienia tego kodu na różnych komputerach.Czy Twojewykresy pasują kształtem do oczekiwanych krzywych? Do jakich wnioskówmożna dojść na podstawie względnej szybkości testowych komputerów?Jaki wpływ na wyniki mają rozmaite ustawienia optymalizacji kompilato-rów? Czy algorytm sortowania pozycyjnego rzeczywiście jest liniowy?35.Poniższa funkcja wyświetla zawartość drzewa binarnego.Ile (w przybliżeniu) Patrzodpowiedz 35
[ Pobierz całość w formacie PDF ]
