Czy koncepcja złożoności obliczeniowej jest ważna dla twórców oprogramowania? [Zamknięte]

Miałem wrażenie, że pojęcia złożoności czasu i pamięci są koniecznością dla absolwentów kursów compsci, ale po studiach inżynierskich nie wiem, czy tak jest. Ostatnio byłem zaskoczony, że przeprowadziłem wywiad z kilkoma absolwentami miejscowej uczelni, którzy nawet nie znają tej koncepcji. Myślę, że moje pytanie brzmi:

Czy koncepcja złożoności obliczeniowej jest ważna dla twórców oprogramowania? I czy należy tego uczyć na studiach licencjackich?

Na większości uniwersytetów zakładam (mam nadzieję!), Że złożoność czasu i pamięci jest zdecydowanie częścią ich kursów.

Teraz te „złożoności” są bardzo elastycznym tematem. Czy ludzie powinni naprawdę znać całą teorię, np. „ZPP to klasa złożoności problemów decyzyjnych, którą można rozwiązać przy zerowym błędzie na probabilistycznej maszynie Turinga w czasie wielomianowym”. i tego rodzaju rzeczy są wątpliwe. Osobiście uważam te zaawansowane teorie za nieistotne dla rozwoju oprogramowania.

Przeciwnie, uważam, że każdy programista powinien być świadomy złożoności czasowo-przestrzennej stosowanych przez siebie struktur danych i algorytmów.

Wielu początkujących ma obsesję na punkcie mikrooptymalizacji. Nauka komp. Z mojego doświadczenia wynika, że ​​złożoność kieruje studentów w stronę bardziej praktycznego sposobu oceny wydajności i skalowalności.

Z tego, co widziałem, wydaje się, że notacja big-O oraz złożoność czasu i pamięci są bardzo podkreślane w formalnej edukacji informatycznej ... bez względu na to, że są samoukami, ta percepcja opiera się na słuchaniu i czytaniu osób posiadających takie wykształcenie mów i pisz.

Chociaż wierzę, że ogólne idee i koncepcje są ważne, nie sądzę, aby ich formalizacja (taka jak notacja big-O i różnorodna terminologia) miała tak samo duże znaczenie, z wyjątkiem celów komunikacji. To, że ktoś nie zna formalnej notacji i terminologii, nie oznacza, że ​​nie widzi, w jaki sposób i dlaczego jeden algorytm byłby szybszy od drugiego w konkretnym przypadku. Ludzie widzą, że czas potrzebny na przeszukanie zrównoważonego drzewa binarnego odnosi się do logarytmu podstawy 2 liczby węzłów bez uprzedniego poznania teorii złożoności w jakimkolwiek formalnym sensie, jeśli rozumieją, jak działa drzewo i mają rozsądną wiedzę na temat wysokiego matematyka szkolna. Ważne jest, aby wiedzieć, kiedy zwracać uwagę na złożoność i wykorzystanie pamięci, a także brać pod uwagę typowe i najgorsze przypadki, ale ... niektórzy nie.

Notacja i terminologia stają się ważne dla komunikacji. Dają dobry sposób na przekazanie kwantyfikacji wydajności algorytmu komuś innemu. Ponieważ często pojawia się w dokumentach i objaśnieniach, warto mieć co najmniej niejasne zrozumienie, aby łatwiej było je śledzić.

Tak, koncepcje są ważne (choć mniej ważne, gdy zasoby i czas są wystarczające, ale dane nie są). Ale chociaż pojęcia są ważne, ich sformalizowanie często nie jest tak ważne - należy pamiętać, że notacja i terminologia nie są takie same, jak same pojęcia.

Edytować:

Nie twierdziłbym, że rozumiem te pojęcia tak szczegółowo, jak ktoś, kto formalnie studiował, ale wiele ogólnych pomysłów ma sens. Wydaje mi się, że formalne badanie tego ma wartość, ale niektóre z nich mogą istnieć bez tego.

Jeśli chodzi o wprowadzenie pojęć (poza formalnym studium), myślę, że dobrym początkiem jest zachęcenie ludzi do zastanowienia się, ile pamięci zajmują struktury danych, jakie kroki wymagają algorytmy i jak te rzeczy zmieniają się w zależności od różnych danych.

