Введение в Computer Science для разработчиков

Мышление в Computer Science: модели, абстракции, данные

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

Мышление в Computer Science — это привычка решать задачи через:

построение модели (упрощённого описания реальности)

выбор абстракций (удобных слоёв и интерфейсов)

работу с данными (представлением, ограничениями и преобразованиями)

Эта статья задаёт фундамент курса: мы договоримся о базовых понятиях и научимся применять их к любым инженерным задачам.

Модели

Модель — это упрощённое представление системы или явления, которое сохраняет только важные для текущей цели свойства.

Важные последствия этого определения:

Модель всегда неполная: она намеренно выбрасывает детали.

Одна и та же реальность может иметь разные модели под разные задачи.

Хорошая модель делает задачу решаемой и проверяемой.

!Диаграмма показывает, что модель — это осознанное упрощение ради решения

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

Очередь как модель обслуживания: «первым пришёл — первым обслужен».

Граф как модель связей: дороги между городами, зависимости пакетов, связи в соцсети. См. Граф (математика)).

Состояния и переходы как модель поведения: заказ «создан → оплачен → отправлен → доставлен». Это близко к идеям теории автоматов. См. Конечный автомат.

Как понять, хороша ли модель

Модель полезна, если она отвечает на вопрос «что будет, если…».

Например, вы моделируете очередь запросов в сервис:

если входящий поток больше, чем скорость обработки, очередь растёт

значит, рано или поздно вы упрётесь в память/лимиты

значит, нужны ограничения: backpressure, rate limit, приоритезация, горизонтальное масштабирование

Даже без конкретного кода модель уже помогает принять архитектурное решение.

Абстракции

Абстракция — это способ скрыть детали реализации и оставить понятный контракт (правила использования).

Практически абстракция отвечает на два вопроса:

что можно делать (операции, интерфейс)

что гарантируется (свойства, ограничения, ошибки)

См. также: Абстракция (информатика)).

Зачем абстракции разработчику

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

Позволяют менять реализацию без переписывания всего: при сохранении контракта.

Делают код проверяемым: контракт можно тестировать.

Уровни абстракции: как не смешивать слои

Типичная ошибка — смешивать разные уровни (например, UI напрямую формирует SQL, а доменная логика зависит от формата таблиц). Полезная привычка: явно называть уровни и границы.

Пример типовых уровней в приложении:

Доменные сущности и правила (что такое заказ, когда он валиден)

Сценарии/сервисы (как оформляется заказ)

Инфраструктура (БД, очереди, HTTP)

!Схема уровней абстракции и допустимых зависимостей

«Протекающие» абстракции

Иногда детали реализации всё равно «прорываются» наружу: например, абстракция «таблица в БД» кажется простой, но производительность внезапно начинает зависеть от индексов, планов выполнения и блокировок.

Это нормально:

абстракции экономят время, но не отменяют физику системы

важно знать, в каких местах абстракция может протечь (производительность, память, параллелизм, сеть)

Данные

Данные — это зафиксированные значения, которые система хранит, передаёт и преобразует.

Для разработчика данные важны в трёх смыслах:

представление (как именно закодировано)

структура (как организовано)

смысл и ограничения (что считается корректным)

Представление: одно и то же значение можно закодировать по-разному

Компьютер хранит всё как биты, но «одни и те же биты» могут означать разные вещи в зависимости от договорённости:

текст зависит от кодировки (например, UTF-8)

числа зависят от формата (например, 32-bit integer vs 64-bit, signed vs unsigned)

изображения зависят от формата (PNG/JPEG) и цветового пространства

Практический вывод: при интеграциях и хранении важно явно фиксировать форматы и версии.

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

Тип — это набор допустимых значений и операций над ними.

В языках программирования типы помогают:

отсекать ошибки раннее (на этапе компиляции или проверки)

документировать намерения

задавать ограничения на данные

Структуры данных — способы организации данных, которые делают некоторые операции быстрыми и удобными.

Примеры:

массив/список: удобно проходить по порядку

хеш-таблица (map/dict): удобно быстро искать по ключу

дерево: удобно хранить иерархии

граф: удобно хранить произвольные связи

Важно не запоминать «правильную структуру», а связывать её с моделью и операциями: что чаще делаем с данными — то и оптимизируем.

Инварианты: данные почти всегда имеют правила корректности

Инвариант — это условие, которое должно быть истинным всегда в рамках выбранной модели.

Примеры инвариантов:

баланс счёта не может стать меньше разрешённого лимита

заказ не может перейти в состояние «доставлен», минуя «отправлен»

email в профиле должен быть уникальным

Инварианты — это мост между «реальным смыслом» и «машинными данными». Их можно поддерживать:

типами (где возможно)

проверками в коде

ограничениями в базе (уникальность, внешние ключи)

протоколами и контрактами между сервисами

Модели данных: как договориться о структуре на уровне системы

Модель данных описывает, какие сущности существуют в системе, какие у них поля и связи.

На практике вы встречаете разные подходы:

