Czy kompetentny programista powinien być w stanie wymyślić własny algorytm najkrótszej ścieżki?

58

Cierpię na kryzys zaufania do moich umiejętności programisty komputerowego.

Wczoraj próbowałem wymyślić własny algorytm najkrótszej ścieżki dla wykresu i po kilku godzinach po prostu rzuciłem ręcznik i nauczyłem się algorytmu Dijkstry.

Czy jest to coś, co dobry programista powinien móc „wynaleźć na nowo” za kilka godzin, czy też jestem nierealny?

No cóż, przynajmniej udało mi się odkryć na nowo sortowanie bąbelkowe: D

Początkujący programista
źródło
7
Ktoś, kto tworzy interfejs użytkownika od 20 lat, prawdopodobnie będzie miał trudności ze znalezieniem rozwiązania problemu z innej domeny w krótkim czasie.
Koder
38
Wydaje mi się, że spędzanie dużo czasu na stronach SE powoduje kryzys zaufania! (Nie to, że to zła rzecz). Szczęściem w życiu jest znalezienie idealnej równowagi między akceptacją tego, co jest, a chęcią ich zmiany.
TrojanName
2
Nie mogłem sam tego wymyślić na nowo, ale staram się pamiętać, jak to działa. upewnij się, że rozumiesz tę animację: upload.wikimedia.org/wikipedia/commons/2/23/…
Job
6
@Brian Tragedia lokalnego geniuszu. Trudno już być najlepszym w czymkolwiek.
Rei Miyasaka
7
dobry komputer naukowiec powinien ale niekoniecznie programista komputerowy lub oprogramowanie inżynier
Neil McGuigan

Odpowiedzi:

118

Dobry programista powinien zdać sobie sprawę, że napisano już świetny algorytm, aby rozwiązać problem i nie marnuje czasu na ponowne wymyślanie kół.

Wątpię, aby Dijkstra opracował algorytm najkrótszej ścieżki w ciągu kilku godzin, więc wydaje się to bardzo wysokim standardem do określania, czy ktoś jest „dobrym programistą”

GSto
źródło
25
@Nakilon - programiści, którzy ignorują istniejące rozwiązania, po prostu marnują czas, a jeśli nie marnują czasu, robią gorsze rozwiązanie. Zobacz: Każdy tworzy własny schemat mieszania haseł kontra bcrypt.
Przywróć Monikę
10
@GSto: według wikipedii, Dijkstra wymyślił algorytm w mniej niż godzinę: 20 minut, zgodnie z pierwszą notatką na wikipedii: en.wikipedia.org/wiki/Dijkstra%27s_algorytm
woliveirajr
9
Jest to względnie prosty algorytm, ale Dijkstra był bardzo utalentowany i został przeszkolony w zakresie fizyki teoretycznej i zaawansowanej matematyki. Nie ma to jak kilka lat pisania dowodów w celu poprawy umiejętności projektowania algorytmów.
kevin cline
19
@woliveirajr - Jestem pewien, że Newton poświęcił tyle samo czasu na opracowanie praw ruchu. Po przemyśleniu tego przez pierwsze 20 lat.
Rook
6
@Nakilon - Tak, dlatego wszyscy piszą wszystko w C, ponieważ w przeciwnym razie jesteś tylko programistą, posługującym się językiem wysokiego poziomu innej osoby. Och, czekaj, mam na myśli asemblację, w przeciwnym razie po prostu używasz języka niskiego poziomu. Och, czekaj, mam na myśli przerzucanie przełączników w celu zmiany obwodów elektrycznych, w przeciwnym razie po prostu używasz zestawu instrukcji innej osoby. Lub wiesz, możesz po prostu użyć tego, co już tam jest i pracować nad stworzeniem czegoś nowego . Po co marnować czas na ponowne wynalezienie algorytmu Dijkstry, skoro można wymyślić coś nowego, na przykład program, który go używa?
Przywróć Monikę
54

