Узнайте, что такое массивы, как они устроены внутри и когда их использовать. Практические примеры на Python и советы для собеседований. Читайте сейчас!
Представьте ряд почтовых ящиков: у каждого есть номер (начиная с 0), и в каждом лежит ровно один предмет. Массив — это цифровой аналог такого ряда: коллекция элементов, хранящихся в определённом порядке, где каждый элемент можно найти по его номеру (индексу).
Зачем это нужно? Допустим, нужно хранить результаты тестов 100 студентов. Без массива пришлось бы создать 100 отдельных переменных: score1, score2, ..., score100. А если придёт 101-й студент, код пришлось бы переписывать. Массив решает проблему: используем одну переменную scores и обращаемся к любому результату по индексу.
Ключевые характеристики массива:
Без массивов программирование превратилось бы в кошмар из захардкоженных переменных. Невозможно было бы легко обрабатывать пакеты данных: сортировать списки имён, искать пользователя в базе, рендерить пиксели на экране — всё это потребовало бы тысяч строк повторяющегося кода.
Массивы упрощают:
Массивы — это «атомы» структур данных. Стеки, очереди, хеш-таблицы и даже управление памятью в ОС построены на массивах. Понимая массивы, вы понимаете фундамент организации данных в компьютере.
Чтобы по-настоящему понять массивы, нужно заглянуть в физическую память (RAM).
При создании массива компьютер находит непрерывный блок свободной памяти и резервирует его. Технический термин — непрерывная память (contiguous memory): адреса памяти идут подряд, без промежутков.
Адреса памяти: 1000 1004 1008 1012 1016
|------|------|------|------|------|
Значения: | 10 | 20 | 30 | 40 | 50 |
|------|------|------|------|------|
Индексы: 0 1 2 3 4(Предполагается, что каждое число занимает 4 байта)
Почему индексы начинаются с 0, а не с 1? Потому что индекс — это не «номер позиции», а смещение (расстояние) от начала массива. Индекс 0 означает «ноль шагов от начала», индекс 1 — «один шаг».
Когда вы обращаетесь к array[3], компьютер не перебирает элементы один за другим, а вычисляет адрес по формуле:
Адрес = Базовый адрес + (Индекс × Размер элемента)Для примера выше: базовый адрес 1000, размер элемента 4 байта, индекс 3. Адрес = 1000 + (3 × 4) = 1012. Компьютер мгновенно переходит к ячейке 1012 и читает значение 40. Так как используется одно математическое уравнение, доступ к элементу по индексу всегда мгновенен — в Computer Science это называется временная сложность O(1) (константное время).
Вот профиль производительности стандартного динамического массива:
| Операция | Типичная сложность | Почему |
|---|---|---|
| Доступ по индексу | O(1) | Математическая формула мгновенно вычисляет адрес. |
| Поиск по значению | O(n) | В худшем случае нужно проверить каждый элемент. |
| Вставка в начало | O(n) | Нужно сдвинуть все существующие элементы вправо. |
| Вставка в середину | O(n) | В среднем сдвиг половины элементов. |
| Вставка в конец | O(1)* | Просто кладём в следующую свободную ячейку. |
| Удаление из начала | O(n) | Сдвиг всех оставшихся элементов влево. |
| Удаление из середины | O(n) | В среднем сдвиг половины элементов. |
| Удаление из конца | O(1) | Просто удаляем и уменьшаем счётчик. |
*Примечание: в динамическом массиве иногда происходит увеличение размера (копирование всех элементов в новый блок) — это O(n). Но так как это случается редко, амортизированная сложность остаётся O(1).
Стек (LIFO) и очередь (FIFO) — это концепции или правила поведения данных. Массив — физическая структура, на которой они строятся. Стек — это массив, где добавление и удаление происходит только с конца.
# Создание списка (в Python это динамический массив)
scores = [85, 92, 78, 90]
# Доступ по индексу (O(1))
print(scores[0]) # Вывод: 85
# Итерация (последовательный доступ)
for score in scores:
print(score)
# Добавление в конец (амортизированное O(1))
scores.append(95)Важное отличие Python: список в Python — это не традиционный массив C с сырыми значениями. Внутри это массив указателей на объекты. Сам массив непрерывен, но объекты (числа, строки и т.д.) разбросаны по памяти.
Динамическое расширение: когда список заполняется, он не увеличивается на 1 элемент, а выделяет с запасом (обычно +12.5%), чтобы будущие append() оставались быстрыми.
Альтернативы для низкоуровневой работы:
Задача: вы создаёте фитнес-приложение. У вас есть массив количества шагов за последние 30 дней:
steps = [4000, 8000, 10500, 12000, 5000, 11000, 13000, 14000]Нужно найти самую длинную серию подряд идущих дней, когда пользователь достиг цели в 10000 шагов.
Почему массив? Нам нужно последовательно просматривать данные день за днём, быстро обращаться к элементам (O(1)) и не требуется вставка/удаление.
Решение на Python:
steps = [4000, 8000, 10500, 12000, 5000, 11000, 13000, 14000]
goal = 10000
max_streak = 0
current_streak = 0
# Последовательный доступ: O(n)
for daily_steps in steps:
if daily_steps >= goal:
current_streak += 1 # Увеличиваем текущую серию
if current_streak > max_streak:
max_streak = current_streak # Обновляем рекорд
else:
current_streak = 0 # Сброс при неудачном дне
print(f"Самая длинная серия: {max_streak} дней") # Вывод: 3Мы проходим по массиву один раз (O(n)), храним текущую серию и максимальную. Это эффективно и использует O(1) дополнительной памяти.
Золотое правило: доступ к элементу — O(1), вставка/удаление — O(n). Используйте массивы, когда часто читаете данные и редко меняете структуру.
Непрерывная память: массивы «склеены» в RAM, что ускоряет обработку (кэш-дружественность), но требует достаточно большого непрерывного блока для создания крупного массива.
Индекс 0 — это смещение: индекс 0 означает «нулевое расстояние от начала».
Частые ошибки новичков:
Откройте редактор и напишите функцию, которая принимает массив чисел и возвращает новый массив, где каждый элемент — это произведение всех остальных элементов, кроме текущего (например, для [1,2,3,4] результат [24,12,8,6]). Попробуйте решить за O(n) без деления. Это отличная тренировка понимания массивов!
Хочешь закрепить знания на практике?
Решай задачи на Algolit — интерактивная платформа для обучения
Начать бесплатно →