реляционная модель (таблицы, связи)

документная модель (вложенные документы)

key-value

графовые базы

См. Модель данных.

Выбор модели данных — это не «вкус», а отражение вашей модели мира и типичных запросов.

Как применять: один и тот же алгоритм мышления к разным задачам

Ниже — практический шаблон, который стоит довести до автоматизма.

Сформулируйте цель

Определите границы системы

Постройте модель

Выберите абстракции и уровни

Определите данные и инварианты

Спроектируйте операции над данными (чтение, запись, поиск, обновление)

Проверьте «места протекания» (производительность, сеть, параллелизм, ошибки)

Мини-кейс: сервис сокращения ссылок

Сформулируем модель:

сущности: ShortLink (короткий код), TargetURL (полный адрес), Metadata (владелец, срок жизни)

операция записи: создать короткий код и связать с URL

операция чтения: по коду найти URL и сделать редирект

Абстракции (слои):

домен: правила TTL, права доступа, валидность URL

сервис: сценарии «создать», «перейти», «удалить»

инфраструктура: хранилище (БД/кеш), HTTP, логирование

Данные и инварианты:

инвариант уникальности: короткий код уникален

инвариант корректности: URL валиден

инвариант срока: если TTL истёк, редирект недоступен

Места протекания абстракций:

производительность чтения (редирект должен быть быстрым) → кеширование

гонки при генерации кода → атомарность/транзакции/уникальный индекс

«грязные» данные (пользователь вводит что угодно) → валидация и нормализация

Обратите внимание: мы ещё не написали ни строчки кода, но уже приняли ключевые решения и знаем, какие риски проверять.

Итоги

Модель помогает упростить реальность до формы, с которой можно рассуждать и строить решение.

Абстракция задаёт контракт и скрывает детали, позволяя мыслить уровнями и менять реализацию.

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

Дальше в курсе эти идеи будут постоянно повторяться: структуры данных, алгоритмы, архитектура, базы данных, параллелизм и сети — всё это частные случаи работы с моделями, абстракциями и данными.

Алгоритмы и анализ сложности (Big O) на практике

В прошлой статье мы договорились мыслить как в computer science: строить модели, выбирать абстракции и понимать данные (их структуру и инварианты). Алгоритмы и анализ сложности — это продолжение той же линии: как выбранная модель и структура данных влияют на скорость и потребление памяти.

Алгоритм — это конечная последовательность шагов, которая преобразует входные данные в результат. Когда разработчик спрашивает «это будет быстро?», он обычно спрашивает о том, как время и память растут при увеличении размера входа.

Зачем разработчику Big O

Big O (читается как биг-о) — нотация для описания того, как растёт стоимость алгоритма при росте размера входа .

— размер входа: число элементов массива, длина строки, количество вершин графа, число записей в таблице.

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

Big O отвечает на практический вопрос: если данных станет в 10 раз больше, во сколько раз станет медленнее/прожорливее? Подробности: Big O notation.

Что именно описывает Big O

Big O описывает верхнюю границу роста функции стоимости. На практике в разработке чаще всего используют как «порядок роста».

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

Важно понимать ограничения Big O:

Big O игнорирует константы и «мелкие» слагаемые, но в реальных системах константы могут решать.

Big O не учитывает задержки сети, диска, блокировки, GC, кэш-попадания, хотя в проде это часто главное.

Big O зависит от модели вычислений: что считаем «операцией» и что считаем «входом».

Типовые классы сложности и как их узнавать

!График показывает, почему при росте данных выбор алгоритма важнее микрооптимизааций

Ниже — самые частые классы сложности (время), с интуицией.

| Класс | Как выглядит рост | Типичный источник | Пример | | --- | --- | --- | --- | | | не зависит от | фиксированное число операций | доступ по индексу в массиве | | | очень медленный рост | делим задачу пополам | бинарный поиск, Binary search | | | пропорционален | один проход | поиск максимума в массиве | | | чуть хуже линейного | «разделяй и властвуй» + объединение | сортировки сравнениями, например Quicksort в среднем | | | квадратичный рост | двойной цикл по данным | сравнить все пары элементов | | | взрывной рост | перебор всех подмножеств | полный перебор в задачах выбора |

— логарифм. В Big O основание логарифма не принципиально, потому что смена основания даёт постоянный множитель. Практическая интерпретация: — «сколько раз можно делить пополам, пока не останется 1».

Быстрая оценка сложности по коду

Мы не будем «доказывать теоремы», но натренируем инженерную оценку. Сначала определите, что является .

Правила-эвристики

Последовательные участки кода обычно складываются, но в Big O доминирует самый большой порядок роста.

Вложенные циклы обычно перемножают: цикл по внутри цикла по даёт .

Если на каждом шаге размер задачи уменьшается в фиксированное число раз (например, пополам), часто получается .

Рекурсия требует смотреть на число ветвлений и на то, как уменьшается вход.

Пример: линейный проход

Худший случай: элемента нет, проверим все значений → .

Лучший случай: элемент первый → , но обычно в оценках ориентируются на худший или средний случай.

