Efektywność algorytmiczna

Nie mylić z optymalizacją, która jest omawiana w optymalizacja programu , optymalizacja kompilatora , optymalizacja pętli , optymalizacja kodu obiektowego itp.

W informatyce efektywność algorytmiczna jest właściwością algorytmu , która odnosi się do ilości zasobów obliczeniowych wykorzystywanych przez algorytm. Algorytm musi zostać przeanalizowany , aby określić wykorzystanie zasobów, a efektywność algorytmu można zmierzyć na podstawie wykorzystania różnych zasobów. Efektywność algorytmiczna może być traktowana jako analogiczna do produktywności inżynierskiej dla powtarzalnego lub ciągłego procesu.

Aby uzyskać maksymalną wydajność, pożądane jest zminimalizowanie zużycia zasobów. Jednak różnych zasobów, takich jak czasowa i przestrzenna , nie można porównywać bezpośrednio, więc to, który z dwóch algorytmów jest uważany za bardziej wydajny, często zależy od tego, która miara wydajności jest uważana za najważniejszą.

Na przykład sortowanie bąbelkowe i sortowanie czasowe to algorytmy sortowania listy elementów od najmniejszego do największego. Sortowanie bąbelkowe sortuje listę w proporcjonalnym do liczby elementów do kwadratu ( , notacja O ), ale ilości dodatkowej pamięci która jest względem ( Timsort sortuje listę w czasie liniowo do ilości pomnożonej przez jej logarytm) na długości listy ( wymagania dotyczące liniowe długości z listy ( ). Jeśli duże listy muszą być sortowane z dużą szybkością dla danej aplikacji, lepszym wyborem jest timsort; jeśli jednak ważniejsze jest zminimalizowanie zużycia pamięci przez sortowanie, lepszym wyborem jest sortowanie bąbelkowe.

Tło

Znaczenie wydajności w odniesieniu do czasu zostało podkreślone przez Adę Lovelace w 1843 r. w odniesieniu do mechanicznego silnika analitycznego Charlesa Babbage'a :

„W prawie każdym obliczeniu możliwa jest wielka różnorodność układów następstwa procesów, a na ich wybór dla celów silnika obliczeniowego muszą wpływać różne względy. Jednym z zasadniczych celów jest wybór takiego układu, który będzie dążył do zredukowania do minimum czasu niezbędnego do wykonania obliczeń”

Wczesne komputery elektroniczne miały zarówno ograniczoną prędkość , jak i ograniczoną pamięć o dostępie swobodnym . W związku z tym wymiana czasoprzestrzenna . Zadanie pamięci lub powolnego algorytmu zużywającego mało pamięci. Kompromis inżynierski polegał wówczas na zastosowaniu najszybszego algorytmu, który zmieściłby się w dostępnej pamięci.

Nowoczesne komputery są znacznie szybsze niż pierwsze komputery i mają znacznie większą ilość dostępnej pamięci ( gigabajty zamiast kilobajtów ). Niemniej jednak Donald Knuth podkreślił, że wydajność jest nadal ważnym czynnikiem:

„W uznanych dyscyplinach inżynierskich łatwo osiągalna poprawa o 12% nigdy nie jest uważana za marginalną i uważam, że ten sam punkt widzenia powinien dominować w inżynierii oprogramowania”

Przegląd

Algorytm jest uważany za wydajny, jeśli jego zużycie zasobów, znane również jako koszt obliczeniowy, jest na akceptowalnym poziomie lub poniżej niego. Z grubsza mówiąc, „akceptowalny” oznacza: będzie działać w rozsądnym czasie lub miejscu na dostępnym komputerze, zazwyczaj jako funkcja rozmiaru danych wejściowych. Od lat pięćdziesiątych XX wieku komputery odnotowały dramatyczny wzrost zarówno dostępnej mocy obliczeniowej, jak i dostępnej ilości pamięci, więc obecne akceptowalne poziomy byłyby nie do przyjęcia nawet 10 lat temu. W rzeczywistości, dzięki przybliżonemu podwajaniu mocy komputerów co 2 lata , zadania, które są akceptowalnie wydajne na nowoczesnych smartfonach i systemach wbudowanych, mogły być niedopuszczalnie nieefektywne dla serwerów przemysłowych 10 lat temu.

Producenci komputerów często wprowadzają nowe modele, często o wyższej wydajności . Koszty oprogramowania mogą być dość wysokie, więc w niektórych przypadkach najprostszym i najtańszym sposobem uzyskania wyższej wydajności może być po prostu zakup szybszego komputera, pod warunkiem, że jest on zgodny z istniejącym komputerem.

Istnieje wiele sposobów mierzenia zasobów wykorzystywanych przez algorytm: dwie najczęstsze miary to szybkość i użycie pamięci; inne miary mogą obejmować prędkość transmisji, tymczasowe użycie dysku, długoterminowe użycie dysku, zużycie energii, całkowity koszt posiadania , czas reakcji na bodźce zewnętrzne itp. Wiele z tych miar zależy od wielkości danych wejściowych do algorytmu, tj. ilość danych do przetworzenia. Mogą również zależeć od sposobu ułożenia danych; na przykład niektóre algorytmy sortowania działają słabo na danych, które są już posortowane lub posortowane w odwrotnej kolejności.

W praktyce istnieją inne czynniki, które mogą wpływać na wydajność algorytmu, takie jak wymagania dotyczące dokładności i/lub niezawodności. Jak wyszczególniono poniżej, sposób implementacji algorytmu może również mieć znaczący wpływ na rzeczywistą wydajność, chociaż wiele aspektów tego odnosi się do kwestii optymalizacji .

Analiza teoretyczna

W teoretycznej analizie algorytmów normalną praktyką jest szacowanie ich złożoności w sensie asymptotycznym. Najczęściej używaną notacją do opisania zużycia zasobów lub „złożoności” jest notacja Big O Donalda Knutha , reprezentująca złożoność algorytmu jako funkcję wielkości danych wejściowych. . Notacja dużego O jest asymptotyczną miarą złożoności funkcji, gdzie wymagany czas dla algorytmu jest proporcjonalny do pomijając wyrażenia niższego rzędu , przyczyniają się mniej niż wzrostu funkcji jako rośnie dowolnie duże . To oszacowanie może być mylące, gdy , ale generalnie jest wystarczająco dokładne, gdy jest jest asymptotyczna. Na przykład sortowanie bąbelkowe może być szybsze niż sortowanie przez scalanie, gdy ma być posortowanych tylko kilka elementów; jednak każda implementacja prawdopodobnie spełni wymagania dotyczące wydajności dla małej listy. Zazwyczaj programiści są zainteresowani algorytmami, które efektywnie skalują się do dużych rozmiarów danych wejściowych, a sortowanie przez scalanie jest preferowane zamiast sortowania bąbelkowego w przypadku list o długości spotykanych w większości programów intensywnie korzystających z danych.

Niektóre przykłady notacji Big O zastosowanej do asymptotycznej złożoności czasowej algorytmów obejmują:

Notacja Nazwa Przykłady
stały Znalezienie mediany z posortowanej listy pomiarów; Korzystanie z tabeli przeglądowej o stałym rozmiarze ; Używanie odpowiedniej funkcji skrótu do wyszukiwania elementu.
logarytmiczny Znajdowanie elementu w posortowanej tablicy za pomocą wyszukiwania binarnego lub zrównoważonego drzewa wyszukiwania oraz wszystkich operacji na stercie dwumianowej .
liniowy Znalezienie elementu na nieposortowanej liście lub zniekształconym drzewie (najgorszy przypadek) lub w nieposortowanej tablicy; Dodawanie dwóch n -bitowych liczb całkowitych metodą ripple carry .
liniowej , logliniowej lub quasiliniowej Wykonywanie szybkiej transformaty Fouriera ; sortowanie sterty , sortowanie szybkie ( przypadek najlepszy i średni ) lub sortowanie przez scalanie
kwadratowy Mnożenie dwóch n -cyfrowych liczb za pomocą prostego algorytmu ; sortowanie bąbelkowe (najgorszy przypadek lub naiwna implementacja), sortowanie skorupowe , sortowanie szybkie ( najgorszy przypadek ), sortowanie przez wybór lub sortowanie przez wstawianie
wykładniczy Znalezienie optymalnego (nieprzybliżonego ) rozwiązania problemu komiwojażera z wykorzystaniem programowania dynamicznego ; określenie, czy dwie instrukcje logiczne są równoważne przy użyciu wyszukiwania siłowego

Benchmarking: pomiar wydajności

W przypadku nowych wersji oprogramowania lub w celu zapewnienia porównań z konkurencyjnymi systemami czasami stosuje się testy porównawcze , które pomagają w ocenie względnej wydajności algorytmów. Na przykład, jeśli zostanie stworzony nowy algorytm sortowania , można go porównać z jego poprzednikami, aby upewnić się, że przynajmniej jest wydajny jak poprzednio ze znanymi danymi, biorąc pod uwagę wszelkie ulepszenia funkcjonalne. Benchmarki mogą być wykorzystywane przez klientów podczas porównywania różnych produktów alternatywnych dostawców w celu oszacowania, który produkt najlepiej spełni ich specyficzne wymagania pod względem funkcjonalności i wydajności. Na przykład w komputerów mainframe niektóre zastrzeżone produkty sortujące niezależnych firm programistycznych, takie jak Syncsort , konkurują o szybkość z produktami głównych dostawców, takich jak IBM .

Niektóre testy porównawcze umożliwiają na przykład analizę porównującą względną szybkość różnych języków kompilowanych i interpretowanych, a gra porównawcza języka komputerowego porównuje wydajność implementacji typowych problemów programistycznych w kilku językach programowania.

Nawet tworzenie testów porównawczych „ zrób to sam ” może wykazać względną wydajność różnych języków programowania przy użyciu różnych kryteriów określonych przez użytkownika. Jest to dość proste, jak pokazuje na przykładzie „Podsumowanie występów w dziewięciu językach” autorstwa Christophera W. Cowell-Shaha.

Obawy dotyczące wdrażania

Kwestie implementacyjne mogą również mieć wpływ na wydajność, takie jak wybór języka programowania lub sposób, w jaki algorytm jest faktycznie kodowany, lub wybór kompilatora dla określonego języka, lub stosowane opcje kompilacji , a nawet sposób obsługi używany system . W wielu przypadkach język zaimplementowany przez tłumacza może być znacznie wolniejszy niż język zaimplementowany przez kompilator. Zobacz artykuły na temat kompilacji just-in-time i języków interpretowanych .

Istnieją inne czynniki, które mogą wpływać na kwestie czasu lub przestrzeni, ale które mogą być poza kontrolą programisty; obejmują one wyrównanie danych , ziarnistość danych , lokalizację pamięci podręcznej , spójność pamięci podręcznej , wyrzucanie elementów bezużytecznych , równoległość na poziomie instrukcji , wielowątkowość (na poziomie sprzętu lub oprogramowania), jednoczesną wielozadaniowość i wywołania podprogramów .

Niektóre procesory mają możliwości przetwarzania wektorowego , co pozwala pojedynczej instrukcji na działanie na wielu operandach ; korzystanie z tych możliwości może być łatwe lub trudne dla programisty lub kompilatora. Algorytmy przeznaczone do przetwarzania sekwencyjnego mogą wymagać całkowitego przeprojektowania w celu wykorzystania przetwarzania równoległego lub mogą być łatwo rekonfigurowane. Wraz ze obliczeń równoległych i rozproszonych pod koniec 2010 roku, coraz więcej inwestuje się w wydajne interfejsy API wysokiego poziomu dla równoległych i rozproszonych systemów obliczeniowych, takich jak CUDA , TensorFlow , Hadoop , OpenMP i MPI .

Innym problemem, który może pojawić się podczas programowania, jest to, że procesory kompatybilne z tym samym zestawem instrukcji (takie jak x86-64 lub ARM ) mogą implementować instrukcje na różne sposoby, tak że instrukcje, które są stosunkowo szybkie w niektórych modelach, mogą być stosunkowo wolne w innych modelach . To często stanowi wyzwanie dla optymalizacji kompilatorów , które muszą mieć dużą wiedzę na temat konkretnego procesora i innego sprzętu dostępnego w miejscu docelowym kompilacji, aby jak najlepiej zoptymalizować program pod kątem wydajności. W skrajnym przypadku kompilator może zostać zmuszony do emulacji instrukcji nieobsługiwanych na docelowej platformie kompilacji, zmuszając go do wygenerowania kodu lub połączenia wywołania biblioteki zewnętrznej w celu uzyskania wyniku, który w innym przypadku byłby nieobliczalny na tej platformie, nawet jeśli jest obsługiwany natywnie i bardziej wydajne sprzętowo na innych platformach. Dzieje się tak często w systemach wbudowanych w odniesieniu do arytmetyki zmiennoprzecinkowej , gdzie małe mikrokontrolery o niskim poborze mocy często nie mają sprzętowego wsparcia dla arytmetyki zmiennoprzecinkowej, a zatem wymagają kosztownych obliczeniowo procedur programowych do wykonywania obliczeń zmiennoprzecinkowych.

Miary zużycia zasobów

Miary są zwykle wyrażane jako funkcja wielkości danych wejściowych .

Dwa najczęstsze środki to:

  • Czas : ile czasu zajmuje wykonanie algorytmu?
  • Przestrzeń : ile pamięci roboczej (zwykle RAM) potrzebuje algorytm? Ma to dwa aspekty: ilość pamięci potrzebnej kodowi (wykorzystanie przestrzeni pomocniczej) oraz ilość pamięci potrzebnej na dane, na których działa kod (wewnętrzne wykorzystanie przestrzeni).

W przypadku komputerów zasilanych baterią (np. laptopy i smartfony ) lub w przypadku bardzo długich/dużych obliczeń (np. superkomputery ) inne interesujące miary to:

  • Bezpośredni pobór mocy : energia potrzebna bezpośrednio do obsługi komputera.
  • Pośrednie zużycie energii : moc potrzebna do chłodzenia, oświetlenia itp.

Od 2018 r. zużycie energii rośnie jako ważny wskaźnik dla zadań obliczeniowych wszystkich typów i we wszystkich skalach, od wbudowanych urządzeń Internetu rzeczy, przez urządzenia system-on-chip, po farmy serwerów . Tendencja ta jest często określana mianem zielonej informatyki .

W niektórych przypadkach istotne mogą być również mniej powszechne miary wydajności obliczeniowej:

  • Rozmiar transmisji : przepustowość może być czynnikiem ograniczającym. Kompresję danych można wykorzystać do zmniejszenia ilości przesyłanych danych. Wyświetlenie obrazu lub obrazu (np. logo Google ) może spowodować przesłanie dziesiątek tysięcy bajtów (w tym przypadku 48 KB) w porównaniu z przesłaniem sześciu bajtów tekstu „Google”. Jest to ważne w przypadku zadań obliczeniowych związanych z wejściem/wyjściem .
  • Miejsce zewnętrzne : potrzebne miejsce na dysku lub innym zewnętrznym urządzeniu pamięci; może to być tymczasowe przechowywanie podczas wykonywania algorytmu lub może to być przechowywanie długoterminowe, które należy przenieść do wykorzystania w przyszłości.
  • Czas odpowiedzi ( opóźnienie ): jest to szczególnie istotne w aplikacjach działających w czasie rzeczywistym, kiedy system komputerowy musi szybko reagować na jakieś zewnętrzne zdarzenia .
  • Całkowity koszt posiadania : szczególnie, jeśli komputer jest przeznaczony do jednego konkretnego algorytmu.

Czas

Teoria

Przeanalizuj algorytm, zwykle używając analizy złożoności czasowej , aby uzyskać oszacowanie czasu działania w funkcji rozmiaru danych wejściowych. Wynik jest zwykle wyrażany za pomocą notacji Big O. Jest to przydatne do porównywania algorytmów, zwłaszcza gdy ma być przetwarzana duża ilość danych. Potrzebne są bardziej szczegółowe szacunki, aby porównać wydajność algorytmu, gdy ilość danych jest niewielka, chociaż prawdopodobnie będzie to miało mniejsze znaczenie. algorytmów zawierających przetwarzanie równoległe może być trudniejsza .

Ćwiczyć

Użyj testu porównawczego , aby określić czas użycia algorytmu. Wiele języków programowania ma dostępną funkcję, która zapewnia wykorzystanie czasu procesora . W przypadku długotrwałych algorytmów czas, który upłynął, może być również interesujący. Wyniki należy generalnie uśrednić z kilku testów.

Profilowanie oparte na uruchamianiu może być bardzo wrażliwe na konfigurację sprzętową i możliwość jednoczesnego uruchamiania innych programów lub zadań w środowisku wieloprocesorowym i wieloprogramowym .

Ten rodzaj testu zależy również w dużej mierze od wyboru konkretnego języka programowania, kompilatora i opcji kompilatora, więc porównywane algorytmy muszą być zaimplementowane w tych samych warunkach.

Przestrzeń

Ta sekcja dotyczy wykorzystania zasobów pamięci ( rejestry , pamięć podręczna , pamięć RAM , pamięć wirtualna , pamięć pomocnicza ) podczas wykonywania algorytmu. Jeśli chodzi o powyższą analizę czasu, przeanalizuj algorytm, zwykle używając analizy złożoności przestrzeni , aby uzyskać oszacowanie potrzebnej pamięci czasu wykonywania jako funkcji wielkości danych wejściowych. Wynik jest zwykle wyrażany za pomocą notacji Big O.

Należy wziąć pod uwagę maksymalnie cztery aspekty wykorzystania pamięci:

Wczesne komputery elektroniczne i wczesne komputery domowe miały stosunkowo niewielką ilość pamięci roboczej. Na przykład elektroniczny kalkulator automatycznego przechowywania opóźnień (EDSAC) z 1949 r. Miał maksymalną pamięć roboczą wynoszącą 1024 17-bitowych słów, podczas gdy Sinclair ZX80 z 1980 r . Był początkowo wyposażony w 1024 8-bitowych bajtów pamięci roboczej. Pod koniec 2010 roku komputery osobiste miały zwykle od 4 do 32 GB pamięci RAM, co stanowi wzrost o ponad 300 milionów razy więcej pamięci.

Hierarchia buforowania i pamięci

Dalsze informacje: Hierarchia pamięci

Obecne komputery mogą mieć stosunkowo duże ilości pamięci (prawdopodobnie gigabajty), więc konieczność wciśnięcia algorytmu do ograniczonej ilości pamięci jest znacznie mniejszym problemem niż kiedyś. Ale obecność czterech różnych kategorii pamięci może być znacząca:

Algorytm, którego zapotrzebowanie na pamięć zmieści się w pamięci podręcznej, będzie znacznie szybszy niż algorytm mieszczący się w pamięci głównej, co z kolei będzie znacznie szybsze niż algorytm, który musi uciekać się do pamięci wirtualnej. Z tego powodu zasady zastępowania pamięci podręcznej są niezwykle ważne dla obliczeń o wysokiej wydajności, podobnie jak programowanie uwzględniające pamięć podręczną i wyrównywanie danych . Aby jeszcze bardziej skomplikować problem, niektóre systemy mają do trzech poziomów pamięci podręcznej, z różnymi efektywnymi prędkościami. Różne systemy będą miały różne ilości tych różnych typów pamięci, więc wpływ potrzeb pamięci algorytmu może się znacznie różnić w zależności od systemu.

We wczesnych latach obliczeń elektronicznych, jeśli algorytm i jego dane nie mieściły się w pamięci głównej, nie można było użyć algorytmu. Obecnie użycie pamięci wirtualnej wydaje się zapewniać dużo pamięci, ale kosztem wydajności. Jeśli algorytm i jego dane zmieszczą się w pamięci podręcznej, to można uzyskać bardzo dużą prędkość; w tym przypadku minimalizacja przestrzeni pomoże również zminimalizować czas. Nazywa się to zasadą lokalności i można ją podzielić na lokalność odniesienia , lokalność przestrzenną i lokalność czasową . Algorytm, który nie zmieści się całkowicie w pamięci podręcznej, ale który wykazuje lokalność odniesienia, może działać dość dobrze.

Krytyka obecnego stanu programowania

Wydajność

oprogramowania zmniejsza się o połowę co 18 miesięcy, rekompensując to prawem Moore'a

. zestawy dają duże możliwości dla lepszego oprogramowania i algorytmów: Zmniejszenie liczby operacji z N × N do N × log (N) ma dramatyczny efekt, gdy N jest duże… dla N = 30 miliardów ta zmiana wynosi nawet 50 lat ulepszeń technologii.

  • Autor oprogramowania Adam N. Rosenburg na swoim blogu „ Awaria komputera cyfrowego ” opisał obecny stan programowania jako zbliżający się do „horyzontu zdarzeń oprogramowania” (nawiązując do fikcyjnego „ horyzontu zdarzeń obuwia ” opisanego przez Douglasa Adamsa w jego Książka Autostopem przez Galaktykę ). Szacuje, że od lat 80. XX wieku nastąpił spadek produktywności lub „99,99999 procent jego zdolności do dostarczania towarów” o 70 dB - „Kiedy Arthur C. Clarke porównał rzeczywistość komputerową w 2001 r. Do komputera HAL 9000 w jego book 2001: A Space Odyssey , zwrócił uwagę, jak cudownie małe i potężne były komputery, ale jak rozczarowujące stało się programowanie komputerowe”.

Konkursy na najlepsze algorytmy

Następujące konkursy zapraszają do zgłaszania najlepszych algorytmów opartych na arbitralnych kryteriach ustalonych przez sędziów:

Zobacz też

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Algorithmic_efficiency&oldid=1141448631 ”