Является ли алгоритм более важным, чем язык программирования?

35

Во время текущего (2013 г.) конкурса Google Code Jam возникла проблема, которая потребовала от C ++ и Java людей более 200 строк кода по сравнению с людьми из Python, которые решили ту же проблему, используя только 40 строк кода.

Python не напрямую сопоставим с C ++ и Java, но я думаю, что различие в многословности может повлиять на эффективность алгоритма.

Насколько важно знать правильный алгоритм по сравнению с выбором языка? Может ли превосходно реализованная программа Python быть реализована на C ++ или Java лучше (используя тот же алгоритм), и имеет ли это какое-либо отношение к естественному многословию некоторых языков программирования?

superspacemarines
источник
16
Было сказано (и я верю в это), что язык программирования, на котором вы работаете, влияет на то, как вы думаете о проблеме. Это подразумевает, что очень разные языки программирования могут подходить для разных классов задач.
Йорис Тиммерманс
1
Многое из этого полностью зависит от масштаба, над которым вы работаете за пределами LOC. Некоторые языки просто не поддерживают ни скорость, ни требования параллелизма. Алгоритмы важны, но иногда, если язык x в y раз медленнее, чем язык z, вы просто не можете использовать x независимо от многословия.
Рог
Как примечание, единственное, что я узнал в школе, - это то, что у каждого есть ошибка в строках кода, которая остается постоянной независимо от используемого кода. Таким образом, если язык, который позволяет вам делать это с меньшим количеством строк кода, приводит к меньшему количеству ошибок, вы можете быстрее выводить его на рынок и тем меньше вероятность появления ошибки при ее использовании пользователем. Так что, на мой взгляд, я бы выбрал лучший язык для работы, которую все остальные в компании знают, что требуется для работы над этим проектом.
Трэвис Пессетто
5
@Travis: «процент дефектов на SLOC остается постоянным независимо от языка», но это не так. Смотрите ответ Джона.
Бен Фойгт
Теперь я думаю о том, чтобы принять участие в следующем конкурсе, используя язык F #!
code4life

Ответы:

73

Очевидно, что если вы рассматриваете этот вопрос в контексте чего-то вроде Google Code Jam, то алгоритмическое мышление явно важнее при решении алгоритмических задач.

В повседневной жизни, однако, необходимо учитывать около миллиона других факторов, что делает вопрос гораздо менее черным по сравнению с белым.

Просто контрпример: если вам нужно больше 200 строк в Java, но все в вашей компании знают Java, это не имеет большого значения. Если бы вы могли написать это на 5 строчках Python или на любом другом языке, но вы были бы единственными в компании, кто знал этот язык - это большое дело. На самом деле такое большое дело, что вам даже не разрешат сделать это, а вместо этого придется писать его на Java.

С точки зрения ремесленника, мы всегда стараемся подобрать подходящий инструмент для работы, но слово « прямо там» настолько сложно, что легко ошибиться.

Наоборот, я обнаружил, что алгоритмическое мышление в компаниях практически отсутствует. Этим обладают лишь немногие избранные люди, в то время как у среднего Джо часто возникают проблемы с оценкой сложности циклов, поисков и т. Д.

Однако с точки зрения алгоритмических соревнований мой личный опыт участия в них в течение нескольких лет ясно говорит мне, что вы должны придерживаться одного языка. Скорость является основным фактором, и вы просто не можете позволить себе тратить время на свои инструменты, когда вы должны посвятить его решению проблем в установленные сроки. Также учтите, что написание 200 строк Java-кода без размышлений по-прежнему намного быстрее, чем ручная работа над 50 строками сложного кода на Python, требующего много размышлений и в то же время решающих более или менее одну и ту же проблему.

Ну и, наконец, убедитесь, что вы понимаете основные различия между алгоритмическим кодом конкуренции и кодом компании. Я видел фантастические алгоритмические кодеры, которые написали ужасный код, который я никогда бы не принял в продукте.