Пример: двойной цикл

В худшем случае сравним почти все пары → порядка сравнений.

Это квадратичный рост, значит .

Пример: бинарный поиск

Каждая итерация сужает диапазон примерно в 2 раза → число итераций растёт как , значит .

Средний, худший и амортизированный случаи

Худший и средний случаи

Один и тот же алгоритм может иметь разные оценки в зависимости от распределения входных данных.

Quicksort имеет среднюю сложность , но в худшем случае может деградировать до .

Хеш-таблица (map/dict) часто даёт операции в среднем, но в худшем случае может стать из-за коллизий. См. Hash table.

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

Амортизированный анализ

Амортизированная сложность — это «средняя стоимость операции на длинной серии операций», даже если отдельные операции бывают дорогими. См. Amortized analysis.

Классический пример: динамический массив.

append обычно , потому что кладём элемент в конец.

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

Но если размер буфера увеличивать, например, в 2 раза, то такие копирования редки, и средняя стоимость одного append на длинной дистанции остаётся амортизированно.

Практический вывод: редкие «пики» возможны, и они важны для latency (времени ответа), даже если средняя производительность хорошая.

Big O и структуры данных: одно без другого не работает

Связь с прошлой статьёй:

модель задаёт операции (что мы делаем с данными)

данные и их структура определяют, сколько это будет стоить

абстракции (например, List, Map) скрывают детали, но сложность часто «протекает» через производительность

Ниже — практическая шпаргалка по типовым операциям.

| Структура данных | Найти по ключу | Вставить | Удалить | Пройти все элементы | | --- | --- | --- | --- | --- | | Массив/список (динамический) | | в конец амортизированно | | | | Отсортированный массив | бинарный поиск , но вставка | | | | | Хеш-таблица (map/dict) | в среднем | в среднем | в среднем | | | Сбалансированное дерево поиска | | | | |

Эти оценки — типичные, но конкретные константы и поведение зависят от языка и реализации.

Практика: как выбирать алгоритм в продуктовой задаче

Шаг 1: явно определить

В продукте часто несколько «размеров входа».

Примеры:

в API поиска: — число документов, но также важны число токенов в запросе и число фильтров

в обработке событий: — события в батче, но также важны число уникальных ключей и размер окна агрегации

Если вы неверно выбрали , вы можете оптимизировать не то.

Шаг 2: выписать операции и их частоты

Подход из моделирования:

Какие операции выполняются чаще всего (например, чтение профиля vs обновление профиля)?

Какие операции критичны по latency?

Где узкое место: CPU, память, сеть, диск, блокировки?

Big O помогает с CPU/памятью, но не заменяет системного мышления.

Шаг 3: выбрать структуру данных и алгоритм под операции

Мини-кейс: нужно часто отвечать на вопрос «есть ли пользователь в наборе?»

Решение A: хранить в списке и проверять contains → на запрос.

Решение B: хранить в set/хеш-таблице → в среднем на запрос.

Если запросов много, разница будет огромной.

Шаг 4: проверить «протекание абстракции»

Даже если оценка красивая, спросите:

не превращается ли «операция » в дорогую из-за аллокаций, GC или кеш-промахов

не вызываете ли вы скрытую сортировку/копирование

не делаете ли вы случайно запросов к базе (типичная проблема N+1)

Частые ошибки при использовании Big O

Путать «асимптотику» с реальным временем: может быть медленнее на маленьких из-за констант.

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

Игнорировать память: алгоритм может быть быстрым, но съесть слишком много RAM.

Оценивать только CPU и забывать про I/O: один запрос в сеть может стоить дороже миллионов простых операций.

Мини-чеклист для разработчика

Назовите входной размер и его типичный диапазон.

Определите, что для вас «стоимость»: время, память, число запросов к БД, число обращений к диску.

Оцените порядок роста: , , , , .

Подберите структуру данных под частые операции.

Найдите места, где абстракции могут «протечь», и подтвердите измерениями.

Итоги

Big O — это язык для описания роста стоимости алгоритма при увеличении размера входа .

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

Средний, худший и амортизированный случаи важны по-разному: среднее — про throughput, худшее и пики — про latency и риски.

Выбор структуры данных — это часть модели данных и напрямую влияет на сложность.

Дальше по курсу эти навыки пригодятся везде: от работы со строками и коллекциями до проектирования API, хранения данных и анализа производительности.

Структуры данных: выбор, реализация, применение

В предыдущих статьях курса мы зафиксировали базовую инженерную рамку:

вы строите модель задачи

выбираете абстракции (контракты)

описываете данные и их инварианты

оцениваете стоимость операций через Big O

Структуры данных — это место, где всё это сходится в практику. Одна и та же модель (например, «набор пользователей») может быть реализована разными структурами, и от выбора зависит скорость, память, простота кода и даже корректность.

Что такое структура данных

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

Важно различать два уровня:

абстрактный тип данных (контракт): какие операции доступны и какие гарантии они дают

