W jakich obszarach programowania czas działania algorytmu jest rzeczywiście ważną kwestią?

Czasami słyszę, jak ludzie mówią, że ze względu na szybkość procesorów i ilość dostępnej pamięci efektywność algorytmu i czas działania nie są w praktyce poważnym problemem.

Ale wyobrażam sobie, że wciąż istnieją obszary, w których takie względy mają ogromne znaczenie. Dwa, które przychodzą na myśl, to handel algorytmiczny, w którym tysiące transakcji muszą być przeprowadzane w ułamku sekundy, oraz programowanie systemów wbudowanych, w których często brakuje pamięci i mocy. Czy mam rację co do tych przykładów? a jakie inne obszary byłyby również przykładami?

Prędkość jest zawsze potrzebna. Chyba masz rację. Oto kilka przykładów, gdzie pożądane są porządne algorytmy:

1. Kryptografia

2. Przeszukiwanie dużych baz danych

3. Sortowanie i scalanie

4. Wyszukiwanie tekstu (nieindeksowane), w tym symbole wieloznaczne

5. Problemy matematyczne z intensywnymi obliczeniami

6. Symulacja

7. Aplikacje eksploracji danych

8. Animacja

9. AI

10. Wizja komputerowa

W niektórych przypadkach czas działania algorytmu może nie być wielkim problemem, ponieważ doszliśmy do tego, że możesz po prostu przebić się przez dłużej działający algorytm z mocniejszym sprzętem. Ale zdecydowanie są miejsca, w których przyspieszenie jest niezbędne.

Ogólnie rzecz biorąc, wszystko, co korzysta z ogromnych zestawów danych, będzie stanowić problem. Kiedy masz coś, co źle skaluje się za pomocą n, a następnie tworzysz naprawdę ogromną liczbę, masz problem. Podejrzewam, że jeśli przejdziesz na stronę beta Computational Science i rozejrzysz się po okolicy, możesz znaleźć wiele problemów wymagających lepszych, szybszych algorytmów. Niektóre obszary, na które natrafiłem:

• Szczególnie złożona analiza statystyczna. Połączenie nieefektywnych algorytmów i dużych zestawów danych może oznaczać ogromne spowolnienia. W przypadku niektórych badań może to nie mieć znaczenia, ale co zrobić, jeśli próbujesz zrobić coś szybko? „Zejdzie z serwera za miesiąc” jest prawdopodobnie złą rzeczą, gdy używasz systemu monitorowania zagrożeń chemicznych / jądrowych / biologicznych.
• Eksploracja danych na dużych zestawach danych.
• Symulacje obejmujące wiele zmiennych.

Ogólnie rzecz biorąc, obliczenia naukowe wydają się być obszarem, w którym złożoność tego, co jest programowane, stwarza możliwości poważnego spowolnienia, jeśli twój algorytm jest powolny (wiele z nich cierpi na bardzo duże n). Jak już wspomniałeś, są aplikacje finansowe. Kiedy milisekundy mogą ustalić, czy zarabiasz, czy tracisz pieniądze na handlu, algorytmy „wystarczająco dobre” nie zamierzają go wyciąć, jeśli jest coś lepszego, co można zrobić.

Czasami słyszę, jak ludzie mówią, że ze względu na szybkość procesorów i ilość dostępnej pamięci efektywność algorytmu i czas działania nie są w praktyce poważnym problemem.

Dodaj szczyptę soli. Większa moc obliczeniowa po prostu oznacza, że ​​twoje n może stać się znacznie większe, zanim znacznie spowolni. W przypadku większości codziennych problemów liczba ta jest teraz na tyle duża, że ​​nie musisz się tym przejmować. Jednak nadal powinieneś znać złożoność swoich algorytmów.

Przy większej ilości dostępnych zasobów może być konieczne późniejsze przetworzenie większej ilości danych. Dzisiaj musisz przeanalizować plik dziennika 10 MB zawierający 100 000 linii. W ciągu roku możesz mieć plik dziennika 100 GB z 1 000 000 000 linii. Jeśli ilość danych rośnie szybciej niż zasoby zasobów, później napotkasz problemy.

Przy większej ilości dostępnych zasobów na sobie nakłada się więcej warstw. System operacyjny, framework systemu operacyjnego, framework innej firmy, interpreter języka i wreszcie własne narzędzie. Wszystkie niepotrzebne nieefektywności na wszystkich różnych warstwach mnożą się. Jutro Twoje narzędzie może działać na nowym systemie operacyjnym z większą liczbą dzwonków i gwizdków, które same zjadają więcej cykli i więcej pamięci, pozostawiając mniej dla Ciebie.

Aby odpowiedzieć na twoje pytanie, nadal musisz zadbać o to, gdzie coraz więcej danych musi zostać poddanych analizie (wystarczająca liczba przykładów podanych w innych odpowiedziach) i gdzie nie dostarczasz ostatecznego narzędzia, ale kolejną warstwę abstrakcji dla innych narzędzi.

