Демистификация массивов: структура данных массива

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

Определение. Массив — это набор похожих элементов, хранящихся в смежных ячейках памяти.

Тип данных массива

Структуру данных массива можно математически смоделировать с помощью двух операций.

get(A, I): получить данные, хранящиеся в индексе I.

set(A, I, V): установить значение по индексу I массива A в V

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

Типы массивов:

Одномерные массивы. Простым примером использования может быть хранение оценок 1 учащегося по 3 различным предметам, например, учащийся X набрал 70, 60, 90 баллов по математике, физике и химии соответственно . Его можно представить с помощью одномерного массива как [60, 70,55]. Обычно индексы массива начинаются с 0 (смещение, т.е. первый элемент находится на расстоянии 0 от начального адреса массива).

На рисунке выше показан одномерный массив, в котором хранятся оценки, набранные 1 учащимся по 3 предметам.

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

На приведенном выше рисунке показано логическое представление двумерного массива, представляющего оценки, полученные 3 учащимися по 3 предметам.

Многомерные массивы. У нас также могут быть глубоко вложенные массивы. Трехмерный массив — это массив двумерных массивов, четырехмерный массив — это массив трехмерных массивов и т. д. например, массив пакетов. Каждый элемент представляет пакет в виде массива учащихся, где каждый элемент в массиве учащихся представляет учащегося в виде массива оценок, полученных им/им по определенному предмету. то есть, оценки[2][3][1] дают вам оценки, полученные по 1-му предмету 3-м учеником в пакете 2.

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

Давайте посмотрим, как значения хранятся в памяти…

Здесь мы рассмотрим сохранение 32-битного целочисленного значения 4. Десятичное значение 4 хранится как двоичное в 32 битах (4 байта). например, 0000 0000 0000 0000 0000 0000 0000 0100

Предположим, что компилятор сохранил значение по адресу памяти 2004 (0x7D4).

На рисунке выше показано представление целого числа 4 в памяти (при условии, что переменные int занимают 4 байта). Оно занимает адреса 2004, 2005, 2006 и 2007. Адрес памяти часто выражается в шестнадцатеричном формате, например, 0x7D0, 0x7D4 и т. д.

Так как же хранить массив целых чисел?

Он хранит набор элементов в непрерывных ячейках памяти.

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

Скажем, мы объявляем массив, intmarks[3] = {10, 20, 15}. Память для хранения 3 целых чисел выделяется в смежных местах.

Мы можем инициализировать массив во время компиляции (как мы сделали в приведенном выше примере на языке C) или мы можем сделать это во время выполнения. например, путем чтения пользовательского ввода.

Почему мы должны указывать количество целых чисел, которые нам нужно сохранить в массиве, когда мы его объявляем?

Потому что компьютеру необходимо выделить непрерывную память для всех элементов массива. Помните, что массив — это набор похожих элементов в смежных ячейках памяти. Итак, если мы объявим intmarks[3]; а затем мы пытаемся сохранить 4-й элемент, может оказаться невозможным добавить его в непрерывную ячейку памяти, поскольку это место могло быть уже занято какой-то другой переменной.

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

Что ж, я могу объявить массив, например, let markers = [ ] и добавить в него столько элементов, сколько захочу, в любой момент, если я использую JavaScript (и некоторые другие языки). Почему?

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

Теперь как он хранит двумерный массив или многомерный массив?

У него есть 2 подхода — row-major, где мы храним элементы по строкам. то есть сохранить 1-ю строку, затем 2-ю строку и так далее. Затем есть column-major , где мы храним его по столбцам. то есть сохранить 1-й столбец, затем 2-й столбец.

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

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

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

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

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

Хорошо, а как насчет массива сложных типов данных? скажем, массив структур...

Попробуем понять это с помощью картинки.

struct student{
 char name[8];
 float marks;
 int id;
};
struct student studentArray[2];