реализация (конкретная структура): как это устроено внутри, какие у этого последствия по времени, памяти и “краям”

Пример:

абстракция множество обещает операцию «проверить наличие элемента»

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

Как выбирать структуру данных

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

Шаги выбора

Выпишите операции над данными

Оцените частоту операций

Определите ключевые ограничения

Выберите структуру и проверьте “протекание” абстракции

Какие операции бывают важны

поиск по ключу или по значению

вставка и удаление

обход всех элементов

поддержка порядка (вставки, сортировки, по ключу)

выбор минимума/максимума или top-k

диапазонные запросы (все элементы между и )

Какие ограничения часто решают

объём данных и рост (из Big O)

память и аллокации

требования к худшему случаю (latency, защита от деградации)

необходимость стабильного порядка итерации

параллелизм и конкурентный доступ

требования к сериализации/хранению на диске

> Хороший практический принцип: выбирайте структуру данных под самую частую и самую дорогую операцию, а остальные операции “оплачивайте”, если они редки.

!Дерево решений: от операций и требований к выбору структуры данных

Базовые структуры данных и их свойства

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

Массив и динамический массив

Массив хранит элементы непрерывным блоком памяти. Динамический массив (например, ArrayList, vector, list в Python) автоматически увеличивает этот блок.

Ключевые свойства:

доступ по индексу:

проход по всем элементам:

вставка/удаление в середине: обычно (нужно сдвигать хвост)

добавление в конец: обычно амортизированно (иногда происходит расширение и копирование)

Почему динамический массив обычно быстрый в реальности:

хорошая локальность данных: CPU-кэш любит последовательную память

мало дополнительных объектов (особенно важно при GC)

Ссылка: Массив (структура данных)).

!Наглядное сравнение памяти и операций: массив vs связный список

Связный список

Связный список состоит из узлов, где каждый узел хранит значение и ссылку(и) на соседей.

Ключевые свойства (в типичной реализации):

вставка/удаление после известного узла:

поиск элемента или доступ по индексу:

хуже локальность, больше накладные расходы на память (ссылки, отдельные объекты)

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

Ссылка: Связный список.

Стек и очередь как абстракции

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

стек (LIFO): положили сверху, сняли сверху

очередь (FIFO): пришёл первым, обслужен первым

Типичные реализации:

стек: динамический массив (операции push/pop с конца)

очередь: кольцевой буфер или двусторонняя очередь (deque), чтобы не делать дорогие сдвиги

Практическая связь с алгоритмами:

DFS обычно использует стек (явно или через рекурсию)

BFS использует очередь

Ссылки: Стек, Очередь (структура данных)).

Хеш-таблица (map/dict/set)

Хеш-таблица хранит пары ключ → значение (или только ключи, если это set) и обычно даёт очень быстрые операции.

Идея:

хеш-функция превращает ключ в число

по этому числу выбирается “корзина” (bucket)

коллизии (разные ключи с одинаковым bucket) разрешаются внутренним механизмом

Типичная оценка:

поиск/вставка/удаление: в среднем

в худшем случае возможно (много коллизий)

Важное практическое понятие — коэффициент заполнения (load factor):

Где:

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

— число корзин (bucket-ов)

— насколько “плотно” заполнена таблица

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

Ссылка: Хеш-таблица.

!Как работает хеш-таблица, что такое коллизии и rehash

Практические нюансы (то самое “протекание” абстракций):

качество хеш-функции критично

O(1) обычно означает в среднем, а не всегда

операции могут выделять память и иногда вызывать дорогой rehash, что влияет на пики задержек

Деревья поиска и сбалансированные деревья

Дерево поиска хранит элементы так, чтобы слева были меньшие, справа — большие (для выбранного отношения порядка).

Если дерево сбалансировано (например, красно-чёрное дерево или AVL-дерево), высота дерева остаётся порядка , и операции обычно стоят .

Что дают деревья по сравнению с хеш-таблицами:

устойчивый даже в худшем случае (при корректной балансировке)

поддержка упорядоченного обхода

естественная поддержка диапазонных запросов

Ссылки: Двоичное дерево поиска, Красно-чёрное дерево.

Куча (heap) и очередь с приоритетом

Куча — структура для быстрого доступа к минимальному или максимальному элементу.

Типичная бинарная куча:

peek (посмотреть min/max):

push (добавить):

pop (достать min/max):

Типовые применения:

планировщики задач

поиск top-k

алгоритмы на графах (например, Дейкстра)

Ссылка: Куча (структура данных)).

Графы и способы хранения связей

Граф — модель “объекты + связи”: пользователи и дружба, сервисы и зависимости, страницы и ссылки.

Ссылка: Граф (математика)).

Две основные реализации хранения:

матрица смежности: таблица , где — число вершин

список смежности: для каждой вершины список соседей

Практический выбор:

граф плотный (много рёбер) → матрица может быть удобнее

граф разреженный (мало рёбер) → список смежности экономит память и ускоряет обход соседей

Шпаргалка по выбору: что за что платит

