Как избежать закона инструмента

Я полу-самоучка инженер-программист. В аспирантуре по 3D-анимации и визуальным эффектам у меня было несколько курсов программирования на C++ и RSL (язык шейдеров Renderman), но у меня никогда не было возможности пройти курс по структурам данных и алгоритмам.

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

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

Определения структуры данных

Структура данных — это просто контейнер для хранения и извлечения данных. Вы используете их каждый день. Одной из самых основных структур данных является массив. Однако, если вы работали с несколькими языками, вы, вероятно, заметили, что массив в одном языке может работать не так, как в другом. Например, в Python можно расширить объект anarray.array на месте:

Python 3.8.2 (default, Feb 26 2020, 02:56:10)
> from array import array
> 
> nums = array('I', [1, 2, 3])
> nums
array('I', [1, 2, 3])
> nums.extend([4,5,6])
> nums
array('I', [1, 2, 3, 4, 5, 6])

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

Абстрактные типы данных

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

ADT также должен указывать набор операций, которые он поддерживает. Array ADT имеет две абстрактные операции:

  • Обход: возможность перебора всех элементов.
  • Поиск: возможность найти определенный элемент

Конкретные реализации

Как упоминалось ранее, Go и Python по-разному реализуют Array ADT. Реализация Go представляет собой статический массив (размер не может увеличиваться), а реализация Python — динамический массив. Если вы хотите использовать динамический массив в Go, вам повезло! Он называется slice , и вы можете поиграть с одним здесь. Таким образом, хотя массив Python является динамическим, а массив Go — статическим, оба они удовлетворяют АТД Array.

Не забывайте об алгоритмах

Причина, по которой мы обычно ссылаемся на алгоритмы и структуры данных одновременно, заключается в том, что они взаимозависимы. Алгоритмы преобразуют структуры данных, хранящиеся в памяти; у вас не может быть одного без другого. Некоторые структуры данных разработаны специально для данного набора алгоритмов. Например, в большинстве языков реализованы ADT Hash Table (в Python они называются словарями, а в Go — картами), которые позволяют выполнять поиск и извлечение по ключу.

Сверните свое собственное или нет

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

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