Люди все еще пишут свои собственные структуры данных и алгоритмы?

Question

Вместо STL и подобных библиотек на других языках?

Как новичку, сколько я должен вникать в эту часть разработки программного обеспечения? Ширина первая или глубина?

Нужно ли только концептуальное понимание в наши дни? Или я должен быть в состоянии реализовать двухсвязный список с завязанными глазами?

Answer 1

Хотя никто больше не катит свои собственные стеки или очереди, очень важно понять, как и почему они отличаются. Поэтому нет, чтобы эффективно использовать простые структуры данных, нет необходимости на 100% уметь выполнять всю правильную проверку на наличие ошибок для циклов / нулевого хвоста / параллелизма / и т. Д. В связанном списке, когда они завязаны.

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Answer 5

Лично я чувствую, что эти вещи подпадают под Закон Утечки Абстракций .

Конечно, вы могли бы потратить свои дни на написание кода C # с красивым типом string, но в какой-то момент вам придется понять разницу между "\r\n" и "\n" и почему SVN, кажется, хорошо импортирует из Windows но не работает на вашем Linux-компьютере, и это помогает реализовать строковые функции.

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

Answer 6

… вместо STL и подобных библиотеки на других языках?

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

Как новичку, сколько я должен вникать в эту часть программного обеспечения развитие? Ширина первая или глубина?

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

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

Это только концептуальное понимание необходимо в эти дни? Или я должен быть возможность реализовать двусвязный список с завязанными глазами?

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

Answer 7

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

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

Answer 8

Все зависит от того, что вам нужно / хотите сделать.

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

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

Если ты студент, то, конечно, узнай о них столько, сколько захочешь!

Answer 9

вы, наверное, слышали о правиле 80/20. 80% разработчиков не имеют практического опыта реализации структур данных на своем языке. Поэтому, чтобы быть одним из этих 20%, попытайтесь выучить его и получить практический опыт. Тем не менее, на самом деле 80% работы, которую вы будете выполнять, не потребует внедрения вашего собственного DS. Если речь идет о языке, таком как Java и C #, то иногда написание собственного DS вызывает критику. У вас есть пакеты / библиотеки для большинства ваших потребностей. Но, внедряя эти DS в свой язык, вы улучшите свои навыки программирования. Итак, начните с вашего собственного стека и очереди. Я уверен, что первое, что вы выучите (если вы используете java / c # в качестве выбранного языка), это утечки памяти:)

Answer 10

Вы должны быть способны писать свои собственные структуры данных. На самом деле делать это для работы должно быть необычным обстоятельством. Коллекции C ++ STL или Java или структуры данных, предоставляемые в .NET, должны подходить для 99% случаев.

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

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