Таблица ниже — не “истина навсегда”, а стартовая карта для выбора.

| Задача/операция | Часто подходит | Почему | | --- | --- | --- | | быстрый доступ по индексу | динамический массив | непрерывная память, | | частая проверка “есть ли элемент” | set/хеш-таблица | в среднем | | нужен порядок по ключу и диапазоны | сбалансированное дерево | упорядоченность и | | нужен min/max и частые извлечения | куча | pop за , peek за | | BFS/очередь событий | очередь/deque | FIFO без сдвигов | | моделирование связей | граф (списки смежности) | естественная модель и эффективные обходы |

Реализация как источник скрытой стоимости

С точки зрения “мышления в CS” важно помнить: одна и та же структура на уровне интерфейса может иметь разные реальные свойства.

Типовые причины расхождения ожиданий:

локальность памяти: структуры на массивах часто быстрее “на практике”

аллокации и GC: много мелких объектов (узлы списка, узлы дерева) могут замедлять и давать пики

скрытые копирования: например, расширение динамического массива или rehash в хеш-таблице

худшие случаи: атаки на хеши или патологические входы

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

Практические мини-кейсы: как мыслить выбором структуры

Нужна операция: “пользователь уже встречался?” при обработке большого потока событий

- модель: множество уникальных идентификаторов - структура: set/хеш-таблица - риск: рост памяти, нужен TTL или ограничение окна

Нужны диапазонные запросы: “все заказы между датами A и B”

- модель: упорядоченные ключи (дата/время) - структура: дерево поиска (или индекс на дереве в базе) - риск: неверный ключ сортировки, часовые пояса, сравнение дат

Нужен top-k: “10 самых частых запросов за минуту”

- модель: счётчики + выбор лидеров - структура: хеш-таблица для счётчиков и куча для top-k - риск: пики памяти и пересчёт при скользящем окне

Нужен обход связей: “найти всех друзей на расстоянии 2”

- модель: граф - структура: список смежности + BFS (очередь) - риск: циклы, нужны отметки посещённых вершин

Итоги

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

Выбор начинается с операций и ограничений, а не с названия структуры.

Big O даёт масштабируемость, но реальная скорость зависит от реализации: кэш, аллокации, rehash, худшие случаи.

Умение “приземлить” модель в структуру данных — один из самых прямых навыков, которые повышают качество архитектурных решений и производительность.

Как работает компьютер: память, процессор, ОС и процессы

В предыдущих статьях курса мы смотрели на разработку через призму моделей, абстракций и данных, а также оценивали стоимость операций через Big O и выбирали структуры данных. Теперь добавим ещё один слой реальности: железо и операционная система.

Почему это важно разработчику:

Big O говорит, как растёт стоимость с увеличением , но константы часто определяются кэшем, памятью и системными вызовами.

Одна и та же структура данных может быть «асимптотически одинаковой», но радикально разной по скорости из-за локальности памяти.

Ошибки многопоточности, зависания и «странные» задержки почти всегда связаны с тем, как ОС планирует процессы и как они ждут I/O.

Цель статьи: собрать в одну понятную картину процессор, память, ОС, процессы и потоки и связать это с ежедневной разработкой.

!Карта уровней от приложения до железа

Процессор: что он делает на самом деле

Процессор (CPU) выполняет инструкции программы. На очень грубом уровне цикл такой:

взять инструкцию из памяти

понять, что она означает

выполнить

перейти к следующей

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

Регистры, инструкции и память

Регистры — очень быстрая память внутри CPU, где хранятся временные значения.

Большинство инструкций работают с данными в регистрах.

Данные и код обычно находятся в оперативной памяти, но CPU не читает RAM «напрямую на каждую инструкцию» — между ними есть кэши.

Кэш: почему «одинаковый» код бывает в 10 раз быстрее

CPU использует кэш — маленькую, но очень быструю память между процессором и RAM.

Если данные уже в кэше, доступ быстрый.

Если данных нет в кэше, процессору нужно ждать загрузки из RAM, и это может стоить дорого.

Практический вывод для структур данных:

Динамический массив часто быстрее связного списка не только из-за Big O, а из-за последовательного расположения элементов в памяти.

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

См. про устройство кэшей и общую идею памяти: CPU cache.

!Иерархия памяти и компромисс скорость-объём

Память: адреса, стек, куча и виртуальная память

Адреса и байты

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

Адрес — число, обозначающее позицию в памяти.

Указатель (в терминах многих языков) — значение, которое хранит адрес.

Даже если вы пишете на языке без явных указателей, эта модель полезна для понимания:

почему возникают ошибки доступа

почему копирование больших объектов дорого

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

Стек и куча: две разные «зоны» памяти

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

Стек — память для вызовов функций: параметры, локальные переменные, адрес возврата.

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

Практические следствия:

глубокая рекурсия может переполнить стек

большое количество мелких объектов в куче увеличивает нагрузку на аллокатор и сборщик мусора (если он есть)

Подробнее: Call stack.

Виртуальная память: почему у процесса «своя RAM»

