Выберите правильную структуру данных —  Массивы так часто являются плохим выбором

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

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

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

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

Одним из примеров, и это тема этой статьи, является правильный выбор структуры данных. Что я заметил на своих курсах: всякий раз, когда студентам приходилось работать с набором объектов, они всегда хотели использовать массивы. Многие не знали, что существуют другие типы контейнеров, и даже те, кто знал об их существовании, не рассматривали их. Они всегда — рефлекторно — использовали массив. Но массивы так часто являются неправильным выбором! Поэтому я познакомил их с плюсами и минусами типичных базовых типов контейнеров и обучил их использованию.

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

Массивы

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

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

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

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

Еще одна вещь, которую следует учитывать, — это читабельность. Когда объекты, которые вы хотите хранить в контейнере, имеют некоторый естественный порядок, например, они упорядочены по времени, и вам нужен самый ранний или самый последний объект, тогда запись массива подходит. Но если такого естественного порядка нет, например, когда вы храните кучу цветовых кодов RGB, то произнесение color_codes[3] для получения 4-го цвета в массиве вообще нечитаемо, потому что читатель должен знать, в каком порядке вы хранил цвета в первую очередь.

Разве не было бы намного читабельнее, если бы вместо этого можно было написать color_codes['RED']? Ну, вы можете, но не с массивами. Вот к чему мы придем дальше.

Словари

Второй фундаментальный тип контейнера — это то, что Python называет «словарем». Эта структура данных работает под разными именами. В Java они называются хэш-картами, в других местах таблицами ключ-значение, а иногда их называют обобщенно-ассоциативными структурами данных.

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

color_codes = {
    'RED': '#FF0000',
    'GREEN': '#00FF00',
    'BLUE': '#0000FF'
}

поэтому вы получаете доступ к отдельным элементам через их ключи, например color_codes['RED']. Когда элементы не имеют естественного порядка, это часто приводит к гораздо более читабельному коду.

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

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

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

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

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

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

Наборы

И массивы, и словари позволяют сохранять несколько копий некоторого объекта в одном контейнере. Часто это то, что вам нужно, но иногда вы хотите обеспечить уникальность объектов в контейнере. В последнем случае наборы — это то, что вам нужно в качестве структуры данных. Если вы попытаетесь дважды добавить элемент в набор, как для математических наборов, они не изменятся. Таким образом, вы можете просто добавлять в набор, не беспокоясь о некоторых ограничениях уникальности. Например, в Python мы можем сказать

s = set()
s.add('Apple')
s.add('Orange')
s.add('Apple')
s.add('Orange')
print(s)
Out:
{'Orange', 'Apple'}

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

for el in s:
    print(el)
Out:
Orange
Apple

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

Связанные списки

Другой распространенной структурой данных, которая, однако, нет в стандартной библиотеке Python, является связанный список. Итак, если вы создаете список в Python,

a = list()
a.extend([1, 2, 3])
print(a)
Out:
[1, 2, 3]

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

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

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

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

Деревья, очереди, стеки и т. д.

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

Я опишу некоторые из этих структур в продолжении этой статьи. Так что, если вам интересно, оставайтесь с нами.

Спасибо за прочтение!

Больше контента на plainenglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Получите эксклюзивный доступ к возможностям написания и советам в нашем сообществе Discord.