4.5   Резюме¶

1.   Ключевые выводы¶

• Массивы и связные списки - это две базовые структуры данных, представляющие два способа хранения данных в памяти компьютера: хранение в непрерывной области и хранение в разрозненных областях. Их свойства во многом взаимно дополняют друг друга.
• Массив поддерживает произвольный доступ и занимает меньше памяти; однако вставка и удаление элементов в нем неэффективны, а длина после инициализации неизменяема.
• Связный список позволяет эффективно вставлять и удалять узлы путем изменения ссылок (указателей), а также гибко менять длину; однако доступ к узлам неэффективен, а памяти он занимает больше. Распространенные типы списков включают односвязные, циклические и двусвязные списки.
• Список - это упорядоченная коллекция элементов, поддерживающая добавление, удаление, поиск и изменение, и обычно реализуемая на основе динамического массива. Он сохраняет преимущества массива и при этом может гибко менять длину.
• Появление списка значительно повысило практическую полезность массива, хотя это и может приводить к потерям части памяти.
• Во время работы программы данные в основном хранятся в оперативной памяти. Массив обеспечивает более высокую эффективность использования пространства памяти, а связный список дает большую гибкость в использовании памяти.
• Кэш, используя строки кэша, механизм предвыборки, а также пространственную и временную локальность, предоставляет CPU быстрый доступ к данным и заметно повышает эффективность выполнения программ.
• Поскольку массивы обычно имеют более высокий коэффициент попадания в кэш, они в большинстве случаев работают эффективнее списков. При выборе структуры данных нужно исходить из конкретных требований и сценариев.

2.   Q & A¶

Q: Влияет ли хранение массива в стеке или в куче на временную и пространственную эффективность?

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

1. Эффективность выделения и освобождения: стек представляет собой относительно небольшой участок памяти, а выделение в нем обычно выполняется автоматически компилятором; куча же обычно больше, может выделяться динамически из кода и легче фрагментируется. Поэтому выделение и освобождение памяти в куче обычно медленнее, чем в стеке.
2. Ограничение размера: объем стека относительно невелик, а размер кучи обычно ограничивается доступной памятью. Поэтому куча лучше подходит для хранения больших массивов.
3. Гибкость: размер массива в стеке должен быть известен во время компиляции, а размер массива в куче может определяться динамически во время выполнения.

Q: Почему для массива требуется, чтобы все элементы были одного типа, а для связного списка это не подчеркивается?

Связный список состоит из узлов, а узлы соединяются между собой через ссылки (указатели), поэтому каждый узел в принципе может хранить данные разного типа, например int , double , string , object и т.д.

Напротив, элементы массива должны быть одного типа, иначе нельзя будет вычислять адрес элемента через смещение. Например, если массив одновременно содержит int и long , один элемент занимает 4 байта, а другой - 8 байт ; в этом случае формула ниже уже не позволит вычислить смещение, потому что в массиве будут присутствовать элементы разной длины.

# Адрес элемента в памяти = адрес массива в памяти (адрес первого элемента) + длина элемента * индекс элемента

Q: После удаления узла P нужно ли присваивать P.next = None ?

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

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

Q: Временная сложность вставки и удаления в связном списке равна \(O(1)\) . Но до вставки или удаления обычно еще нужно потратить \(O(n)\) на поиск элемента. Почему тогда общая сложность не \(O(n)\) ?

Если сначала искать элемент, а потом удалять его, то временная сложность действительно будет \(O(n)\) . Однако преимущество связного списка с \(O(1)\) вставкой и удалением проявляется в других сценариях. Например, двустороннюю очередь удобно реализовывать именно на связном списке: мы поддерживаем указатели на голову и хвост, и тогда каждая операция вставки или удаления остается \(O(1)\) .

Q: На рисунке "Определение связного списка и способ хранения" светло-голубой блок с указателем узла - это отдельный адрес памяти? Или он делит память пополам со значением узла?

Этот рисунок дает только качественное представление; количественно все зависит от конкретных условий.

• Значения узлов разных типов занимают разный объем памяти, например int , long , double и объекты-экземпляры.
• Размер памяти, занимаемой переменной-указателем, зависит от операционной системы и среды компиляции и обычно составляет 8 байт или 4 байта.

Q: Всегда ли добавление элемента в конец списка имеет сложность \(O(1)\) ?

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

Q: В утверждении "появление списка сильно повысило практическую полезность массива, но может приводить к потере части памяти" под потерями памяти имеется в виду дополнительная память под такие переменные, как емкость, длина и коэффициент расширения?

Потери памяти здесь в основном имеют два значения: во-первых, список обычно имеет некоторую начальную емкость, которая может быть нам не нужна целиком; во-вторых, чтобы избежать слишком частых расширений, емкость при расширении обычно умножается на некоторый коэффициент, например \(\times 1.5\) . Из-за этого появляется много пустых слотов, которые обычно нельзя полностью заполнить.

Q: В Python после инициализации n = [1, 2, 3] адреса этих трех элементов выглядят непрерывными, но после m = [2, 1, 3] можно заметить, что id элементов не идут подряд, а совпадают с одинаковыми числами из n . Если адреса элементов не непрерывны, остается ли m массивом?

Предположим, что элементами списка являются узлы n = [n1, n2, n3, n4, n5] . Обычно эти 5 объектов-узлов тоже будут храниться в разных местах памяти. Однако, имея индекс списка, мы по-прежнему можем за \(O(1)\) получить адрес памяти соответствующего узла и обратиться к нему. Это связано с тем, что в массиве хранятся ссылки на узлы, а не сами узлы.

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

Q: В C++ STL уже есть двусвязный список std::list , но в некоторых учебниках по алгоритмам им пользуются не так часто. Это связано с какими-то ограничениями?

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

• Накладные расходы по памяти: поскольку каждому элементу нужны два дополнительных указателя (на предыдущий и следующий элементы), std::list обычно занимает больше памяти, чем std::vector .
• Низкая дружелюбность к кэшу: поскольку данные не лежат непрерывно, std::list хуже использует кэш. В большинстве случаев std::vector показывает лучшую производительность.

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

Q: Операция res = [[0]] * n создает двумерный список. Каждый [0] в нем независим?

Нет, они не независимы. В таком двумерном списке все [0] на самом деле являются ссылками на один и тот же объект. Если изменить один из них, окажется, что меняются и все остальные соответствующие элементы.

Если нужно, чтобы каждый [0] был независимым, можно использовать res = [[0] for _ in range(n)] . В этом варианте создаются \(n\) независимых объектов-списков [0] .

Q: Операция res = [0] * n создает список. Каждый целочисленный 0 в нем независим?

В этом списке все целые числа 0 являются ссылками на один и тот же объект. Это связано с тем, что Python использует механизм кэш-пула для маленьких целых чисел (обычно от -5 до 256), чтобы максимально переиспользовать объекты и повысить производительность.

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

Однако если элементами списка являются "изменяемые объекты" (например списки, словари или экземпляры классов), то изменение одного элемента прямо меняет сам объект, и все элементы, ссылающиеся на него, увидят одно и то же изменение.

Оставляйте свои идеи, вопросы и предложения в комментариях