Kilka lat temu musiałem napisać algorytm sortujący ustawione probówki n stojakach na dwie odrębne partycje: tj. Jeden podzbiór probówek został „wybrany”, a reszta „nie wybrana”, a końcowy wynik byłby taki, że żaden stojak miałby na sobie zarówno „wybraną”, jak i „niewybraną” rurkę (były pewne dodatkowe wymagania, takie jak kompresja). Każdy stojak zawierał maksymalnie 100 rurek.

Algorytm miał zostać wykorzystany do sterowania robotem sortującym rurki w laboratorium farmaceutycznym.

Kiedy otrzymałem oryginalną specyfikację, przydzielono mi około 1 minuty czasu obliczeń na posortowanie około 2000 rurek, ponieważ uważaliśmy, że pod względem użyteczności nie jest to zbyt bolesne. Wymagano minimalnej liczby ruchów we wszystkich możliwych kombinacjach, ponieważ sam robot był wolny .

Domniemane założenie było takie, że złożoność byłaby wykładnicza wraz z liczbą lamp. Jednak podczas pracy nad projektem algorytmu odkryłem, że istnieje szybki O(n)algorytm, w którym njest liczba stojaków, które wykonały optymalny podział rur. W rezultacie czas sortowania algorytmu był natychmiastowy, więc wyświetlanie sortowania będzie aktualizowane w czasie rzeczywistym, gdy użytkownik skonfiguruje swoją operację sortowania.

Dla mnie różnica między użytkownikiem siedzącym przez minutę po każdej zmianie a posiadaniem natychmiastowego reagującego GUI stanowiła różnicę między oprogramowaniem, które było funkcjonalnie wystarczające, a oprogramowaniem, które było przyjemnością w użyciu.

Inne obszary obejmują wiele rodzajów przetwarzania sygnału w czasie rzeczywistym, systemy kontroli sprzężenia zwrotnego, dekonwolucję eksploracji ropy naftowej, kompresję wideo, śledzenie promieni i renderowanie klatek filmu, systemy rzeczywistości wirtualnej, gry, w których wysoka częstotliwość klatek może być znaczącą przewagą konkurencyjną, a także smartfony i inne aplikacje na urządzenia mobilne, w których duża liczba cykli procesora zużywa baterię użytkownika szybciej.

Jestem zaskoczony, że to pytanie zostanie nawet zadane, ponieważ dla każdego superkomputera Top-500, jaki kiedykolwiek zbudowano, istnieje prawdopodobnie lista oczekujących naukowców, którzy mogą ją zwiększyć i życzyć większej mocy obliczeniowej lub lepszych algorytmów do rozwiązania jakiegoś problemu (złóż trochę białka, aby rozszyfrować raka itp.), zanim przejdą na emeryturę.

Myślę, że wyszukiwarki takie jak Google i Bing są jednym z największych obszarów, w których stosowane są złożone algorytmy i odgrywają kluczową rolę w przyspieszaniu wyników, a ich trafność (ranking strony) zapewnia większą użyteczność dla użytkowników.

Wydajność algorytmu nie jest obecnie głównym problemem, ponieważ używamy wydajnych algorytmów. Jeśli użyjesz algorytmu O (n!), Będzie on działał wolno na dowolnym sprzęcie.

Złożoność algorytmów staje się coraz ważniejsza wraz ze wzrostem ilości danych. Na szczęście wydajne ogólne rozwiązania typowych problemów programistycznych (głównie wyszukiwanie i sortowanie) są zawarte w prawie każdej standardowej bibliotece każdego nowoczesnego języka programowania, więc zwykle programista nie musi się tym zbytnio przejmować. Minusem jest to, że wielu programistów w ogóle nie wie, co dzieje się pod maską i jakie są cechy używanych przez nich algorytmów.

Staje się to szczególnie problematyczne, ponieważ wiele aplikacji nie jest odpowiednio poddanych testom warunków skrajnych: ludzie piszą kod, który działa dobrze w przypadku małych zestawów danych testowych, ale w przypadku kilku tysięcy razy więcej danych kod zatrzymuje się. Coś, co działa dobrze dla dziesięciu rekordów, szybko eksploduje, gdy rośnie zbiór danych. Przykład z realnego świata: fragment kodu, który miał wyczyścić elementy, które nie były już powiązane z żadną kategorią, używał trzypoziomowej zagnieżdżonej pętli, czyli O (n ^ 3). Mając zaledwie 10 rekordów w testowej bazie danych, oznaczało to 1000 kontroli - doskonale wykonalnych i nie wprowadza zauważalnego opóźnienia. Jednak produkcyjna baza danych szybko zapełniła się około 1000 wierszami i nagle kod za każdym razem wykonuje miliard kontroli.

