Что такое куча в программировании
Перейти к содержимому

Что такое куча в программировании

  • автор:

Куча (память)

Ку́ча (англ. heap ) в информатике и программировании — название структуры данных, с помощью которой реализована динамически распределяемая память приложения, а также объём памяти, зарезервированный под эту структуру.

Организация

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

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

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

Принцип работы

Для размещения и удаления динамических объектов используются примитивы «создать объект» (например, malloc) и «удалить объект» (например, free). Кроме того, перед началом работы программы выполняется инициализация кучи, в ходе которой вся изначально выделенная под кучу память отмечается как свободная.

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

При удалении объекта реализация примитива «удалить объект» отмечает, что область, ранее использованная удаляемым объектом, теперь свободна.

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

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

Алгоритмы кучи и производительность

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

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

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

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

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

Куча (программирование)

Сортирующее дерево (куча, пирамида) — такое двоичное дерево, для которого выполнены два условия:

  1. Каждый лист имеет глубину либо d либо d-1
  2. Значение в любой вершине больше (меньше), чем значения ее потомков.

структура данных для хранения сортирующего дерева

Удобная структура данных для сортирующего дерева — такой массив Array, что Array[1] — элемент в корне, а потомки элемента Array[i]Array[2i] и Array[2i+1].

\Theta \left( \log<n></p>
<p>Рассматривая кучу как дерево, определим ‘высоту’ ее узла как число ребер в самом длинном нисходящем простом пути от этого узла к какому-то из листьев дерева. Высота кучи есть высота ее корневого узла. Высота кучи равна \right)» width=»» height=»» />.</p><div class='code-block code-block-5' style='margin: 8px 0; clear: both;'>
<!-- 5eurosoft -->
<script src=

Базовые процедуры

В этом разделе представлены основные базовые процедуры для работы с кучей.

Heapify

O \left( \log<n></p>
<p>Процедура Heapify служит для поддержки свойства кучи и выполняется за время \right) » width=»» height=»» />.</p>
<p>Heapify A A A</p><div class='code-block code-block-6' style='margin: 8px 0; clear: both;'>
<!-- 6eurosoft -->
<script src=

Build_Heap

\Theta \left( n\log<n></p>
<p>Эта процедура предназначена для создания кучи из неупорядоченного массива входных данных. Время работы равно \right)» width=»» height=»» />.</p>
<p>Build_Heap<span <- length<span i <- floor<span /


<h4>Heapsort</h4>
<p><img decoding=

Процедура Heapsort сортирует массив без привлечения дополнительной памяти за время \right)» width=»» height=»» />.

Heapsort A

Heap_Change_Key

O \left( \log<n></p>
<p>Выполняет изменение элемента в куче за время \right) » width=»» height=»» />.</p><div class='code-block code-block-8' style='margin: 8px 0; clear: both;'>
<!-- 8eurosoft -->
<script src=

Heap_Change_Key AHeap_Insert

O \left( \log<n></p>
<p>Выполняет вставку в кучу за время \right) » width=»» height=»» />.</p>
<p>Heap_Insert</p><div class='code-block code-block-9' style='margin: 8px 0; clear: both;'>
<!-- 9eurosoft -->
<script src=

Heap_Extract

O \left( \log<n></p>
<p>Выполняет извлечение из кучи за время \right) » width=»» height=»» />.</p>
<pre>Heap_Extract <span heap_size<span < <span error <span пустаmax

См. также

Ссылки

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое "Куча (программирование)" в других словарях:

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

Основные принципы программирования: стек и куча

Обложка поста Основные принципы программирования: стек и куча

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

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

Стек

Стек — это область оперативной памяти, которая создаётся для каждого потока. Он работает в порядке LIFO (Last In, First Out), то есть последний добавленный в стек кусок памяти будет первым в очереди на вывод из стека. Каждый раз, когда функция объявляет новую переменную, она добавляется в стек, а когда эта переменная пропадает из области видимости (например, когда функция заканчивается), она автоматически удаляется из стека. Когда стековая переменная освобождается, эта область памяти становится доступной для других стековых переменных.

