Должен ли компетентный программист придумать свой собственный алгоритм кратчайшего пути?

58

Я испытываю кризис уверенности в своих способностях программиста.

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

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

Ну что ж, по крайней мере, мне удалось изобрести пузырьковую сортировку: D

Новичок Программист
источник
7
Тем, кто занимался пользовательским интерфейсом в течение 20 лет, вероятно, будет сложно найти решение проблемы в другом домене за короткий промежуток времени.
Кодер
38
Я думаю, что много времени проводя на сайтах SE, дает каждому кризис доверия! (Не то чтобы это плохо). Счастье в жизни - это найти идеальный баланс между принятием того, что есть, и желанием изменить его.
TrojanName
2
Я не мог изобрести это сам, но я пытаюсь вспомнить, как это работает. убедитесь, что вы понимаете эту анимацию: upload.wikimedia.org/wikipedia/commons/2/23/…
работа
6
@ Брайан Трагедия местного гения. Ты вряд ли когда-нибудь сможешь быть лучшим в чем-либо.
Рей Миясака
7
хороший компьютерный ученый должен, но не обязательно программист или программист
Нил Макгиган

Ответы:

118

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

Я сомневаюсь, что Дейкстра придумал алгоритм кратчайшего пути за несколько часов, так что это похоже на действительно высокий стандарт, который можно использовать для определения, является ли кто-то «хорошим программистом»

GSto
источник
25
@Nakilon - Программисты, которые игнорируют существующие решения, просто тратят свое время, и если они не тратят свое время, они делают худшее решение. Смотрите: Каждый делает свою собственную схему хеширования паролей против bcrypt.
Восстановить Монику
10
@GSto: согласно Википедии, Дейкстра придумал алгоритм менее чем за час: 20 минут, согласно первой заметке в Википедии: en.wikipedia.org/wiki/Dijkstra%27s_algorithm
woliveirajr
9
Это относительно простой алгоритм, но Дейкстра был очень талантлив и обучался теоретической физике и продвинутой математике. Нет ничего лучше, чем несколько лет написание доказательств для улучшения способности разрабатывать алгоритмы.
Кевин Клайн
19
@woliveirajr - Ну, я уверен, что Ньютон потратил столько же времени, чтобы придумать законы движения. Подумав об этом в течение первых 20 лет.
Ладья
6
@Nakilon - Да, именно поэтому все пишут все на C, потому что в противном случае вы просто кодер, используя чужой язык высокого уровня. Ой, подождите, я имею в виду сборку, иначе вы просто используете чужой язык низкого уровня. Ой, подождите, я имею в виду переключение переключателей для изменения электрических цепей, иначе вы просто используете чей-то набор инструкций. Или вы знаете, вы можете просто использовать то, что уже есть, и работать над созданием чего-то нового . Зачем тратить время на переизобретение алгоритма Дейкстры, когда вы можете изобрести что-то новое, например, программу, которая его использует?
Восстановить Монику
54

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

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

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

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

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

Конрад Рудольф
источник
56
Не волнуйтесь, если грубая сила не работает, вы просто не используете ее достаточно.
Робби
2
+1 за то, чтобы подчеркнуть разницу между теоретическим CS и программированием. Программирование - это реальное решение проблем, и теоретическая CS предназначена для поддержки программирования. Однако теоретический CS не на 100% необходим в повседневном программировании большинства людей.
Фил
17

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

Определенно нереально. Люди не просто «придумывают» алгоритмы за несколько часов. Это требует много усилий и работы. Цитировать этот блог:

В «Программировании жемчуга» Бентли, цитируя Дональда Кнута, говорит: «Хотя первый двоичный поиск был опубликован в 1946 году, первый двоичный поиск, который работает корректно для всех значений n, не появлялся до 1962 года».

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

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

