Czy bycie programistą bez wiedzy o złożoności obliczeniowej jest problemem?

Na moim uniwersytecie przydzielono mi ćwiczenie. Zabrałem go do domu i próbowałem zaprogramować algorytm, aby go rozwiązać, było to coś związanego z grafami, znajdowaniem połączonych komponentów, tak myślę.

Potem zrobiłem najbardziej trywialną rzecz, która przyszła mi do głowy, a następnie pokazałem jej wykładowcowi. Po krótkiej obserwacji zauważył, że złożoność środowiska wykonawczego mojego rozwiązania była nie do przecenienia i pokazał coś bardziej wydajnego. I jest tradycja programistów, którzy nie mają pojęcia o złożoności obliczeniowej (byłem jednym z nich), więc czy jest problem, jeśli programista nie ma pojęcia o złożoności obliczeniowej?

Tak, powiedziałbym, że wiedza o złożoności obliczeniowej jest koniecznością dla każdego poważnego programisty. Tak długo, jak nie masz do czynienia z dużymi zestawami danych, nic ci nie będzie, wiedząc o złożoności, ale jeśli chcesz napisać program, który rozwiązuje poważne problemy, potrzebujesz go.

W twoim konkretnym przypadku przykład znalezienia połączonych komponentów mógł zadziałać dla wykresów zawierających do węzłów. Jeśli jednak wypróbujesz wykres z węzłami, algorytm twojego wykładowcy prawdopodobnie poradziłby sobie z tym w ciągu 1 sekundy, podczas gdy twój algorytm zająłby (w zależności od tego, jak złożona była złożoność) 1 godzinę, 1 dzień, a może nawet 1 wieczność.$100$$100.000$

Dość częstym błędem popełnianym przez studentów w naszym kursie algorytmów jest iteracja takiej tablicy:

while array not empty
    examine first element of array
    remove first element from array

To może nie być najpiękniejszy kod, ale w skomplikowanym programie coś takiego może się pojawić bez wiedzy programisty. Jaki jest problem z tym programem?

Załóżmy, że działamy na zestawie danych elementów. W porównaniu z następującym programem poprzedni program będzie działał o wolniej.$100.000$$50.000$

while array not empty
    examine last element of array
    remove last element from array

Mam nadzieję, że zgadzasz się, że posiadanie wiedzy umożliwiającej uruchomienie programu razy szybciej jest prawdopodobnie ważną rzeczą dla programisty. Zrozumienie różnicy między tymi dwoma programami wymaga podstawowej wiedzy na temat teorii złożoności oraz pewnej wiedzy o szczegółach języka, w którym programujesz.$50.000$

W moim języku pseudokodów „usunięcie elementu z tablicy” przesuwa wszystkie elementy na prawo od usuwanego elementu o jedną pozycję z lewej strony. To sprawia, że ​​usunięcie ostatniego elementu jest operacją , ponieważ w tym celu wystarczy interakcja z 1 elementem. Usunięcie pierwszego elementu to ponieważ w celu usunięcia pierwszego elementu musimy przesunąć wszystkie pozostałe elementy jedną pozycję w lewo.O ( n ) n - $O(1)$$O(n)$$n-1$

Bardzo podstawowym ćwiczeniem w złożoności jest udowodnienie, że pierwszy program wykona operacje , podczas gdy drugi program używa tylko operacji. Jeśli podłączysz , zobaczysz, że jeden program jest znacznie bardziej wydajny niż drugi.nn=$\frac{1}{2}n^2$$n$$n=100.000$

To tylko zabawkowy przykład, ale już wymaga podstawowej znajomości złożoności, aby odróżnić oba programy, a jeśli faktycznie próbujesz debugować / zoptymalizować bardziej skomplikowany program, który ma ten błąd, znalezienie jeszcze większego zrozumienia wymaga jeszcze większego zrozumienia gdzie jest błąd. Ponieważ błąd, taki jak usunięcie elementu z tablicy w ten sposób, można bardzo dobrze ukryć przez abstrakcje w kodzie.

Dobre zrozumienie złożoności pomaga również przy porównywaniu dwóch podejść do rozwiązania problemu. Załóżmy, że sam wymyśliłeś dwa różne sposoby rozwiązania problemu z połączonymi komponentami: aby zdecydować między nimi, bardzo przydatne byłoby (szybko) oszacowanie ich złożoności i wybranie lepszego.