SQL запрос SELECT: значение и примеры

Из-за такой природы стека управление памятью оказывается весьма логичным и простым для выполнения на ЦП; это приводит к высокой скорости, в особенности потому, что время цикла обновления байта стека очень мало, т.е. этот байт скорее всего привязан к кэшу процессора. Тем не менее, у такой строгой формы управления есть и недостатки. Размер стека — это фиксированная величина, и превышение лимита выделенной на стеке памяти приведёт к переполнению стека. Размер задаётся при создании потока, и у каждой переменной есть максимальный размер, зависящий от типа данных. Это позволяет ограничивать размер некоторых переменных (например, целочисленных), и вынуждает заранее объявлять размер более сложных типов данных (например, массивов), поскольку стек не позволит им изменить его. Кроме того, переменные, расположенные на стеке, всегда являются локальными.

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

Куча

Куча — это хранилище памяти, также расположенное в ОЗУ, которое допускает динамическое выделение памяти и не работает по принципу стека: это просто склад для ваших переменных. Когда вы выделяете в куче участок памяти для хранения переменной, к ней можно обратиться не только в потоке, но и во всем приложении. Именно так определяются глобальные переменные. По завершении приложения все выделенные участки памяти освобождаются. Размер кучи задаётся при запуске приложения, но, в отличие от стека, он ограничен лишь физически, и это позволяет создавать динамические переменные.

Вы взаимодействуете с кучей посредством ссылок, обычно называемых указателями — это переменные, чьи значения являются адресами других переменных. Создавая указатель, вы указываете на местоположение памяти в куче, что задаёт начальное значение переменной и говорит программе, где получить доступ к этому значению. Из-за динамической природы кучи ЦП не принимает участия в контроле над ней; в языках без сборщика мусора (C, C++) разработчику нужно вручную освобождать участки памяти, которые больше не нужны. Если этого не делать, могут возникнуть утечки и фрагментация памяти, что существенно замедлит работу кучи.

Разработка на C++ с нуля в 2022 году: дорожная карта

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

Заключение

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

Принципы программирования: стек и куча: что это такое?

2stack-20219-1097c5.jpg

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

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

Стек — что это такое?

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

Итак, стек — это метод представления однотипных данных в порядке LIFO (Last In — First Out, то бишь, «первый вошел — последний вышел»). Некоторые ассоциируют стек с оружейным магазином для патронов, так как принцип работы схож, и первый вставленный в магазин патрон будет использоваться в последнюю очередь (у термина стек бывают и другие значения, поэтому, если речь идёт не об информационных технологиях, то смысл лучше уточнить).

Стек и простой жизненный пример

1stack-20219-ef97b7.jpg

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

Стек и особенности его работы

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

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

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

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

Для чего нужен стек?

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

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

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

Стеки и операции стека

Если говорить об основных операциях, то стек имеет таковых две: 1. Push — ни что иное, как добавление элемента непосредственно в вершину стека. 2. Pop — извлечение из стека верхнего элемента.

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

Как организуется стек?

Когда программисты организуют или реализуют стек, они применяют два варианта: 1. Используя массив и переменную, указывающую на ячейку вершины стека. 2. Используя связанные списки.

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

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

Стек и куча

Куча — хранилище памяти, расположенное в ОЗУ. Оно допускает динамическое выделение памяти и работает не так, как стек. По сути, речь идёт о простом складе для ваших переменных. Когда вы выделяете здесь участок памяти для хранения, к ней можно обращаться как в потоке, так и во всём приложении в целом (именно так и определяются переменные глобального типа). По завершении работы приложения все выделенные участки освобождаются.

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

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

Итак, теперь вы знаете и что такое стек, и что такое куча. Это довольно простые знания, больше подходящие для новичков. Если же вас интересуют более серьёзные профессиональные навыки, выбирайте нужный вам курс по программированию в OTUS!

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *