Wydajność algorytmiczna - Algorithmic efficiency
W informatyce , wydajność oprogramowania jest właściwością algorytmu , która odnosi się do ilości zasobów obliczeniowych wykorzystywanych przez algorytm. Algorytm należy przeanalizować, aby określić jego wykorzystanie zasobów, a wydajność algorytmu można zmierzyć na podstawie wykorzystania różnych zasobów. Wydajność algorytmiczną można uznać za analogiczną do produktywności inżynierskiej w przypadku powtarzającego się lub ciągłego procesu.
Dla maksymalnej wydajności chcemy zminimalizować zużycie zasobów. Jednak różnych zasobów, takich jak złożoność 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 timsort są algorytmami sortowania listy elementów od najmniejszego do największego. Sortowanie bąbelkowe sortuje listę w czasie proporcjonalnie do liczby elementów do kwadratu ( , patrz notacja Big O ), ale wymaga tylko niewielkiej ilości dodatkowej pamięci, która jest stała w odniesieniu do długości listy ( ). Timsort sortuje listę liniowo w czasie (proporcjonalnie do ilości pomnożonej przez jej logarytm) w długości listy ( ), ale ma wymaganie przestrzenne liniowo w długości listy ( ). Jeśli duże listy muszą być sortowane z dużą szybkością dla danej aplikacji, timsort jest lepszym wyborem; jednak jeśli minimalizacja śladu pamięci związanego z sortowaniem jest ważniejsza, lepszym wyborem jest sortowanie bąbelkowe.
tło
Znaczenie wydajności w odniesieniu do czasu zostało podkreślone przez Adę Lovelace w 1843 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 różne względy muszą wpływać na wybór spośród nich dla celów silnika obliczeniowego. Jednym z zasadniczych celów jest wybór takiego układu, który będzie dążył do zredukowania do minimalny czas potrzebny na wykonanie kalkulacji"
Wczesne komputery elektroniczne były poważnie ograniczone zarówno szybkością działania, jak i ilością dostępnej pamięci. W niektórych przypadkach zdano sobie sprawę, że istnieje kompromis czasowo-przestrzenny , w którym zadanie można obsłużyć albo za pomocą szybkiego algorytmu, który zużywa dość dużo pamięci roboczej, albo za pomocą wolniejszego algorytmu, który zużywa bardzo mało pamięci roboczej . Inżynieryjny kompromis polegał wówczas na użyciu najszybszego algorytmu, który zmieściłby się w dostępnej pamięci.
Nowoczesne komputery są znacznie szybsze niż wczesne 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, zwane również kosztem obliczeniowym, jest na lub poniżej pewnego akceptowalnego poziomu. Z grubsza mówiąc, „dopuszczalne” oznacza: będzie działać w rozsądnym czasie lub przestrzeni na dostępnym komputerze, zazwyczaj w zależności od rozmiaru danych wejściowych. Od lat pięćdziesiątych komputery odnotowały dramatyczny wzrost zarówno dostępnej mocy obliczeniowej, jak i dostępnej ilości pamięci, więc obecne dopuszczalne poziomy byłyby nie do przyjęcia nawet 10 lat temu. W rzeczywistości, dzięki przybliżonemu podwojeniu mocy komputera co 2 lata , zadania, które są akceptowalnie wydajne na nowoczesnych smartfonach i systemach wbudowanych, mogły być niedopuszczalnie nieefektywne w przypadku 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 na uzyskanie wyższej wydajności może być zakup szybszego komputera, pod warunkiem, że jest on kompatybilny z istniejącym komputerem.
Istnieje wiele sposobów pomiaru zasobów wykorzystywanych przez algorytm: dwie najczęstsze miary to szybkość i zużycie pamięci; inne miary mogą obejmować prędkość transmisji, tymczasowe wykorzystanie dysku, długoterminowe wykorzystanie 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 uporządkowania 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 opisano poniżej, sposób implementacji algorytmu może również mieć znaczący wpływ na rzeczywistą wydajność, chociaż wiele aspektów tego dotyczy kwestii optymalizacji .
Analiza teoretyczna
W teoretycznej analizie algorytmów normalną praktyką jest szacowanie ich złożoności w sensie asymptotycznym. Najczęściej używanym do opisania notacja zużycie zasobów lub „złożoność” jest Donald Knuth „s Big O notacja , reprezentujący złożoność algorytmu w funkcji wielkości wejściowych . Notacja Big O jest asymptotyczną miarą złożoności funkcji, gdzie z grubsza oznacza, że wymagany czas dla algorytmu jest proporcjonalny do , pomijając terminy niższego rzędu, które przyczyniają się mniej niż do wzrostu funkcji, gdy rośnie arbitralnie duża . To oszacowanie może być mylące, gdy jest małe, ale generalnie jest wystarczająco dokładne, gdy jest duże, ponieważ notacja 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 interesuje algorytmów że skala skutecznie dużych rozmiarach wejściowych i scalania sortowania jest korzystniejsze niż bańka sortowania list długości spotykanych w większości programów intensywnie przetwarzających dane.
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, a także wszystkich operacji na stercie dwumianowej . | |
liniowy | Znalezienie elementu na nieposortowanej liście lub zniekształconym drzewie (najgorszy przypadek) lub w nieposortowanej tablicy; Dodanie dwóch n- bitowych liczb całkowitych przez ripple carry . | |
linearithmic , loglinear lub quasilinear | Wykonywanie szybkiej transformacji Fouriera ; sortowanie sterty , sortowanie szybkie ( najlepszy i przeciętny przypadek ) lub sortowanie przez scalanie | |
kwadratowy | Mnożenie dwóch liczb n- cyfrowych przez prosty algorytm ; sortowanie bąbelkowe (najgorszy przypadek lub naiwna implementacja), sortowanie powłokowe , sortowanie szybkie ( najgorszy przypadek ), sortowanie przez wybór lub sortowanie przez wstawianie | |
wykładniczy | Znalezienie optymalnego (nie przybliżonego ) rozwiązania problemu komiwojażera z wykorzystaniem programowania dynamicznego ; określenie, czy dwa wyrażenia logiczne są równoważne przy użyciu wyszukiwania brute-force |
Analiza porównawcza: pomiar wydajności
W przypadku nowych wersji oprogramowania lub w celu porównania z konkurencyjnymi systemami czasami stosuje się benchmarki , które pomagają w ocenie względnej wydajności algorytmów. Jeśli na przykład zostanie utworzony nowy algorytm sortowania , można go porównać z jego poprzednikami, aby upewnić się, że jest przynajmniej wydajny jak poprzednio ze znanymi danymi, z uwzględnieniem wszelkich ulepszeń funkcjonalnych. Benchmarki mogą być wykorzystywane przez klientów podczas porównywania różnych produktów od alternatywnych dostawców w celu oszacowania, który produkt będzie najlepiej odpowiadał ich konkretnym wymaganiom pod względem funkcjonalności i wydajności. Na przykład, w mainframe światowych niektórych zastrzeżonych sortowania produktów pochodzących z niezależnych producentów oprogramowania, takich jak Syncsort konkurować z produktami z głównych dostawców takich jak IBM dla prędkości.
Niektóre testy porównawcze dają możliwość stworzenia analizy porównującej względną szybkość różnych kompilowanych i interpretowanych języków, na przykład, a The Computer Language Benchmarks Game porównuje wydajność implementacji typowych problemów programistycznych w kilku językach programowania.
Nawet tworzenie testów porównawczych typu „ zrób to sam ” może zademonstrować 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 wydajności w dziewięciu językach” Christophera W. Cowell-Shah.
Obawy wdrożeniowe
Na wydajność mogą mieć również wpływ kwestie implementacyjne, takie jak wybór języka programowania, czy sposób, w jaki algorytm jest faktycznie zakodowany, czy wybór kompilatora dla danego języka, czy zastosowane opcje kompilacji , a nawet sposób działania. używany system . W wielu przypadkach język zaimplementowany przez interpreter 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 , szczegółowości danych , cache lokalizację , spójności pamięci podręcznej , zbieranie śmieci , instrukcja poziomu równoległości , wielowątkowości (albo w sprzęcie lub poziomu oprogramowania), jednoczesną wielozadaniowość i podprogramów połączeń.
Niektóre procesory mają możliwości przetwarzania wektorowego , które pozwalają pojedynczej instrukcji operować na wielu operandach ; może, ale nie musi być łatwe dla programisty lub kompilatora do korzystania z tych możliwości. Algorytmy zaprojektowane do przetwarzania sekwencyjnego mogą wymagać całkowitego przeprojektowania w celu wykorzystania przetwarzania równoległego lub mogą być łatwo przekonfigurowane. Wraz ze wzrostem znaczenia obliczeń równoległych i rozproszonych pod koniec 2010 roku, coraz więcej inwestycji poczyniono 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ę w programowaniu, jest to, że procesory kompatybilne z tym samym zestawem instrukcji (takie jak x86-64 lub ARM ) mogą implementować instrukcję na różne sposoby, tak że instrukcje, które są stosunkowo szybkie w niektórych modelach, mogą być stosunkowo wolne w innych modelach . Często stanowi to wyzwanie dla optymalizacji kompilatorów , które muszą mieć dużą wiedzę na temat konkretnego procesora i innego sprzętu dostępnego w celu kompilacji, aby jak najlepiej zoptymalizować program pod kątem wydajności. W skrajnym przypadku kompilator może być zmuszony do emulowania 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 inny sposób byłby nieobliczalny na tej platformie, nawet jeśli jest on natywnie obsługiwany i bardziej wydajny sprzętowo na innych platformach. Dzieje się tak często w systemach wbudowanych w odniesieniu do arytmetyki zmiennoprzecinkowej , gdzie małe mikrokontrolery o małej mocy często nie obsługują sprzętowej arytmetyki zmiennoprzecinkowej, a zatem wymagają obliczeniowo kosztownych procedur programowych do wykonywania obliczeń zmiennoprzecinkowych.
Miary wykorzystania zasobów
Miary są zwykle wyrażane jako funkcja wielkości danych wejściowych .
Dwa najczęstsze środki to:
- Czas : jak długo trwa algorytm?
- Przestrzeń : ile pamięci roboczej (zwykle RAM) potrzebuje algorytm? Ma to dwa aspekty: ilość pamięci potrzebnej do kodu (wykorzystanie przestrzeni pomocniczej) oraz ilość pamięci potrzebnej do danych, na których działa kod (wewnętrzne wykorzystanie przestrzeni).
W przypadku komputerów zasilanych baterią (np. laptopy i smartfony ) lub bardzo długich/dużych obliczeń (np. superkomputery ) innymi miarami zainteresowania są:
- Bezpośredni pobór mocy : moc potrzebna bezpośrednio do obsługi komputera.
- Pośredni pobór mocy : moc potrzebna do chłodzenia, oświetlenia itp.
Od 2018 r. zużycie energii rośnie jako ważny wskaźnik dla zadań obliczeniowych wszelkiego rodzaju i we wszystkich skalach, od wbudowanych urządzeń Internetu rzeczy, przez urządzenia typu system-on-chip , po farmy serwerów . Ten trend jest często określany jako zielone przetwarzanie .
W niektórych przypadkach istotne mogą być również mniej powszechne miary wydajności obliczeniowej:
- Rozmiar transmisji : przepustowość może być czynnikiem ograniczającym. Kompresja danych może służyć do zmniejszenia ilości przesyłanych danych. Wyświetlenie obrazka lub obrazu (np. logo Google ) może skutkować przesłaniem dziesiątek tysięcy bajtów (w tym przypadku 48K) w porównaniu z przesłaniem sześciu bajtów dla tekstu „Google”. Jest to ważne w przypadku zadań związanych z przetwarzaniem we/wy .
- Przestrzeń zewnętrzna : wymagana przestrzeń na dysku lub innym urządzeniu pamięci zewnętrznej; może to dotyczyć tymczasowego przechowywania podczas wykonywania algorytmu lub przechowywania długoterminowego, które należy przenieść do późniejszego wykorzystania.
- Czas odpowiedzi ( opóźnienie ): jest to szczególnie istotne w przypadku aplikacji czasu rzeczywistego, gdy system komputerowy musi szybko reagować na jakieś zdarzenie zewnętrzne .
- Całkowity koszt posiadania : szczególnie jeśli komputer jest dedykowany do jednego konkretnego algorytmu.
Czas
Teoria
Przeanalizuj algorytm, zwykle używając analizy złożoności czasowej, aby uzyskać oszacowanie czasu pracy 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 zostać przetworzona duża ilość danych. Bardziej szczegółowe szacunki są potrzebne do porównania wydajności algorytmu, gdy ilość danych jest niewielka, chociaż prawdopodobnie ma to mniejsze znaczenie. Algorytmy zawierające przetwarzanie równoległe mogą być trudniejsze do analizy .
Ćwiczyć
Użyj benchmarku, aby określić czas użycia algorytmu. Wiele języków programowania ma dostępną funkcję, która zapewnia wykorzystanie czasu procesora . W przypadku algorytmów długoterminowych interesujący może być również czas, który upłynął. Wyniki powinny być generalnie uśredniane z kilku testów.
Profilowanie oparte na uruchomieniu może być bardzo wrażliwe na konfigurację sprzętu i możliwość jednoczesnego działania innych programów lub zadań w środowisku wieloprocesowym i wieloprogramowym .
Ten rodzaj testu zależy również w dużym stopniu 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 ( rejestrów , pamięci podręcznej , pamięci RAM , pamięci wirtualnej , pamięci wtórny ), podczas gdy algorytm jest wykonywany. Jeśli chodzi o powyższą analizę czasową, przeanalizuj algorytm, zwykle używając analizy złożoności przestrzeni, aby uzyskać oszacowanie pamięci czasu wykonywania potrzebnej jako funkcja jako rozmiar danych wejściowych. Wynik jest zwykle wyrażany za pomocą notacji Big O .
Należy wziąć pod uwagę maksymalnie cztery aspekty wykorzystania pamięci:
- Ilość pamięci potrzebnej do przechowywania kodu algorytmu.
- Ilość pamięci potrzebnej na dane wejściowe .
- Ilość pamięci potrzebnej na dowolne dane wyjściowe .
- Niektóre algorytmy, takie jak sortowanie, często zmieniają kolejność danych wejściowych i nie wymagają dodatkowego miejsca na dane wyjściowe. Ta właściwość jest określana jako operacja „ w miejscu ”.
- Ilość pamięci potrzebnej jako przestrzeń robocza podczas obliczeń.
- Obejmuje to zmienne lokalne i wszelkie miejsca na stosie potrzebne przez procedury wywoływane podczas obliczeń; ta przestrzeń stosu może być istotna dla algorytmów wykorzystujących techniki rekurencyjne .
Wczesne komputery elektroniczne i wczesne komputery domowe miały stosunkowo niewielką ilość pamięci roboczej. Na przykład elektroniczny kalkulator z opóźnieniem elektronicznym (EDSAC) z 1949 r. miał maksymalną pamięć roboczą 1024 17-bitowych słów, podczas gdy Sinclair ZX80 z 1980 r. miał początkowo 1024 8-bitowe bajty pamięci roboczej. Pod koniec 2010 roku komputery osobiste miały zwykle od 4 do 32 GB pamięci RAM, co stanowi ponad 300 milionów razy więcej pamięci.
Buforowanie i hierarchia pamięci
Obecne komputery mogą mieć stosunkowo duże ilości pamięci (prawdopodobnie gigabajty), więc konieczność ściśnięcia algorytmu w ograniczonej ilości pamięci jest znacznie mniejszym problemem niż kiedyś. Ale obecność czterech różnych kategorii pamięci może być znacząca:
- Rejestry procesora , najszybsza z technologii pamięci komputerowych z najmniejszą ilością miejsca do przechowywania. Większość bezpośrednich obliczeń na nowoczesnych komputerach odbywa się z operandami źródłowymi i docelowymi w rejestrach, zanim zostaną zaktualizowane do pamięci podręcznej, pamięci głównej i pamięci wirtualnej, jeśli zajdzie taka potrzeba. W rdzeniu procesora są zazwyczaj dostępne rejestry rzędu setek bajtów lub mniej, chociaż plik rejestru może zawierać więcej rejestrów fizycznych niż rejestrów architektonicznych zdefiniowanych w architekturze zestawu instrukcji.
- Pamięć podręczna to druga najszybsza i druga najmniejsza pamięć dostępna w hierarchii pamięci. Pamięć podręczna jest obecna w procesorach, procesorach graficznych, dyskach twardych i zewnętrznych urządzeniach peryferyjnych i zazwyczaj jest zaimplementowana w statycznej pamięci RAM . Pamięć podręczna jest wielopoziomowa ; niższe poziomy są większe, wolniejsze i zazwyczaj dzielone między rdzeniami procesorów w procesorach wielordzeniowych . Aby przetworzyć operandy w pamięci podręcznej, jednostka przetwarzająca musi pobrać dane z pamięci podręcznej, wykonać operację na rejestrach i zapisać dane z powrotem do pamięci podręcznej. Działa to z prędkością porównywalną (około 2-10 razy wolniejszą) z jednostką arytmetyczno-logiczną procesora lub GPU lub jednostką zmiennoprzecinkową, jeśli znajduje się w pamięci podręcznej L1 . Jest około 10 razy wolniejszy w przypadku braku pamięci podręcznej L1 i musi zostać pobrany i zapisany w pamięci podręcznej L2 , a kolejne 10 razy wolniejszy w przypadku braku pamięci podręcznej L2 i musi być pobrany z pamięci podręcznej L3 , jeśli teraźniejszość.
- Główna pamięć fizyczna jest najczęściej implementowana w dynamicznej pamięci RAM (DRAM). Główna pamięć jest znacznie większa (zazwyczaj gigabajtów w porównaniu do ≈8 megabajtów ) niż pamięć podręczna procesora L3, z opóźnieniami odczytu i zapisu zwykle 10-100 razy wolniejszymi. Od 2018 r. pamięć RAM jest coraz częściej wdrażana na chipach procesorów, jako pamięć CPU lub GPU .
- Pamięć wirtualna jest najczęściej implementowana w postaci dodatkowej pamięci masowej, takiej jak dysk twardy , i jest rozszerzeniem hierarchii pamięci, która ma znacznie większą przestrzeń dyskową, ale znacznie większe opóźnienie, zwykle około 1000 razy wolniejsze niż brak pamięci podręcznej dla wartości w pamięci RAM . Chociaż pierwotnie motywowano ją do stworzenia wrażenia większej ilości dostępnej pamięci niż była naprawdę dostępna, pamięć wirtualna jest ważniejsza we współczesnym użyciu ze względu na kompromis czasowo-przestrzenny i umożliwia korzystanie z maszyn wirtualnych . Braki w pamięci podręcznej pamięci głównej są nazywane błędami stron i powodują ogromne spadki wydajności programów.
Algorytm, którego pamięć potrzebuje, zmieści się w pamięci podręcznej, będzie znacznie szybszy niż algorytm, który zmieści się w pamięci głównej, co z kolei będzie znacznie szybsze niż algorytm, który musi odwoływać 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 o różnych efektywnych szybkościach. Różne systemy będą miały różne ilości tych różnych typów pamięci, więc efekt zapotrzebowania na pamięć algorytmu może się znacznie różnić w zależności od systemu.
We wczesnych dniach obliczeń elektronicznych, jeśli algorytm i jego dane nie mieściły się w pamięci głównej, to algorytm nie mógł być użyty. Obecnie wydaje się, że użycie pamięci wirtualnej zapewnia dużo pamięci, ale kosztem wydajności. Jeśli algorytm i jego dane zmieszczą się w pamięci podręcznej, 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 wykazuje lokalizację odniesienia, może działać dość dobrze.
Krytyka obecnego stanu programowania
- David May FRS do brytyjskiego informatykiem i obecnie profesor z informatyki na Uniwersytecie w Bristolu oraz założyciel i CTO z XMOS Semiconductor uważa jeden z problemów jest to, że istnieje zależność od prawa Moore'a rozwiązania nieefektywności. Wysunął „alternatywę” do prawa Moore'a (prawo Maya ) stwierdzające w następujący sposób:
Wydajność oprogramowania zmniejsza się o połowę co 18 miesięcy, rekompensując prawo Moore'a
- W maju stwierdza:
W wszechobecnych systemach zmniejszenie o połowę wykonywanych instrukcji może podwoić żywotność baterii, a duże zbiory danych dają duże możliwości lepszego oprogramowania i algorytmów: Zmniejszenie liczby operacji z N x N do N x log(N) ma dramatyczny efekt, gdy N jest duże ... dla N = 30 miliardów ta zmiana jest tak dobra, jak 50 lat ulepszeń technologicznych.
- Autor oprogramowania Adam N. Rosenburg w 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ń butów ” opisanego przez Douglasa Adamsa w jego Przewodnik Autostopowicza po Galaktyce ). Szacuje, że od lat 80. XX wieku nastąpiła utrata czynnika wydajności o 70 dB, czyli „99,99999% zdolności do dostarczania towarów” – „kiedy Arthur C. Clarke porównał rzeczywistość komputerów w 2001 r. z komputerem HAL 9000 w swoim książki 2001: A Space Odyssey , zwrócił uwagę, jak cudownie małe i potężne są komputery, ale jak rozczarowujące stało się programowanie komputerowe”.
Konkursy na najlepsze algorytmy
Poniższe konkursy zapraszają zgłoszenia najlepszych algorytmów na podstawie arbitralnych kryteriów ustalonych przez sędziów:
Zobacz też
- Analiza algorytmów — jak określić zasoby potrzebne algorytmowi
- Kodowanie arytmetyczne — forma kodowania entropijnego o zmiennej długości w celu wydajnej kompresji danych
- Tablica asocjacyjna — struktura danych, która może być bardziej wydajna przy użyciu drzew Patricia lub tablic Judy
- Benchmark — metoda pomiaru porównawczych czasów wykonania w określonych przypadkach
- Najlepszy, najgorszy i średni przypadek — rozważania dotyczące szacowania czasów wykonania w trzech scenariuszach
- Algorytm wyszukiwania binarnego — prosta i wydajna technika wyszukiwania posortowanych tablic
- Tablica rozgałęzień — technika zmniejszania długości ścieżki instrukcji, rozmiaru kodu maszynowego (a często także pamięci)
- Porównanie paradygmatów programowania — względy wydajnościowe specyficzne dla paradygmatu
- Optymalizacja kompilatora — optymalizacja wywodząca się z kompilatora
- Złożoność obliczeniowa operacji matematycznych
- Teoria złożoności obliczeniowej
- Wydajność komputera — metryki sprzętu komputerowego
- Kompresja danych — zmniejszenie przepustowości transmisji i miejsca na dysku
- Indeks bazy danych — struktura danych, która poprawia szybkość operacji wyszukiwania danych w tabeli bazy danych
- Kodowanie entropii — wydajne kodowanie danych z wykorzystaniem częstotliwości występowania ciągów jako kryterium substytucji
- Zbieranie śmieci — automatyczne zwalnianie pamięci po użyciu
- Zielone przetwarzanie — krok w kierunku wdrażania „bardziej ekologicznych” technologii, zużywających mniej zasobów
- Algorytm Huffmana — algorytm wydajnego kodowania danych
- Poprawa wydajności kodu zarządzanego — biblioteka Microsoft MSDN
- Lokalność odniesienia — w celu uniknięcia opóźnień w pamięci podręcznej spowodowanych nielokalnym dostępem do pamięci
- Optymalizacja pętli
- Zarządzanie pamięcią
- Optymalizacja (informatyka)
- Analiza wydajności — metody pomiaru rzeczywistej wydajności algorytmu w czasie wykonywania
- Obliczenia w czasie rzeczywistym — dalsze przykłady zastosowań, w których czas ma krytyczne znaczenie
- Analiza run-time — oszacowanie oczekiwanych czasów działania i skalowalności algorytmu
- Jednoczesne wielowątkowość
- Algorytm sortowania § Porównanie algorytmów
- Egzekucja spekulacyjna lub egzekucja gorliwa
- Przewidywanie oddziałów
- Super-wątkowość
- Kod wątkowy — podobny do tabeli metod wirtualnych lub tabeli rozgałęzień
- Wirtualna tablica metod — tablica rozgałęzień z dynamicznie przypisywanymi wskaźnikami do wysyłania