Jest to odpowiedź na odpowiedź Toma van der Zandena , która stwierdza, że ​​jest to koniecznością.

Rzecz w tym, że 50 000 razy wolniej nie ma znaczenia (chyba że pracujesz w Google oczywiście).

Jeśli wykonywana operacja zajmie mikrosekundę lub jeśli twoje N nigdy nie przekroczy pewnego progu (duża część kodowania wykonywanego obecnie), NIGDY nie będzie to miało znaczenia. W takich przypadkach myślenie o złożoności obliczeniowej zmarnuje tylko czas (i najprawdopodobniej pieniądze).

Złożoność obliczeniowa jest narzędziem umożliwiającym zrozumienie, dlaczego coś może być wolne lub źle skalowane, i jak to poprawić, ale w większości przypadków jest to przesada.

Jestem profesjonalnym programistą od ponad pięciu lat i nigdy nie potrzebowałem myśleć o złożoności obliczeniowej podczas zapętlania wewnątrz pętli O (M * N), ponieważ zawsze operacja jest naprawdę szybka lub M i N są tak bardzo mały.

Są o wiele ważniejsze, powszechnie używane i trudniejsze rzeczy do zrozumienia dla każdego, kto wykonuje zadania programistyczne (gwintowanie i profilowanie to dobre przykłady w obszarze wydajności).

Oczywiście są pewne rzeczy, których nigdy nie będziesz w stanie zrobić bez zrozumienia złożoności obliczeniowej (na przykład: znalezienie anagramów w słowniku), ale przez większość czasu nie potrzebujesz tego.

Tworzę oprogramowanie od około trzydziestu lat, pracując zarówno jako wykonawca, jak i pracownik, i odniosłem z tym duży sukces. Moim pierwszym językiem był BASIC, ale szybko nauczyłem się języka maszynowego, aby uzyskać przyzwoitą prędkość z mojego słabego komputera. Przez lata spędziłem wiele czasu w profilowaniu i nauczyłem się dużo o tworzeniu szybkiego, zoptymalizowanego pod kątem pamięci kodu.

Niezależnie od tego, jestem samoukiem. Nigdy nie spotkałem notacji O, dopóki nie zacząłem przeprowadzać wywiadów kilka lat temu. Nigdy nie pojawia się w mojej pracy zawodowej Z WYJĄTKIEM podczas wywiadów. Musiałem więc nauczyć się podstaw, aby poradzić sobie z tym pytaniem w wywiadach.

Czuję się jak muzyk jazzowy, który nie potrafi czytać nut. Nadal mogę grać dobrze. Wiem o hashtable (cholera, wymyśliłem hashtable, zanim dowiedziałem się, że zostały już wynalezione) i innych ważnych struktur danych, a może nawet znam pewne sztuczki, których nie uczą w szkole. Ale myślę, że prawda jest taka, że ​​jeśli chcesz odnieść sukces w tym zawodzie, albo będziesz musiał przejść niezależność, albo poznać odpowiedzi na pytania, które zadadzą podczas wywiadów.

Nawiasem mówiąc, ostatnio przeprowadzałem wywiad dla roli programisty frontonu. Zadali mi pytanie, gdzie odpowiedź wymaga zarówno znajomości złożoności obliczeniowej, jak i logarytmów. Udało mi się zapamiętać dość matematyki sprzed dwudziestu lat, aby odpowiedzieć na nią mniej więcej poprawnie, ale było to trochę denerwujące. Nigdy nie musiałem używać logarytmów w żadnym rozwoju frontonu.

Powodzenia!

Pytanie jest dość subiektywne, więc myślę, że odpowiedź zależy .

Nie ma to większego znaczenia, jeśli pracujesz z małą ilością danych. W takich przypadkach zwykle dobrze jest użyć dowolnej, np. Standardowej biblioteki języka.

Jeśli jednak masz do czynienia z dużymi ilościami danych lub z jakiegoś innego powodu nalegasz, aby Twój program był szybki, musisz zrozumieć złożoność obliczeniową. Jeśli nie, to skąd wiesz, jak rozwiązać problem lub jak szybko można go nawet rozwiązać? Ale zrozumienie samej teorii nie wystarczy, aby być naprawdę dobrym programistą. Uważam, że aby stworzyć wyjątkowo szybki kod, musisz także zrozumieć, jak np. Działa twoja maszyna (pamięci podręczne, układ pamięci, zestaw instrukcji) i co robi twój kompilator (kompilatory robią wszystko, co w ich mocy, ale nie są doskonałe).

