Podczas bieżącego (2013) konkursu Google Code Jam wystąpił problem polegający na tym, że C ++ i Java mieli ponad 200 linii kodu w porównaniu do osób w Pythonie, które rozwiązały ten sam problem przy użyciu tylko 40 linii kodu.
Python nie jest bezpośrednio porównywalny z C ++ i Javą, ale różnica w gadatliwości, która, jak sądzę, może mieć wpływ na wydajność algorytmu.
Jak ważna jest znajomość właściwego algorytmu w porównaniu do wyboru języka? Czy doskonale zaimplementowany program Python można lepiej zaimplementować w C ++ lub Javie (przy użyciu tego samego algorytmu) i czy ma to jakiś związek z naturalną gadatliwością niektórych języków programowania?
java
c++
algorithms
python
superpacemaryny
źródło
źródło
Odpowiedzi:
Oczywiście, jeśli rozważymy to pytanie w kontekście czegoś takiego jak Google Code Jam, wówczas myślenie algorytmiczne jest wyraźnie ważniejsze przy rozwiązywaniu problemów algorytmicznych.
W życiu codziennym należy jednak wziąć pod uwagę około milion innych czynników, co sprawia, że pytanie jest znacznie mniej czarne niż białe.
Tylko kontrprzykład: jeśli potrzebujesz 200 kolejnych linii w Javie, ale wszyscy w Twojej firmie znają Javę, to nie jest wielka sprawa. Gdybyś mógł napisać go w 5 wierszach Pythona lub w innym języku, ale byłbyś jedynym w firmie, który znałby ten język - to wielka sprawa. Tak wielka sprawa, że nawet nie będziesz mógł tego robić i zamiast tego będziesz musiał napisać ją w Javie.
Z punktu widzenia Craftman za, zawsze staramy się podchodzić z odpowiednim narzędziem do pracy, ale słowo prawo w nie jest tak trudne, że można łatwo dostać to źle.
Przeciwnie, stwierdziłem, że algorytmiczne myślenie w firmach jest prawie nieobecne. Tylko nieliczne wybrane osoby go posiadają, podczas gdy przeciętny Joe często ma problemy z oszacowaniem złożoności pętli, wyszukiwań itp.
Jeśli chodzi o konkursy algorytmiczne, moje osobiste doświadczenia z kilkuletniej rywalizacji wyraźnie wskazują, że powinieneś trzymać się jednego języka. Szybkość jest głównym czynnikiem i po prostu nie możesz sobie pozwolić na marnowanie czasu na swoje narzędzia, kiedy powinieneś poświęcić je na rozwiązywanie problemów w wyznaczonym terminie. Weź również pod uwagę, że pisanie 200 wierszy kodu Java bez zastanowienia jest wciąż znacznie szybsze niż ręczne tworzenie 50 wierszy skomplikowanego kodu python wymagającego dużo myślenia, ale oba rozwiązują mniej więcej ten sam problem.
No i na koniec upewnij się, że rozumiesz główne różnice między algorytmicznym kodem konkurencji a kodem produkcyjnym firmy. Widziałem fantastyczne kodery algorytmiczne, które napisały okropny kod, którego nigdy nie zaakceptowałbym w produkcie.
źródło
Twierdziłbym, że nawet poza zawodami myślenie algorytmiczne jest ważniejsze niż znajomość każdej sztuczki dla określonego języka.
Oczywiście chcesz jak najlepiej znać język, z którym pracujesz, ale języki przychodzą i odchodzą, a umiejętność abstrakcyjnego myślenia w zakresie algorytmów jest umiejętnością bardzo łatwą do przenoszenia.
Przykład: jeśli dobrze pamiętam, jakiś czas temu tutaj był programista, w którym ktoś narzekał na niepowodzenie FizzBuzz w wywiadzie i obwiniał go za brak wiedzy o operatorze modulo Javy. Ten wniosek jest błędny - brak wiedzy na temat działania modulo sprawił, że nie był w stanie myśleć algorytmicznie o problemie i rozwiązać go, nawet przy braku dedykowanego operatora modulo. Idąc dalej: Java ma klasę drzewa - co jeśli w przyszłości będziesz musiał pracować z językiem, który nie implementuje tej klasy? Ponownie umiejętność myślenia o problemie przebija szczegóły specyficzne dla języka.
Przyznaję, że przykłady są uproszczone, ale pomagają przybliżyć sprawę.
źródło
Język ma znaczenie.
DARPA i marynarka wojenna USA przeprowadziły eksperyment strzelaninowy prawie 20 lat temu. Zwycięzcą uciekającego ciemnego konia został Haskell. Zarówno Ada, jak i C ++ były reprezentowane; Java nie była.
Mniej więcej w tym samym czasie Pratt & Whitney przeprowadził badanie eksploracji danych dotyczące projektów sterowników silników odrzutowych, analizując dane karty czasu i narzędzia do śledzenia błędów. Odkryli, że Ada podwoiła wydajność programisty i gęstość defektów w każdym innym używanym języku.
Atari używał FORTH do opracowywania gier wideo, a fakt, że korzystali z FORTH, był uważany za wyjątkowo zastrzeżony.
Komentarze Paula Grahama dotyczące korzystania z LISP są dobrze znane. Erann GAT za komentarze na LISP w JPL są równie przekonujące, choć nie tak dobrze znane.
Boeing 777 awioniki oprogramowanie jest dość dużo wszystko Ada. Ich doświadczenie było bardzo dobre, chociaż jeden główny podwykonawca musiał zacząć od nowa w połowie strumienia.
Język ma znaczenie.
źródło
Kilka punktów:
Najwyższe pozycje to zwykle C ++ / C / Java, niezależnie od tego, ile wierszy kodu różni się między tym a innym językiem. Może to być bardziej związane z tym, że najlepsi koderzy wybierają te języki spośród innych, prawdopodobnie ze względu na ich szybkość.
Niestety nie można łatwo zobaczyć języka programowania w Google Code Jam, ale pobrałem kilka najlepszych i, o ile pamiętam, są to głównie C / C ++. TopCoder (popularny serwis hostingowy internetowych konkursów programistycznych) ma w większości podobne wyniki.
Ponieważ mają dość niski poziom, jestem pewien, że nie pokonasz C / C ++ pod względem surowego czasu działania (a Java nie pozostawia zbyt wiele w tyle). Z mojego doświadczenia wynika, że języki pisane dynamicznie są zwykle wolniejsze niż języki pisane statycznie. Optymalne rozwiązanie może nawet nie być wystarczająco szybkie w niektórych językach, ale nie powinna to być ogólna zasada.
Właściwy algorytm jest niezbędny. Jeśli od samego początku wiedziałeś, jak rozwiązać wszystkie problemy (bardzo szczegółowo), i jesteś dobrym, szybkim programistą, najprawdopodobniej wygrasz, bez względu na język, w którym kodujesz (przy założeniu optymalnego rozwiązania w tym języku) jest wystarczająco szybki).
Prosta liczba linii nie jest taka wielka. Gdy zdobędziesz wystarczające doświadczenie w programowaniu, będziesz wiedział, że możesz poświęcić 10 minut na programowanie 10 linii lub 200 linii, wszystko zależy od stopnia złożoności linii. Ponadto, jeśli kodujesz podobny kod setki razy, będziesz mógł to zrobić dość szybko. Nie wspominając już o wszystkich makrach, których często używają najlepsi kodery C / C ++ w celu optymalizacji swojego czasu kodowania.
Frank ma rację - (poza konkursami programistycznymi) nie możesz zajmować się kodowaniem w Pythonie dla swojej firmy, jeśli cała baza kodu jest w C lub cokolwiek innego, musisz dostosować się do ich języka.
Przełączanie między językami jest dość łatwe, nie jest łatwo zbudować lata wiedzy na temat algorytmicznego myślenia. Jestem skłonny założyć się, że prawie każdy doskonały programista może przełączyć się na inny (nieco podobny) język w, powiedzmy, tygodniu. Być może on / ona nie będzie wystarczająco dobry, aby wygrać konkursy programistyczne w tym języku (daj mu kolejne 2 tygodnie), ale będzie miał podstawy.
źródło
Czy ta sama logika może być lepiej zaimplementowana w C ++? Oczywiście, że tak, jeśli przez to lepiej rozumiesz szybszą i bardziej wydajną pamięć. Problem polega na tym, że wysiłek wymagany do tego celu jest znacznie wyższy. Co więcej, teoretycznie nadal możesz przejść na niższy poziom i wdrożyć go w czystym C lub nawet ASM, co potrwa jeszcze dłużej, ale możesz mieć jeszcze bardziej zoptymalizowany kod.
Oczywiście w przypadku zawodów takich jak Code Jam czy TopCoder nie jest to biggie, ponieważ ma tylko 40 linii w porównaniu do 200 linii. Z drugiej strony w tego rodzaju zawodach najważniejsze jest złożoność algorytmu w czasie / przestrzeni. Podczas gdy w rzeczywistych aplikacjach, YMMV, w tego rodzaju konkursach algorytm O (n) napisany w najwolniejszym języku zawsze pokonuje O (n²) napisany w najszybszych językach. Zwłaszcza, że będzie wiele testów, które są najgorszym scenariuszem.
Ale pomijając konkursy, jeśli mówimy o dużych projektach z prawdziwego życia, to nie jest to już 40 linii w porównaniu do 200 linii. W dużych projektach ogromna baza kodu zaczyna stanowić problem. W którym momencie dojdziesz do:
C ++ vs Python?
Czysty Python działa wolno. Dlatego standardem interpreter Pythona (CPython) jest napisany w C. Praktycznie wszystkie z wbudowanych funkcji pisanych jako wysoce zoptymalizowanej C. Python również mogą być łatwo wykorzystane w połączeniu z bibliotekami C (poprzez ctypes lub natywnych modułów CPython ) i C bibliotek ++ przez Boost :: Python . W ten sposób możesz napisać logikę wysokiego poziomu w języku Python, który jest elastyczny, umożliwia szybkie prototypowanie i adaptację (co oznacza, że możesz poświęcić więcej czasu na ulepszanie i ulepszanie algorytmu). OTOH, możesz pisać funkcje biblioteki niższego poziomu w module C lub C ++. Świetnym przykładem takiego podejścia jest SciPy, która jest biblioteką Python, ale pod maską wykorzystuje wysoce zoptymalizowane biblioteki numeryczne, takie jak ATLAS, LAPACK, Intels MKL lub ACML AMD.
źródło
Moim zdaniem to, co ludzie potocznie uważają za „języki programowania”, to tak naprawdę trzy osobne rzeczy:
Na przykład, gdy ktoś porusza C # w dyskusji, możesz myśleć, że mówi on o składni języka (1), ale jest 95% pewności, że dyskusja będzie dotyczyła frameworka .Net (3). Jeśli nie projektujesz nowego języka, trudno jest izolować (1) i ignorować (2) i (3). Wynika to z faktu, że IDE i standardowa biblioteka to „czynniki komfortu”, które bezpośrednio wpływają na korzystanie z określonego narzędzia.
W ostatnich latach również uczestniczyłem w Google Code Jam. Po raz pierwszy zdecydowałem się na C ++, ponieważ ma ładne wsparcie dla odczytu danych wejściowych. Na przykład odczyt trzech liczb całkowitych ze standardowego wejścia w C ++ wygląda następująco:
Podczas gdy w C # to samo wyglądałoby tak:
To o wiele więcej kosztów ogólnych dla prostej funkcjonalności. Sprawa staje się jeszcze bardziej skomplikowana w języku C # przy wprowadzaniu multilinii. Może po prostu wtedy nie wymyśliłem lepszego sposobu. W każdym razie nie udało mi się zaliczyć pierwszej rundy, ponieważ miałem błąd, którego nie mogłem naprawić przed końcem rundy. Jak na ironię metoda odczytu danych wejściowych zaciemniła błąd. Problem był prosty, wejście zawierało liczbę, która była zbyt duża dla 32-bitowej liczby całkowitej. W C #
int.Parse(string)
zgłasza wyjątek, ale w C ++ strumień wejściowy do pliku ustawia pewną flagę błędu i nie powiedzie się po cichu, powodując, że niczego nie podejrzewający programista nie będzie wiedział o problemie.Oba przykłady pokazują, w jaki sposób biblioteka była używana, a nie składnia języka. Pierwszy pokazuje gadatliwość, a drugi wiarygodność. Wiele bibliotek jest przeniesionych do wielu języków, a niektóre języki mogą korzystać z bibliotek, które nie zostały specjalnie dla nich zbudowane (patrz odpowiedź @ vartec na temat Pythona z bibliotekami C).
Podsumowując, znajomość właściwego algorytmu pomaga. W konkursach kodowania ma to kluczowe znaczenie, szczególnie gdy zasoby takie jak czas wykonania i pamięć są celowo ograniczone. Przy tworzeniu aplikacji jest to mile widziane, ale generalnie nie jest kluczowe. Utrzymanie jest tam ważniejsze. Można to osiągnąć poprzez zastosowanie prawidłowych wzorców projektowych, dobrą architekturę, czytelny kod i odpowiednią dokumentację, a wszystkie te metody w dużym stopniu zależą od bibliotek wewnętrznych i zewnętrznych. Dlatego uważam, że ważniejsze jest, aby wiedzieć, jakie koła są już wynalezione i jak pasują, a następnie jak zrobić własne.
źródło
Main
i kilkoma elementami wMain
metodzie (instancja mojej klasy wejściowej oraz strumień wyjściowy i pętla spraw).Jeśli chcesz brać udział w konkursach programowania czasowego, powinieneś nauczyć się najbardziej ekspresyjnego języka dozwolonego w konkursie. Perl byłby prawdopodobnie najlepszy, a za nim Ruby lub Python. Nadal będziesz potrzebować dobrego zaplecza z algorytmami, ale przynajmniej nie utkniesz w pisaniu czegoś takiego
zamiast
Nie martw się o naukę kilku bibliotek. Wszystkie są bardzo podobne, a dokumentacja jest dostępna online. Znajomość języków bardziej ekspresyjnych sprawi, że będziesz lepszym (ale być może sfrustrowanym) programistą w mniej ekspresyjnych językach. Przeciwnie nie jest prawdą.
NB
Różnica między 200 liniami kodu a 40 liniami kodu jest ogromna, a nawet większa, gdy jest to różnica między programem 200 000 linii a programem 40 000 linii. To jest różnica między pięcioosobowym zespołem plus menedżerem, a zespołem jednego lub dwóch.
źródło
Dowolny algorytm można zaimplementować w dowolnym języku programowania. W końcu nie liczy się składnia. Ale używanie języka wysokiego poziomu, takiego jak Python, ma swoje zalety. Mniej pracy i mniej kodowania. Aby więc zaimplementować algorytm w Pythonie, potrzebujesz mniej wierszy niż jest to wymagane w języku niskiego poziomu, takim jak C.
W Pythonie większość struktur danych jest wbudowanych w jego bibliotekę. Ale w C musimy zacząć od zera i użyć struktury, aby wszystko zbudować. Z pewnością istnieją różnice między językiem wysokiego i niskiego poziomu, ale język ten nie powinien powstrzymywać Cię przed implementacją jakiegokolwiek algorytmu.
źródło
Chociaż ekstrapolacja przykładu „40 LoC vs 200 LoC”, mówiąc: „cóż, tylko jedna piąta całego LoC jest oczywiście szybsza do pisania, więc musi być lepiej”, może wydawać się kusząca, ale naprawdę uważam, że nie ma tam wiele prawdy.
Moim zdaniem optymalizacja pod kątem najmniejszej liczby LoC prawie nigdy nie jest dobrym pomysłem. Tak, każdy napisany LoC może powodować błędy i nigdy nie musisz debugować tego, czego nigdy nie napisałeś itp. Chodzi o to, aby zoptymalizować czytelność i oddzielenie. Nie ma znaczenia, czy rozwiązujesz problem za pomocą 20-liniowego dużego wyrażenia regularnego, w przeciwieństwie do pisania modułu 1k LoC. Wyrażenie regularne będzie nieprzejrzystą ścianą, niezwykle podatną na błędy, trudną do zrozumienia, koszmarną do zmiany bez zmiany jej zachowania w niewyobrażalny sposób itp.
Pozbycie się podstawki i gadatliwości, która nie wnosi żadnej wartości, jest dobre i dobre, ale z drugiej strony, używając czegoś takiego jak Java lub C #, posiadając wiedzę o wzorcach projektowych i narzędziach takich jak resharper, dajesz tak dużą elastyczność w refaktoryzacji kodu , czyszczenie go z czasem, rozwiązywanie problemów itp., byłoby po prostu DUŻO trudniejsze, gdybyś napisał go jako znacznie mniejszy skrypt Pythona lub aplikację ruby.
Bardzo wymowne porównanie: wolałbym mieć 100k LoC pokrytego testem odsprzęgniętego kodu C #, wypełnionego „nadmiarowymi” rzeczami, takimi jak wzorzec strategii, fabryki itp., Niż 20k pytonową aplikację, która po prostu „załatwia sprawę”. 5 razy więcej kodu lub nie, architektura wygrywa każdego dnia.
W pełni zgadzam się, że niektóre rodzaje pracy są łatwiejsze i wygodniejsze w niektórych językach, ale wierzę bardziej w wybór języka na podstawie potrzebnych narzędzi i wymagań (i może być w najbliższej przyszłości).
źródło