Czy jest to coś, co dobry programista powinien móc „wynaleźć na nowo” za kilka godzin, czy też jestem nierealny?

Po pierwsze, być może mylisz programowanie z teoretyczną informatyką. Fantastyczny programista potrzebuje dobrej podstawy informatyki, ale nie musi być fantastyczny. Dijkstra był fantastyczny w informatyce.

Po drugie, spodziewałbym się, że każdy, kto dobrze rozumie wykresy, opracuje własne przemyślenia wykresów po chwili namysłu. Ale nie algorytm najkrótszej ścieżki. W szczególności algorytm Dijkstry jest bardzo wyrafinowany. Kiedy to zrozumiesz, jest to zdecydowanie oczywiste. Ale większość rzeczy jest taka.

Prawdopodobnie możesz wyprowadzić jakiś algorytm najkrótszej ścieżki po wypróbowaniu kilku rzeczy i pozostawieniu pomysłu trochę czasu. Ale nie zawiedź się, jeśli zajmie to godziny, a nawet kilka dni. Jest to całkowicie OK i normalne.

(Uwaga: powinieneś być w stanie brutalnie wymusić problem w ciągu kilku godzin, ale to nie dałoby działającego algorytmu nawet na dość małych wykresach.)

Konrad Rudolph
źródło
56
Nie martw się, jeśli brutalna siła nie działa, po prostu jej nie używasz.
Robbie
2
+1 za rozjaśnienie różnicy między teoretycznym CS a programowaniem. Programowanie jest rozwiązywaniem problemów w świecie rzeczywistym, a teoretyczne CS służy do wspierania programowania. Jednak teoretyczna CS nie jest w 100% niezbędna w codziennym programowaniu większości ludzi.
Phil
17

Czy jest to coś, co dobry programista powinien móc „wynaleźć na nowo” za kilka godzin, czy też jestem nierealny?

Zdecydowanie nierealne. Ludzie nie tylko „wymyślają” algorytmy w ciągu kilku godzin. To wymaga dużo wysiłku i pracy. Aby zacytować tego bloga:

W Programming Pearls, Bentley, cytując Donalda Knutha, mówi: „Podczas gdy pierwsze wyszukiwanie binarne zostało opublikowane w 1946 roku, pierwsze wyszukiwanie binarne, które działa poprawnie dla wszystkich wartości n, pojawiło się dopiero w 1962 roku”.

a wersja Bentleya była również problematyczna, gdy została wdrożona dla dużych zestawów.

Ponadto dobry programista wie, jakie narzędzia są do jego dyspozycji i kiedy ich używać. Nie dostajesz dodatkowych punktów za oryginalność lub robienie rzeczy inaczej - chcesz, żeby działało i działało dobrze.

Maczuga
źródło
1
BlackJack, musiałem dołączyć do tego forum, aby wskazać, że Bentley nie powiedział tego, co twierdziłeś, że powiedział: Knuth to powiedział, a Bentley go zacytował. Kiedy czytałem twój komentarz, pomyślałem, że masz rację, ale lubię weryfikować moje źródła i nigdy nie słyszałem o Bentleyu. Jednak słyszałem o Knuth i mogę zaufać temu, co mówi. Następnym razem sprawdź swoje źródła.
Richard
8
@Richard - komentarz brzmiał: „W Programming Pearls, Bentley mówi…” Knuth był pierwszym, który to powiedział, ale moim źródłem są Programming Pearls, a nie TAoCP, więc napisałem to, co napisał Bentley. Nie twierdziłem, że Bentley jest pomysłodawcą - cytowałem tylko to, co powiedziano w książce. Znaczna część materiałów w książkach nie została wymyślona przez samych autorów, więc nie rozumiem, dlaczego tak to postrzegasz.
BlackJack
Przypisując wycenę wyłącznie Bentleyowi, nie należy się należny kredyt Knutha, a jeśli oświadczenie „Bentleya” było błędne, stawiasz Bentley w sytuacji, w której przedstawił nieprawidłowe informacje, a nie tylko je rozpowszechnił. Ściśle mówiąc, nie powiedziałeś tego, co powiedział Bentley: gdybyś to zrobił, powiedziałbyś: „Bentley powiedział, że Knuth tak powiedział…”. Cytat jest tu dobrze używany, ale jest wyjęty z kontekstu, w którym został wypowiedziane.
Richard
3
@Richard - cytowany przeze mnie cytat pochodzi bezpośrednio z bloga, który cytuje bezpośrednio z książki (dosłownie, myślę, że jest to strona 57 pierwszego wydania). Jeśli masz tak dużo problemów ze stwierdzeniem, skontaktuj się z autorem bloga i poproś go o zmianę.
BlackJack
1
@Richard i BlackJack: Oboje macie rację, ale przypisanie do oryginalnego autora dodaje wiarygodności i kontekstu do oświadczenia. Moja edycja powinna wystarczyć.
Steven Evers,
9