Więc: Nie, nie musisz znać tajników implementacji różnego rodzaju porządnych algorytmów i nie musisz mieć możliwości wymyślania własnych, ale potrzebujesz podstawowej wiedzy na temat popularnych algorytmów, jakie są ich mocnymi i słabymi punktami są, kiedy i kiedy ich nie używać, i musisz zdawać sobie sprawę z możliwego wpływu złożoności algorytmicznej, abyś mógł zdecydować, który poziom złożoności jest dopuszczalny.

Nie jest kwestią tego, które domeny aplikacji są wrażliwe na środowisko wykonawcze. Każdy program, gdziekolwiek, ma minimalną wydajność, poniżej której jest faktycznie bezwartościowy. Istotą złożoności algorytmu jest to, jak zmienia się on wraz ze wzrostem wielkości wejściowej. Innymi słowy, obszary, w których prędkość ma szczególne znaczenie, to obszary, w których oczekuje się, że będziesz musiał skalować nie tylko obecny rozmiar problemu, ale rząd wielkościTwojego obecnego rozmiaru problemu. Jeśli rozpatrzysz wnioski podatkowe obywateli departamentu Francji, zadanie może być duże, ale nie jest prawdopodobne, że ani liczba ludności, ani złożoność przetwarzania jednego rekordu wzrośnie dziesięciokrotnie lub stukrotnie, więc cokolwiek działa teraz prawdopodobnie będziesz dalej działać. Ale jeśli spróbujesz stworzyć coś, co wystartuje w woluminach internetowych, złożoność algorytmu jest kluczowa: wszystko, co zależy bardziej niż liniowo lub log-liniowo od wielkości wejściowej, stanie się znacznie droższe bardzo szybko, a ostatecznie prędkość procesora po prostu nie będzie w stanie nadążyć za wzrostem.

W mojej dziedzinie (efekty wizualne, które obejmują takie elementy, jak śledzenie ścieżki, animacja komputerowa, symulacja cząstek, dynamika płynów, przetwarzanie obrazu itp.), Złożoność algorytmiczna ma fundamentalne znaczenie. Nie ma możliwości, aby cokolwiek działającego w gorszym czasie niż liniowo-rytmiczny mogło mieć nadzieję na ukończenie w rozsądnym czasie na wejściach, które zwykle osiągają miliony wierzchołków, wielokątów, wokseli, cząstek, tekstur, szczególnie gdy wiele z tych rzeczy musi wypełnić wiele razy na sekundę, aby zapewnić interaktywne opinie w czasie rzeczywistym.

Biorąc to pod uwagę, nie kładzie się tak dużego nacisku na złożoność algorytmiczną w dyskusji zwykle wśród współpracowników, być może dlatego, że jest to nieco oczywiste i raczej „szczątkowe”. Ogólnie przyjmuje się, że jeśli piszesz moduł śledzenia ścieżki, że będzie on działał w czasie logarytmicznym lub lepszym, a struktury danych, takie jak ograniczające hierarchie woluminów, są znane i względnie trywialne w implementacji dla czytnika. Miałem nawet wykwalifikowanego kolegę, który powtarzał, że wielowątkowość i SIMD są ważniejsze niż algorytmy, i nie sądzę, żeby miał na myśli to, że można oczekiwać, że wyciągniesz wiele z równoległego tworzenia bąbelków. Myślę, że to powiedział, ponieważ wziął za pewnik, że zastosujemy rozsądne algorytmy,

Obecnie dużą uwagę skupia się na przyjęciu wielu znanych algorytmów i lepszym wykorzystaniu podstawowych cech sprzętu, takich jak pamięć podręczna procesora, rejestry i instrukcje SIMD, procesory graficzne i wiele rdzeni. Na przykład Intel wymyślił nowatorski sposób na przejęcie znanego starego BVH i zaproponowanie koncepcji „pakietów promieni”, polegających w zasadzie na testowaniu wielu spójnych promieni za jednym razem z rekurencyjnym rodzajem przechodzenia przez drzewa (co może brzmieć jak to przyszedłby ze swoją częścią złożoności i kosztów ogólnych, z tym że więcej niż to wynika z faktu, że promienie te można teraz testować jednocześnie pod kątem skrzyżowań promień / AABB i promień / trójkąt za pomocą instrukcji i rejestrów SIMD).

Podobnie jest z podobnym podziałem catmull-clark, co jest bardzo podstawowym elementem grafiki komputerowej. Jednak obecnie konkurencyjne, gorące i super wydajne są implementacje GPU, które przybliżają podział CC za pomocą łatek Gregory, spopularyzowanych przez Charlesa Loopa, a następnie przyjętych przez Pixara. Prostsza implementacja procesora jest teraz raczej przestarzała, niekoniecznie dlatego, że została zastąpiona pod względem złożoności algorytmicznej, ale dlatego, że została zastąpiona przez coś, co dobrze gra z GPU.

