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

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ą”

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.)

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.

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.

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.

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.

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ą).

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.

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 :-).

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!

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.