Jest bardzo mało prawdopodobne, że będziesz w stanie znaleźć lepsze rozwiązanie niż te, które możesz wybrać.

Opracowanie algorytmu lepszego niż ten uważany za „najlepszy” (w twoim przypadku najkrótszy) nie jest czymś, co każdy może zrobić. Prawdopodobnie nie jest to nawet możliwe.

Dobry programista powinien być w stanie zrozumieć logikę algorytmu i dlaczego jest on lepszy lub gorszy (lub po prostu nieodpowiedni dla tego konkretnego problemu) niż inne algorytmy, które próbują rozwiązać ten sam problem.

(s) Powinien także wiedzieć, czy to naprawdę najlepszy sposób na rozwiązanie tego konkretnego problemu.

W każdym razie, jeśli chcesz ćwiczyć, nadal możesz spróbować napisać swoją osobistą implementację algorytmu, próbując rozwiązać problem za pomocą umysłu. To może nie być najlepsze, ale jest to dobra praktyka rozwiązywania problemów.

Jose Faeti
źródło
6

To przypomina mi coś, co czytałem o różnicy między „inżynierią oprogramowania” (co nazwałbym programowaniem) a innymi dyscyplinami inżynierii. Pomyśl o tym, myślę, że to była oryginalna książka Design Patterns. Jestem pewien, że ktoś tutaj może zacytować to z głowy.

W każdym razie chodziło o to (choć nie do końca ukierunkowane na projektowanie algorytmów), że dyscypliny inżynierskie są skodyfikowane; żaden inżynier lądowy prawdopodobnie nie poświęci czasu na ponowne wynalezienie wiązki światła, ale programiści robią to cały czas. Problem (i zdaję sobie sprawę, że tylko powtarzam sentyment wielu) polega na tym, że takie zachowanie jest marnotrawne i podatne na błędy i służy ego bardziej niż rozwiązanie.

Informatyka doprowadziła mnie do programowania i uwielbiam oba. Jestem jednak znacznie lepszym programistą niż informatyk. Nigdy nie oskarżałbym cię o niekompetencję, ponieważ po południu nie można było na nowo wymyślić algorytmu Dijkstry. Chciałbym zakwestionować twoje kompetencje jako programisty, jeśli nie potrafisz rozpoznać problemu, który można rozwiązać za pomocą algorytmu grafowego o najkrótszej ścieżce.

To powiedziawszy, uważam, że myślenie o algorytmach oraz próba zaprojektowania i wdrożenia nowych jest (potencjalnie) zabawna i (prawie) zawsze pouczająca. Staram się po prostu oddzielić czas CS od czasu programowania. Dla programistów nasz (szczególnie płatny) czas jest lepiej spędzany na rozwiązywaniu problemów praktycznych niż rozwiązywaniu problemów. Poza tym czas CS prawie zawsze miażdży moją pewność siebie.

