Насколько важно для программиста знать, как реализовать алгоритм QuickSort / MergeSort из памяти? [закрыто]

58

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

Когда я попытался осмыслить реализацию QuickSort и MergeSort, мне пришло в голову, что, хотя я занимаюсь программированием для жизни и считаю себя порядочным в том, что я делаю, у меня нет ни фотографической памяти, ни просто умственных способностей для реализации этих алгоритмов без опираясь на мои заметки. Все, что я помнил, это то, что некоторые из этих алгоритмов стабильны, а некоторые нет. Некоторым требуется время O (nlog (n)) или O (n ^ 2). Некоторые используют больше памяти, чем другие ...

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

Джон Смит
источник
13
Вы должны помнить, что решение существует и когда его использовать. Затем зайдите в документы и реализуйте его. Если бы вы не знали о быстрой сортировке или слиянии, вы все равно использовали бы пузырьковую сортировку и смотрели бы, как ваша программа переходит в режим сканирования, и при увеличении данных находят решения низкого уровня.
Питер Б
1
Помимо хороших ответов, упомянутых ниже, обратите внимание также на то, что многие компании требуют (1) знать сложность таких алгоритмов, (2) свободно реализовывать их на доске.
Сакиск
3
Я уверен, что важно запомнить эти алгоритмы для частого появления Google в автономном режиме. : o
Ли Джеймс
Вам нужно знать их производительность, варианты использования и т. Д. Знание того, как реализовать их наизусть, - это то, что требуется только техническим компаниям в интервью.
Сакиск
@PieterB, я не согласен. Не нужно знать о 'mergesort' и 'quicksort', чтобы Google 'наилучшим алгоритмом сортировки'
hyankov

Ответы:

117

Давайте спросим Альберта и посмотрим, что он скажет по этому вопросу:

«Мне не нужно знать все, мне просто нужно знать, где это найти, когда мне это нужно»

- Альберт Эйнштейн , перефразированный

Аминь, брат Альберт, аминь.

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

Питер Роуэлл
источник
9
Как это отвечает на вопрос? Он сказал: «Мне не нужно знать все», он не сказал «Мне не нужно ничего знать». Некоторые навыки являются основополагающими, и весь вопрос был в том, относится ли конкретная часть информации к категории фундаментальных навыков или нет.
Конрад Рудольф
1
Думать, что цель состоит в том, чтобы запомнить быструю сортировку, значит упустить смысл вопроса. Конечно, в реальном мире, если вам нужна общая быстрая сортировка, вы будете использовать библиотечную процедуру или искать код и копировать его. Тест состоит в том, чтобы понять, понимаете ли вы рекурсию, инварианты цикла и т. Д., И попросить вас быстро записать алгоритм сортировки - это просто простая демонстрация этих знаний. Если вы не в состоянии заново получить 20-строчную быструю сортировку на месте, сколько вещей вы обычно делаете действительно неэффективно или неправильно, даже не подозревая об этом?
Ларри Гриц
3
@Larry: я думаю, что я забыл больше, чем многие программисты знают о деталях алгоритмов - и быстрая сортировка с нуля - один из них - по очень хорошей причине - я решил читать вещи высокого уровня и использовать языки высокого уровня чем оставаться в чашах низкого уровня детализации реализации. Честно говоря - мне все равно, какую библиотечную подпрограмму я использую, - она ​​может использовать пиксельную пыль и фей, насколько мне известно. Документы скажут O () для определения размера - это все, что мне нужно знать.
Mattnz
2
@mattnz: несколько запоздалое продолжение вашего "размера O ()". Одна сложная вещь, которую я узнал, заключалась в том, что при большом наборе данных неправильная локальная ссылка может полностью перегрузить O (). У вас может быть алгоритм, который есть O(n log n), но если вы получите много ошибок в кеше или (не дай бог) попадете на диск, тогда это n log nбудет просто приятная память.
Питер Роуэлл
49
  1. Это не вопрос запоминания. Это вопрос глубокого понимания общих классов алгоритмов, таких как разделяй и властвуй. Если вы действительно понимаете «разделяй и властвуй», вам не нужно запоминать быструю сортировку. Вы можете восстановить его на месте по мере необходимости. Более того, реальная отдача заключается даже не в том, что вы можете самостоятельно восстановить быструю сортировку, а в том, что вы можете распознать, когда новая проблема поддается решению «разделяй и властвуй».

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

Чарльз Э. Грант
источник
5
Я не думаю, что можно понять QuickSort, не помня QuickSort. Это не сложная и загадочная вещь, это просто две общие идеи. То же самое относится и к сортировке слиянием, но у вас есть только одна идея: P
drxzcl
Я не согласен со вторым пунктом. все рабочие места одинаковы, меняется только интервьюер. этот хорошо знает сортировку и думает, что каждый хороший программист должен знать сортировку, потому что это все, что он знает и заботится о нем.
IAdapter
2
@IAdapter, конечно, ты шутишь! По своему опыту я знаю, что знания и навыки, которые мне понадобились для моей первой работы по написанию макросов TROFF для компании, выпускающей программное обеспечение в термоусадочной пленке, сильно отличаются от тех, которые мне нужны для моей текущей работы в лаборатории вычислительной биологии.
Чарльз И. Грант
@ CharlesE.Grant большую часть времени интервьюер не проверяет, есть ли у вас навыки, необходимые для выполнения вашей работы (я не могу вспомнить последний вопрос javascript / css, который мне задавали, и я делаю веб-приложения).
IAdapter
10

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

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

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

scaryrawr
источник
6

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

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

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

Е.Л. Юсубов
источник
5

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

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

HGH
источник
3

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

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

Вкратце к этому бессвязному ответу: определенно используйте API (NIH - признак незрелости разработчика), но всегда понимайте основные принципы. Надеюсь, это поможет.

Майк Полен
источник
2

Сортировка и поиск очень важны, будь вы поклонник Дональда Кнута или хотите стать следующим Ларри Пейджем. В зависимости от бизнеса, в котором вы находитесь, и уровня конкуренции, которым вы можете управлять среди своих кандидатов, я бы порекомендовал вам включить в собеседование некоторые из следующих понятий.

Сортировка

  • Набросок какого-то алгоритма сортировки.
  • Перечислите несколько примеров алгоритмов сортировки.
  • Сравните / сопоставьте два вида с различными характеристиками производительности.
  • Если они не упоминают использование памяти, спросите об этом.

Поиск

  • Назовите как можно больше алгоритмов поиска.
  • Сравните / сопоставьте два алгоритма поиска.
  • Нарисуйте любой поиск, кроме линейного поиска.

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

DeveloperDon
источник
Раньше я считал, что просить людей программировать на собеседованиях было глупо, но вы просто не поверите количеству людей, которые кажутся фантастическими, и которые отвечают на «социальные» вопросы летающими красками, но которые, для жизни их, не могут запишите правильную реализацию 'strcat' или другой простой функции. Несколько раз это избавляло меня от найма кого-то, кто, если бы не глупый кодовый вопрос, мог бы вызвать бесконечное горе и утащить команду из-за некомпетентности.
Ларри Гриц