Реализовать структуры данных в реальном мире

Question

Сегодня темой класса алгоритмов было переопределение структур данных, в частности ArrayList в Java. Тот факт, что вы можете настраивать структуру различными способами, определенно заинтересовал меня, в частности, вариациями методов add () и iterator.remove ().

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

Answer 1

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

Редактировать
Я не сторонник того, чтобы вы переопределяли существующие структуры данных ! Не делай этого. Я говорю, что знания имеют практическое применение. Например, вам может потребоваться создать структуру данных двунаправленной карты (которую вы можете реализовать, составив две структуры данных однонаправленной карты), или вам может потребоваться создать стек, который отслеживает различные статистические данные (такие как min, max, имеется в виду) с использованием существующей структуры данных стека с типом элемента, который содержит значение, а также эти различные статистические данные. Это несколько простых примеров того, что вам может понадобиться реализовать в реальном мире.

Answer 2

Я несколько раз повторно реализовывал некоторые встроенные в язык структуры данных, функции и классы. Как разработчик встраиваемых систем, главная причина, по которой я бы это сделал, - скорость или эффективность. Стандартные библиотеки и типы были разработаны, чтобы быть полезными в различных ситуациях, но есть много случаев, когда я могу создать более специализированную версию, специально адаптированную для использования преимуществ и ограничений моей текущей платформы. Если язык не предоставляет возможности открывать и изменять существующие классы (как, например, вы можете в Ruby), то повторная реализация класса / функции / структуры может быть единственным путем.

Например, одна система, над которой я работал, использовала процессор MIPS, который был быстрым при работе с 32-разрядными числами, но медленнее при работе с меньшими. Я переписал несколько структур данных и функций для использования 32-разрядных целых чисел вместо 16-разрядных целых чисел, а также указал, что поля должны быть выровнены по 32-разрядным границам. Результатом стало заметное повышение скорости в части кода, которая являлась узким местом для других частей программного обеспечения.

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

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