ОС обычно даёт каждому процессу виртуальное адресное пространство.

Это абстракция, которая делает сразу несколько вещей:

изоляция: процесс не должен читать память другого процесса

удобство: процесс может думать, что память «непрерывная»

управление: ОС может подкачивать редко используемые страницы и освобождать RAM

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

Если процесс обращается к странице, которой нет в RAM, возникает page fault — ОС подгружает страницу, и это может резко замедлить выполнение.

См. базовую идею: Virtual memory.

Операционная система: какие абстракции она даёт разработчику

ОС — это прослойка между программами и железом. Её ценность в абстракциях и управлении ресурсами.

Ресурсы и мультиплексирование

Железо ограничено:

CPU ядер меньше, чем программ

RAM ограничена

диски и сеть медленные по сравнению с CPU

ОС решает задачу: как разделить ресурсы между множеством программ так, чтобы:

было безопасно

было относительно справедливо

система оставалась отзывчивой

Системные вызовы

Чтобы использовать ресурсы (файлы, сеть, таймеры, процессы), программа обращается к ОС через системные вызовы.

Примеры действий, которые почти всегда означают переход в ОС:

открыть/прочитать файл

отправить/получить данные по сети

создать процесс или поток

выделить память (часто это смесь работы рантайма и обращений к ОС)

См. определение и общую идею: System call.

Практический вывод:

системные вызовы обычно дороже обычных операций в памяти

частые мелкие операции I/O почти всегда проигрывают батчам и буферизации

Процессы и потоки

Что такое процесс

Процесс — это выполняющаяся программа вместе с её ресурсами.

Обычно процесс включает:

собственное виртуальное адресное пространство

открытые файлы/сокеты

контекст выполнения (регистры, состояние)

См. базовое определение: Process (computing)).

Что такое поток

Поток (thread) — это «линия выполнения» внутри процесса.

потоки одного процесса обычно разделяют память (кучу)

у каждого потока свой стек

См. базовое определение: Thread (computing)).

Практическое сравнение:

процессы изолированнее, но общение между ними обычно дороже

потоки дешевле для обмена данными, но сложнее для корректности из-за гонок

Планировщик и переключение контекста

Когда поток выполняется, CPU хранит его состояние в регистрах. Если ОС решает дать CPU другому потоку, происходит переключение контекста:

сохранить состояние текущего

загрузить состояние другого

Это не «бесплатно», поэтому большое число активных потоков может:

увеличивать накладные расходы

ухудшать кэш-попадания (данные одного потока вытесняют данные другого)

См. концепцию: Context switch.

!Как ОС переключает потоки и почему ожидание I/O влияет на выполнение

I/O и блокировки: почему программа «ничего не делает», но медленно

Частая реальность продакшена: CPU почти свободен, но сервис медленный. Причина — ожидание I/O:

диск

сеть

база данных

блокировки на синхронизации

Блокирующее ожидание

Если поток делает операцию чтения из сети и ждёт ответа, он может быть в состоянии blocked.

ОС в это время может выполнить другой поток. Но если у вас архитектура «один запрос = один поток», то при большом числе одновременных запросов вы получите:

много потоков в blocked

много памяти под стеки

накладные расходы на планирование

Неблокирующий ввод-вывод и событийные циклы

Альтернатива — неблокирующий I/O и событийная модель, где небольшое число потоков обслуживает много соединений.

Это не «магия», а другой способ использовать те же абстракции ОС:

вместо ожидания в потоке вы получаете уведомление о готовности данных

CPU тратится на обработку готовых событий

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

Как это связано с Big O и структурами данных

Big O остаётся важным, но теперь у нас есть более приземлённые правила.

Правило локальности

Даже при одинаковой асимптотике может выигрывать решение, которое:

читает память последовательно

хранит данные компактно

уменьшает количество указателей и разрозненных объектов

Отсюда практические паттерны:

массивы и компактные структуры часто быстрее деревьев и списков на малых и средних объёмах

батчи и буферы часто быстрее большого числа мелких операций

Правило «системный вызов дороже цикла»

Часто эффективнее:

сделать один запрос к базе и обработать данные в памяти

чем:

сделать маленьких запросов (типичная проблема N+1)

Big O здесь может выглядеть одинаково «на бумаге» для части кода, но реальная стоимость определяется числом I/O операций.

Правило «пики важны»

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

паузы из-за сборки мусора

page fault

rehash в хеш-таблице

конкуренция потоков за блокировку

Инженерный навык: отличать среднюю производительность (throughput) от хвостов распределения задержек (latency).

Мини-чеклист для разработчика

Отделяйте CPU-задачи от I/O-задач: оптимизации будут разными.

Помните про кэш: локальность памяти часто важнее «формальной красоты» структуры.

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

Различайте процессы и потоки: память общая, а проблемы синхронизации реальные.

Если стало «иногда медленно», ищите пики: page fault, блокировки, GC, rehash.

Итоги

CPU выполняет инструкции быстро, но часто ждёт память: кэш и локальность данных критичны.

