Я — Денис, Junior Android-разработчик в «Лайв Тайпинге». В этой статье расскажу о массивах. Вы узнаете: как они устроены в памяти компьютера, особенности реализации в разных ЯП, оптимизациях, а также частых вопросах на собеседованиях.

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

Введение

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

Никлаус Вирт, швейцарский ученый-информатик, в 1976 году написал книгу под названием «Алгоритмы + Структуры данных = Программы».

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

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

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

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

Структура данных — это?

Хабр

Структура данных — это контейнер, информация в котором скомпонована характерным образом. Благодаря такой «компоновке», структура данных будет эффективна в одних операциях и неэффективна — в других.

Яндекс

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

Википедия

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

Характеристики структур данных

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

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

Характеристики структур данных следующие:

• данные в памяти представлены определённым образом, который однозначно позволяет определить структуру;

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

• существуют алгоритмы, которые позволяют взаимодействовать с этой структурой.

Типы структур данных

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

• смежные структуры данных реализованы в виде непрерывных блоков памяти. К ним относятся массивы, матрицы, кучи и хэш-таблицы;

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

Важные структуры данных

1. массив (Array);

2. динамический массив (Dynamic array);

3. связный список (Linked list);

4. стек (Stack);

5. очередь (Queue);

6. множество (Set);

7. карта (Map);

8. двоичное дерево поиска (Binary search tree);

9. префиксное дерево (Trie);

10. граф (Graph).

Массив

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

Основы

Одна из самых простых структур данных, которая встречается чаще всего. Именно на массивах основаны многие другие структуры данных: списки, стеки, очереди.

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

Массивы бывают двух видов:

• Одномерные

У каждого элемента только один индекс. Можно представить это как строку с данными, где одного номера достаточно, чтобы чётко определить положение каждой переменной.

• Многомерные

У каждого элемента два или больше индексов. По сути, это комбинация из нескольких одномерных массивов, то есть вложенная структура.

Область применения

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

• для хранения несложных данных небольших объёмов;

• для сортировки данных.

Достоинства массивов

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

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

Недостатки

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

Динамический массив

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

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

Очевидным расточительством в этой процедуре является операция копирования содержимого старого массива в новый при каждом удвоении размера массива. Первый вставленный элемент нужно будет перекопировать при расширении массива после 1-ой, 2-ой, 4-ой, 8-ой и т. д. вставок.

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

Если половина элементов перемещается один раз, четверть элементов два раза и т. д, то общее число перемещений определяется следующей формулой:

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

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

Область применения

• в качестве блоков для структур данных;

• для хранения неопределённого количества элементов.

Работа с памятью

Под каждое значение выделяется некоторый объем памяти в соответствии с типом, в которой и хранится само значение. А как должна выделиться память под хранение массива? И что такое массив в памяти? На уровне хранения, понятия массив не существует. Массив представляется цельным куском памяти, размер которого вычисляется по следующей формуле:

n — количество элементов;

M — количество памяти под каждый элемент.

Из этого утверждения есть два интересных вывода:

• размер массива — фиксированная величина;

• все элементы массива имеют один тип и занимают одно и то же количество памяти. Благодаря этому появляется возможность простым умножением (по формуле, описанной выше) получить адрес той ячейки, в которой лежит нужный нам элемент.

Индекс в массиве — смещение относительно начала куска памяти, содержащего данные массива. Адрес, по которому расположен элемент под конкретным индексом, рассчитывается так:

A — начальный адрес;

index — индекс;

M — количество памяти (для данного типа данных).

Начальный адрес, это адрес ячейки памяти, начиная с которой размещается массив. Он формируется во время выделения памяти под массив.

Если предположить, что тип int занимает в памяти 2 байта (зависит от архитектуры), то адрес элемента, соответствующего индексу 3, вычисляется так:

В такой формуле расчета адреса, есть ровно один способ физически разместить данные в начале доступной памяти – использовать нулевой индекс: начальный адрес + 0 * размер элемента конкретного типа = начальный адрес.

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

Массивы в языках высокого уровня

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

Capacity

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

В Kotlin напрямую нельзя узнать какая capacity у массива. Но это можно сделать в Go:

