А вы знаете стандартные структуры и алгоритмы?

Question

[Андрей]

Приветствую тостеро-сообщество!
Собственно, сабж! Во многих вакансиях умные( я на это надеюсь ) люди пишут, что соискатель должен знать стандартные алгоритмы и структуры данных. Вот у меня возник вопрос: А вы знаете стандартные структуры данных и алгоритмы?
А используете в своей работе? Когда вы последний раз писали самостоятельно сортировку? Хотя бы пузырьком :)
А какой-нибудь алгоритм?
А пишете на чем?

Answer 1

[Сергей Протько]

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

Вообще все упирается в знание сложности алгоритмов, из этого вытекает что вы должны знать хотя бы примерно как эти алгоритмы работают. Скажем вы должны знать что при таком-то случае, с которым у вас чаще сталкивается программа, алгоритм А имеет сложность O(N) а другой при таком же случае всего то O(logN).... при том что в большинстве других задач тот же самый алгоритм A c определенными допущениями может иметь сложность O(1).

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

Сейчас вот собираюсь перечитать Кромена, "Алгоритмы: построение и анализ". Ибо поймал себя на мысли что я уже плохо помню все это дело.

Comments

[Андрей]

Вы на чем пишете? Это ведь важно. Вот я пишу на питоне. Ну какой тут пузырек?

[Сергей Протько]

@xmdy PHP, Javascript в основном. Балуюсь с C++ и D (DSP, балуюсь с процессингом аудио, классификацией и все такое прочее)... Сейчас вот планирую Go освоить.

[Андрей]

ну так вот. Как там у вас, часто сортировки пишете свои? Или дерево бинарное?)

[Сергей Протько]

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

Для 99% задач это не нужно знать, но для меня интерес как раз составляет тот самый 1%.

[thepry]

@Fesor приведите, пожалуйста, пару примеров таких задач?

[Сергей Протько]

@thepry любые задачи, где вам нужно обрабатывать большие массивы данных, обходы графов... Задачи связанные с поиском пути, аналитикой, разбор текстов и слов, морфологические словари, разбор корпуса языка и т.д. Возможно свои кастомные заточенные под задачу простенькие СУБД, когда более универсальные решения не достаточно производительны, или просто некие структуры, хранящиеся в памяти для более быстрого поиска... Конечно для графов есть neo4j, но на клиенте с этим будет сложнее...

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

Answer 2

[Виталий Желтяков]

Допустим, что знаю.

Здесь фишка в другом - мало того, что надо знать алгоритмы, надо ещё их применять. То есть не важно количество умных книг, которые вы прочли. Важно, как часто вы их применяете и смотрите другие решения - опыт использования.

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

Answer 3

[Сергей]

> А вы знаете стандартные структуры данных и алгоритмы?
Нет, не знаю я стандартных структур и алгоритмов, потому что:
1. Стандарта такого нет
2. Для каждого человека стандарты свои.
Поэтому:
1. Элементарное знаю.
2. Если нужно что-то забубенное (а такое нужное редко), то приходится лезть в Гугл.

Comments

[andymitrich]

1 и 2 - чушь.

[Сергей]

Покажите мне ГОСТ, тогда поговорим.

Answer 4

[Shetani]

Все знать невозможно, да и не нужно. Лучше знать где можно найти нужную информацию.

Answer 5

[mpavlov]

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

Пишу на C# под Web.

Comments

[andymitrich]

Вы сами себе противоречите.

Answer 6

[andymitrich]

Знаю и использую.

Answer 7

[Mrrl]

Некоторые стандартные структуры и алгоритмы знаю. Но в работе использую редко: обычно ситуации возникают такие, что непосредственное применение стандартного алгоритма будет не очень эффективным (или по какой-то причине вообще не подойдёт), так что приходится строить более специальные структуры и алгоритмы - обычно как комбинацию стандартных приёмов, но не обязательно.
Из стандартных приходилось писать, разве что, приоритетную очередь: почему-то в C# её не сделали. И QR-алгоритм для собственных значений матрицы (про мелочи типа многомерного метода Ньютона не говорю - они попадаются регулярно, и каждый раз со своими особенностями).
Сортировку в последний раз писал с полгода назад. Получился монстр на полтысячи строк, но он работал.
Сортировку пузырьком (или простыми вставками) приходится писать когда по какой-то причине неудобно вызывать стандартный Sort. Например, при сортировке фрагмента массива с нестандартной функцией сравнения - опять же, в C# этот метод не вывели. Там проще написать три строчки в коде, чем оформлять класс-компаратор.