Размер структуры не всегда будет суммой размеров ее элементов из-за заполнения структуры. Архитектура компьютерного процессора такова, что он может считывать 1 слово (4 байта в 32-битном процессоре) из памяти за раз. Чтобы воспользоваться этими преимуществами, данные всегда выравниваются как 4-байтовый пакет, чтобы сократить циклы чтения памяти.

Ну а теперь пришло время поговорить об указателях

Давайте посмотрим на приведенный ниже фрагмент кода…

int arr[5];

Что происходит в строке выше?

Он выделяет память для хранения 5 целочисленных значений. Предположим, что int занимает 4 байта на этой конкретной машине, тогда он выделяет 4 * 5 = 20 байтов пространства в памяти. Здесь идентификатор arr представляет собой указатель типа int, указывающий на первый слот.

На приведенном выше рисунке каждый блок представляет 4 байта. Идентификатор arr содержит адрес до первого индекса массива arr

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

int arr[2][3];

Здесь идентификатор arr указывает на одномерный массив, который, в свою очередь, указывает на целое число. Вы можете рассматривать двумерный массив как указатель на одномерный массив. Точно так же трехмерный массив как указатель на двумерный массив и так далее.

Здесь на приведенном выше рисунке arr , arr[0] , &arr[0][0] все указывают на одну и ту же ячейку памяти, т. е. первый слот. arr указывает на одномерный массив int , arr[0] указывает на int , arr[0][0] дает фактическое значение в слоте, равное 3, а &arr[0][0] дает адрес 2000

Если мы попытаемся углубиться в более подробную информацию об отношении указателя и массива, мы увидим, что arr[4] на самом деле означает *(arr + 4), т. е. значение по адресу, заданному арифметикой указателя arr + 4. Теперь как мы вычисляем arr + 4? Это зависит от того, на что указывает arr. Если arr представляет собой одномерный массив, то есть указатель на целое число, то arr + 4 означает адрес, хранящийся в arr + 4 * sizeof(int)

Давайте рассмотрим пример, скажем, arr представляет собой одномерный массив целых чисел и указывает на первый слот с адресом 2000. Предположим, что int занимает 4 байта на конкретной машине, arr[2], что равно *(arr + 2) , что совпадает со значением, хранящимся по адресу arr + 4. Теперь arr + 4 = 2000 + 4 * (4) = 2016

В общем случае для одномерного массива arr[i] = *(arr + i ) и &arr[i] = arr + i. Здесь arr +i — это арифметика указателя (т. е. вы должны учитывать тип значения, на которое указывает arr). arr + 1 изменяет размер int, когда a указывает на int, аналогично, arr + 1 изменяет размер одномерного массива, когда a является двухмерным массивом, т. е. arr указывает на одномерный массив.

Теперь для двумерного массива:

int arr[2][3];

Предполагая реализацию по строкам, arr указывает на одномерный массив, который может хранить 3 целых числа. Итак, здесь arr + 1 перепрыгивает слоты, которые могут хранить 3 целых числа, т.е. 3 * 4 = 12 байтов, и это будет достигать первого байта следующей строки (массив 1-d).

Здесь, на приведенном выше рисунке, arr + 1 дает 2000 + 1 * (3 * 4) = 2012, что является адресом начального местоположения 2-й строки / 1-го массива.

Чтобы сделать его еще более интересным, arr[1] = 1[arr] = *(arr + 1) = *(1 + arr)

Для двумерных массивов

arr[i][j] = *(arr + i) + j

arr + i — указатель на одномерный массив iᵗʰ. Таким образом, *(arr + i) дает фактический массив 1-d, а массив 1-d является указателем на int. Таким образом, указатель на int + j перейдет к jᵗʰ int в массиве iᵗʰ 1-d, который представляет собой [i][j]

Что ж, на этом обсуждение отношения указатель-массив должно быть завершено.

А как насчет других языков программирования?

Скажем, JavaScript. Мы можем объявить массив, как показано ниже:

let arr = []

Я могу добавить любое количество элементов в этот список, например:

arr.push(7)
arr.push(8)

Это не фиксированный размер в JavaScript, верно? Значит ли это, что JavaScript лучше, чем C?