ОС даёт абстракции: виртуальная память, процессы, потоки, файлы и сеть через системные вызовы.

Процесс изолирует память, поток делит память внутри процесса, а планировщик распределяет CPU через переключения контекста.

В реальных системах производительность упирается не только в Big O, но и в кэш, I/O и накладные расходы ОС.

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

Инженерные основы: отладка, тестирование, контроль версий, качество кода

Фундаментальные знания из предыдущих статей курса дают правильную модель мышления:

мы строим модель задачи и данных

выбираем абстракции и границы

оцениваем стоимость операций через Big O

помним, что реальная производительность упирается в память, кэш и I/O

Инженерные практики делают эти идеи управляемыми в реальном проекте:

отладка помогает быстро находить, где модель расходится с реальностью

тестирование фиксирует инварианты и не даёт системе «тихо сломаться»

контроль версий делает изменения обратимыми и объяснимыми

качество кода снижает стоимость изменений и ошибок

Эта статья про практические навыки, которые превращают «я написал код» в «я могу поддерживать систему годами».

Отладка как поиск расхождения модели и реальности

Отладка начинается не с инструмента, а с вопроса: какое утверждение в моей модели неверно? Например:

я думал, что список отсортирован, но он не отсортирован

я думал, что операция , но она запускает дорогой системный вызов

я думал, что два потока не трогают общий объект, но трогают

Минимальный цикл отладки

!Цикл отладки: как системно двигаться от симптома к исправлению

Практический цикл выглядит так:

Зафиксируйте симптом: что именно не так и где это видно.

Воспроизведите проблему: сделайте так, чтобы ошибка повторялась.

Сформулируйте гипотезу: что должно быть истинно, но не истинно.

Наблюдайте: соберите факты через логи, дебаггер, метрики.

Минимизируйте: найдите самый маленький вход или сценарий, который ломает систему.

Исправьте причину: меняйте не симптом, а источник расхождения.

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

Ключевая идея: если проблема не воспроизводится, вы не управляете процессом отладки.

Инструменты наблюдения

#### Логи

Логи полезны, когда:

баг проявляется только в окружении, куда нельзя подключить дебаггер

проблема связана с конкуренцией или редкими таймингами

нужно собрать контекст: входные параметры, идентификаторы, порядок событий

Практические правила:

логируйте границы (вход/выход) и инварианты (ожидаемые условия)

добавляйте корреляционный идентификатор запроса, чтобы склеивать события

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

#### Дебаггер

Дебаггер помогает «заморозить мир» и посмотреть состояние программы.

Что обычно делают:

ставят breakpoint (точку остановки)

смотрят стек вызовов, локальные переменные, значения выражений

выполняют код построчно

Полезное понятие: стек вызовов показывает, какие функции привели к текущей точке. Это напрямую связано с тем, как память выделяется под вызовы функций (стек), о чём мы говорили в статье про устройство компьютера. См. Call stack.

#### Профилирование

Если «всё правильно, но медленно», нужен не дебаггер, а профилировщик.

Профилирование отвечает на вопросы:

где тратится CPU-время

где много аллокаций и давление на сборщик мусора

какие функции вызываются слишком часто

Это практическое продолжение тем Big O и структур данных: асимптотика говорит как растёт, профилирование показывает где именно больно сейчас.

#### Трассировка и метрики

Для распределённых систем важны:

метрики (время ответа, ошибки, очереди, использование CPU/RAM)

трассировка запросов между сервисами

Одна из причин «странной медленности» часто не в алгоритме, а в I/O и ожиданиях (сеть, диск, база, блокировки), что напрямую связано с темой ОС и процессов.

Частые классы ошибок и как их распознавать

| Симптом | Частая причина | Что проверить сначала | | --- | --- | --- | | «Иногда падает» | гонка потоков, неинициализированное состояние | общий доступ к данным, критические секции | | «Иногда медленно» | GC-пауза, page fault, блокировки, rehash | хвосты latency, пики аллокаций, локи | | «Работает локально, не работает в проде» | конфиг, окружение, данные, права | различия конфигов, версии, входные данные | | «Долго грузит и много памяти» | слишком много объектов, плохая локальность | структура данных, аллокации, кеширование |

Тестирование как фиксация инвариантов

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

Тестирование отвечает на два вопроса:

что система делает правильно (корректность)

что не сломалось после изменений (регрессия)

См. обзорно: Software testing.

Уровни тестов

!Пирамида тестов: баланс скорости, надёжности и покрытия

Определения:

Юнит-тест проверяет маленький кусок логики изолированно, обычно функцию или класс.

Интеграционный тест проверяет взаимодействие компонентов, например код + база данных.

Сквозной тест (E2E) проверяет сценарий целиком, как пользователь: UI или API + все зависимости.

Практический принцип: чем выше уровень теста, тем он обычно медленнее и сложнее в сопровождении.

Что именно тестировать

Хорошие кандидаты для тестов:

чистые функции и бизнес-правила (валидаторы, расчёты, переходы состояний)