Krótko mówiąc, myślę, że zrozumienie złożoności wyraźnie czyni cię lepszym programistą.

Jest to z pewnością problem, jeśli ktoś, kto opracowuje znaczące algorytmy, nie rozumie złożoności algorytmu. Użytkownicy algorytmu zasadniczo polegają na dobrej jakości implementacji, która ma dobrą charakterystykę wydajności. Chociaż złożoność nie jest jedynym czynnikiem wpływającym na charakterystykę wydajności algorytmu, jest znacząca. Ktoś, kto nie rozumie złożoności algorytmu, ma mniejsze szanse na opracowanie algorytmów o użytecznej charakterystyce wydajności.

Jest to mniejszy problem dla użytkowników algorytmu, zakładając, że dostępne algorytmy są dobrej jakości. Odnosi się to do programistów, którzy używają języków, które mają znaczną, dobrze określoną, standardową bibliotekę - muszą tylko wiedzieć, jak wybrać algorytm, który spełnia tam potrzeby. Problem polega na tym, że jest w nich wiele algorytmów pewnego rodzaju (powiedzmy sortowania) dostępnych w bibliotece, ponieważ złożoność jest często jednym z kryteriów wyboru. Deweloper, który nie rozumie złożoności, nie jest w stanie zrozumieć podstaw wyboru skutecznego algorytmu dla danego zadania.

Są też programiści, którzy koncentrują się (z braku lepszego opisu) na problemach nie algorytmicznych. Na przykład mogą skupić się na tworzeniu intuicyjnych interfejsów użytkownika. Tacy programiści często nie będą musieli martwić się o złożoność algorytmu, chociaż znowu mogą polegać na wysokiej jakości bibliotekach lub innym kodzie.

Zależy, ale nie od ilości danych, z którymi pracujesz, ale od rodzaju pracy, którą wykonujesz, tworzonych programów.

Nazwijmy programistą, który nie wie o złożoności pojęciowej, programistą noobish.

Programista noobish potrafi:

• tworzyć bazy danych big data - nie musi wiedzieć, jak to działa w środku, wszystko, co musi wiedzieć, to zasady tworzenia baz danych. Wie takie rzeczy: co powinno być indeksowane, ... gdzie lepiej jest nadmiarowość danych, gdzie nie jest ...
• tworzyć gry - musi on po prostu przestudiować działanie silnika gry i postępować zgodnie z jego paradygmatami, gry i grafika komputerowa to dość duże problemy z danymi. Rozważ 1920 * 1080 * 32bit = cca 7,9 MB dla pojedynczego zdjęcia / klatki ... @ 60 FPS to co najmniej 475 MB / s. Weź pod uwagę, że tylko jedna niepotrzebna kopia obrazu pełnoekranowego zmarnowałaby około 500 MB przepustowości pamięci na sekundę. Ale nie musi się tym przejmować, ponieważ używa tylko silnika!

Programista noobish nie powinien:

• opracowuj bardzo często używane złożone programy bez względu na rozmiar danych, z którymi współpracuje, ... na przykład małe dane nie spowodują zauważalnego wpływu niewłaściwego rozwiązania podczas programowania, ponieważ będzie wolniejsze niż czas kompilacji itp. Tak więc, 0,5 sekunda dla jednego prostego programu nie jest aż tak duża z perspektywy noobish programiście, rozważ serwer server, który uruchamia ten program dwadzieścia razy na sekundę. Wymagałoby 10 rdzeni, aby móc utrzymać ten ładunek!
• opracowywać programy dla urządzeń wbudowanych. Urządzenia osadzone działają z małymi danymi, ale muszą być tak wydajne, jak to możliwe, ponieważ nadmiarowe operacje powodują niepotrzebne zużycie energii

Tak więc programista noobish jest w porządku, gdy chcesz po prostu korzystać z technologii. Jeśli więc chodzi o opracowywanie nowych rozwiązań, niestandardowych technologii itp., Lepiej zatrudnić programistę noobish.

Jeśli jednak firma nie rozwija nowych technologii, wykorzystuje tylko te, które już zostały stworzone. Zatrudnianie wykwalifikowanych i utalentowanych programistów byłoby marnotrawstwem. To samo dotyczy, jeśli nie chcesz pracować nad nowymi technologiami i dobrze jest wprowadzać pomysły klientów w projekty i programy przy użyciu już stworzonych ram, to marnowanie czasu na naukę czegoś, czego nigdy nie będziesz potrzebować, z wyjątkiem jeśli to twoje hobby i lubisz logiczne wyzwania.

