Czy algorytmy (i ogólnie wydajność) stają się coraz mniej ważne?

29

Skoro kupowanie mocy obliczeniowej jest znacznie tańsze niż w przeszłości, to czy znajomość algorytmów i efektywność stają się coraz mniej ważne? Oczywiste jest, że chciałbyś uniknąć nieskończonej pętli, więc nie wszystko idzie. Ale jeśli masz lepszy sprzęt, czy możesz mieć gorsze oprogramowanie?

efficiency

— Quora Feans
źródło

2

„zarówno tak, jak i nie”!

— vzn

4

Teraz, gdy istnieją samoloty, a ładunki transatlantyckie nie muszą już wszystkie pływać na statkach, czy prędkość wysyłki jest mniej ważna? Klienci FedEx i DHL nie sądzą.

— Peter Shor,

2

Jeśli wielkość wejściowa jest wystarczająco duża, różnica rzędów wielkości między algorytmami jest ważna bez względu na szybkość maszyny. Ale od czasu do czasu jestem oszukiwany, aby wprowadzać zmiany w celu „optymalizacji” stałej różnicy czynnikowej tylko po to, aby zdać sobie sprawę, że użycie wyrażeń wbudowanych w cukier syntaktyczny języka programowania <cough> Python </cough> jest znacznie szybszy niż moja „optymalizacja”.

— kojiro

patrz także prawo Mooresa

— vzn

jednym interesującym studium przypadku tutaj jest np. Windows, który pod pewnymi / wieloma względami działa mniej wydajnie nawet na wysoce zoptymalizowanym sprzęcie niż kiedyś ... podobnie jak prawo Moores poprawia sprzęt, wydaje się, że istnieje odpowiednie prawo inflacyjne w oprogramowaniu, w którym nowoczesne oprogramowanie robi coraz więcej, z dodawanymi i mnożonymi nowymi warstwami ... nieco analogicznie do sposobu, w jaki gaz wypełnia całą dostępną objętość ... lub w którym budżet bez względu na to, jak duży lub rosnący jest zawsze wykorzystywany lub nieco przekroczenia ... zobacz też ewolucyjny wyścig

— vzn

31

Bardzo podoba mi się przykład z książki Wprowadzenie do algorytmów , który ilustruje znaczenie wydajności algorytmu:

Porównajmy dwa algorytmy sortowania: sortowanie wstawiane i scalanie . Ich złożoność wynosi odpowiednio i . Zwykle sortowanie scalone ma większy stały współczynnik, więc załóżmy . $O(n^2) = c_1n^2$ $O(n\log n) = c_2n \lg n$ $c_1 < c_2$

Aby odpowiedzieć na twoje pytanie, oceniamy czas wykonania szybszego komputera (A) z uruchomionym algorytmem sortowania wstawiania względem wolniejszego komputera (B) z uruchomionym algorytmem sortowania po scaleniu.

Przyjmujemy:

rozmiar problemu wejściowego wynosi 10 milionów liczb: ; $n=10^7$
komputer A wykonuje instrukcji na sekundę (~ 10GHz); $10^{10}$
komputer B wykonuje tylko instrukcji na sekundę (~ 10 MHz); $10^7$
współczynniki stałe wynoszą (co jest nieco ) i (w rzeczywistości jest mniejsze). $c_1=2$ $c_2=50$

Tak więc przy tych założeniach trzeba

\frac{2 \cdot (10^{7})^{2} instructions}{10^{10} instructions / second} = 2 \cdot 10^{4} seconds

$\frac{2 \cdot (10^7)^2 \text{ instructions}} {10^{10} \text{ instructions}/\text{second}} = 2 \cdot 10^4 \text{ seconds}$ dla komputer A do sortowania liczb i

10^{7}

$10^7$

\frac{50 \cdot 10^{7} \lg 10^{7} instructions}{10^{7} instructions / second} \approx 1163 seconds

$\frac{50 \cdot 10^7 \lg 10^7 \text{ instructions}} {10^{7} \text{ instructions}/\text{second}} \approx 1163 \text{ seconds}$

dla komputera B.

Komputer, który jest 1000 razy wolniejszy, może rozwiązać problem 17 razy szybciej. W rzeczywistości przewaga sortowania będzie jeszcze bardziej znacząca i będzie rosła wraz z rozmiarem problemu. Mam nadzieję, że ten przykład pomoże odpowiedzieć na twoje pytanie.

