Czy big-O naprawdę jest tak istotny podczas pracy w przemyśle?

W każdym wywiadzie, w którym uczestniczyłem, byłem pytany o matematyczną analizę złożoności, w tym notację big-O.

Jak istotna jest analiza Big-O dla rozwoju przemysłu? Jak często tak naprawdę go używasz i jak konieczne jest wyostrzone podejście do problemu?

Moje pytanie brzmi: jak istotny jest ten test dla rozwoju w branży?

Dobre zrozumienie teorii złożoności obliczeniowej (np. Duża notacja O) jest niezbędne do projektowania skalowalnych algorytmów, aplikacji i systemów. Ponieważ skalowalność ma duże znaczenie dla komputerów w przemyśle, również duża notacja O.

Jak często korzystasz z niego i jak konieczne jest wyostrzone podejście do problemu?

Zależy, co rozumiesz przez „reeeally use it”. Z jednej strony nigdy nie robię formalnych dowodów złożoności obliczeniowej oprogramowania, które piszę. Z drugiej strony przez większość dni mam do czynienia z aplikacjami, w których skalowalność jest potencjalnym problemem, a decyzje projektowe obejmują wybór (na przykład) odpowiednich typów kolekcji na podstawie ich cech złożoności.

(Nie wiem, czy możliwe jest konsekwentne wdrażanie skalowalnych systemów bez solidnego zrozumienia teorii złożoności. Byłbym skłonny myśleć, że tak nie jest.)

Powodem tego jest to, że wskazuje na skalowalność .

Proces, który jest O (n ^ 2), będzie skalowany gorzej niż ten, który jest O (n log n), ale lepszy niż jeden w O (n ^ 3) lub nawet O (n!).

Jeśli nie znasz różnic i kiedy mają one zastosowanie, jesteś mniej odpowiedni do wyboru odpowiednich implementacji funkcjonalności, a także do ekstrapolacji wydajności testu na wydajność produkcyjną.

EDYCJA: Porównanie 48n z n ^ 3 z http://www.codinghorror.com/blog/2007/09/everything-is-fast-for-small-n.html (który z kolei pochodzi z Programming Pearls)

To zależy od tego, co robisz.

Dla twórców stron internetowych (takich jak ja) zwykle ma to duże znaczenie. Chcesz, aby aplikacje internetowe były skalowane. Jeśli Twoja aplikacja ma wąskie gardło, które skaluje się z O (n ^ 2), i uważasz, że to jest w porządku, ponieważ Twój serwer może obsłużyć 1000 jednoczesnych użytkowników, wydaje się, że nie musisz się tym przejmować. Chodzi o to, że aby obsłużyć tylko dwa razy więcej (co jest prawdopodobne, że stanie się to tuż po nocy), będziesz potrzebować 4 razy więcej mocy obliczeniowej. Idealnie byłoby, gdyby aplikacje internetowe były skalowane w O (n), ponieważ sprzęt jest tani przy rozsądnym stałym stosunku użytkownik / serwer.

Ogólnie w aplikacjach, w których masz 100 000 obiektów, duże O przyjdzie i zje ciebie. Jesteś niezwykle podatny na szczyty. Na przykład obecnie pracuję nad grą 3D, która jest aplikacją, która obsługuje mnóstwo danych. Oprócz renderowania masz kontrolę kolizji, nawigację itp. Nie możesz sobie pozwolić na oczywistą drogę. Potrzebujesz wydajnych algorytmów, potrzebujesz dużo buforowania, więc te mniej wydajne amortyzują się. I tak dalej.

Oczywiście, jeśli robisz coś w stylu tworzenia aplikacji mobilnej, łącząc GUI w projektancie interfejsu, połącz to z niektórymi usługami internetowymi i to wszystko, nigdy nie będziesz mieć problemów ze złożonością. Ponieważ usługi internetowe, do których dzwonisz, już się tym zajmują.

W życiu zawodowym nigdy tak naprawdę nie stosowałem formalnie tej reguły.

Musisz jednak znać tę koncepcję i stosować ją w intuicyjny sposób za każdym razem, gdy projektujesz algorytm.

Zasada jest następująca:

Powinieneś być na tyle zaznajomiony z notacją O, aby móc określić dla danego zadania, czy jest to wymagane do formalnego obliczenia, czy wystarczy intuicyjnie ją ocenić, czy też możesz ją całkowicie pominąć. Podobnie jak wiele innych podstawowych pojęć matematycznych.

