Коллекции и типы в коде
Связь с алгоритмами и структурами данных
Никлаус Вирт формулировал суть так: программы = алгоритмы + структуры данных. Алгоритмы описывают шаги; структуры данных — как хранить множество значений в памяти программы.
В этой статье — четыре базовых вида данных, которые встречаются в любом языке, до погружения в list, dict, HashMap и другие имена из раздела 5. Теория стека, очереди, дерева и хеш-таблицы — в 3.02; оценка скорости — Big-O и Lab / 1128.
Тип данных — правило, какие значения может хранить переменная и какие операции над ней допустимы. Коллекция — тип, который хранит много значений сразу. Выбор коллекции влияет на скорость программы сильнее, чем кажется на первых задачах — анализ эффективности.
Скаляр — одно значение
Скаляр — переменная с одним значением за раз. В учебниках его ещё называют примитивом (primitive) — базовый тип языка, не составной.
Основные скалярные типы
- Целое число (
0,42,-7) — счётчики, индексы в массиве, количество элементов. - Дробное (
3.14,0.001) — расчёты, координаты, проценты. - Логическое (true / false) — условия в
if, флаги "включено / выключено". - Символ — один знак в языках, где он выделен отдельно (Java
char, C#char). - Строка (
"hello","Иван") — текст; во многих языках строка ведёт себя как объект, но логически это одно значение.
Сравнение и присваивание
В большинстве языков скаляры сравнивают по значению:
ПСЕВДОКОД
a ← 5
b ← 5
если a = b
// true — значения совпали
Частые ошибки новичка со скалярами
| Ошибка | Пример | Последствие |
|---|---|---|
| Строка вместо числа | "42" + "1" → "421" | Сложение склеивает текст |
| Число вместо строки | 42[0] | Ошибка или неожиданное поведение |
| Сравнение float | 0.1 + 0.2 = 0.3 | Иногда false из-за двоичной дроби |
Путаница = и == | if (x = 5) | Присваивание вместо сравнения |
Подробнее — операторы, типы в языке, базовые операции с данными.
Null, None и "пустое значение"
Null (в Java, C#, JS — null; в Python — None) — специальное значение "ссылка ни на что" или "отсутствует объект". Это не ноль и не пустая строка "".
ПСЕВДОКОД
имя ← null
если имя = null
вывести "имя не задано"
Обращение к полям null вызывает ошибку (NullPointerException, TypeError). Проверяйте null до использования — валидация.
Массив — упорядоченный список по номеру
Массив (array, list, vector) — элементы лежат в заданном порядке. К каждому обращаются по индексу — номеру позиции. В большинстве языков нумерация с нуля: первый элемент — индекс 0, второй — 1.
ПСЕВДОКОД
массив оценки ← [5, 4, 5, 3]
длина ← 4
для i от 0 до длина - 1
сумма ← сумма + оценки[i]
среднее ← сумма / длина // 4.25
Операции и сложность
| Операция | Сложность | Пояснение |
|---|---|---|
Прочитать оценки[i] | O(1) | Прямой доступ по номеру |
| Добавить в конец | O(1)* | *В среднем; resize иногда O(n) |
| Вставить в середину | O(n) | Сдвигает хвост |
| Найти "есть ли X?" | O(n) | Линейный перебор |
| Удалить по индексу | O(n) | Сдвиг элементов |
| Отсортировать | O(n log n) | Встроенная сортировка |
Когда массив подходит
- нужен список по порядку (оценки, координаты, история действий);
- часто обращаетесь к элементу по номеру;
- элементы одного типа или близких типов;
- порядок важен (очередь задач, timeline событий).
Имена в языках
| Язык | Тип | Ссылка |
|---|---|---|
| Python | list | коллекции Python |
| JavaScript | Array | массивы JS |
| Java | ArrayList | коллекции Java |
| C# | List<T> | коллекции C# |
| Go | slice | Go — слайсы |
Перебор массива — циклы. Фильтрация и map по массиву — функциональные приёмы.
Пример — список задач
# Python — список словарей (map внутри list)
tasks = [
{"id": 1, "title": "Купить молоко", "done": False},
{"id": 2, "title": "Позвонить маме", "done": True},
]
for task in tasks:
if not task["done"]:
print(task["title"])
// JavaScript
const tasks = [
{ id: 1, title: "Купить молоко", done: false },
{ id: 2, title: "Позвонить маме", done: true },
];
tasks.filter(t => !t.done).forEach(t => console.log(t.title));
Кортеж (tuple) — массив фиксированной длины
Кортеж — упорядоченная последовательность, которую нельзя изменить после создания (immutable). В Python (1, 2, 3), в TypeScript — tuple type [number, string]. Удобен для координат (x, y) или записи из БД с фиксированным набором полей.
Map — словарь "ключ → значение"
Map (словарь, dictionary, associative array; часто реализован как хеш-таблица) хранит пары: уникальный ключ и значение. По ключу значение ищут быстро — обычно за O(1) в среднем.
ПСЕВДОКОД
словарь телефоны ← пустой словарь
телефоны["Иван"] ← "+7-900-111-22-33"
телефоны["Мария"] ← "+7-900-444-55-66"
если "Иван" есть в телефоны
вывести телефоны["Иван"]
Операции map
| Операция | Сложность | Пример |
|---|---|---|
| Получить по ключу | O(1)* | телефоны["Иван"] |
| Записать пару | O(1)* | телефоны["Пётр"] ← "..." |
| Проверить ключ | O(1)* | "Иван" in телефоны |
| Удалить ключ | O(1)* | удалить "Мария" |
| Перебрать все ключи | O(n) | цикл for |
*В среднем; при коллизиях хеш-таблицы возможна деградация — реализация структур.
Когда map подходит
- ищете запись по идентификатору (логин, id товара, код страны);
- храните настройки и кэш;
- работаете с JSON-объектом
{"name": "Anna", "age": 25}— это map; - нужна быстрая проверка "есть ли ключ?".
Имена в языках
| Язык | Тип |
|---|---|
| Python | dict |
| JavaScript | объект { } или Map |
| Java | HashMap, LinkedHashMap |
| C# | Dictionary<K, V> |
| Go | map[K]V |
JSON и map
JSON-объект при десериализации превращается в map (или объект языка):
{
"userId": 42,
"role": "admin",
"permissions": ["read", "write"]
}
"userId"и"role"— ключи map со скалярными значениями;"permissions"— ключ со значением-массивом.
Ошибка на границе API — поле "25" (строка) вместо 25 (число). Проверяйте типы — валидация, JSON.
Ловушка Python — in для list и dict
# O(n) — перебор всего списка
1000000 in big_list
# O(1) в среднем — хеш по ключу
1000000 in big_dict
1000000 in big_set
Разбор — Lab / Big-O, ловушки Python.
Пример — телефонная книга
phones = {}
phones["Иван"] = "+7-900-111-22-33"
phones["Мария"] = "+7-900-444-55-66"
def find_phone(name):
if name in phones:
return phones[name]
return "не найден"
Set — множество уникальных элементов
Set (множество) хранит уникальные значения без повторов. Порядок элементов может не гарантироваться — зависит от языка и реализации.
ПСЕВДОКОД
множество теги ← {}
добавить теги "it"
добавить теги "news"
добавить теги "it" // второй раз не добавится
размер ← 2
если "news" в теги
вывести "тег news есть"
Операции set
| Операция | Сложность | Пояснение |
|---|---|---|
| Добавить элемент | O(1)* | Игнорирует дубликат |
| Проверить принадлежность | O(1)* | x in set |
| Объединение двух set | O(n) | Все уникальные из обоих |
| Пересечение | O(n) | Общие элементы |
| Разность | O(n) | В первом, но не во втором |
Когда set подходит
- убрать дубликаты из потока данных;
- часто спрашиваете "этот элемент уже встречался?";
- пересечение или объединение двух наборов (общие теги, общие пользователи);
- быстрая проверка членства на больших данных.
Пример — уникальные посетители
visited = set()
visited.add("user_1")
visited.add("user_2")
visited.add("user_1") # дубликат
print(len(visited)) # 2
# общие элементы двух наборов
tags_a = {"python", "web", "sql"}
tags_b = {"java", "web", "docker"}
common = tags_a & tags_b # {"web"}
Какую структуру выбрать
| Задача | Скаляр | Массив | Map | Set |
|---|---|---|---|---|
| Одно число, флаг, имя | ✓ | |||
| Список по порядку | ✓ | |||
| Поиск по id / ключу | ✓ | |||
| Уникальные значения | ✓ | |||
Частая проверка x in ... на больших данных | медленно | ✓ | ✓ | |
| JSON с фиксированными полями | ✓ | |||
| Группировка "ключ → список" | ✓* |
*Значение map может быть массивом — {"work": ["task1", "task2"]}.
Сравнение скорости на примере
Задача: среди 100 000 id проверить, есть ли target_id.
| Структура | Подход | Сложность |
|---|---|---|
| Массив | цикл for | O(n) |
| Set | target in ids_set | O(n) на построение + O(1) на проверку |
| Map | ключ = id | O(1) на проверку ключа |
Два вложенных цикла по массиву дают O(n²). Один цикл с проверкой в set — O(n). Поэтому выбор структуры часто важнее "ещё одного цикла".
Вложенные и комбинированные структуры
В реальных программах типы сочетают:
Массив объектов
Список пользователей — каждый элемент map с полями:
[
{"id": 1, "name": "Anna", "age": 25},
{"id": 2, "name": "Bob", "age": 30}
]
Map со значением-массивом
Группировка заказов по статусу:
ПСЕВДОКОД
заказы ← {
"new": [101, 102],
"done": [99, 98]
}
Map со значением-set
Теги у каждой статьи:
ПСЕВДОКОД
статьи ← {}
статьи[42] ← {"python", "web"}
статьи[43] ← {"java", "web"}
Схема данных перед кодом
Перед написанием кода полезно нарисовать схему:
- какие сущности есть (пользователь, заказ, товар);
- какие поля у каждой;
- какой тип у поля (скаляр, массив, map);
- что должно быть уникальным (email, id).
Это снижает переделки при переходе к SQL, ORM и нормализации таблиц.
Строка как последовательность
Строка — текст, но технически это упорядоченная последовательность символов. К ней применимы идеи массива:
- длина строки;
- доступ по индексу
s[0](в Python, JS); - перебор символов в цикле;
- поиск подстроки — часто O(n·m).
Строки в большинстве языков неизменяемы (immutable): операция s + "!" создаёт новую строку, а не меняет старую. Для частой склейки в цикле используйте StringBuilder (Java, C#) или join (Python) — строки в языках.
Изменяемость (mutable) и неизменяемость (immutable)
| Тип | Обычно | Пример |
|---|---|---|
| Скаляр (число, bool) | immutable | x = 5; x = 6 — новое значение |
| Строка | immutable | s + "!" — новая строка |
| Массив / list | mutable | arr[0] = 99 меняет элемент |
| Map / dict | mutable | d["key"] = val |
| Tuple | immutable | нельзя t[0] = 1 |
Неизменяемые структуры безопаснее передавать между потоками и функциями — меньше сюрпризов "кто-то изменил мой список". Подробнее — функции, область видимости.
Типичные ошибки по типам структур
Массив
- Выход за границу — индекс
arr[len(arr)]или-1там, где ожидали последний элемент (в Python-1— последний, в других языках — ошибка). - Изменение во время перебора — удаление элементов в
forпо тому же массиву пропускает элементы. - Поиск в цикле внутри цикла — O(n²); замените внутренний поиск на
set.
Map
- Обращение к несуществующему ключу — KeyError / undefined; используйте
.get("key", default)или проверкуin. - Изменяемый ключ — ключ map должен быть хешируемым и стабильным; list как ключ в Python запрещён.
- Путаница ключ/значение при итерации —
for k, v in d.items().
Set
- Попытка индексировать —
my_set[0]не существует; set не упорядочен по индексу (до Python 3.7+ dict тоже; сейчас dict сохраняет порядок вставки).
Практические задачи
Задача 1 — средний балл
Дан массив оценок [5, 4, 5, 3]. Вычислите сумму и среднее.
Подсказка (пseudocode)
сумма ← 0
для каждой оценки в массиве
сумма ← сумма + оценка
среднее ← сумма / длина(массива)
Задача 2 — телефонная книга
Реализуйте добавление и поиск по имени через map.
Задача 3 — уникальные email
Из списка email уберите дубликаты через set, сохранив один экземпляр каждого.
Задача 4 — группировка
Список {category: "food", name: "milk"}, {category: "food", name: "bread"}, {category: "tech", name: "mouse"} — сгруппируйте имена по category в map → list.
Связь с базой данных
| В коде | В SQL (упрощённо) |
|---|---|
| Скаляр | одна ячейка (INT, VARCHAR) |
| Массив записей | результат SELECT (несколько строк) |
| Map / объект | одна строка таблицы (поля = ключи) |
| Set | UNIQUE constraint, DISTINCT |
CRUD в SQL — 3.07 / 5. ORM маппит строки БД в объекты — 4.10.
Связь с веб и JSON
HTTP API почти всегда обменивается JSON:
- GET
/users→ массив объектов; - GET
/users/5→ один объект (map); - POST body → map с полями формы.
Стек и очередь на базе массива
Стек (stack) — структура "последним пришёл — первым ушёл" (LIFO). Операции:
- push — положить на вершину;
- pop — снять с вершины;
- peek — посмотреть вершину без снятия.
Пример — история "Назад" в браузере, undo в редакторе. Реализуют массивом с push/pop с конца — O(1).
Очередь (queue) — "первым пришёл — первым ушёл" (FIFO). Операции enqueue (в хвост) и dequeue (из головы). Пример — очередь печати, обработка сообщений. На массиве dequeue из начала — O(n); для O(1) используют кольцевой буфер или deque — структуры данных / 2.
ПСЕВДОКОД — стек на массиве
стек ← []
push(стек, 10)
push(стек, 20)
x ← pop(стек) // 20
Поиск и сортировка — кратко
| Алгоритм | Когда | Сложность |
|---|---|---|
| Линейный поиск | несортированный массив | O(n) |
| Бинарный поиск | отсортированный массив | O(log n) |
| Встроенная сортировка | sort(), sorted() | O(n log n) |
Бинарный поиск не работает на обычном map — нужен отсортированный массив или дерево. Путаница "ищу в dict за O(1)" и "бинарный поиск" — частая ошибка на собеседованиях — алгоритмы / intro.
Сравнение по языкам — шпаргалка
| Концепция | Python | JavaScript | Java | C# |
|---|---|---|---|---|
| Массив | list | Array | ArrayList | List<T> |
| Map | dict | Object, Map | HashMap | Dictionary |
| Set | set | Set | HashSet | HashSet |
| Null | None | null, undefined | null | null |
| Проверка ключа | "k" in d | "k" in obj | containsKey | ContainsKey |
Детали синтаксиса — раздел 5. Языки.
Разбор ошибки из практики
Симптом: API возвращает список, код ожидает один объект.
// пришло
[{"id": 1}]
// код делает
data["id"] // ошибка — data это list, не map
Решение: проверить тип на входе — list или map — и взять data[0] или исправить контракт API — валидация, типовые ошибки.
Упражнения с решениями
Задача 5 — подсчёт слов
Текст "hello world hello" — посчитать, сколько раз каждое слово встретилось (map → число).
ПСЕВДОКОД
слова ← разбить(текст, " ")
счётчик ← пустой словарь
для каждого слова w в слова
если w нет в счётчик
счётчик[w] ← 0
счётчик[w] ← счётчик[w] + 1
// hello → 2, world → 1
Задача 6 — два списка id
Есть list_a и list_b. Найти id, которые есть и там, и там — через set:
ПСЕВДОКОД
set_a ← множество(list_a)
set_b ← множество(list_b)
общие ← пересечение(set_a, set_b)
Память и ссылки (важно для map и массивов)
В языках с ссылочной семантикой (Python, Java, JS для объектов) две переменные могут указывать на один массив:
a = [1, 2, 3]
b = a
b.append(4)
# a тоже [1, 2, 3, 4]
Для копии нужен явный clone — copy(), [...arr], list(arr). Иначе функция "случайно" меняет данные вызывающего — Как искать баг.
Итерация по коллекциям
| Структура | Python | JavaScript |
|---|---|---|
| Массив | for x in arr: | for (const x of arr) |
| Map | for k, v in d.items(): | for (const [k,v] of Object.entries(o)) |
| Set | for x in s: | for (const x of set) |
| С индексом | for i, x in enumerate(arr): | arr.forEach((x,i) => ...) |
List comprehension и map/filter (Python/JS)
# квадраты чётных чисел
[x*x for x in nums if x % 2 == 0]
nums.filter(x => x % 2 === 0).map(x => x * x);
Это синтаксический сugar над циклом; сложность та же O(n).
OrderedDict и сохранение порядка
В Python 3.7+ обычный dict сохраняет порядок вставки ключей. Раньше для порядка использовали OrderedDict. В JavaScript объекты ES2015+ тоже сохраняют порядок строковых ключей (с оговорками для числовых).
Frozen set и неизменяемость
frozenset в Python — set, который нельзя изменить после создания. Используют как ключ map или элемент другого set.
defaultdict и Counter (Python)
collections.defaultdict(list) — при отсутствии ключа создаёт пустой list. Удобно для группировки:
from collections import defaultdict
groups = defaultdict(list)
for item in items:
groups[item["category"]].append(item["name"])
Counter — подсчёт частот слов — связь с map "ключ → число".
Weak references (упоминание)
В продвинутых сценариях weak map не удерживает объект в памяти — GC может собрать. В JS — WeakMap; в Java — WeakHashMap. Для новичка достаточно знать, что такое существует при кэшах.
Таблица "антипаттерн → решение"
| Антипаттерн | Проблема | Решение |
|---|---|---|
| List для membership | O(n) на каждый in | Set или map |
| Map без нормализации ключей | "User" и "user" — два ключа | .lower() при вставке |
| Глубокая вложенность без схемы | data["a"]["b"]["c"] KeyError | dataclass / typed model |
| JSON число как float | 0.1 + 0.2 | Decimal для денег |
| Мutation shared list | side effect | .copy() или immutable |
Pet-проект — модель данных
Сущность Task:
| Поле | Тип | Примечание |
|---|---|---|
| id | int | уникальный |
| title | str | скаляр |
| done | bool | скаляр |
| tags | set[str] | уникальные теги |
Хранение в памяти: tasks: dict[int, Task] — map по id. Список для UI: list(tasks.values()) — массив.
Связь с веб CRUD.
Самопроверка
- Чем map отличается от массива при доступе?
- Когда set лучше list?
- Что такое сериализация JSON?
- Почему
x in big_listмедленнееx in big_set? - Нарисуйте схему "категория → список товаров".
Ответы — в тексте выше. Дальше — чек-лист веба (JSON/map) и Lab 1128.
Что читать дальше
- Структуры данных — о разделе — стек, очередь, дерево, хеш-таблица, таблицы O(·).
- Lab / 1128 — как оценить сложность по коду на Python.
- Язык программирования — типизация и коллекции в вашем стеке.
- Циклы — перебор массивов и коллекций.
- Коллекции в Python, массивы JS.
- Базовые операции с данными — мост от "данных" вообще к коду.
- Как искать баг — ошибки типов часто маскируются под "странное поведение".