Nie chodzi jednak o złożoność algorytmu. Dzisiaj jest prawie niemożliwe, aby uzyskać znaczne przyspieszenie tylko dzięki użyciu maszyny o wyższej częstotliwości procesora. Ludzie muszą projektować algorytmy dla systemów wielordzeniowych, które dobrze skalują się. Jest to również trudne zadanie, ponieważ wraz ze wzrostem liczby rdzeni zwiększa się również narzut (na przykład w celu zarządzania dostępem do pamięci). Tak więc uzyskanie liniowego przyspieszenia jest prawie niemożliwe.

Podsumowując, dzisiejszy projekt wydajnych algorytmów jest tak samo ważny jak wcześniej, ponieważ ani wzrost częstotliwości, ani dodatkowe rdzenie nie zapewnią przyspieszenia w porównaniu do tego, które zapewnia efektywny algorytm.

— Pavel Zaichenkov
źródło

4

Warto wspomnieć, że niemożność przyspieszenia liniowego wynika z prawa Amdhala .

— Bartosz Przybylski,

f (x)

$f(x)$

n^{2}

$n^2$

\sum_{i = 1}^{n} f (x_{i})

$\sum_{i=1}^n f(x_i)$

n

$n$

x_{i}^{'} s

$x_i's$

O (n \cdot n^{2} + n) = O (n^{3})

$O(n\cdot n^2 + n) = O(n^3)$

n

$n$

O (n^{2} + n) = O (n^{2})

$O(n^2 + n) = O(n^2)$

„Tak więc komputer, który jest 1000 razy wolniejszy, może rozwiązać problem 17 razy szybciej.” To fałszywe stwierdzenie, ponieważ łączysz szybkość sprzętu i różne algorytmy jednocześnie. Porównaj raczej komputer A z komputerem B dla każdego rodzaju sortowania osobno. (Dlaczego nie mogę używać seryjnej porządek na komputerze A, lub wstawki porządek na komputerze B?)

— AquaAlex

3

@AquaAlex, celem tego przykładu jest pokazanie, że wolny komputer może przewyższyć szybki tylko za pomocą wybranego algorytmu. Możemy porównać czas wykonania dla każdego rodzaju sortowania osobno lub uruchomić sortowanie scalające na A, a wstawianie sortować na B. Ale pokazanie, że szybszy komputer zwykle działa lepiej niż wolny, po prostu nie ma sensu.

— Pavel Zaichenkov

OK, więc pomysł polegał na tym, aby pokazać, że bardziej wydajny algorytm nadal ma ciężar nawet w ciągu dnia na szybszych procesorach i większej pamięci.

— AquaAlex

36

Przeciwnie. W tym samym czasie, gdy sprzęt staje się tańszy, odbywa się kilka innych zmian.

Po pierwsze, ilość danych do przetworzenia rośnie wykładniczo. Doprowadziło to do badania quasilinearnych algorytmów czasu i obszaru dużych zbiorów danych . Pomyśl na przykład o wyszukiwarkach - muszą one obsługiwać duże ilości zapytań, przetwarzać duże ilości danych i robić to szybko. Algorytmy są ważniejsze niż kiedykolwiek.

Po drugie, obszar uczenia maszynowego staje się silny i pełen algorytmów (choć innego rodzaju niż to, czego uczysz się na licencjacie). Obszar ten kwitnie i co jakiś czas wymyślany jest naprawdę nowy algorytm, który znacznie poprawia wydajność.

Po trzecie, algorytmy rozproszone stały się ważniejsze, ponieważ napotykamy przeszkodę w zwiększaniu szybkości przetwarzania procesora . W dzisiejszych czasach moc obliczeniowa jest zwiększana przez zrównoleglanie , a to wymaga dedykowanych algorytmów.

Po czwarte, aby zrównoważyć rosnącą moc procesorów, nowoczesne paradygmaty programowania wykorzystują metody maszyn wirtualnych do zwalczania luk bezpieczeństwa. To spowalnia te programy o znaczny czynnik. Dodając do tej zagadki, Twój system operacyjny inwestuje więcej czasu procesora w dzwonki i gwizdy, pozostawiając mniej czasu procesora dla twoich programów, co może obejmować algorytmy wymagające procesora, takie jak kompresja wideo i dekompresja. Chociaż sprzęt jest szybszy, nie jest wykorzystywany tak skutecznie.

Podsumowując, wydajne algorytmy są niezbędne do obsługi dużych ilości danych; pojawiają się nowe rodzaje algorytmów w dziedzinie sztucznej inteligencji ; algorytmy rozproszone stają się coraz bardziej popularne; a moc procesora jest wykorzystywana mniej wydajnie z różnych powodów (ale głównie dlatego, że komputery stają się coraz wydajniejsze). Algorytmy nie są jeszcze martwe.

— Yuval Filmus
źródło

„algorytmy jeszcze nie umarły” ... wręcz przeciwnie, prawdopodobnie żyjemy w „złotym wieku algorytmów” ....

— dniu

12

Znajomość algorytmów to znacznie więcej niż pisanie szybkich algorytmów.

Daje ci także metody rozwiązywania problemów (np. Dziel i zwyciężaj, programowanie dynamiczne, zachłanność, redukcja, programowanie liniowe itp.), Które możesz zastosować, gdy zbliżasz się do nowego i trudnego problemu. Odpowiednie podejście zwykle prowadzi do kodów, które są prostsze i znacznie szybsze do napisania. Więc muszę się nie zgodzić z odpowiedzią Kevina, ponieważ kody, które nie są starannie ułożone, są często nie tylko powolne, ale także skomplikowane. Podoba mi się ten cytat Davida Parnasa:

Często słyszę programistów opisywanych jako „ktoś, kto wie, jak szybko zbudować duży system”. Nie ma sztuczki w szybkim budowaniu dużych systemów; im szybciej je zbudujesz, tym większe będą!

(Oczywiście musimy również łączyć algorytmy z metodami projektowania oprogramowania, aby pisać dobre kody).

Znajomość algorytmów mówi nam również, jak organizować dane, abyś mógł je łatwiej i wydajniej przetwarzać za pomocą struktur danych.

Co więcej, daje nam to sposób na oszacowanie wydajności twojego podejścia i zrozumienie kompromisów między kilkoma różnymi podejściami pod względem złożoności czasowej, złożoności przestrzeni i złożoności kodów. Znajomość tych kompromisów jest kluczem do podjęcia właściwej decyzji w ramach ograniczeń zasobów.

Jeśli chodzi o znaczenie wydajności oprogramowania, zacytuję prawo Wirtha:

Oprogramowanie działa wolniej niż sprzęt szybciej.

Larry Page niedawno stwierdził, że oprogramowanie robi się dwa razy wolniejsze co 18 miesięcy, a tym samym wyprzedza prawo Moore'a.

— Dai
źródło

7

Tak , są „względnie” mniej ważne w szerokim przemyśle. Edytor tekstu może być „wystarczająco szybki” i może nie wymagać wielu ulepszeń. Duża część wysiłków IT polega na upewnieniu się, że komponent A napisany w Javie współpracuje z komponentem B napisanym za pomocą C komunikuje się poprawnie za pośrednictwem kolejki komunikatów napisanej w Cobolu (lub coś takiego), lub aby wprowadzić produkt na rynek itp

Ponadto architektura się skomplikowała. Kiedy miałeś proste stare proste procesory, w których miałeś 1 instrukcję na cykl i pisałeś w asemblerze, optymalizacje były „łatwe” (wystarczyło policzyć liczbę instrukcji). Obecnie nie masz prostego procesora, ale w pełni potokowy, superskalarny, niedziałający procesor z nazwami rejestrów i wielopoziomową pamięcią podręczną. I nie piszesz w asemblerze, ale w C / Java / etc. gdzie kod jest skompilowany / JITed (zwykle w celu lepszego kodu, niż ty lub ja napisalibyśmy w asemblerze), lub w Pythonie / Ruby / ... gdzie kod jest interpretowany i dzieli Cię kilka poziomów abstrakcji od maszyny. Mikrooptymalizacje są trudne i większość programistów osiąga efekt odwrotny.

Nie , są one tak samo ważne w badaniach, jak i w kategoriach „absolutnych” . Istnieją obszary, w których szybkość jest ważna, ponieważ operują na dużej ilości danych. W tej skali złożoność ma znaczenie, jak pokazuje przykład Pavla.

Istnieją jednak inne przypadki - obniżanie algorytmów jest nadal opcją wybraną, gdy liczy się prędkość (HPC, urządzenia wbudowane itp.). Znajdziesz na wielu uniwersytetach grupy specjalizujące się w kompilatorach i / lub optymalizacji oprogramowania. Na przykład prosta zamiana kolejności w pętli może uzyskać tysiąckrotne przyspieszenie tylko dlatego, że efektywnie wykorzystuje pamięć podręczną - chociaż może to być przykład z granicy, luka między pamięcią procesora rośnie 1000 razy w ciągu ostatnich 30 lat. Również architektura komputerowa jest częścią CS. Dlatego wiele ulepszeń szybkości obliczeń jest w rzeczywistości częścią ogólnego pola CS.

Po stronie przemysłowej - gdy masz klaster HPC, liczy się szybkość, ponieważ pojedynczy program może działać przez kilka dni, miesięcy lub lat. Nie tylko trzeba płacić rachunek za prąd, ale czekanie może również kosztować pieniądze. Możesz rzucić dwa razy więcej sprzętu, ale 700 mln $ nie może być uważane za drobną zmianę dla wszystkich oprócz największych firm - w takich przypadkach programiści są tańszą opcją i jeśli przepisanie programu na nowy język oznacza tylko „małe” przyspieszenie - mogą rozważ to.

Również prędkość może oznaczać lepszy UX. Wiele recenzji systemu operacyjnego na telefony komórkowe mówi, który z nich jest „szybszy” i chociaż można to zrobić za pomocą „sztuczek”, z pewnością jest to obszar badań. Ponadto chcesz szybciej uzyskać dostęp do swoich danych i szybko robić to, czego potrzebujesz. Czasami oznacza to, że możesz zrobić więcej - w grach masz do zrobienia wszystko 0,017s, a im szybciej, tym więcej cukierków możesz włożyć.

— Maciej Piechotka
źródło

2

To ciekawa dyskusja. I mamy tutaj kilka rzeczy do obejrzenia.

Informatyka teoretyczna - jest to nauka ewoluująca, co oznacza, że wraz z upływem czasu znajdziemy nowe i lepsze sposoby rozwiązywania problemów, co oznacza na przykład ulepszone algorytmy wyszukiwania i sortowania.
Większe społeczności / większe biblioteki - Ponieważ wiele osób wykonało wiele pracy, możemy po prostu bazować na ich pracy i korzystać z algorytmów, które już stworzyli, a nawet zakodowali. Biblioteki te będą aktualizowane z czasem, umożliwiając nam automatyczny dostęp do wydajniejszych programów / algorytmów.
Rozwój - myślę, że teraz mamy problem. Wielu programistów nie jest informatykami, więc piszą kod, aby rozwiązać problemy biznesowe, a nie techniczne / teoretyczne, i byliby tak samo zadowoleni z sortowania bąbelkowego, jak na przykład szybkiego sortowania. I tutaj szybkość sprzętu pozwala złym programistom uciec od używania złych algorytmów i złych praktyk kodowania. Pamięć, szybkość procesora, miejsce do przechowywania te rzeczy nie są już poważnymi problemami, a co kilka miesięcy rzeczy stają się większe, szybsze i tańsze. Mam na myśli spojrzenie na nowe telefony komórkowe. Są teraz bardziej zaawansowane niż komputery / serwery mainframe z lat 70. i 80. Więcej pamięci, więcej mocy obliczeniowej, szybsza pamięć.
Interfejs użytkownika i dane - interfejs użytkownika / interfejs użytkownika i dane są obecnie uważane za ważniejsze niż super wydajny kod w większości dziedzin rozwoju. Szybkość staje się więc problemem, gdy użytkownik musi długo czekać. Jeśli damy użytkownikowi dobry wygląd, a on otrzyma dobrą odpowiedź z aplikacji, jest szczęśliwy. A jeśli firma wie, że wszystkie dane są bezpiecznie przechowywane, mogą je odzyskać i nimi manipulować w dowolnym momencie, nie obchodzi ich, ile miejsca potrzebuje.

Muszę więc powiedzieć, że wydajni programiści nie są już ważni ani potrzebni, po prostu bardzo niewiele firm / użytkowników nagradza ludzi za to, że są super wydajnymi programistami, a ze względu na to, że sprzęt jest lepszy, uciekamy od bycia mniej wydajny. Ale są jeszcze ludzie, którzy koncentrują się na wydajności i dzięki duchowi wspólnoty wszyscy zyskują z czasem.

— AquaAlex
źródło

1

Kilka innych punktów widzenia na to interesujące i głębokie pytanie, które podkreślają interdyscyplinarne i przekrojowe aspekty tego zjawiska. Dai cytuje prawo Wirtha w swojej odpowiedzi:

Oprogramowanie działa wolniej niż sprzęt szybciej.

Istnieją ciekawe podobieństwa tego pomysłu do zjawisk obserwowanych w ekonomii. Należy zauważyć, że ekonomia ma wiele głębokich powiązań z informatyką, np. W harmonogramie powiedzmy, w którym ograniczone zasoby (np. Wątki itp.) Są przydzielane na żądanie za pomocą algorytmów „równoważenia obciążenia”. Innym przykładem jest tak zwana kolejka producent-konsument. Aukcje.

Także np. Lista praw tytułowych, Wikipedia :

Prawo Parkinsona - „Praca rozwija się, aby wypełnić czas dostępny na jej ukończenie”. Stworzony przez C. Northcote Parkinson (1909–1993), który także ukuł następstwo: „Wydatki rosną, by zaspokoić dochód”. W komputerach: programy rozwijają się, aby wypełnić całą dostępną pamięć.

Istnieje pewne silne podobieństwo do paradoksu Jevona, który zaobserwowano we wzroście zużycia energii po tym, jak bardziej wydajne silniki parowe Watt zaczęły zastępować konstrukcję Newcomen, ale zwiększyło się użycie lub rozprzestrzenianie się silników:

W ekonomii paradoks Jevonsa (/ ˈdʒɛvənz /; czasami efekt Jevonsa) jest propozycją, że postęp technologiczny, który zwiększa efektywność wykorzystania zasobów, ma tendencję do zwiększania (a nie zmniejszania) tempa zużycia tego zasobu.

Analogia jest taka, że sprzęt jest zasobem, a oprogramowanie przypomina zużycie zasobów (inaczej podaż kontra popyt). Tak więc oprogramowanie i sprzęt (i postępy w każdym z nich) istnieją nieco w ściśle sprzężonej symbiotycznej pętli sprzężenia zwrotnego, w pewnym sensie koewoluującej . Istnieje wiele złożonych i powiązanych ze sobą czynników wpływających na tę grę, np .:

— vzn
źródło

Dlaczego głosowanie negatywne? Uważam, że wzmianka o prawie Parkinsona i paradoksie Jevonsa jest bardzo odkrywcza.

— Yuval Filmus

@YuvalFilmus Moje przypuszczenie: problemy z gramatyką. Tym razem nie przeszkadzało mi to, że zbyt mocno przeczytałem odpowiedź, ale starałem się ją poprawić.

— Juho

1

To nie „problemy z gramatyką”, to inny styl. To tak, jakby powiedzieć, że native speaker popełnia „błędy” w swoim języku, podczas gdy w rzeczywistości albo język się zmienia, albo występuje regionalna wariancja. W tym przypadku jest to idiomatyczny styl vzn.

— Yuval Filmus,

-3

Nie, głównie biorąc pod uwagę złożoność przestrzeni! Pojemność zwykłego komputera rośnie wykładniczo.

— Andy
źródło

Nie byłoby odwrotnie - jeśli masz „nieskończone” miejsce do przechowywania, nie musisz się martwić złożonością przestrzeni. „Problem” nie polega na tym, że pamięć się powiększa, ale że dane, na których operuje się, rosną w synchronizacji, wypełniając przyspieszenia oferowane przez wzrost mocy obliczeniowej i pamięci - co jest dobre, chcemy modelować kosmos bardziej realistycznie, składać więcej białka itp. (PS. Nie

— oddałem głosu

4

To prawda, że wielu programistów aplikacji mobilnych wydaje się zakładać nieskończone zasoby, ale niestety moje urządzenie jest bardzo ograniczone.

— Raphael