Pomaga również rozważać hipotetyczne sytuacje i zmiany, takie jak rozważenie, co się stanie, jeśli drzewo jest zrównoważone, a co się stanie, jeśli będzie tak niezrównoważone, jak to możliwe, lub ile poziomów w drzewie byłoby w większości węzłów, lub ile więcej węzłów może przytrzymaj, jeśli głębokość zostanie zwiększona o jeden poziom. Ten sposób myślenia jest na ogół przydatny dla programistów, nie tylko patrząc na złożoność; a jeśli zastosuje się je do myślenia o tym, jak algorytmy i struktury danych działają w różnych okolicznościach, w naturalny sposób wskazuje ten sam kierunek, jak w przypadku bardziej formalnego badania złożoności.

tak

Zrozumienie podstaw złożoności jest ważne i powinno być czymś, czego uczysz się jako student. W rzeczywistości myślę, że jest to zazwyczaj poruszane w dowolnej klasie, która uczy cię o strukturach danych. Rozumiem absolwentów, którzy nie rozumieją lub nie pamiętają, ale nie widzę, że nie uczono ich podstaw złożoności.

Aktualizacja: Dlaczego jest to ważne

Miałem migrację bazy danych przy określonym zadaniu. Mieliśmy termin, kiedy migracja musiała zostać wykonana. Osoba, która napisała scenariusz, nie miała złożonego uzasadnienia. Niestety nikt inny nie przyjrzał się logice, której użył w skrypcie. Nie pamiętam szczegółów innych niż to, że używał podwójnie zagnieżdżonej pętli zamiast tablicy mieszającej. Po tygodniu ciągłego działania skryptu przyjrzeliśmy się logice i zdaliśmy sobie sprawę z problemu. Po zmianie zajęło to około 5 godzin. Prawie nie dotrzymaliśmy terminu zakończenia migracji z powodu niezrozumienia złożoności.

Chodzi o to, że łatwo jest przypadkowo zrobić coś o rząd wielkości wolniejszego lub zawsze zabraknie pamięci przed zakończeniem zadania. Chociaż szybsze maszyny z większą pamięcią mogą łagodzić drobne błędy, często nie mogą złagodzić problemów ze złożonością.

Uważam, że pytanie, czy jest „ważne czy nie”, jest raczej niejasne.

Znajdziesz wielu ludzi ewangelizujących, jak ich zdaniem najmniejsza część wiedzy na tym świecie jest ściśle wymagana. Jest to jednak trochę bezcelowe, ponieważ nigdy nie można wiedzieć wszystkiego i nie należy się tego spodziewać, chyba że pomoże to w spełnieniu wymagań stawianych mu przez pracę. Ogólnie wolę bardziej pragmatyczne podejście do wymagań edukacyjnych, chyba że jest to kwestia hobby lub arbitralnych preferencji osobistych.

Czy jest to ważne dla programistów, którzy mają pisać wyjątkowo wydajny kod lub innowacyjne algorytmy infrastrukturalne? Tak.

Czy jest to ważne dla programistów, którzy opracowują konwencjonalne aplikacje internetowe? Mogą poradzić sobie bez niego lub uzyskać wydajne wdrożenia w świecie open source.

Czy jest to ważne dla programistów, którzy opracowują GUI dla aplikacji? Prawdopodobnie nie, ponieważ udane frameworki GUI usuwają wszystkie te małe szczegóły.

Zawsze miło jest wiedzieć, tak jak wszystko, ale nie powstrzymuje wielu (a nawet większości) programistów od wykonywania swojej pracy w sposób zadowalający dla pracodawców.

Z drugiej strony, jeśli zapisano się na studia wyższe, w poszukiwaniu edukacji podstawowej i teoretycznej, należy oczekiwać nauki przedmiotów, które z definicji są bardziej teoretyczne niż praktyczne. Moim zdaniem CompSci jest niezbędne. uczniowie uczą się o złożoności, tak jak ważne jest, aby uczą się rachunku różniczkowego.

Ale tak czy inaczej, od kiedy to robi CompSci. programy uczą ludzi, jak być dobrym programistą? W tym celu masz specjalistyczne programy szkoleniowe i praktyczne doświadczenie (zarówno twoje, jak i innych programistów, którzy mogą dzielić się swoimi programami z tobą).