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

Обратите внимание, я не прошу рекомендации книги по реализации алгоритмов. Меня не волнует их реализация, я просто хочу уметь распознавать, когда алгоритм / структура данных будет хорошим решением проблемы. Я прошу больше список алгоритмов / структур данных, которые я должен «распознать». Например, я знаю решение такой проблемы:

Вы управляете набором шкафчиков с надписью 0-999. Люди приходят к вам, чтобы арендовать шкафчик, а затем возвращаются, чтобы вернуть ключ от шкафчика. Как бы вы создали программное обеспечение для управления, зная, какие шкафчики бесплатны, а какие используются?

Решением будет очередь или стек.

Я ищу такие вещи, как «в какой ситуации следует использовать B-Tree - какой алгоритм поиска следует использовать здесь» и т. Д. И, возможно, быстрое представление о том, как более сложные (но обычно используемые) структуры данных / алгоритмы работают.

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

Объективный ответ:

В то время как мой первоначальный ответ на этот вопрос был основан на моем эмпирическом опыте студента CS, готовящегося к поступлению в аспирантуру, и моем прогнозируемом мнении о типе людей, с которыми я хотел работать в области CS. На самом деле существует объективный (в отношении субъективных мнений компьютерных сообществ ACM SIGCSE и IEEE) ответ. Каждые 10 лет органы ACM и IEEE сотрудничают в совместной публикации, в которой подробно излагаются предложения по учебной программе по компьютерным наукам для студентов на основе профессиональных знаний о состоянии компьютерной индустрии. Более подробную информацию можно найти на cs2013.org . Комитет публикует итоговый отчет, в котором перечисляются рекомендации по учебной программе .

Тем не менее, я все еще думаю, что мой список довольно хорош.

Оригинальный ответ ниже.

Что я должна знать?

минимальный

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

Чтобы ответить на заглавный вопрос, вот, что студент бакалавриата CS (основа для программиста-адепта) должен знать после окончания обучения:

Структуры данных

• Представление машинных данных
  • Единицы, дополнение к двум и связанная с ними арифметика
  • Слова, Указатели, Плавающая Точка
  • Битовый доступ, смещение и манипулирование
• Связанные списки
• Хеш-таблицы (карты или словари)
• Массивы
• деревья
• Стеки
• Очереди
• диаграммы
• Базы данных

Алгоритмы

• Сортировка:
  • Bubble Sort (чтобы понять, почему это плохо)
  • Сортировка вставки
  • Сортировка слиянием
  • Быстрая сортировка
  • Сортировка в стиле Radix, сортировка по счетам и сортировка по ведрам
  • Куча сортировка
  • Bogo и Quantum Sort (=
• Поиск:
  • Линейный поиск
  • Бинарный поиск
  • Глубина Первый Поиск
  • Ширина Первый Поиск
• Манипуляция строк
• итерация
• Обход дерева
• Обход списка
• Хеширующие функции
• Конкретная реализация хеш-таблицы, дерева, списка, стека, очереди, массива и набора или коллекции
• Алгоритмы планирования
• Обход и манипулирование файловой системой (на уровне inode или эквивалентном уровне).

Шаблоны проектирования

• Модульность
• завод
• строитель
• одиночка
• адаптер
• декоратор
• легкий вес
• наблюдатель
• Итератор
• Государственный аппарат]
• Контроллер модельного вида
• Потоки и шаблоны параллельного программирования

парадигмы

• Императив
• Объектно-ориентированный
• функциональная
• декларативный
• Статическое и Динамическое Программирование
• Разметка данных

Теория сложности

• Сложность Пространств
• Computability
• Обычные, контекстно-свободные и универсальные машины Тьюринга завершают языки
• Обычные выражения
• Подсчет и базовая комбинаторика

за

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

Вот несколько советов для алгоритмов и структур данных:

• Бинарный поиск может (и должен) использоваться только для отсортированных данных.
• Сортировка в стиле Radix - это круто, но только когда у вас есть сортировка по конечным классам.
• Деревья хороши для чего угодно, как и Хеш-таблицы. Функциональность хэш-таблицы может быть экстраполирована и использована для решения многих проблем за счет эффективности.
• Массивы могут использоваться для поддержки большинства структур данных более высокого уровня. Иногда «структура данных» - это не более чем умная математика для доступа к местоположениям в массиве.
• Выбор языка может быть разницей между тем, как выдернуть волосы или преодолеть проблему.
• Таблица ASCII и массив из 128 элементов образуют неявную хеш-таблицу (=
• Регулярные выражения могут решить много проблем, но их нельзя использовать для разбора HTML .
• Иногда структура данных так же важна, как и алгоритм.

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

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

Ответьте на проблему, поставленную в вашем вопросе.

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

У вас есть 0-999 шкафчиков. Теперь, поскольку у вас есть фиксированное количество шкафчиков, вы можете легко представить функцию хеширования без коллизий в диапазоне 0-999. Эта функция просто h (x) = x mod 1000. Теперь [концептуально] создайте хеш-таблицу с целочисленными ключами и содержимым массива char из 1000 элементов в качестве ваших значений. Если клиент хочет зарезервировать шкафчик 78 для использования, просто поместите 78 в хеш-функцию (возвращая 78), а затем добавьте это число к базовому указателю массива - сохраняя истинное значение в месте, указанном значением смещения , Точно так же, если вам нужно проверить, используется ли 78, просто прочитайте значение, хранящееся в этом месте, и проверьте значение true.

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

Теперь вы можете спросить, а что если мне нужно знать все доступные шкафчики, не будет ли приоритетная очередь лучше? Если в очереди приоритетов имеется k доступных шкафчиков, итерация по всем из них займет k шагов. Кроме того, в зависимости от реализации приоритетной очереди вам может потребоваться перестроить приоритетную очередь при просмотре всего этого, что потребует k * log (k): (k <1000) шагов. В решении с массивами вам нужно всего лишь перебрать массив из 1000 элементов и проверить, какие из них открыты. Вы также можете добавить доступный или использованный список к реализации, чтобы проверить только за k раз.

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

Там нет "должен". A. Познакомьтесь с базовыми классами сложности (линейными, логарифмическими и т. Д.). Б. Поймите, что вы можете делать что угодно с простым массивом, как с сложной структурой данных, такой как B-дерево. Хитрость в выборе подходящей структуры / алгоритма заключается в балансировке производительности, ожидаемого размера ввода и сложности реализации.

Затем есть абстрактные, но чрезвычайно полезные вещи (хотя полезность не сразу очевидна): конечные автоматы, теория графов, теория выпуклости (линейное программирование и т. Д.).

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

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