Во время текущего (2013 г.) конкурса Google Code Jam возникла проблема, которая потребовала от C ++ и Java людей более 200 строк кода по сравнению с людьми из Python, которые решили ту же проблему, используя только 40 строк кода.
Python не напрямую сопоставим с C ++ и Java, но я думаю, что различие в многословности может повлиять на эффективность алгоритма.
Насколько важно знать правильный алгоритм по сравнению с выбором языка? Может ли превосходно реализованная программа Python быть реализована на C ++ или Java лучше (используя тот же алгоритм), и имеет ли это какое-либо отношение к естественному многословию некоторых языков программирования?
java
c++
algorithms
python
superspacemarines
источник
источник
Ответы:
Очевидно, что если вы рассматриваете этот вопрос в контексте чего-то вроде Google Code Jam, то алгоритмическое мышление явно важнее при решении алгоритмических задач.
В повседневной жизни, однако, необходимо учитывать около миллиона других факторов, что делает вопрос гораздо менее черным по сравнению с белым.
Просто контрпример: если вам нужно больше 200 строк в Java, но все в вашей компании знают Java, это не имеет большого значения. Если бы вы могли написать это на 5 строчках Python или на любом другом языке, но вы были бы единственными в компании, кто знал этот язык - это большое дело. На самом деле такое большое дело, что вам даже не разрешат сделать это, а вместо этого придется писать его на Java.
С точки зрения ремесленника, мы всегда стараемся подобрать подходящий инструмент для работы, но слово « прямо там» настолько сложно, что легко ошибиться.
Наоборот, я обнаружил, что алгоритмическое мышление в компаниях практически отсутствует. Этим обладают лишь немногие избранные люди, в то время как у среднего Джо часто возникают проблемы с оценкой сложности циклов, поисков и т. Д.
Однако с точки зрения алгоритмических соревнований мой личный опыт участия в них в течение нескольких лет ясно говорит мне, что вы должны придерживаться одного языка. Скорость является основным фактором, и вы просто не можете позволить себе тратить время на свои инструменты, когда вы должны посвятить его решению проблем в установленные сроки. Также учтите, что написание 200 строк Java-кода без размышлений по-прежнему намного быстрее, чем ручная работа над 50 строками сложного кода на Python, требующего много размышлений и в то же время решающих более или менее одну и ту же проблему.
Ну и, наконец, убедитесь, что вы понимаете основные различия между алгоритмическим кодом конкуренции и кодом компании. Я видел фантастические алгоритмические кодеры, которые написали ужасный код, который я никогда бы не принял в продукте.
источник
Я бы сказал, что даже вне соревнований алгоритмическое мышление важнее, чем знание каждого трюка для конкретного языка.
Конечно, вы хотите знать язык, с которым вы работаете, как можно лучше, но языки приходят и уходят, в то время как способность абстрактно мыслить в терминах алгоритмов является очень переносимым навыком.
Показательный пример: если я правильно помню, некоторое время назад здесь была статья о Программистах, в которой кто-то жаловался на неудачу с FizzBuzz в интервью и обвинял его в недостатке знаний об операторе Java по модулю. Этот вывод неверен - отсутствие знаний о том, как работает модуль, делало его неспособным мыслить алгоритмически о проблеме и решать ее даже в отсутствие специального оператора по модулю. Идем дальше: у Java есть класс Tree - что, если в будущем вам придется работать с языком, который не реализует этот класс? Опять же, способность думать о проблеме важнее специфических для языка деталей.
Я признаю, что примеры являются упрощенными, но они помогают донести эту мысль до конца.
источник
Язык имеет значение.
DARPA и ВМС США провели эксперимент по перестрелке почти 20 лет назад. Победителем побега из темной лошади был Хаскелл. Ada и C ++ были оба представлены; Ява не была.
Примерно в то же время компания Pratt & Whitney провела исследование данных о проектах контроллеров реактивных двигателей, изучив данные карт учета и отслеживания ошибок. Они обнаружили, что Ада удвоила производительность программиста и 1/4 плотности дефектов любого другого языка, который они использовали.
Atari использовала FORTH для разработки видеоигр, и тот факт, что они использовали FORTH, считался чрезвычайно проприетарным.
Комментарии Пола Грэма об использовании LISP хорошо известны. Erann GAT в комментарии на LISP в JPL одинаково убедительны, хотя и не так хорошо известны.
Программное обеспечение Boeing 777 для авионики - это почти вся Ада. Их опыт был очень хорошим, хотя одному крупному субподрядчику пришлось начинать все сначала.
Язык имеет значение.
источник
Некоторые моменты:
Верхние позиции, как правило, занимают C ++ / C / Java, независимо от того, сколько строк кода разница между этим и некоторым другим языком. Это может быть больше из-за того, что лучшие программисты предпочитают эти языки другим, вероятно, из-за их сырой скорости.
К сожалению, вы не можете легко увидеть язык программирования в Google Code Jam, но я скачал несколько лучших, и, насколько я помню, это в основном C / C ++. TopCoder (популярный сайт хостинга соревнований по программированию), в основном, дает схожие результаты.
Поскольку они довольно низкого уровня, я уверен, что вы не сможете легко победить C / C ++ с точки зрения сырого времени выполнения (а Java не слишком сильно отстает). Исходя из моего опыта, динамически типизированные языки, как правило, значительно медленнее, чем языки со статической типизацией. Оптимальное решение может даже не быть достаточно быстрым в некоторых языках, но это не должно быть общим правилом.
Правильный алгоритм жизненно важен. Если вы знали, как решить все проблемы (с высокой степенью детализации) с самого начала, и вы хороший, быстрый программист, вы, скорее всего, выиграете, независимо от того, на каком языке вы кодируете (при условии оптимального решения на этом языке). достаточно быстро).
Прямое количество строк не так уж важно. Получив достаточный опыт программирования, вы поймете, что можете потратить 10 минут на программирование 10 или 200 строк, все зависит от сложности линий. Кроме того, если вы кодировали подобный код сотни раз, вы сможете сделать это довольно быстро. Не стоит также упоминать все макросы, которые топовые C / C ++ кодеры часто используют для оптимизации своего времени кодирования.
Фрэнк делает хорошее замечание - (вне соревнований по программированию) вы не можете заниматься программированием на Python для своей компании, если вся их кодовая база находится на C или где-то еще, вам нужно соответствовать их языку.
Переключение между языками достаточно простое, нелегко накопить многолетние знания алгоритмического мышления. Я готов поспорить, что почти любой отличный программист может переключиться на другой (смутно похожий) язык, скажем, через неделю. Может быть, он / она не будет достаточно хорош, чтобы выиграть соревнования по программированию на этом языке (дайте ему еще 2 недели), но у него не будет основ.
источник
Может ли та же логика быть реализована лучше в C ++? Конечно, может, если под лучшими вы подразумеваете более быструю и более эффективную память. Проблема в том, что количество усилий, необходимых для этого, значительно выше. Кроме того, теоретически вы все равно можете перейти на более низкий уровень и реализовать его в чистом C или даже ASM, что займет еще больше времени, но вы сможете получить еще более оптимизированный код.
Конечно, в случае таких соревнований, как Code Jam или TopCoder, это не так уж важно, так как это всего 40 строк против 200 строк. С другой стороны, в этом типе соревнования важнее всего время / пространство сложности алгоритма. В то время как в реальных приложениях YMMV, в этих типах соревнований алгоритм O (n) , написанный на медленном языке, всегда будет бить O (n²), написанный на самом быстром из языков. Тем более что будет несколько тестов, которые являются худшим сценарием.
Но если не считать конкурсов, если мы говорим о реальных крупных проектах, то это уже не 40 строк против 200 строк. В больших проектах огромная кодовая база становится проблемой. В какой момент вы получите:
C ++ против Python?
Чистый Питон медленный. Вот почему стандартный интерпретатор Python (CPython) написан на C. Практически все со встроенными функциями написаны как высокооптимизированные C. Python также может быть легко использован в сочетании с библиотеками C (через ctypes или как собственные модули cpython ) и с библиотеками C ++. через Boost :: Python . Таким образом, вы можете написать свою высокоуровневую логику на языке Python, который является гибким, позволяет быстро создавать прототипы и адаптировать (это означает, что вы можете потратить больше времени на настройку и улучшение алгоритма). OTOH, вы можете написать свои библиотечные функции более низкого уровня в модуле C или C ++. Отличным примером такого подхода является библиотека SciPy, представляющая собой библиотеку Python, однако в ней используются высокооптимизированные числовые библиотеки, такие как ATLAS, LAPACK, Intel MKL или AMD ACML.
источник
На мой взгляд, то, что люди в разговорной речи считают «языками программирования», - это на самом деле три разные вещи:
Например, когда кто-то поднимает C # в обсуждении, вы можете подумать, что он / она говорит о синтаксисе языка (1), но на 95% уверены, что в обсуждении будет использоваться .Net framework (3). Если вы не разрабатываете новый язык, трудно и обычно бессмысленно выделять (1) и игнорировать (2) и (3). Это связано с тем, что IDE и стандартная библиотека являются «факторами комфорта», которые непосредственно влияют на опыт использования определенного инструмента.
Последние несколько лет я тоже участвовал в Google Code Jam. Впервые я выбрал C ++, потому что он имеет хорошую поддержку для чтения ввода. Например, чтение трех целых чисел из стандартного ввода в C ++ выглядит так:
В то время как в C # то же самое будет выглядеть так:
Это намного больше умственных затрат для простой функциональности. Все становится еще сложнее в C # с многострочным вводом. Может быть, я просто не нашел лучшего пути тогда. В любом случае, я не смог пройти первый раунд, потому что у меня была ошибка, которую я не мог исправить до конца раунда. По иронии судьбы метод чтения ввода запутал ошибку. Проблема была проста, входные данные содержали слишком большое число для 32-битного целого числа. В C #
int.Parse(string)
генерировалось бы исключение, но в C ++ поток ввода файлов устанавливал определенный флаг ошибки и молча терпел неудачу, делая ничего не подозревающего разработчика о проблеме.Оба примера демонстрируют, как использовалась библиотека, а не синтаксис языка. Первый демонстрирует многословие, а другой демонстрирует надежность. Многие библиотеки портированы на несколько языков, и некоторые языки могут использовать библиотеки, которые специально не созданы для них (см. Ответ @ vartec о Python с библиотеками C).
Чтобы обернуть это, знание правильного алгоритма помогает. В соревнованиях по кодированию это очень важно, особенно когда ресурсы, такие как время выполнения и память, намеренно ограничены. В разработке приложений это приветствуется, но, как правило, это не важно. Ремонтопригодность там важнее. Этого можно добиться, применяя правильные шаблоны проектирования, имея хорошую архитектуру, читаемый код и соответствующую документацию, и все эти методы в значительной степени зависят от собственных и сторонних библиотек. Поэтому я считаю более важным знать, какие колеса уже изобретены и как они подходят, а затем сделать мои собственные.
источник
Main
и несколько вещей внутриMain
метода (экземпляр моего входного класса и выходной поток и регистр case).Если вы хотите участвовать в соревнованиях по программированию по расписанию, вы должны выучить самый выразительный язык, допустимый в соревновании. Perl, вероятно, будет лучшим, а затем Ruby или Python. Вам все еще понадобится хорошее средство с алгоритмами, но по крайней мере вы не будете увязать в написании чего-то вроде
вместо того
Не беспокойтесь об изучении нескольких библиотек. Все они очень похожи и документация находится в сети. Свободное владение более выразительными языками сделает вас лучшим (но, возможно, разочарованным) программистом в менее выразительных языках. Обратное не верно.
NB
Разница между 200 строками кода и 40 строками кода огромна, и она еще больше, если она отличается от программы на 200 000 строк и программы на 40 000 строк. Тогда разница между командой из пяти человек плюс менеджер и командой из одного или двух человек.
источник
Любой алгоритм может быть реализован на любом языке программирования. В конце концов, не синтаксис имеет значение. Но использование языка высокого уровня, такого как Python, имеет свои преимущества. Меньше работы и меньше кода. Поэтому для реализации алгоритма в Python вам потребуется меньше строк, чем требуется для языка низкого уровня, такого как C.
Python имеет большинство структур данных, встроенных в его библиотеку. Но в C нам нужно начать с нуля и использовать структуру, чтобы построить все это. Конечно, существуют различия между языком высокого уровня и языком низкого уровня, но язык не должен мешать вам реализовать какой-либо алгоритм.
источник
Хотя экстраполяция примера «40 LoC против 200 LoC», говорящего «ну, только пятая часть от общего LoC, очевидно, быстрее писать, так что это должно быть лучше», может показаться заманчивой, я действительно думаю, что там мало правды.
По моему мнению, оптимизация под наименьшее количество LoC почти никогда не является хорошей идеей. Да, каждый написанный LoC является потенциальной ошибкой, и вам никогда не придется отлаживать то, что вы никогда не писали etcetc. Дело в том, оптимизировать для удобства чтения и развязки. Неважно, если вы решите проблему с помощью регулярного выражения с 20 строками, в отличие от написания модуля 1k LoC. Регулярное выражение будет непрозрачной стеной, чрезвычайно склонной к ошибкам, трудной для понимания, кошмарной для изменения, не изменяющей своего поведения безо всяких изменений и т. Д.
Избавиться от шаблонов и многословия, которые не приносят никакой пользы, все хорошо, но, с другой стороны, используя что-то вроде Java или C #, имея знания о шаблонах проектирования и инструментах, таких как resharper, вы ОЧЕНЬ очень гибки в рефакторинге кода. очистить его с течением времени, сломать вещи и т. д., что было бы НАМНОГО сложнее, если бы вы написали его как гораздо меньший скрипт на python или приложение ruby.
Очень показательное сравнение: я бы предпочел иметь 100 тыс. LoC отрытого кода C #, покрытого тестами, заполненного такими «излишними» вещами, как шаблоны стратегий, фабрики и т. Д., А не 20-килобайтное приложение на python, которое просто «выполняет работу». В 5 раз больше кода или нет, архитектура побеждает каждый день.
Я полностью согласен с тем, что некоторые виды работ проще и удобнее на некоторых языках, но я больше верю в выбор языка на основе того, какие инструменты вам нужны и каковы требования (и которые могут появиться в ближайшем будущем).
источник