Фрэнк
источник
1
+1 для «миллиона других факторов, которые необходимо учитывать»
ozz
1
Я добавлю к этому, что если вы пытаетесь решить функциональную проблему, то ради всего святого, пожалуйста, используйте функциональный язык! Поэтому я бы сказал, что вы должны придерживаться одного языка для каждой основной парадигмы программирования.
Мартейн Вербург
6
+1 за последнее предложение.
Shivan Dragon
4
+1 Строки кода - ужасная метрика сама по себе. Нам нужно измерять ремонтопригодность , а не строки кода. 200 строк кодобезопасного кода потенциально могут быть намного более удобны в обслуживании, чем 50 строк Python.
Фил
2
@Phil: 200 строк Python могут быть гораздо более удобны в обслуживании, чем 50 строк кода, безопасного для типов. Я никогда не видел такого преимущества ясности в типобезопасных языках, при условии хорошо написанного кода.
Дэвид Торнли
17

Я бы сказал, что даже вне соревнований алгоритмическое мышление важнее, чем знание каждого трюка для конкретного языка.

Конечно, вы хотите знать язык, с которым вы работаете, как можно лучше, но языки приходят и уходят, в то время как способность абстрактно мыслить в терминах алгоритмов является очень переносимым навыком.

Показательный пример: если я правильно помню, некоторое время назад здесь была статья о Программистах, в которой кто-то жаловался на неудачу с FizzBuzz в интервью и обвинял его в недостатке знаний об операторе Java по модулю. Этот вывод неверен - отсутствие знаний о том, как работает модуль, делало его неспособным мыслить алгоритмически о проблеме и решать ее даже в отсутствие специального оператора по модулю. Идем дальше: у Java есть класс Tree - что, если в будущем вам придется работать с языком, который не реализует этот класс? Опять же, способность думать о проблеме важнее специфических для языка деталей.

Я признаю, что примеры являются упрощенными, но они помогают донести эту мысль до конца.

ACEG
источник
14

Язык имеет значение.

DARPA и ВМС США провели эксперимент по перестрелке почти 20 лет назад. Победителем побега из темной лошади был Хаскелл. Ada и C ++ были оба представлены; Ява не была.

Примерно в то же время компания Pratt & Whitney провела исследование данных о проектах контроллеров реактивных двигателей, изучив данные карт учета и отслеживания ошибок. Они обнаружили, что Ада удвоила производительность программиста и 1/4 плотности дефектов любого другого языка, который они использовали.

Atari использовала FORTH для разработки видеоигр, и тот факт, что они использовали FORTH, считался чрезвычайно проприетарным.

Комментарии Пола Грэма об использовании LISP хорошо известны. Erann GAT в комментарии на LISP в JPL одинаково убедительны, хотя и не так хорошо известны.

Программное обеспечение Boeing 777 для авионики - это почти вся Ада. Их опыт был очень хорошим, хотя одному крупному субподрядчику пришлось начинать все сначала.

Язык имеет значение.

Джон Р. Штром
источник
Очевидно, что Java была выпущена после того эксперимента, на который вы ссылаетесь.
toasted_flakes
статья была выпущена в 1994 году. Первый публичный выпуск Java был в 1995 году.
Алессандро Теруцци
Дело не в том, что ваш любимый язык был или не был представлен в одном конкретном эксперименте. Дело в том, что язык имеет значение. Было много анекдотических исследований, которые показывают это довольно убедительно. Стоит также отметить, что, несмотря на то, что в основном американские программисты отвергают его, Ada по-прежнему активно используется в Европе, особенно для высоконадежных систем, и все еще используется в некоторых полевых системах в США.
Джон Р. Штром
7

