Так был ли этот курс Data Structures & Algorithms действительно полезным в конце концов?

Question

Я помню, когда я был в DSA, я был похож на wtf O (n) и задавался вопросом, где бы я использовал его, кроме как в аспирантуре, или если вы не доктор наук, как Блох. Каким-то образом его использование действительно появляется в бизнес-анализе, поэтому мне было интересно, когда вам, ребята, пришлось вызывать ваши Big O навыки, чтобы увидеть, как написать алгоритм, какую структуру данных вы использовали для соответствия или нужно ли вам было на самом деле создать новый ds (как ваша собственная реализация Splay Tree или Trie).

Answer 1

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

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

Answer 2

Нотация Big-O является одной из базовых нотаций, используемых при описании алгоритмов, реализованных конкретной библиотекой. Например, вся документация по STL, которую я видел, описывает различные операции в терминах big-O, поэтому, естественно, вы должны, например, понять разницу между O (1), O (log n) и O (n), чтобы понять последствия вашего выбора контейнеров и алгоритмов STL. MSDN также делает это для классов .NET, а документация по Java IIRC делает это для стандартных классов Java. Таким образом, я бы сказал, что знание нотации является в значительной степени требованием для понимания документации наиболее популярных фреймворков.

Answer 3

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

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

Если вы не знаете, что n2 будет работать медленнее по сравнению с n log n, у вас есть чему поучиться.

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

Answer 4

Конечно (хотя я скромный MS в EE - не доктор наук, не CS, в отличие от моего коллеги Джошуа Блока), я пишу много вещей, которые должны быть хорошо масштабируемыми (или компоненты, которые могут понадобиться использоваться в приложениях с высокой степенью масштабируемости), поэтому соображения о биг-о наиболее часто используются в моем дизайне (и их нетрудно принять во внимание). Структуры данных, которые я использую, почти всегда взяты из простого, но богатого предложения Python (которое я помогал в разработке ;-), редко бывают совершенно необходимыми (вместо того, чтобы опираться на список, дикт и т. Д.); но когда это происходит (например, битвекторы в моем проекте с открытым исходным кодом gmpy), ничего страшного.

Answer 5

Абсолютно: хотя стеки, очереди и т. Д. Довольно просты, это помогает быть представленным им дисциплинированным образом.

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

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

... просто назвать несколько примеров.

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

Answer 6

Я смог использовать B-Trees сразу, когда узнал о них в классе алгоритмов (это было около 15 лет назад, когда было намного меньше доступных реализаций с открытым исходным кодом). И даже позже знание о различиях эл. г. контейнерные классы пригодились ...

Answer 7

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

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

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

Answer 8

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

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

Answer 9

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

Answer 10

К сожалению, я много работаю над приложениями «бизнес» и «формы поверх данных», поэтому большинство проблем, над которыми я работаю, могут быть решены путем объединения массивов, связанных списков и хеш-таблиц. Тем не менее, у меня была возможность поработать над магией структур данных тут и там:

• Из-за странных сложных бизнес-правил я работал над приложением, в котором использовался пользовательский пул потоков, реализованный в виде левой кучи.

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

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

Если по каким-либо другим причинам я рад, что я потратил время на чтение о структурах данных и алгоритмах, чтобы просто по-другому представить новые проблемы, особенно комбинаторные задачи и задачи о графах. Теория графов больше не является синонимом слова «страшно».