Cóż, może krótka historia wyjaśni ci, dlaczego NA PEWNO jest to konieczne:

W projekcie, nad którym pracowałem, był program odpowiedzialny za drukowanie wszelkiego rodzaju dokumentów (etykiet, list kompletacyjnych itp.) Program ten składał się z dwóch części, jednej odczytywającej wszystkie niezbędne dane z bazy danych i zapisującej je w Plik w stylu .ini oraz inna część, która odczytuje te pliki i wypełnia je w szablonach. Działa to dość dobrze w przypadku etykiet i małych list (z tylko kilkoma polami), ale działało przez prawie 10 minut, kiedy trzeba było wydrukować „dużą” listę ~ 20 stron. Ponieważ dostęp do tych plików ini spowodował czasy dostępu O (n²), gdzie n jest liczbą pól do wydrukowania.

Gdyby pierwotni programiści tego programu zrozumieli notację O, nigdy by tego nie zrobili. Zastąpienie tej głupoty haszyszem sprawiło, że była o wiele szybsza.

Wydajność Big-O jest ważna, ale została w dużej mierze zinternalizowana.

Wydajność sortowania i wyszukiwania według Big-O nie ma znaczenia, ponieważ ludzie zazwyczaj korzystają z dostarczonych przez system, a te będą tak dobre, jak tylko mogą być (biorąc pod uwagę, że muszą być ogólnie przydatne). Istnieją struktury danych, które są bardziej wydajne dla różnych rzeczy, ale zwykle można je wybierać na ogólnych zasadach (i zwykle są one wbudowane w nowoczesne języki). Istnieje pewne wyczucie algorytmów, które skalują się lub nie skalują.

W rezultacie kwestie formalne rzadko pojawiają się w praktyce, ale praktyka opiera się na tych samych zasadach.

IMHO wiele programów informatycznych pozostawia wielu studentów wędrujących tam wśród chwastów. Programy te nigdy nie przedstawiają pełnego obrazu nauki o obliczeniach. Studenci wchodzą w branżę, zmagając się ze sposobem zastosowania koncepcji, których się nauczyli, z niewielkim wglądem w ich relacje ze światem rzeczywistym.

Powiedziałbym, że sednem nauki o obliczeniach jest umiejętność rozumowania o obliczeniach. Nauczysz się różnych metod i technik, aby to zrobić, i zastosujesz je do abstrakcyjnych problemów, które są prototypowymi prymitywami występującymi w wielu rzeczywistych problemach. Sztuką jest dostrzeżenie tych prototypowych prymitywów w prawdziwym świecie, a następnie rozumowanie takich rzeczy, jak poprawność, złożoność, czas itp., Które, możesz się zgodzić, są prawdziwymi problemami, o które musisz się martwić. Wgląd w zachowanie części często daje wgląd w zachowanie całości. I te same ogólne metody i techniki można również zastosować do całości, ale nie z taką samą rygorystycznością, jaką zapewniają mniejsze, dobrze abstrakcyjne, dobrze określone części. Ale w końcu nauka obliczeń obdarza cię zdolnością do racjonalnego myślenia decyzje o tym, jak zorganizować obliczenia, z prawdziwym wglądem w to, jak będzie się zachowywać w różnych warunkach.

Notatka do siebie !:

Ja i wielu innych zadajemy sobie to pytanie regularnie.

Myślę, że prawdziwym powodem, dla którego o to pytamy, jest to, że jesteśmy leniwi.

Ta wiedza nigdy się nie stanie i nie stanie się przestarzała. Nie możesz stosować go bezpośrednio na co dzień, ale będziesz go używał podświadomie i będzie to miało pozytywny wpływ na twoje decyzje projektowe. Pewnego dnia może to zaoszczędzić Ciebie lub inne godziny i dni kodowania.

Ponieważ coraz więcej problemów jest zamykanych przez biblioteki i narzędzia innych firm i są dostępne dla coraz większej liczby programistów, musisz znać tę wiedzę, aby odróżnić się od innych i pomóc w rozwiązywaniu nowych problemów.

Nie całkiem. Zasadniczo jedyny raz, kiedy o tym myślę, to dostęp do bazy danych. Zwykle patrzę na kod i mówię: „To robi zapytania n + 1, powinieneś to zmienić, aby zrobić tylko 1 lub 2”