Некоторые моменты:

  • Верхние позиции, как правило, занимают C ++ / C / Java, независимо от того, сколько строк кода разница между этим и некоторым другим языком. Это может быть больше из-за того, что лучшие программисты предпочитают эти языки другим, вероятно, из-за их сырой скорости.
    К сожалению, вы не можете легко увидеть язык программирования в Google Code Jam, но я скачал несколько лучших, и, насколько я помню, это в основном C / C ++. TopCoder (популярный сайт хостинга соревнований по программированию), в основном, дает схожие результаты.

  • Поскольку они довольно низкого уровня, я уверен, что вы не сможете легко победить C / C ++ с точки зрения сырого времени выполнения (а Java не слишком сильно отстает). Исходя из моего опыта, динамически типизированные языки, как правило, значительно медленнее, чем языки со статической типизацией. Оптимальное решение может даже не быть достаточно быстрым в некоторых языках, но это не должно быть общим правилом.

  • Правильный алгоритм жизненно важен. Если вы знали, как решить все проблемы (с высокой степенью детализации) с самого начала, и вы хороший, быстрый программист, вы, скорее всего, выиграете, независимо от того, на каком языке вы кодируете (при условии оптимального решения на этом языке). достаточно быстро).

  • Прямое количество строк не так уж важно. Получив достаточный опыт программирования, вы поймете, что можете потратить 10 минут на программирование 10 или 200 строк, все зависит от сложности линий. Кроме того, если вы кодировали подобный код сотни раз, вы сможете сделать это довольно быстро. Не стоит также упоминать все макросы, которые топовые C / C ++ кодеры часто используют для оптимизации своего времени кодирования.

  • Фрэнк делает хорошее замечание - (вне соревнований по программированию) вы не можете заниматься программированием на Python для своей компании, если вся их кодовая база находится на C или где-то еще, вам нужно соответствовать их языку.

  • Переключение между языками достаточно простое, нелегко накопить многолетние знания алгоритмического мышления. Я готов поспорить, что почти любой отличный программист может переключиться на другой (смутно похожий) язык, скажем, через неделю. Может быть, он / она не будет достаточно хорош, чтобы выиграть соревнования по программированию на этом языке (дайте ему еще 2 недели), но у него не будет основ.

Dukeling
источник
Ложь: загрузка нескольких решений с некоторых сайтов, посвященных конкурсу кода, является окончательным научным исследованием, достаточным для того, чтобы сделать вывод, что вы точно знаете, как выглядят лидирующие позиции.
Ложь Райан
@LieRyan Правда, но участие в нескольких десятках соревнований по программированию (как у меня) на (возможно) самом популярном таком сайте (TopCoder) и постоянное наблюдение большинства топовых позиций в качестве C / C ++ / Java довольно значимо. Кроме того, я сказал «склонен», а не «всегда».
Dukeling
не согласен с тем, что «прямое количество строк не такая уж большая проблема». код враг
JK.
6
@jk. Должен ли я выделить «такой»? Это важно, но это не альфа и омега. Вы предпочитаете на несколько строк меньше читабельности? Я уверен, что нет. Я возьму несколько простых операторов if в очень запутанное, нечитаемое, смещающее бит, умножение, деление, сложение, вычитание, XORing, ANDing, мульти-условное выражение в любой день. Возможно, не то, о чем вы говорили, но вот к чему иногда сводится сокращение количества строк. И я больше говорил о реализации чего-то сложного в несколько строк или чего-то простого во многих строках; последнее часто занимает меньше времени.
Dukeling
5

Может ли та же логика быть реализована лучше в 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.

Vartec
источник
То, что ты пишешь, только царапает поверхность. Вы принимаете понятие «лучше», которое разделяют не все. Качество - это всегда вопрос соответствия целям. Программирование на C ++ не всегда подходит для каждой цели.
reinierpost
1
@reinierpost: вот почему я написал о значительно больших усилиях. В тех случаях, когда вы упоминаете, что C ++ не подходит, но не потому, что это невозможно сделать. Это плохо подходит, потому что это потребует слишком много ресурсов для разработчиков.
vartec
Более того, в этом случае не лучше.
reinierpost
2
и на самом деле это то, что происходит во многих отраслях, например, в играх много кода Lua, который склеивает код C ++ вместе для производительности и производительности.
gbjbaanb
4

На мой взгляд, то, что люди в разговорной речи считают «языками программирования», - это на самом деле три разные вещи:

  1. Тип языка и синтаксис
  2. Language IDE
  3. Доступные библиотеки для языка

Например, когда кто-то поднимает C # в обсуждении, вы можете подумать, что он / она говорит о синтаксисе языка (1), но на 95% уверены, что в обсуждении будет использоваться .Net framework (3). Если вы не разрабатываете новый язык, трудно и обычно бессмысленно выделять (1) и игнорировать (2) и (3). Это связано с тем, что IDE и стандартная библиотека являются «факторами комфорта», которые непосредственно влияют на опыт использования определенного инструмента.