Keith Layne
źródło
O ironio ... skoro mogę teraz komentować, czy powinienem usunąć odpowiedź, która zapewniła mi ten przywilej? Powinna być na to odznaka.
Keith Layne
Jest - Zdyscyplinowany , jeśli twoja reputacja zostanie ponownie obliczona, wrócisz do 1.
ChrisF
Tak, właśnie o to mi chodzi ... W tym momencie wykraczałbym poza dyscyplinę. Jeśli przekonwertowałem odpowiedź na komentarz przed usunięciem, mógłbym mieć to wszystko ... Proponuję nową plakietkę o nazwie UberDisciplined dla każdego usunięcia, które powoduje powrót do zupełnie nowego statusu użytkownika. :)
Keith Layne
3

Nie zauważysz tych samych rzeczy, co wszyscy inni. Myślę, że to fakt, z którym musimy żyć. Wiele z nich sprowadza się do biernego uczenia się i modeli mentalnych, które opracowałeś w wyniku ich działania.

Znam bardzo inteligentnych i kompetentnych programistów, których trzeba było nauczyć prawa DeMorgan w szkole, zanim będą mogli to robić konsekwentnie. Zdarzyło mi się, że sam opracowałem Algorytm Dijkstry (i muszę przyznać, że jestem z tego dumny), ale zajęło mi to naprawdę dużo czasu, zanim zrozumiałem sortowanie bąbelkowe.

Bardziej znane jest to, że Einstein, który mógłby być ekspertem w teorii węzłów, nie mógł zawiązać własnych sznurowadeł, dopóki nie skończy około dziesięciu lat.

Są duże szanse, że nieświadomie na nowo odkryłeś wiele rzeczy, których wielu innych nigdy by się nie domyśliło, gdyby nie nauczono ich wyraźnie.

Rei Miyasaka
źródło
3

Błagam, by różnić się tym, co mówi większość odpowiedzi. Chociaż nie spodziewałbym się, że programista na dowolnym poziomie będzie w stanie sam wymyślić algorytm Dijkstry, zdecydowanie oczekiwałbym, że wymyśli jakiś sposób (skuteczny lub nie) rozwiązania problemu.

Na przykład powiedziałeś jako komentarz boczny, że sam możesz wymyślić sortowanie bąbelkowe. Wiem, że to najtrudniejszy z algorytmów sortowania, ale znalazłeś sposób na rozwiązanie problemu i właśnie tego oczekuję od programistów: znaleźć sposób na rozwiązanie problemów.

Oczywiście, sprawdzanie i znajdowanie rozwiązań wykonanych przez innych również działa, ale skrajność tego punktu jest facetem, który nie myśli o sobie i którego programy są kompendium wyszukiwań w Google.

Wydaje mi się, że brzmię ostrzej, niż chciałbym, ale mam na myśli: spodziewałbym się, że programista będzie wystarczająco kreatywny, aby wymyślić rozwiązanie problemu, nawet jeśli rozwiązanie jest błędne lub nieuporządkowane.


Wracając do sprawy, nie sądzę, że powinieneś wymyślić algorytm Dijkstry, ale jeśli masz możliwość napisania algorytmu, wypróbowania kilku możliwości i znalezienia najkrótszej ścieżki bez kończenia się na nieskończonej pętli, to masz moją aprobatę.

(BTW moja aprobata liczy się w tym samym porządku ważności co kupon na bezpłatną myjnię samochodową).