Давайте посмотрим, чем отличаются массивы JavaScript.

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

Мы знаем, что массив – это набор похожих элементов в смежных ячейках памяти. Но я могу хранить смешанные типы в массивах JavaScript или списках Python и т.д. c Почему?

Python использует списки. Подумайте о связанных списках.

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

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

Теперь давайте рассмотрим некоторые основные операции с массивами.

Мы рассмотрим следующие операции:

Доступ к элементу по определенному индексу
Обход всего массива от индекса 0 до (n-1), где n - размер массива
Нахождение максимального/минимального элемента в массиве
Поиск второго по величине/второго по величине элемента в массиве
Перевернуть массив
Отсортировать массив по возрастанию/убыванию
Поиск, существует ли конкретный элемент в массиве
Удаление дубликатов из массива
Нахождение пика в массиве
Повернуть массив

Мы будем использовать псевдокод для реализации вышеуказанных операций:

Доступ к элементу по определенному индексу

Это было бы самым простым. Скажем, вы хотите получить доступ к элементу по индексу i массива arr, где 0 ≤ i ‹ n (n — размер массива) , arr[i] даст вам его.

Сложность O(1) , так как

обр[я] = *(обр + я).

2. Обход всего массива от индекса 0 до (n-1), где n – размер массива

for i = 1 to n
    print arr[i]

Сложность – O(n), так как описанный выше цикл будет выполняться n (длина arr)раз для каждого i = 1, i = 2, … до i = n.

3. Нахождение максимального/минимального элемента в массиве

max = min = arr[1]
for i = 1 to n
    if arr[i] > max
        max = arr[i]
    if arr[i] < min
        min = arr[i]

Сложность равна O(n), так как мы проходим по всему массиву (при условии, что массив несортированный).

4. Поиск второго по величине/второго по величине элемента в массиве

smallest = secondSmallest = INT_MAX
for i = 1 to n
    // if the item is smaller than the smallest , then update both
    if arr[i] < smallest
        secondSmallest = smallest
        smallest = arr[i]
// if the item lies between smallest and second smallest , update second smallest
    if arr[i] < secondSmallest and arr[i] != smallest
        secondSmallest = arr[i]

Теперь второй по величине можно реализовать с небольшой доработкой приведенного выше кода.

largest = secondLargest= INT_MIN
for i = 1 to n
    // if the item is larger than the largest, then update both
if arr[i] > largest
        secondLargest = largest
        largest = arr[i]
// if the item lies between largest and second largest , update second largest
    if arr[i] > secondLargest and arr[i] != largest
        secondLargest = arr[i]

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

5. Обратить массив

start = 1 , end = n
while start < end
    swap(arr[start],arr[end])
    start = start + 1
    end = end - 1

Сложность O(n), так как цикл выполняется n/2 раза.

6. Сортировка массива по возрастанию/убыванию

Здесь мы рассмотрим алгоритм сортировки вставками, который имеет сложность O(n²). Алгоритм сортировки слиянием использует разделяй и властвуй и дает нам O (nlogn)

Упорядочить в порядке возрастания:

for i = 2 to n
    key = arr[i]
    j = i - 1
    while j > 0 and arr[j] > key
        arr[j + 1] = arr[j]
        j = j - 1
    arr[j + 1] = key

Сортировать по убыванию:

for i = 2 to n
    key = arr[i]
    j = i - 1
    while j > 0 and arr[j] < key
        arr[j + 1] = arr[j]
        j = j - 1
    arr[j + 1] = key

7. Поиск наличия определенного элемента в массиве

Мы будем использовать линейный поиск (предполагая несортированный массив). Он возвращает индекс элемента, если элемент найден, иначе он возвращает -1.

for i = 1 to n
    if arr[i] == item
        return i
    return -1

Сложность — O(n), так как здесь нам придется пройти весь массив.

8. Удаление дубликатов из массива

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

