Обзор того, как работают массивы

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

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

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

Перемотать время назад

Объекты и функции и все, что мы знаем о компьютерах, в основном хранятся в битах и ​​байтах в компьютере.

В таких языках, как Java и C, вы должны заранее явно объявить размер массива.

Подождите, но Ruby этого не делает?

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

Это здорово, не правда ли ?! Это означает, что массивы бесконечно велики, не так ли? И что Ruby - лучший язык? Нам повезло!

Но не так быстро. * всплывает пузырь *

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

Чтобы понять, что такое динамические массивы, давайте сначала посмотрим, как массивы представлены в памяти. Поскольку MRI Ruby (Matz ’Ruby Interpreter) компилируется до кода C, мы рассмотрим, как массивы представлены в C.

C-ing верит

Мы немного углубимся в код C, чтобы помочь нам немного лучше… :)

В языках более низкого уровня, таких как C, вы должны сами иметь дело с указателями и распределением памяти. Даже если вы раньше не сталкивались с C (d isclaimer - я тоже), у вас может быть C-een один из самых (не) известных примеров ниже:

Давайте разберем этот фрагмент кода:

• malloc не имеет никакого магического значения, это буквально означает memory allocation
• malloc возвращает указатель
• malloc принимает аргумент, который представляет собой размер памяти, которую программа должна выделить для вас.
• 100 * sizeof(int) сообщает программе, что мы хотим сохранить 100 целых чисел, поэтому выделите нам 100 * размер того, что занимало бы каждое целое число.
• ptr / указатель хранит ссылку на адрес памяти.

Тимми хранит багаж!

Если приведенный выше пример не имеет смысла, попробуйте эту аналогию. Думайте о распределении памяти как о багажном консьерже. Работает это так:

• Тимми идет к стойке, говорит консьержу, что у него есть 2 места багажа, примерно этого большого, и что он хотел бы оставить их на складе.
• Консьерж осматривает складское помещение и говорит: «Да, у нас есть место в обозначенной B4 зоне, и мы выделим это место для хранения вашего багажа».
• Они передают Тимми карточку для получения с обозначенным местом на ней, B4 в нашем случае.
• Тимми счастлив, ходит и делает что угодно, а когда хочет забрать свой багаж, он возвращается к стойке и показывает им свою карточку получения. «Ты забрал мой багаж?»

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

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

Кроме того, вы когда-нибудь задумывались, почему вы получаете доступ к элементам в массиве с помощью индекса, например?

Это связано с тем, что массив содержит ссылки на блок памяти, а индекс сообщает ему смещение.

Аналогия: если я попрошу вас искать Тимми в очереди из 20 человек, вы, по логике, должны спросить каждого из них, были ли они Тимми. Но если я скажу вам, что Тимми - шестой (указатель) от первого лица (ваш исходный указатель), вы точно знаете, где искать.

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

Что же тогда такое динамические массивы?

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

Помните, как вам нужно явно указать необходимый вам объем памяти? Это означает, что в массиве найдется место, которое будет точно соответствовать вашему размеру. Нет гарантии, что он сможет вместить больше, чем у вас есть (потому что блок памяти сразу за ним может быть занят).

Вернемся к нашей аналогии с багажом: представьте, что Тимми должен хранить 2 единицы багажа, а B4 может хранить ровно 2 единицы багажа, поэтому они передают это Тимми. Теперь по какой-то причине Тимми хочет хранить другую единицу багажа, но B4 не может хранить 3 единицы, а только 2, так что они делают?

Они берут весь его существующий багаж, перемещают его на новое место, где может поместиться более трех предметов, а затем хранят их все вместе.

Это дорогостоящая операция, но именно так работает и память!

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

Что делает динамический массив, так это то, что если массив приближается к своей полной емкости, он автоматически объявляет новый, более крупный массив и перемещает в него все существующие элементы, а затем старый массив собирается сборщиком мусора. Насколько больше? Фактор роста обычно 2; удвоить размер текущего массива.

На самом деле, не верьте мне на слово.

В Ruby есть модуль ObjectSpace, который позволяет нам взаимодействовать с текущими объектами, живущими в памяти. Мы можем использовать этот модуль, чтобы взглянуть на использование памяти нашим динамическим массивом - звучит именно так, как мы хотим!

Я написал небольшой скрипт на Ruby, который вычисляет коэффициент роста динамического массива. Не стесняйтесь взглянуть на это здесь, и если вы это сделаете, вы увидите, что массивы Ruby имеют коэффициент роста в 1,5 раза (то есть они создают массив, который на 50% больше на каждой копии).

Я знаю, что такое массивы, что такое связанные списки?

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

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

Это похоже на то, как будто Тимми пытается хранить 5 единиц багажа, а у консьержа нет места и он решает оставить их повсюду. Звучит неорганизованно?

Кроме того, если они хранятся в разных местах, как узнать, какие сумки принадлежат Тимми? Подсказка: просто отслеживайте следующий узел / сумку! В нашем случае консьерж хранит их отдельно, но с меткой на каждой из них, указывающей на следующую сумку.

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

node = [ data | pointer ]

Например, учитывая следующий пример, хранящийся в памяти:

[C | D] [A | B] [B | C] [D | nil]

Эти биты выглядят так, как будто они не в порядке, но если бы я сказал вам, что первый элемент - это A, вы могли бы сказать мне точный порядок в списке:

list = [A -> B -> C -> D -> nil]

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

Вы также можете прочитать больше о List / Cons на Wiki здесь.

Заключительная записка

Изначально я написал эту статью для немного другой темы - [Эликсир | Почему именно связанные списки?] , Но обнаружил, что мне потребовалось слишком много времени, чтобы объяснить, как работают массивы, прежде чем я смог объяснить, почему Elixir использует связанные списки. Поэтому я разделил их на две статьи.

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

Источники

1. Https://medium.com/@rebo_dood/ruby-has-a-memory-problem-part-1-7887bbacc579 - Здесь я узнал о дополнительных ObjectSpace методах, потребовав их

Изначально размещено на dev.to