Блэк Джек
источник
1
Блэкджек, я должен был присоединиться к этому форуму, чтобы указать, что Бентли не сказал то, что вы утверждали, он сказал: Кнут сказал это, и Бентли процитировал его. Когда я прочитал ваш комментарий, я подумал, что вы сделали правильное замечание, но мне нравится проверять мои источники и никогда не слышал о Bentley. Однако я слышал о Кнуте и могу доверять тому, что он говорит. Пожалуйста, проверьте ваши источники лучше в следующий раз.
Ричард
8
@Richard - Комментарий был «В программировании жемчуга, говорит Бентли ...» Кнут был первым, кто сказал это, но мой источник - «Программирование жемчуга», а не TAoCP, поэтому я написал то, что написал Бентли. Я не утверждал, что Бентли является создателем - я просто процитировал то, что сказано в книге. Огромное количество материала в книгах не было придумано самими авторами, поэтому я не понимаю, почему вы бы это увидели.
Блэкджек
Приписывая цитату исключительно Bentley, вы не в состоянии отдать должное Кнуту, и, если заявление «Bentley» было неверным, вы ставите Bentley в положение, дающее неверную информацию, а не просто распространяющую ее. Строго говоря, вы не сказали, что сказал Бентли: если бы вы это сделали, вы бы сказали: «Бентли сказал, что Кнут сказал, что ...». Цитата здесь хорошо используется, но она вырвана из контекста, в котором она была сказана.
Ричард
3
@Richard - цитата, которую я перечислил, прямо из блога, который цитирует непосредственно из книги (буквально, я думаю, что это страница 57 первого издания). Если у вас возникли серьезные проблемы с заявлением, обратитесь к автору блога и попросите его изменить его.
Блэкджек
1
@Richard и BlackJack: Вы оба правы, но приписывание оригинальному автору добавляет доверия и контекста к заявлению. Моего редактирования должно быть достаточно.
Стивен Эверс
9

Очень маловероятно, что вы сможете найти лучшее решение, чем те, которые вы можете выбрать.

Выйти с лучшим алгоритмом, чем тот, который считается «лучшим» (в вашем случае, самым коротким), не каждый может сделать. Вероятно, это даже невозможно.

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

(s) Он также должен знать, действительно ли это лучший способ решить эту конкретную проблему.

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

Хосе Фаэти
источник
6

Это напоминает мне кое-что о разнице между «разработкой программного обеспечения» (то, что я бы назвал программированием) и другими инженерными дисциплинами. Если подумать, я думаю, что это была оригинальная книга Design Patterns. Я уверен, что кто-то здесь может процитировать это на макушке.

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

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

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

Кит Лэйн
источник
О, ирония ... теперь, когда я могу комментировать где угодно, я должен удалить ответ, который принес мне эту привилегию? Там должен быть значок для этого.
Кейт Лэйн
Там есть - Дисциплинированный , однако, если ваша репутация получает пересчитаны вы будете обратно к 1.
ChrisF
Да, в этом и заключается моя точка зрения ... Я бы вышел за рамки дисциплины на этом этапе ИМО. Если бы я преобразовал свой ответ в комментарий перед удалением, у меня могло бы быть все это ... Я предлагаю новый значок UberDisciplined для любого удаления, которое заставляет вас возвращаться к совершенно новому статусу пользователя. :)
Кейт Лэйн
3

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

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

Более того, Эйнштейн, который, как вы думаете, будет экспертом в теории узлов, не мог завязать свои шнурки, пока ему не исполнилось десять лет.

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

Рей Миясака
источник
3

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

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

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

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


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

(Кстати, мое одобрение считается в том же порядке важности, что и бесплатный купон на автомойку.)

Альфа
источник
3
Я согласен, что да, компетентный программист должен быть в состоянии придумать пузырьковую сортировку или ее эквивалент. Это может быть даже продуктивное использование времени для его реализации и опробования, возможно, просто для лучшего понимания проблемы. Но я думаю, что нужно сказать, что ни один компетентный программист не станет использовать его в производственном коде. Это то, что заставляет ваших клиентов возвращаться в следующем году и жаловаться, что теперь, когда у них есть больше данных для обработки, ваш алгоритм O (n!) Потребует вдвое больше времени вселенной для завершения ...
Томас Падрон-МакКарти
Кого волнует, если вы можете изобрести алгоритмы, если вы даже не можете распознать, когда это отстой? Самокритика так же важна для программиста, как и творчество. Я предпочел бы работать с программистом, который быстро признает, когда они знают, что их собственное решение занимает слишком много времени или вряд ли будет лучшим, чем с программистом, который хочет заново изобретать каждое колесо, потому что это мешает их эго сделать иначе.
Рей Миясака
Я согласен с обоими пунктами, но я думаю, что мы измеряем две разные вещи. Одним из них является способность программиста решать проблемы (что я считаю важным). Другое - это самокритика (я считаю это важным, но не для программирования: для жизни) и способность судить о коде (очень желательно). Я также сказал бы, что решения, которые принимают навсегда, на самом деле не являются решениями, не так ли? ;)
Альфа
2

Да, он / она должен.

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

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

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

Ханс-Петер Стёрр
источник
1

Не волнуйтесь

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

Итак, что я говорю, это:

  1. Я не рекомендую изобретать велосипед, но когда вы делаете ...
  2. Постарайтесь не изобретать его полностью и ...
  3. Не волнуйтесь, если вы не можете это сделать. Вот почему у нас есть сообщество программистов :-).
динамический
источник
Дело не в том, чтобы заново изобретать, а в том, чтобы решать проблемы в целом. Если вы не пытаетесь изобретать вещи самостоятельно, вы никогда не улучшитесь.
Нильс
0

Теория графов и применяемые к ней алгоритмы на первый взгляд кажутся простыми, но, как правило, далеки от этого. Можно подумать, что формирование непересекающихся (плоских) графов просто, например, на первый взгляд. В прошлом году я тщательно изучил эту проблему (планарность путем исключения подграфов Куратовского). Исходя из этого опыта, я могу сказать, что люди, которые пишут эти алгоритмы, обычно тратят на это свое обучение в аспирантуре, а иногда это исследование проводится в группах. И, как исследователи , это их единственный рабочий фокус в течение этого периода времени. Не имеет смысла думать, что мы, инженеры на местах, можем ожидать того же. Как правильно сказал кто-то здесь, это ослепительно очевидно, когда перед вами предстает решение. Это всегда так!

инженер
источник
0

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

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

Это означало бы, что вы игнорируете довольно сложную историю проблемы кратчайшего пути , переходя от алгоритма O (| V | ^ 4), опубликованного в 1955 году, к алгоритму O (E + V log V), опубликованному в 1984 году (который является Дейкстрой алгоритм с деревьями Фибоначчи). Вы почти гарантированно сделаете хуже, чем уже разработанные алгоритмы. Что еще хуже, есть хороший шанс, что в вашем алгоритме есть пробелы или ошибки, делающие его некорректным. Кроме того, вы почти наверняка потратите гораздо больше времени на разработку своего алгоритма, его реализацию и тестирование, чем на повторное использование существующего алгоритма.

Оставьте разработку алгоритмов разработчикам алгоритмов. Программисты являются потребителями своих результатов. Программисты комбинируют алгоритмы и используют их для решения реальных задач. Сотрудник полиции не должен быть в состоянии заново изобрести закон, чтобы иметь возможность работать или быть хорошим офицером.

Я даже призываю вас использовать реализации, сделанные экспертами, а не реализовывать алгоритмы самостоятельно для любого умеренно сложного алгоритма. Скорее всего, это будет правильно, скорее всего, они сделали это быстрее, чем вы когда-либо, и это сэкономит вам много времени. Это особенно верно для криптографических алгоритмов, потому что вы получаете дополнительные требования безопасности, которые обычно могут предоставить только эксперты.

Алекс тен Бринк
источник
Криптографические алгоритмы легко проверить реализацию; Известные правильные тестовые векторы - это десятки для любого публично определенного алгоритма, и он либо правильный, либо нет. (Вы можете получить неоптимальную производительность с пользовательской реализацией, но если это только правильно, с этим можно поработать.) Трудная часть в криптографии - такие вещи, как генерация случайных чисел, правильная обработка необработанных ключей и таблиц расширения ключей в памяти, правильная обработка пользовательского ввода (засолка и т. д.), сохранение чего-либо, чтобы вы могли выяснить, действительны ли расшифрованные данные, и так далее.
CVn
Я больше думал о времени атаки и т. Д., О чем почти никто не знает программисту. Это не всегда проблема, но тем не менее важная. Кроме того, объединение криптографических примитивов обычно не работает так, как ожидается, это также является сложной частью безопасности.
Алекс тен Бринк
Хотя временные атаки и т. Д., Безусловно, являются серьезной проблемой (и не только в криптографии), я бы сказал, что восприимчивость реализации к такому не влияет на ее правильность . И есть много, много способов запутаться в криптографии больше, чем просто активировать атаки по времени. Брюс Шнайер имел обыкновение управлять его сериалом Конуры ; В последнее время я ничего в этом не видел, но есть множество предостерегающих примеров. google.com/search?q=site%3Aschneier.com+%22the+doghouse%22
CVn