Последние несколько лет я тоже участвовал в Google Code Jam. Впервые я выбрал C ++, потому что он имеет хорошую поддержку для чтения ввода. Например, чтение трех целых чисел из стандартного ввода в C ++ выглядит так:

int n, h, w;
cin >> n >> h >> w;

В то время как в C # то же самое будет выглядеть так:

int n, h, w;
string[] tokens = Console.ReadLine().Split(' ');
n = int.Parse(tokens[0]);
h = int.Parse(tokens[1]);
w = int.Parse(tokens[2]);

Это намного больше умственных затрат для простой функциональности. Все становится еще сложнее в C # с многострочным вводом. Может быть, я просто не нашел лучшего пути тогда. В любом случае, я не смог пройти первый раунд, потому что у меня была ошибка, которую я не мог исправить до конца раунда. По иронии судьбы метод чтения ввода запутал ошибку. Проблема была проста, входные данные содержали слишком большое число для 32-битного целого числа. В C # int.Parse(string)генерировалось бы исключение, но в C ++ поток ввода файлов устанавливал определенный флаг ошибки и молча терпел неудачу, делая ничего не подозревающего разработчика о проблеме.

Оба примера демонстрируют, как использовалась библиотека, а не синтаксис языка. Первый демонстрирует многословие, а другой демонстрирует надежность. Многие библиотеки портированы на несколько языков, и некоторые языки могут использовать библиотеки, которые специально не созданы для них (см. Ответ @ vartec о Python с библиотеками C).

Чтобы обернуть это, знание правильного алгоритма помогает. В соревнованиях по кодированию это очень важно, особенно когда ресурсы, такие как время выполнения и память, намеренно ограничены. В разработке приложений это приветствуется, но, как правило, это не важно. Ремонтопригодность там важнее. Этого можно добиться, применяя правильные шаблоны проектирования, имея хорошую архитектуру, читаемый код и соответствующую документацию, и все эти методы в значительной степени зависят от собственных и сторонних библиотек. Поэтому я считаю более важным знать, какие колеса уже изобретены и как они подходят, а затем сделать мои собственные.

Император Орионий
источник
1
Подготовка важна, когда это возможно. С Google Code Jam у меня есть небольшая библиотека, которая читает ввод и отображает вывод так, как они хотят, и я включаю этот код в свое представление.
Марк Херд
Второй раз я делал что-то похожее, но как шаблон проекта. Он создает исходный файл с входным классом ниже Mainи несколько вещей внутри Mainметода (экземпляр моего входного класса и выходной поток и регистр case).
Император Орионий
Я не могу вспомнить последний раз, когда я читал со стандартного ввода. Дайте мне файл, который я могу вставить в анализатор JSON.
gnasher729
2

Если вы хотите участвовать в соревнованиях по программированию по расписанию, вы должны выучить самый выразительный язык, допустимый в соревновании. Perl, вероятно, будет лучшим, а затем Ruby или Python. Вам все еще понадобится хорошее средство с алгоритмами, но по крайней мере вы не будете увязать в написании чего-то вроде

Integer prev = b.get(k)
if (prev == null) prev = 0
Integer v = a.get(k);
if (v == null) v = 0;
b.put(prev + v);

вместо того

b[k] += a[k]

Не беспокойтесь об изучении нескольких библиотек. Все они очень похожи и документация находится в сети. Свободное владение более выразительными языками сделает вас лучшим (но, возможно, разочарованным) программистом в менее выразительных языках. Обратное не верно.

NB

Разница между 200 строками кода и 40 строками кода огромна, и она еще больше, если она отличается от программы на 200 000 строк и программы на 40 000 строк. Тогда разница между командой из пяти человек плюс менеджер и командой из одного или двух человек.