Jestem nieco niezdecydowany, by napisać tutaj odpowiedź, ale odkąd zacząłem podrywać innych ”[niektóre z moich komentarzy zostały przeniesione na czat], oto jak to widzę ...

Istnieje wiele poziomów wiedzy na temat wielu zagadnień z zakresu informatyki (i pod tym pojęciem rozumiem z grubsza związek informatyki z technologią informatyczną). Złożoność obliczeń z pewnością jest ogromną dziedziną (czy wiesz, co to jest OptP? Czy też twierdzenie Abiteboul-Vianu?), A także przyznaje dużą głębię: większość osób ze stopniem CS nie może przedstawić dowodów eksperckich, które są przedmiotem badań publikacje o złożoności obliczeniowej.

Poziom wiedzy i umiejętności / kompetencji wymagany w takich sprawach zależy w dużej mierze od tego, nad czym się pracuje. Całkowicie nieświadome sortowanie O ( ) jest czasem uważane za główną przyczynę powolnych programów ^{[potrzebne źródło]} , ale w artykule SIGCSE z 2003 r. Zauważono: „Sortowanie wstawiane jest używane do sortowania małych (pod) tablic w standardowych bibliotekach Java i C ++. „ Z drugiej strony, przedwczesna optymalizacja pochodząca od kogoś, kto nie rozumie, co oznacza asymptoza (złożoność obliczeniowa jest taką miarą), jest czasem problemem w praktyce programowania. Jednak wiedza o tym, kiedy liczy się złożoność obliczeniowa, jest powodem, dla którego musisz mieć jakieś wskazówki, przynajmniej na poziomie licencjackim.$n^2$

Szczerze mówiąc, odważyłbym się porównać sytuację, w której wiem, kiedy zastosować koncepcje złożoności obliczeniowej (i wiedzieć, kiedy można je bezpiecznie zignorować) z dość powszechną praktyką (poza światem Java) wdrażania jakiegoś wrażliwego na kod kodu w C i niewrażliwego na wydajność rzeczy w Pythonie itp. (Nawiasem mówiąc, nazywało się to w trakcie rozmowy Julii „standardowym kompromisem” ). Wiedząc, kiedy nie musisz myśleć o wydajności, oszczędzasz czas programowania, co jest dość cennym towarem.

I jeszcze jedna kwestia: znajomość złożoności obliczeniowej nie spowoduje, że będziesz dobry w optymalizacji programów; musisz zrozumieć więcej rzeczy związanych z architekturą, takich jak lokalizacja pamięci podręcznej, [czasami] potokowanie, a obecnie także programowanie równoległe / wielordzeniowe; ten drugi ma zarówno własną teorię złożoności, jak i względy praktyczne; przedsmak tego ostatniego z artykułu SOSP z 2013 r. „Każdy schemat blokowania ma piętnaście minut sławy. Żaden z dziewięciu schematów blokowania, który uważamy za konsekwentnie, nie przewyższa żadnego innego, na wszystkich docelowych architekturach lub obciążeniach. Ściśle mówiąc, aby szukać optymizmu, Dlatego algorytm blokady należy wybrać na podstawie platformy sprzętowej i oczekiwanego obciążenia. ”

Jeśli nie znasz big-O, powinieneś się tego nauczyć. To nie jest trudne i bardzo przydatne. Zacznij od wyszukiwania i sortowania.

Zauważam, że wiele odpowiedzi i komentarzy zaleca profilowanie i prawie zawsze oznacza użycie narzędzia do profilowania .

Problem polega na tym, że narzędzia do profilowania są rozmieszczone po całej mapie pod względem ich skuteczności w znajdowaniu tego, czego potrzebujesz, aby przyspieszyć. Tutaj wymieniłem i wyjaśniłem nieporozumienia, na które cierpią profilerzy.

W rezultacie programy, jeśli są większe niż ćwiczenie akademickie, mogą zawierać śpiące olbrzymy , których nawet najlepszy automatyczny profiler nie może ujawnić. Ten post pokazuje kilka przykładów tego, jak problemy z wydajnością mogą ukryć się przed profilerami.

Ale nie mogą ukryć się przed tą techniką.