s := make([]int, 0, 5)
fmt.Println("Длина:", len(s)) // Выводит: size = 0
fmt.Println("Емкость:", cap(s)) // Выводит: capacity = 5

У ArrayList capacity по умолчанию составляет 10 (в классе ArrayList есть константа DEFAULT_CAPACITY, равная 10). Если добавить элементы и их количество достигнет 10, то будет создан новый массив с размером ячеек, и данные из старого массива будут скопированы в новый. При каждом последующем увеличении массива будет создан новый массив (на 25, 38, 58...), и данные будут копироваться в него из старого.

Если заранее известно, что в массив нужно будет добавить много элементов, то имеет смысл указать нужное значение capacity при создании массива, при помощи метода ensureCapacity. В этом случае не будет необходимости многократно создавать новые массивы и копировать данные в них.

Оптимизации в Kotlin

Один из способов оптимизации при работе с массивами — использование встроенных методов. Далее мы рассмотрим их.

Метод trimToSize() — встроенный метод класса ArrayList<T>. Принцип его работы прост. Например, вы создали массив на четыре элемента, при этом capacity будет равен десяти по умолчанию. Но нужны ли вам пустые ячейки в памяти? Если нет, то можно воспользоваться методом trimToSize(). Он уменьшит capacity с десяти до одного.

/*
Уменьшает capacity массива до его текущего размера.
*/

val array = arrayListOf(3)
array.trimToSize()

Метод ensureCapacity() — тоже встроенный метод класса ArrayList<T>. У него есть единственный параметр minCapacity, который принимает capacity, которое необходимо установить массиву. При этом отрицательные значения будут игнорироваться.

/*
Увеличивает capacity массива, чтобы он мог содержать как минимум
количество элементов, указанное в minCapacity.
*/

val array = arrayListOf(3)
array.ensureCapacity(5000) // теперь массив может хранить до 5000 элементов

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

trimToSize

Kotatsu — приложение для чтения манги.

suspend fun getAllTracks(): List<TrackingItem> {
  val result = ArrayList<TrackingItem>()
  ...
  if (AppSettings.TRACK_HISTORY in sources) {
    val history = repository.getAllHistoryManga()
    val historyTracks = repository.getTracks(history)
    ...
    for (track in historyTracks) {
      if (knownManga.add(track.manga.id)) {
        result.add(TrackingItem(track, channelId))
      }
    }
  }
  result.trimToSize() // тут
  return result
}

Signal — мессенджер