//sort array using any sorting algorithm e.g, merge sort
sort(arr)
//declare a temp array to hold unique elements
temp = []
i = 0, j = 0
while i < n
    // insert arr[i] into temp
    temp[j] = arr[i]
    //move i to next unique element. Duplicates will come together 
    // when you sort the array
    while arr[i] == arr[i+1]
        i = i + 1
    i = i + 1
    j = j + 1 // j gives you the no:of unique elements

Сложность = сложность сортировки + обход массива. Если для сортировки используется сортировка слиянием, это будет O(nlogn) + O(n), то есть O(nlogn)

9. Поиск пика в массиве

Элемент arr[i] является вершиной, если arr[i-1] ≤ arr[i] ≤ arr[i+1] . Пик всегда существует на основе вышеуказанного условия.

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

findPeak(arr, start , end)
    mid = start + (end - start)/2
    //you can add checks to ensure mid - 1 and mid + 1 are valid
    // array indices       
    if arr[mid -1] <= arr[mid] and arr[mid + 1] <= arr[mid]
        return arr[mid] //peak is at index mid
    if arr[mid -1] >= arr[mid]
        findPeak(arr, start, mid -1) //recursive call
    else if arr[mid + 1] >= arr[mid]
        findPeak(arr , mid + 1 , end)

Первоначальный вызов будет findPeak(arr, 1 , n)

Сложность O(logn), так как при каждом вызове размер массива уменьшается вдвое. n , n/2 , n/4 и т. д. до 1 . то есть он работает logn раз.

10. Поворот массива

например, поворот массива влево [ 1, 2, 3, 4, 5 ] на 2 элемента даст [ 3, 4, 5, 1, 2 ]

rotate(arr)
    temp = arr[0] //holds the first item of arr
    for i = 1 to n
        arr[i] = arr[i+1] // shift elements by 1 position
    arr[i] = temp // copy the first element to index i(i is the last index by the time loop finishes)

Теперь, если нам нужно повернуть массив k раз.

for i = 1 to k
    rotate(arr)

Сложность = количество раз, когда вызывается ротация * количество, когда цикл в функции поворота выполняется. т. е. O (n * k)

Хорошо. Мы много обсуждали, верно? Может быть, теперь нам следует обратить внимание на некоторые недостатки структуры данных массива…

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

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

Разработчик: «Эй, я хочу хранить 1000 целых чисел»

Компилятор: «Хорошо, объявите целочисленный массив размером 1000. Об остальном я позабочусь».

Разработчик: «Круто»

Компилятор: «Эй, что случилось? Вы просили меня зарезервировать 1000 мест, но теперь вы дали мне только 10 позиций. Что мне делать с остальными 990 местами ?»

Разработчик: «Ой, извините! Я ожидал 1000, но, похоже, будет только 10».

Составитель: «Тебе еще нужно заплатить за 1000 мест»

Разработчик: «Ура! Да, памяти много. В следующий раз буду осторожнее»

Составитель: «Тебе лучше быть»

Еще один день…

Разработчик: «Привет, у меня для тебя кое-что есть. Зарезервируй мне 10 мест для целых чисел»

Компилятор: «10 ? Вы уверены ?"

Разработчик: «О да! На этот раз я так много думал об этом. Больше никаких потерь»

Компилятор: «Хорошо для вас»

Компилятор: «Эй, я не понимаю. Вы попросили меня зарезервировать 10 мест, а теперь присылаете мне 100 целых чисел. Куда мне девать этих 90 парней? У меня нет для них места. Меня это совсем не устраивает»

Разработчик: «Я тоже»

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

Допустим, мы объявили массив для хранения 1000 целых чисел, тогда он резервирует место в памяти 1000 * 4 = 4000 байт. А что, если в итоге мы сохранили только 10 целых чисел, т. е. 10 * 4 = 40 байт. Ой!! 3960 байт потрачены впустую, потому что зарезервированные места нельзя использовать ни для чего другого.

Другим сценарием может быть то, что нам нужно хранить более 1000 целых чисел, теперь нет места для более чем 1000 целых чисел.

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

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

Спасибо! Увидимся в другой раз.