Ponieważ wszystkie moje dane są odczytywane z bazy danych i pokazywane użytkownikowi, staram się minimalizować ilość danych, z którymi pracuję, do tego stopnia, że ​​różnica między algorytmem liniowym a algorytmem O (n ^ 2) jest dość duża nieistotny.

Jeśli wystąpi problem, profilujemy go i naprawimy później.

Trzy pytania, które stawiasz i myślę, że krótkie odpowiedzi mogą pomóc w dłuższych argumentach podanych do tej pory.

Jak istotny jest ten test dla rozwoju przemysłu?

Zależy od branży.

Wszędzie tam, gdzie problemem jest szybkość kodu lub przestrzeń kodu, jest to całkowicie istotne dla branży. Często musisz wiedzieć, ile czasu zajmie procedura lub ile zajmie pamięci (w trybie offline / offline).

Jak często korzystasz z niego?

Zależy od branży.

Jeśli wydajność i skalowanie nie mają większego znaczenia dla wykonywanego zadania, rzadko, tylko wtedy, gdy występuje poważny niedobór wydajności. Jeśli jesteś inżynierem bardzo używanego systemu krytycznego, prawdopodobnie na co dzień.

Jak konieczne jest wyuczone podejście do problemu?

Całkowicie konieczne.

Być może będziesz musiał używać go codziennie lub tylko w tragicznych okolicznościach; ale czasami będzie to potrzebne. Najlepiej podczas projektowania, zanim pojawi się problem, niż rozpaczliwie profilować system dławienia.

Powiedziałbym, że to bardzo często. Zasadniczo nie udowadniamy, że coś ma konkretny duży O, ale zinternalizowaliśmy ten pomysł i zapamiętaliśmy / zapoznaliśmy się z gwarancjami dużego O dla określonych struktur danych i algorytmów i wybieramy te najszybsze do określonego zastosowania. Pomaga mieć bibliotekę pełną wszystkich opcji, taką jak biblioteka kolekcji Java lub C ++ STL. Domyślnie i naturalnie używasz big-O każdego dnia, kiedy decydujesz się użyć java.util.HashMap( O(1)odnośnika) zamiast java.util.TreeMap( O(lg n)odnośnika) i na pewno zdecydujesz się nie uruchamiać wyszukiwania liniowego w java.util.LinkedList( O(n)odnośniku) czegoś, co nie wymaga posortowanego dostępu.

Kiedy ktoś wybiera nieoptymalną implementację, a ktoś, kto wie lepiej, przychodzi i widzi swój kod, częścią naszego słownika jest ich poprawianie ”, twoja implementacja zajmuje kwadratowy czas, ale możemy to sprowadzić do n-log-n, wykonując to w ten sposób zamiast tego ”tak naturalnie i automatycznie, jak przy użyciu języka angielskiego, aby zamówić pizzę.

tak

Być może nie musisz przeprowadzać formalnych analiz, ale zrozumienie co do kolejności złożoności algorytmu - i jak porównać dwa algorytmy wokół niego - ma kluczowe znaczenie, jeśli chcesz wykonywać nietrywialne prace i sprawić, by dobrze się sprawdził.

Pracowałem na dwóch różnych systemach, które wydawały się dobre na wczesnym etapie rozwoju, ale sprowadziłem sprzęt na kolana w testach produkcyjnych, ponieważ ktoś użył algorytmu O (n ^ 2). W obu przypadkach poprawka była trywialną zmianą w algorytmie O (n).

Prawdopodobnie jest używany w miejscach, w których opracowują interfejsy API do konsumpcji. C ++ STL jest jednym z niewielu interfejsów API, które mają ograniczenia złożoności nałożone na jego algorytmy. Ale dla codziennego pracującego programisty / starszego programisty / projektanta / architekta nie przychodzi im to do głowy.

Nie uważam tego za ważne poza komunikowaniem pomysłów i pracuję w obszarach krytycznych pod względem wydajności (raytracing, przetwarzanie obrazu i siatki, systemy cząstek, silniki fizyki itp.) I musiałem opracować wiele zastrzeżonych algorytmów i struktur danych podczas pracy w R&D. W tych obszarach często garstka bardzo wydajnych struktur danych i algorytmów może przynieść zupełnie nowe, najnowocześniejsze produkty, podczas gdy wczorajsze algorytmy powodują, że istniejące produkty stają się przestarzałe, dlatego zawsze dąży się do robienia rzeczy bardziej wydajnie. Jednak z zastrzeżeniem, nigdy nie opublikowałem żadnych artykułów na temat opracowanych przeze mnie algorytmów. Wszystkie były zastrzeżone. Gdybym to zrobił, potrzebowałbym pomocy matematyka, aby sformułować dowody i tak dalej.

