Jakie algorytmy są najczęściej stosowane w praktyce?

Które algorytmy są najczęściej używane?

Napisz jeden algorytm na odpowiedź, staraj się, aby twoja odpowiedź była krótka (jedna lub dwie linie).

Czy szybka transformata Fouriera rozwiązuje problem algorytmiczny większość razy dziennie przez prawdziwe systemy komputerowe? To musi być blisko. Nominowałbym więc algorytm FFT Cooleya-Tukeya .

Mnożenie.

Być może jeden z najstarszych nie całkiem trywialnych algorytmów i problem, który jest rozwiązywany częściej niż FFT.

Algorytmy najkrótszej ścieżki Dijkstry i Bellmana-Forda . W 2010 r. W Internecie jest aktywnych co najmniej 35 000 systemów autonomicznych (AS). Każdy AS obsługuje protokół routingu według stanu łącza (Dijkstra) lub protokół routingu w oparciu o wektor odległości (Bellman-Ford). Routery w ramach jednego systemu AS zazwyczaj aktualizują tabele co kilka minut, powiedzmy 10.

Tak więc liczba egzekucji Dijkstra i Bellman-Ford dziennie wynosi co najmniej 5 milionów. I to tylko z routerów.

Nie policzyliśmy obliczeń najkrótszej ścieżki z Map Google i polubień, które powinny z łatwością stanowić 10 razy więcej. Pół miliarda egzekucji dziennie nie jest daleko idące.

Szybkie sortowanie

Wyszukiwanie binarne

Myślę, że najczęściej stosowanym algorytmem jest kontrola parzystości (a może CRC lub jakiś kod korygujący błędy), ponieważ pojawiają się one przy każdym dostępie do pamięci RAM.

Algorytm simpleksowy - czy to nadal nie jest konkurencyjne w stosunku do najlepszych metod punktowania wewnętrznego? Jeśli tak, należy go często używać.

$k$

Mówiąc bardziej ogólnie, należy spojrzeć na laureatów nagrody Kanellakis na pomysły, które mają teoretyczną i praktyczną wagę.

Dopasowywanie wyrażeń regularnych przez konwersję do automatów skończonych - wierzę, że grep działa zgodnie z tymi liniami.

Głębokie pierwsze wyszukiwanie (DFS)

Trudno wymyślić bardziej powszechnie stosowane algorytmy niż te we współczesnych implementacjach TCP : tj. Unikanie zatorów , szybka retransmisja . Zależy to jednak od tego, jak określa się, co spełnia kryteria algorytmu ...

Eliminacja Gaussa Jest to nadal stosowane w praktyce, prawda? Jeśli nie, zastąp to tym, co jest najczęściej używane do rozwiązywania układów liniowych ...

SHA-1 (i ogólnie funkcje skrótu). Prawdopodobnie pokonał większość innych algorytmów pod względem liczby wykonań.

Algorytmy związane z drzewem B + są używane do tworzenia baz danych

Algorytmy szeregowania. Są używane przez każde urządzenie użytkownika i serwer na całym świecie. Używa się wielu odmian, znalazłem wiele odniesień do „kolejki wielopoziomowej informacji zwrotnej”

Ta odpowiedź interpretuje „najczęściej” w kategoriach faktycznych cykli procesora.

Kiedy uczyłem się informatyki w latach 70., przypominam sobie, że zdecydowana większość cykli komputerowych (czytaj: mainframe) była poświęcona sortowaniu. Aplikacje biznesowe wymagają obszernego sortowania do analiz i raportów. Nie sądzę, że to się bardzo zmieniło, ale oczywiście pojawienie się innych aplikacji - e-mail, edytor tekstów itp. - musiało zmienić ten miks. Te rodzaje są zwykle stabilnymi rodzajami (nie Quicksort) ze względu na konieczność sortowania według kolejnych pól w celu utworzenia podsortów.

Ściśle mówiąc, najczęściej stosowanym algorytmem jest bez wątpienia to, co wykonuje proces oczekiwania systemu Windows, gdy nic innego się nie dzieje ;-).

Sprase Matrix Vector Multiply

... jest obliczeniowym koniem roboczym stojącym za rozwiązaniem prawie wszystkich systemów liniowych. W rezultacie jest uruchamiany za każdym razem

• Naukowcy / inżynierowie rozwiązują równania różniczkowe
• Statystycy znajdują nowe korelacje (PCA)
• Google uruchamia PageRank
• Twój telefon przewiduje Twoją lokalizację na podstawie GPS, akcelerometrów, lokalizacji wieży komórkowej
• Twój samochód dostosowuje zawieszenie do ruchu
• itp....

Większość FLOP-ów na dowolnym superkomputerze lub klastrze jest wydawana wewnątrz rzadkiego mat-vec.

Metoda Newtona. Służy do obliczania pierwiastków kwadratowych, do obliczania podziału. Może być używany do programowania liniowego. Mówiąc bardziej ogólnie, jest to koń roboczy optymalizacji (wypukłej). Może być stosowany do rozwiązywania równań różniczkowych w fizyce poprzez minimalizację akcji / energii.

Skośne i czerwono-czarne drzewa.

Są już zaimplementowane w STL (hash_map, map), a każdy programista wie, że taki kontener jest niezwykle wygodny, gdy chcesz przechowywać pewne informacje indeksowane według dowolnego typu danych.

Algorytmy korekcji błędów, takie jak Reed-Solomon.

http://en.wikipedia.org/wiki/Error-correcting_code#List_of_error-correcting_codes http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

Programowanie dynamiczne .

Myślę, że DP jest używany „częściej” niż inne algorytmy cytowane do tej pory w ankiecie. Wnioskuję „częściej” w tym sensie, jak często implementowano nietrywialną koncepcję algorytmu programiści w rzeczywistości, a nie jak często wywoływana jest konkretna implementacja algorytmu.

DP jest wszechstronny i ma wiele twarzy. Czasami używałem go nieco podświadomie, a potem uświadomiłem sobie, że robię DP.

Oczywiście są rzeczy, które są jeszcze bardziej powszechne niż Program Dynamiczny, ale są to głównie struktura danych (tablica, lista połączona, skrót).

Ciągłe dopasowanie, używane przez cały czas w oprogramowaniu aplikacyjnym i na poziomie bazy danych.

W tym konkretnym przypadku istnieje kilka dość zaangażowanych algorytmów (KMP, Boyer-Moore), z których niektóre osiągają sublinearny oczekiwany czas działania. Są również interesujące do studiowania z punktu widzenia CS.

Przybliżone dopasowanie ciągów, czyli wyrównanie, jest prawdopodobnie jeszcze bardziej interesujące. Znasz funkcje „autokorekty”? Ponadto wyszukiwanie hałaśliwych danych łańcuchowych (np. DNA) odbywa się za pomocą dopasowań.