class SignalInstrumentationApplicationContext : ApplicationContext() {
  override fun initializeLogging() {
  Log.initialize({ true }, AndroidLogger(), PersistentLogger(this))
  SignalProtocolLoggerProvider.setProvider(CustomSignalProtocolLogger())

  SignalExecutors.UNBOUNDED.execute {
    Log.blockUntilAllWritesFinished()
    LogDatabase.getInstance(this).logs.trimToSize() // тут
  }
}

ensureCapacity

С этим методом немного сложнее. Он в основном используется в исходном коде JetBrains. Также этот метод можно встретить в тестах работы с массивами, но это нам сейчас не важно. Вероятно, только малое количество разработчиков из сообщества Kotlin знакомо с этим методом. Либо просто не нашло ему применение для прикладных задач. Хотя при помощи этого метода можно избежать большое количество перестановок из-за роста размера массива.

Реализация в разных ЯП

Clang

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

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

int a[] = { 5, 4, 3, 2, 1 };

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

/* 
массив из трех элементов, внутри которого массивы по 10 элементов
это значит, что здесь можно хранить 3 строки длиной не больше 10 символов
*/

char strings[3][10] = {
  "spike",
  "tom",
  "jerry"
};

strings[0]; // spike

Golang

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

В отличии от массивов в С, работа со строками тут реализована также как в языках высокого уровня. А также Go имеет несколько built-in функций для работы с массивами. Но функциональность этих функций сильно уступает другим ЯП высокого уровня.

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

var planets [8]string
planets[0] = "Меркурий" // Присваивает планете индекс 0
planets[1] = "Венера"
planets[2] = "Земля"
earth := planets[2] // Получает планету с индексом 2
fmt.Println(earth) // Выводит: Земля

Python

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

import array as arr
numbers = arr.array('i',[10,20,30])

Kotlin

В Kotlin/Java массивы представлены как объекты. Они также типо-безопасны, так как тип вычисляется во время компиляции. Это гарантирует, что в массив могут быть сохранены только элементы указанного типа.

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

Для создания статического массива в Kotlin нужно написать следующий код:

/*
inline fun <reified T> arrayOf(vararg elements: T): Array<T> { }
при этом arrayOf метод является built-in функцией
в отличии от библиотеки коллекций, которая поставляется с Java
*/

val arr = arrayOf(1, 2, 3)
// или
val arr = Array<Int>(3) { 0 }

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

val bytes = byteArrayOf(42)
val shorts = shortArrayOf(42)
val ints = intArrayOf(42)
val longs = longArrayOf(42)
val floats = floatArrayOf(42.0f)
val doubles = doubleArrayOf(42.0)
val chars = charArrayOf('a')
val booleans = booleanArrayOf(true)

/*
bytecode
0: iconst_1
1: newarray  byte
/

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

Array<Int> — это Integer[] под капотом, в то время как IntArray — это int[]. Это означает, что когда вы поместите Int в Array<Int>, он всегда будет в boxed. В случае IntArray boxed не произойдет, потому что он преобразуется в примитивный массив Java.

Для создания динамического массива (автоматически увеличивает capacity) нужно написать следующий код:

/*
fun <T> arrayListOf(vararg elements: T): ArrayList<T> { }
возвращает экземпляр ArrayList<T>()
который является реализацией List по умолчанию.
таким образом, детали реализации изменяемого списка абстрагированы
*/

val arr = arrayListOf(1, 2, 3)
// или
val arr = ArrayList<Int>(initialCapacity = 3)

Иерархия

В рамках коллекций в Java/Kotlin класс Array находится вне этой иерархии. А стоит как отдельный класс.

ArrayList — это конкретная реализация интерфейса List. Внутри он использует массив, отсюда и название. Однако ArrayList не является массивом. List, LinkedList, MutableList и ArrayList — семейство списочных структур в Kotlin. Важно понимать, что под капотом используются массивы с дополнительным функционалом. При этом mutableListOf() и arrayListOf() под капотом создают ArrayList.

Основные операции

Для статических массивов это операции:

• get — получение элемента по индексу;

• set — запись элемента по индексу;

• fill — заполняет значением весь массив:

val arr = arrayListOf(1, 2, 3)
arr.fill(1)
arr.forEach(::println) // [1, 1, 1]

• copyOf, clone — копирует весь массив; copyOfRange — копирует часть массива:

При этом метод clone после вызова создает shallow копию массива. При изменении оригинального массива, эти изменения отразятся в копии.

Напротив метод copyOf не привязан к оригинальному источнику, поэтому изменения не затронут копию.

arr.copyOf()
arr.clone()

Но при этом метод copyOf уступает в производительности методу clone:

Время необходимое для copyOf: 32825 ms
Время необходимое для clone: 30138 ms

• plusElement — добавляет один элемент к исходному массиву и возвращает новый массив;

• reverse — переворачивает массив полностью или только часть с указанием диапазона;

• slice — возвращает срез массива;

• sort — сортирует массив за , TimSort, QuickSort (2 pivot);

• contentDeepEquals — сравнивает два массива по их элементам.

Для динамических массивов это операции:

• все, которые были представлены для статических массивов;

• add — добавляет новый элемент в массив; addAll — добавляет целый массив в другой массив;

• Collection.sort — сортировка данных производиться после конвертации в массив, после вызывается метод sort для массива за ;

• дополнительные методы для агрегирования над данными.

Vararg

Чтобы передать функции переменное количество аргументов, мы должны объявить эту функцию с параметром vararg. Внутри тела функции мы можем рассматривать параметры vararg как массив:

fun <T> printAll(vararg ts: T) {
  ts.forEach { println(it) }
}

Для vararg ссылочного типа параметр vararg будет рассматриваться как массив этого ссылочного типа. Например, в приведенном выше примере параметр ts будет доступен как Array<T> в теле функции. Аналогичным образом в следующем примере это будет Array<String>:

fun printStrings(vararg vs: String) {
  vs.forEach { println(it) }
}

Однако для примитивных типов параметр vararg будет действовать как специализированные типы массивов Array. Например, в функции sum() параметр vararg представляет собой массив IntArray в теле функции.

Список vs массив

Чистые массивы в Kotlin представлены в классе Array и не относятся к пакету Collection. Они не изменяемы и представляют из себя чистую структуру данных типа JVM array.

Списки же в свою очередь входят в пакет Collection. Они изменяемы. Под капотом используют массивы. Но при этом массивы эффективнее и быстрее нежели списки.

Fun fact

Условно есть массив на 100к элеметов типа String. В каждой ячейки массива лежит строка на 100к символов кодировки UTF-8. Сколько памяти потребуется, чтобы разместить такой массив в памяти компьютера?

В JVM, в ячейке массива лежит указатель на строку, а не сама строка, как и для любого массива, содержащего не примитивы. Для 64-битной JVM это 100к 8-байтовых указателей, т.е. 800 000 байт = 0,0008гб. А строки лежат, например в куче. Кроме того, длина строки не является частью сигнатуры типа для массива, поэтому при создании массива 100к под один элемент не выделяются и не предполагаются, потому что эти строки уже где-то размещены к этому моменту (например в куче). И они могут быть разной длины.

Обратите внимание, что, начиная с Java 9, класс String будет использовать только 1 байт на символ, и при необходимости 2 байта на символ.

Безопасность

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

Скорость

По большой части такие языки как C, C++, Fortran и пр. языки низкого уровня ЯП будут работать с массивами эффективнее и быстрее чем в языки высокого уровня. Но отрыв будет не столь большой. Асимптотика массивов останется +- на том же уровне в любом ЯП. Списки же в Kotlin работают медленнее нежели чистые массивы.

Complexity

Вопросы, часто задаваемые на собеседованиях

Найти второй минимальный элемент массива

val array = arrayOf(1, 2, 3)

/*
первый способ:

отсортировать массив по возрастанию
и выбрать второй элемент

complexity: O(n*logn)
*/

array.sort().second()

/*
второй способ:

если число из массива < первого и второго минимального числа, то
первое минимальное число будет = числу из массива
в противном случае, если первое и второе минимальное
число < числа из массива, то второе минимальное число
будет = числу из массива

complexity: O(n)
*/

var firstMin = Int.MAX_VALUE
var secondMin = Int.MAX_VALUE

array.forEach { num ->
  if (num < secondMin && num < firstMin) {
    firstMin = num
  } else if (firstMin < num && num < secondMin) {
    secondMin = num
  }
}

Найти неповторяющиеся числа в массиве

const val DEFAULT_VALUE = 0
const val ONE_INSTANCE = 1

val array = intArrayOf(1, 3, 4, 3)

/*
создадим hashMap для хранения чисел и количества их входа
в оригинальном массиве после выведем лишь те числа,
которые встречались один раз

complexity: O(n)
*/

val hashMap = hashMapOf<Int, Int>()

array.forEach {
  hashMap[it] = hashMap.getOrDefault(it, DEFAULT_VALUE) + ONE_INSTANCE
}

val res = hashMap.filter { it.value == ONE_INSTANCE }

/*
первый способ:

функция zip объединит два массива в один прогон
в transform отсортируем два значения заранее
поместив их в список, после преобразуем в плоский список

complexity: O(n^2*logn)
*/

val array = intArrayOf(1, 3)
val anotherArray = intArrayOf(2, 4)
val mergeArray = array.zip(anotherArray) { a, b -> listOf(a, b).sorted() }.flatten()

/*
второй способ:

тут решение "в лоб", но оно намного эффективнее первого
при этом, если измерить время выполнения в IDE, то
первое решение будет в 25 раз медленее работать нежели второе

complexity: O(n)
*/

val res = arrayListOf<Int>()
array.zip(anotherArray) { a, b ->
  if (a > b) {
    res.add(b)
    res.add(a)
  } else {
    res.add(a)
    res.add(b)
  }
}

Если вы нашли неточности/ошибки в статье или просто хотите дополнить её своим мнением — то прошу в комментарии!