Jednak moim zdaniem ilość pracy obliczeniowej na iterację jest często bardziej bezpośrednia niż skalowalność algorytmu, chyba że algorytm skaluje się naprawdę słabo. Jeśli ktoś wymyśli najnowocześniejszą technikę raytracingu, bardziej interesują mnie techniki obliczeniowe, takie jak sposób reprezentowania i dostępu do danych niż złożoność algorytmiczna, ponieważ rozsądna skalowalność jest już zapewniona w tym konkurencyjnym i innowacyjnym scenariuszu. Nie możesz być konkurencyjny wymyślając algorytmy, które nie skalują się.

Oczywiście, jeśli porównujesz złożoność kwadratową do liniowej, to ogromna różnica. Ale większość ludzi w mojej dziedzinie jest wystarczająco kompetentna, aby uniknąć zastosowania algorytmu złożoności kwadratowej do imponujących danych wejściowych. Skalowalność jest często głęboko implikowana, a bardziej znaczące i interesujące pytania brzmią: „Czy korzystałeś z GPGPU? SIMD? Czy działa równolegle? Jak reprezentowałeś dane? Czy zreorganizowałeś je dla wzorców dostępu przyjaznych dla pamięci podręcznej? Jak zajmuje dużo pamięci? Czy może solidnie poradzić sobie z tą sprawą? Czy odraczasz pewne przetwarzanie czy robisz to za jednym razem?

Nawet algorytm liniowo-rytmiczny może przewyższyć algorytm liniowo-czasowy, jeśli ten pierwszy uzyskuje dostęp do pamięci w bardziej optymalny sposób, np. Lub lepiej nadaje się do wielowątkowości i / lub SIMD. Czasami nawet algorytm liniowy może przewyższyć algorytm logarytmiczny z tych powodów, a naturalnie algorytmy czasu liniowego przewyższają algorytmy logarytmiczne dla małych wejść.

Dlatego dla mnie ważniejsze są to, co niektórzy nazywają „mikrooptymalizacjami”, takie jak reprezentacje danych (układy pamięci, wzorce dostępu z podziałem pól gorących / zimnych itp.), Wielowątkowość, SIMD, a czasami GPGPU. W dziedzinie, w której wszyscy są już wystarczająco kompetentni, aby używać przyzwoitych i najnowocześniejszych algorytmów do wszystkiego, a nowe artykuły są publikowane przez cały czas, twoja przewaga konkurencyjna w pokonaniu algorytmów nie polega na poprawie złożoności algorytmicznej, ale na bardziej bezpośredniej wydajność obliczeniowa.

Moje pole jest zdominowane przez genialnych matematyków, ale nie zawsze tych, którzy znają obliczeniowy koszt tego, co robią lub wiele sztuczek na niższym poziomie, aby przyspieszyć kod. To zazwyczaj moja przewaga nad nimi w opracowywaniu szybszych i węższych algorytmów i struktur danych, mimo że moje są o wiele mniej skomplikowane. Bawię się tym, co lubi sprzęt, w stronę bitów i bajtów i sprawia, że ​​każda iteracja pracy jest znacznie tańsza, nawet jeśli wykonuję kilka kolejnych iteracji pracy niż naprawdę wyrafinowany algorytm - praca w moim przypadku jest znacznie tańsza. Kod, który piszę, również jest o wiele prostszy. Jeśli ludzie uważają, że mikrooptymalizowane wersje prostych algorytmów i struktur danych są trudne do zrozumienia i utrzymania,

Jako podstawowy przykład wymyśliłem prostą strukturę siatki, która ostatecznie przewyższyła drzewo KD w naszej firmie w zakresie wykrywania kolizji i usuwania zbędnych punktów. Moja głupia, prymitywna siatka była o wiele mniej skomplikowana algorytmicznie i jestem głupsza matematycznie i algorytmicznie niż facet, który zaimplementował drzewo KD w swoim nowatorskim sposobie znajdowania punktu środkowego, ale właśnie dostroiłem pamięć mojej siatki i wzorce dostępu oraz to wystarczyło, by przewyższyć coś znacznie bardziej wyrafinowanego.