I to zwykle stanowi duże wyzwanie w dzisiejszych czasach, gdy nie ma najlepszego algorytmu w sposób stosunkowo niezależny od podstawowych cech sprzętu. Dostałem stopę w branży, opracowując nowatorską strukturę przyspieszenia, która znacznie przyspieszyła wykrywanie kolizji dla animowanych postaci i innych miękkich ciał w latach 90., stosując hierarchiczne podejście do segmentacji w przeciwieństwie do indeksu przestrzennego, co dało mi dużo oferty pracy, ale w dzisiejszych czasach nie jest już tak imponująca, ponieważ opublikowałem ją na długo, zanim mieliśmy tak imponujące pamięci podręczne procesora i wiele rdzeni i programowalnych układów GPU, a co nie, a obecnie stosuję zupełnie inne podejście w wyniku znacznych zmian w podstawowy sprzęt.

Kiedyś natknąłem się na problem polegający na tym, że algorytm zwykle działał w O (n), ale w rzadkich i bardzo mało prawdopodobnych okolicznościach potrzebowałby czasu O (n ^ 3) - „rzadkimi” okolicznościami był katalog zawierający pliki o nazwach, które były prawidłowe w jeden system operacyjny, ale nie w innym.

Nikt nigdy nie miał problemów. Następnie jeden klient zastosował strategię do nazwania plików, które systematycznie trafiałyby do skrzynki O (n ^ 3), a przy kilku 100 plikach system wirtualnie przestał działać. W rezultacie algorytm musiał zostać zmieniony.

Trzy kolejne, o których nie wspomniano:

1) Wiele gier strategicznych w czasie rzeczywistym. Spójrz na te, które mają jednostki, które nie mogą dzielić pozycji. Zobacz, co dzieje się z wyszukiwaniem ścieżek, gdy duża grupa jednostek porusza się przez ograniczony teren. Nie spotkałem się jeszcze z grą bez jakiegoś poważnego problemu, ponieważ po prostu nie ma wystarczającej mocy procesora.

2) Wiele problemów z optymalizacją. (Edycja: odkąd napisałem tę odpowiedź, trafiłem na jeden. Moim celem było przycinanie zbędnych ścieżek, aby pozostawić wszystkie węzły połączone z minimalną wagą łączących ścieżek. Moje oryginalne podejście działało całkiem dobrze, dopóki nie przeniosłem więcej przycinania do rutyny, potem zdałem sobie sprawę, że to 2 ^ n. Teraz jest n ^ 2, chociaż czasem może to dać nieco nieoptymalny wynik).

3) Rzeczy, które muszą działać na dużych ilościach danych w czasie rzeczywistym. Rozważ DVD: zazwyczaj dostajesz 2 godziny wideo w 4,7 GB. Rozważ typowy plik wideo o tej samej rozdzielczości: te 2 godziny wideo zwykle będą miały mniej niż 1 GB. Powodem tego jest to, że kiedy określono specyfikację DVD, nie można było stworzyć odtwarzacza DVD w rozsądnej cenie, który mógłby wystarczająco szybko dekodować bardziej nowoczesne formaty.

Cóż, każda aplikacja, która zwykle działa na superkomputerze ( lista największych komputerów ) kwalifikuje się. Są one zróżnicowane, ale dużą ich podklasą są symulacje fizyki:

• Symulacje fizyki:
  • Prognoza pogody
  • Symulacje klimatyczne
  • Symulacje wybuchających gwiazd itp.
  • Symulacje wybuchających atomów
  • Symulacje aerodynamiczne samochodów / samolotów / pociągów itp.
  • ...
• Obliczanie obrazów z danych z radiotelefonu
• Zastosowania biologiczne:
  • Rzeczy z sekwencjami DNA (tak naprawdę nie lubię ich)
  • Materiały biochemiczne, takie jak fałdowanie białek
  • Symulacje współpracy komórek nerwowych w celu przetwarzania informacji
  • Symulacje innych złożonych interakcji, takich jak ekosystemy
  • ...
• ...

To tylko najważniejsze z moich głównych tematów, ale po prostu przeczytaj listę różnych superkomputerów i zdaj sobie sprawę, że każdy z nich jest zbudowany, aby umożliwić jakieś obliczenia, które nie byłyby możliwe bez takich gigantycznych maszyn.

A kiedy zobaczysz, że faktycznie potrzebujemy tych maszyn, uświadom sobie, ile kosztów można zaoszczędzić, po prostu przyspieszając te aplikacje o 10% . Każda optymalizacja tych kodów bezpośrednio zwiększa ilość wyników, które jesteśmy w stanie wydostać się z tych maszyn.