Alfa
źródło
3
Zgadzam się, że tak, kompetentny programista powinien być w stanie wymyślić sortowanie bąbelkowe lub jego odpowiednik. Może to być nawet produktywne wykorzystanie czasu, aby go wdrożyć i wypróbować, być może po prostu w celu lepszego zrozumienia problemu. Ale myślę, że należy powiedzieć, że żaden kompetentny programista nie poszedłby dalej i nie używałby go w kodzie produkcyjnym. W ten sposób Twoi klienci wracają w przyszłym roku i narzekają, że teraz, gdy mają więcej danych do przetworzenia, Twój algorytm O (n!) Zajmie dwa razy więcej czasu niż wszechświat ...
Thomas Padron-McCarthy
Kogo to obchodzi, jeśli potrafisz wymyślić algorytmy, jeśli nie możesz nawet rozpoznać, kiedy jest do bani? Samokrytyka jest dla programisty równie ważna jak kreatywność. Wolę pracować z programistą, który szybko przyznaje, gdy wie, że jego własne rozwiązanie trwa zbyt długo lub jest mało prawdopodobne, aby był najlepszy, niż z programistą, który chce na nowo wymyślić każde koło, ponieważ rujnuje ich ego, aby zrobić inaczej.
Rei Miyasaka
Zgadzam się co do obu kwestii, ale myślę, że mierzymy dwie różne rzeczy. Jednym z nich jest zdolność programisty do rozwiązywania problemów (coś, co uważam za niezbędne). Inną jest samokrytyka (uważam to za niezbędne, ale nie do programowania: na całe życie) i umiejętność oceny kodu (wysoce pożądane). Powiedziałbym również, że rozwiązania, które trwają wiecznie, nie są tak naprawdę rozwiązaniami, prawda? ;)
Alpha
2

Tak, powinien / powinna.

Może to być moralny odpowiednik sortowania bąbelkowego, ale uważam, że dobry programista powinien być w stanie wymyślić co najmniej coś, co działa, jakkolwiek może być nieefektywne.

Nie trzeba dodawać, że jeśli pojawiłby się ten konkretny problem, dobry programista najpierw sprawdziłby, czy jest dla niego biblioteka, lub które opublikowane algorytmy to robią i są łatwe do wdrożenia.

Oczywiście wiele zadań programistycznych jest znacznie mniej trudnych i nie wszyscy muszą być w stanie poradzić sobie z tak trudnymi problemami. Ale będziesz chciał mieć kogoś z takim umysłem w swoim zespole, ponieważ możesz mieć skomplikowane problemy związane z konkretnym projektem, w których nie możesz polegać na wielu wcześniejszych badaniach naukowych.

Hans-Peter Störr
źródło
1

Nie martw się

Jako programista Perla staram się nigdy nie wymyślać koła na nowo. To jest praca CPAN. Jeśli istnieje prosty, dobrze obsługiwany algorytm lub moduł, korzystamy z niego. Jeśli nie jest to dobry moduł, wtedy możemy wymyślać koła. To jedna z największych rzeczy w Perlu.

Mówię więc:

  1. Nie polecam wynajdowania koła, ale kiedy to zrobisz ...
  2. Staraj się nie wymyślać go całkowicie i ...
  3. Nie martw się, jeśli nie możesz tego zrobić. Właśnie dlatego mamy społeczność programistów :-).
Dynamiczny
źródło
Nie chodzi o wymyślanie na nowo, chodzi o ogólne rozwiązywanie problemów. Jeśli nie spróbujesz samodzielnie wymyślać rzeczy, nigdy się nie poprawisz.
Nils,
0

Teoria grafów i stosowane do niej algorytmy wyglądają prosto na powierzchni, ale generalnie są od niej dalekie. Można by pomyśleć, że tworzenie wykresów nieprzecinających się (płaskich) jest proste, na przykład na pierwszy rzut oka. W ubiegłym roku przyjrzałem się temu problemowi (planarność poprzez wyeliminowanie podgrafów Kuratowskiego). Mogę powiedzieć, z tego doświadczenia, że ​​ludzie, którzy piszą te algorytmy, zwykle poświęcają na to czas studiów doktoranckich, a czasami badania są przeprowadzane w zespołach. A jako naukowcy jest to ich jedyna praca skupiona na tym okresie. Nie ma sensu myśleć, że my, inżynierowie na ziemi, możemy oczekiwać tego samego. Jak słusznie powiedział ktoś tutaj, jest to wprost oczywiste, gdy rozwiązanie jest przed tobą. Tak zawsze się dzieje!