Inną zaletą, która pozwala mi przetrwać na polu zdominowanym przez ludzi znacznie mądrzejszych ode mnie, jest po prostu zrozumienie, w jaki sposób działa użytkownik, ponieważ używam oprogramowania, które rozwijam w ten sam sposób. To daje mi pomysły na algorytmy, które naprawdę natychmiast dostosowują się do zainteresowań użytkowników. Jako podstawowy przykład większość ludzi próbuje przyspieszyć takie rzeczy, jak wykrywanie kolizji za pomocą indeksowania przestrzennego. Prawie kilkadziesiąt lat temu poczyniłem prostą obserwację kształtującą karierę dla modeli organicznych, które na przykład, jeśli postać położy dłonie na twarzy, struktura indeksowania przestrzennego będzie musiała rozdzielić węzły i dokonać drogich aktualizacji, jeśli postać potem zdjął rękę z twarzy. Jeśli zamiast tego partycjonujesz na podstawie danych łączności, a nie pozycji wierzchołków, możesz uzyskać stabilną strukturę hierarchiczną, która aktualizuje się bardzo szybko i nigdy nie musi dzielić ani ponownie równoważyć drzewa (musi tylko aktualizować obwiednię w każdej klatce animacji) ... takie rzeczy - algorytmuje dziecko bez ciężkiego tła matematycznego mogliby wymyślić, gdyby po prostu zrozumieli podstawową koncepcję, ale ci, którzy wymykali się matematykom, ponieważ nie myśleli o rzeczach w sposób tak bliski jak pracowali użytkownicy i zbyt dużo myśleli o właściwościach geometrii, a nie o geometrii był powszechnie używany. Dobrze sobie radzę, opierając się bardziej na ogólnej wiedzy obliczeniowej i wiedzy użytkownika końcowego niż na algorytmach. W każdym razie tak naprawdę nie uważałem za tak ważne skupienie się na złożoności algorytmicznej.

Tak, złożoność ma znaczenie w branży. Jeśli w końcu zaprojektujesz coś, w którym ścieżka krytyczna skaluje się jako N-kwadrat (podwojenie liczby czegoś powoduje, że system jest czterokrotnie obciążony), uderzysz w wąskie gardło skalowania znacznie szybciej niż jeśli masz coś, co skaluje się w N.

Jednak zwykle nie jest to robione jako właściwy, formalny dowód, że coś ma określoną złożoność, więc posiadanie dobrej intuicji co do złożoności wzoru operacji jest dobrym początkiem.

Nigdy nie myślę o wielkim O w perspektywie matematycznej, nigdy nie myślę o wielkim O, chyba że o to poproszę. Po prostu widzę algorytm w mojej głowie i mogę stwierdzić, czy jest zły, ponieważ wykonuje wiele pętli w pamięci dla każdego N, czy dzieli i podbija lub coś w tym rodzaju. W razie potrzeby mogę to przełożyć na dużą notację O w kilka sekund, ale łatwiej mi po prostu wiedzieć, jak algorytm / kontener działa z pamięcią, niż myśleć o matematycznej perspektywie.

Pytania zadawane w wywiadach mają na celu sprawdzenie, czy potrafisz wyjaśnić i logicznie myśleć . Ankieter próbuje również dowiedzieć się, czy możesz wykorzystać to, co wiesz, aby rozwiązać związany z tym problem .

Każdy, kto poświęcił jakieś wartościowe studium inżynierii oprogramowania, zetknie się z „Big O”, aby odpowiedzieć na dobre pytanie o „Big O”, musisz także zrozumieć standardowe struktury danych i algorytmy.

Podczas rozmowy z pracownikiem poszukujesz kogoś, kto szybko nauczy się pracy, a nie kogoś, kto zna dany zestaw szczegółowych umiejętności, więc może być bardzo trudno wybrać pytania, które zarówno ankieter, jak i ankieter mają wspólne zrozumienie z.

Zatem pytania dotyczące „dużego O” mogą być bardzo istotne w procesie wywiadu.

Przynajmniej co roku przez długi czas jako programista musiałem naprawiać powolny kod, ponieważ ktoś nie rozumie poprawnych struktur danych i algorytmów, ale możesz rozwiązać te problemy bez szczegółowego zrozumienia Big O. Jednak ludzie, którzy rozumieją namiot Big O, nie unikają tych problemów.