Кевин Клайн
источник
3
(а) Я точно знаю, что C / C ++ / Java, как правило, занимают лидирующие позиции в соревнованиях по программированию. (б) C / C ++ считается многими «самым мощным языком» (определенно выше Perl / Ruby / Python). (c) Из-за перегрузки операторов код C ++ может выглядеть почти так же, как ваш второй пример. (d) Такая обширная проверка (в Java это так?) требуется только в том случае, если: (1) Вы не знаете, что делаете. (2) Характер данных таков, что это требуется (не происходит в соревнованиях по кодированию). (3) Вы пишете код, который будет использоваться другими людьми (не применимо).
Dukeling
1
@Dukeling: Согласно этому исследованию ( page.mi.fu-berlin.de/prechelt/Biblio/jccpprtTR.pdf ) языки сценариев позволяют быстрее разрабатывать и уменьшать исходный код. Согласно другому исследованию ( flownet.com/gat/papers/lisp-java.pdf ), Lisp предлагает еще большую производительность, чем языки сценариев. Согласно второму исследованию, процитированному выше, код на Лиспе оказывается почти таким же быстрым, как и код на С ++, хотя на его написание уходит меньше времени.
Джорджио
«между программой из 200 000 строк и программой из 40 000 строк»: я думаю, вы должны различать. Различия из-за многословности языка программирования (синтаксиса) не добавляют сложности к коду и, следовательно, могут оказать незначительное влияние на необходимые усилия по обслуживанию. С другой стороны, у вас может быть другое количество строк из-за разных языковых возможностей. Например, в Python вам не нужно управлять памятью, в то время как в C вы должны самостоятельно реализовать все управление памятью. Тогда я согласен с вами, что в коде C у вас больше функциональности и вам определенно нужно дополнительное время на обслуживание.
Джорджио
@ Джорджио Я не спорю о времени разработки или размере исходного кода, просто о том, что на самом деле происходит на соревнованиях по программированию, основываясь на значительном опыте.
Dukeling
1
Я цитировал две научные статьи (на которые стоит обратить внимание IMO), я не говорил о том, что люди на веб-страницах думают об этом. Тот факт, что мнение широко распространено, не означает автоматически, что оно действительно. :-) По крайней мере, нужно это проверить каким-то строгим способом.
Джорджио
2

Любой алгоритм может быть реализован на любом языке программирования. В конце концов, не синтаксис имеет значение. Но использование языка высокого уровня, такого как Python, имеет свои преимущества. Меньше работы и меньше кода. Поэтому для реализации алгоритма в Python вам потребуется меньше строк, чем требуется для языка низкого уровня, такого как C.

Python имеет большинство структур данных, встроенных в его библиотеку. Но в C нам нужно начать с нуля и использовать структуру, чтобы построить все это. Конечно, существуют различия между языком высокого уровня и языком низкого уровня, но язык не должен мешать вам реализовать какой-либо алгоритм.

Робин Томас
источник
2

Хотя экстраполяция примера «40 LoC против 200 LoC», говорящего «ну, только пятая часть от общего LoC, очевидно, быстрее писать, так что это должно быть лучше», может показаться заманчивой, я действительно думаю, что там мало правды.

По моему мнению, оптимизация под наименьшее количество LoC почти никогда не является хорошей идеей. Да, каждый написанный LoC является потенциальной ошибкой, и вам никогда не придется отлаживать то, что вы никогда не писали etcetc. Дело в том, оптимизировать для удобства чтения и развязки. Неважно, если вы решите проблему с помощью регулярного выражения с 20 строками, в отличие от написания модуля 1k LoC. Регулярное выражение будет непрозрачной стеной, чрезвычайно склонной к ошибкам, трудной для понимания, кошмарной для изменения, не изменяющей своего поведения безо всяких изменений и т. Д.

Избавиться от шаблонов и многословия, которые не приносят никакой пользы, все хорошо, но, с другой стороны, используя что-то вроде Java или C #, имея знания о шаблонах проектирования и инструментах, таких как resharper, вы ОЧЕНЬ очень гибки в рефакторинге кода. очистить его с течением времени, сломать вещи и т. д., что было бы НАМНОГО сложнее, если бы вы написали его как гораздо меньший скрипт на python или приложение ruby.

Очень показательное сравнение: я бы предпочел иметь 100 тыс. LoC отрытого кода C #, покрытого тестами, заполненного такими «излишними» вещами, как шаблоны стратегий, фабрики и т. Д., А не 20-килобайтное приложение на python, которое просто «выполняет работу». В 5 раз больше кода или нет, архитектура побеждает каждый день.

Я полностью согласен с тем, что некоторые виды работ проще и удобнее на некоторых языках, но я больше верю в выбор языка на основе того, какие инструменты вам нужны и каковы требования (и которые могут появиться в ближайшем будущем).

Сара
источник