Inżynier
źródło
0

Czy jest to coś, co dobry programista powinien móc „wynaleźć na nowo” za kilka godzin, czy też jestem nierealny?

Chciałbym powiedzieć, że jeśli jesteś w stanie samodzielnie opracować algorytm dla znanego problemu, takiego jak Shortest Path, jesteś złym programistą.

Oznaczałoby to, że ignorujesz dość historię problemu najkrótszej ścieżki , przechodząc od algorytmu O (| V | ^ 4) opublikowanego w 1955 r. Do algorytmu O (E + V log V) opublikowanego w 1984 r. (Który jest algorytmem Dijkstry algorytm z drzewami Fibonacciego). Masz prawie gwarancję, że będziesz gorszy niż algorytmy, które już opracowałeś. Co gorsza, istnieje duże prawdopodobieństwo, że w algorytmie występują luki lub błędy, które powodują, że jest on nieprawidłowy. Ponadto prawie na pewno poświęcisz znacznie więcej czasu na przemyślenie algorytmu, wdrożenie go i przetestowanie, niż czas potrzebny na ponowne użycie istniejącego algorytmu.

Pozostaw projekt algorytmów projektantom algorytmów. Programiści są konsumentami ich wyników. Programiści łączą algorytmy i wykorzystują je do wykonywania rzeczywistych zadań. Funkcjonariusz policji nie musi być w stanie wymyślić prawa, aby móc pracować lub być dobrym funkcjonariuszem.

Zachęcam nawet do korzystania z implementacji wykonanych przez ekspertów zamiast samodzielnego wdrażania algorytmów dla każdego umiarkowanie skomplikowanego algorytmu. Jest bardziej prawdopodobne, że jest poprawny, są szanse, że zrobili to szybciej niż kiedykolwiek i zaoszczędzi ci dużo czasu. Jest to szczególnie prawdziwe w przypadku algorytmów kryptograficznych, ponieważ zyskujesz dodatkowe wymagania bezpieczeństwa, które zwykle mogą zapewnić tylko eksperci.

Alex ten Brink
źródło
Algorytmy kryptograficzne są łatwe do zweryfikowania implementacji; znane prawidłowe wektory testowe są dziesiątką za każdy publicznie określony algorytm i jest albo poprawne, albo nie. (Możesz uzyskać nieoptymalną wydajność dzięki niestandardowej implementacji, ale jeśli jest to tylko poprawne, można nad tym popracować.) Trudne w kryptografii są takie rzeczy, jak generowanie liczb losowych, właściwa obsługa surowych kluczy i tabel rozszerzeń kluczy w pamięci, właściwe obsługa danych wejściowych użytkownika (solenie itp.), przechowywanie czegoś, co pozwala dowiedzieć się, czy odszyfrowane dane są prawidłowe i tak dalej.
CVn
Myślałem bardziej o atakach czasowych itp., O czym prawie żaden programista nie wie. Nie zawsze jest to problem, ale mimo to ważny. Ponadto łączenie prymitywów kryptograficznych zwykle nie działa tak, jak można się tego spodziewać, jest to również trudny element bezpieczeństwa.
Alex ten Brink
Chociaż ataki czasowe itp. Są z pewnością ważnym problemem (i nie tylko w kryptografii), argumentowałbym, że podatność implementacji na takie nie ma wpływu na jego poprawność . I istnieje wiele, wiele sposobów, aby ukryć w kryptografii znacznie więcej niż tylko umożliwianie ataków na czas. Bruce Schneier prowadził swoją serię Doghouse ; Ostatnio nic w tym nie widziałem, ale jest tam wiele przykładów ostrzegawczych. google.com/search?q=site%3Aschneier.com+%22the+doghouse%22
CVn