критичные инварианты (например, «баланс не уходит ниже лимита»)

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

Плохие кандидаты:

детали реализации, которые вы хотите свободно менять

поведение, зависящее от таймингов, если это можно переписать детерминированно

Моки, стабы и тестовые двойники

Если тест зависит от внешнего мира (сеть, база, время), он становится нестабильным.

Чтобы изолировать логику, используют тестовые двойники:

стаб возвращает заранее заданный ответ

мок дополнительно проверяет, как именно его вызвали

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

Флейки-тесты

Флейки-тест — тест, который иногда проходит, иногда падает при одинаковом коде.

Типовые причины:

гонки и параллельность

зависимость от времени и таймеров

общий изменяемый глобальный стейт между тестами

реальная сеть или нестабильные внешние сервисы

Флейки-тесты опасны, потому что команда перестаёт доверять тестам, а значит теряет главное преимущество автоматической проверки.

Покрытие кода и его ограничения

Покрытие показывает, какие строки или ветки кода выполнялись тестами. Оно полезно как сигнал, но не как цель.

высокое покрытие не гарантирует, что проверены правильные свойства

низкое покрытие почти всегда означает риск, особенно в критичной логике

См. Code coverage.

Контроль версий как «память проекта»

Контроль версий отвечает на вопросы:

что изменилось и почему

кто и когда это сделал

как вернуться к рабочему состоянию

Стандарт де-факто в индустрии — Git. См. Git и Pro Git.

Базовые понятия Git

репозиторий хранит историю изменений

коммит фиксирует снимок состояния проекта и описание изменения

ветка указывает на последовательность коммитов

слияние (merge) объединяет изменения двух веток

Практическая привычка: делайте коммиты маленькими и смысловыми, чтобы историю можно было читать как объяснение проекта.

Сообщения коммитов

Хорошее сообщение коммита отвечает на вопрос что и зачем, а не как.

Пример:

плохо: fix

хорошо: Fix validation: reject empty email to keep uniqueness invariant

Это связывает контроль версий с темой инвариантов из первой статьи.

Код-ревью

Код-ревью — это не «проверка новичка», а механизм качества.

Что обычно ловят на ревью:

нарушения инвариантов и неочевидные граничные случаи

ухудшение асимптотики или лишние аллокации

плохие границы модулей и смешение уровней абстракции

небезопасные изменения в конкурентном коде

Поиск коммита, который сломал систему

Если «вчера работало, сегодня нет», полезно найти точку поломки.

Git даёт инструмент git bisect, который делает бинарный поиск по истории коммитов: вы помечаете известный хороший коммит и известный плохой, а Git помогает быстро найти первый плохой.

Это прямое применение идеи деления пополам из алгоритмов и мышления, но к истории проекта.

Качество кода как снижение стоимости изменений

Качество кода — это не про «красоту», а про способность безопасно менять систему.

Определение, удобное для практики:

качественный код легко читать

в нём ясно, где границы и ответственность

он защищён тестами на уровне инвариантов

его производительность предсказуема

Читаемость и когнитивная нагрузка

Код читают чаще, чем пишут.

Практические правила:

имена должны отражать модель предметной области

функции должны делать одну понятную вещь

сложные участки должны быть оформлены через понятные абстракции, а не через комментарии к хаосу

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

Границы модулей и зависимости

Ключевой вопрос качества: что от чего зависит.

Плохой признак:

доменная логика зависит от деталей SQL, HTTP, UI

Хороший признак:

доменная логика выражена отдельно и тестируется быстро

Это продолжает идею «не смешивать уровни абстракции» из первой статьи.

Линтеры, форматтеры и статический анализ

Инструменты качества помогают автоматизировать рутину:

форматтер делает стиль единообразным

линтер ловит подозрительные места

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

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

Рефакторинг и технический долг

Рефакторинг — изменение внутренней структуры кода без изменения внешнего поведения.

Почему он нужен:

требования меняются, и код должен оставаться гибким

накопление временных решений увеличивает риск ошибок и стоимость изменений

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

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

Качество и производительность

Производительность часто «вшита» в качество дизайна:

неудачная структура данных даёт лишние в горячем месте

лишние системные вызовы превращают быстрый код в медленный из-за I/O

плохая локальность памяти может сделать «нормальный алгоритм» в разы медленнее

Поэтому качество кода включает и дисциплину измерений: профилировать, а не гадать.

Практический рабочий процесс

Ниже — типичный поток изменений, который связывает всё вместе.

Опишите изменение через модель и инварианты.

Сделайте маленькую ветку.

Добавьте или обновите тесты на нужном уровне.

Реализуйте изменение.

Запустите линтеры, тесты и базовые проверки.

Откройте pull request и пройдите код-ревью.

Слейте в основную ветку.

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

Итоги

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

Тесты фиксируют инварианты и защищают от регрессий; уровень теста определяет его скорость и стоимость сопровождения.

Git делает изменения объяснимыми и обратимыми, а git bisect превращает поиск поломки в управляемый процесс.

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

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