Задачник Базовый курс EN

Как устроен

дружит с кэшем

Статьи

DS Структура данных Динамический массив Массив, который растёт сам: доступ по индексу за O(1), добавление в конец — за O(1) амортизированно. O(1) амортизированно на append 2 задачи DS Структура данных B-дерево Дерево с сотнями ключей в узле-странице: поиск среди миллиарда ключей читает пять страниц. O(log n) сравнений, O(log_B n) чтений страниц 2 задачи GRA Приём Как хранить граф Матрица, списки, массив рёбер и CSR: память, скорость и какие вопросы каждая запись задаёт дёшево.

соседи вершины: O(n) у матрицы, O(deg) у списков и CSR; есть ли ребро: O(1) у матрицы, O(deg) у списков

2 задачи NUM Алгоритм Решето Эратосфена Все простые до n за O(n log log n): вычёркиваем кратные каждого простого, начиная с его квадрата. O(n log log n) 2 задачи TEC Приём Данные, удобные кэшу Тот же алгоритм, другой порядок обращений к памяти: обход блоками, запас в строках и раскладка по полям. O-большое то же 1 задача TEC Приём Числа, которые стоит знать Кэш, память, диск и сеть отличаются в сотни раз — прикидка по этим числам показывает, что ускорять. прикидка — минута на салфетке 1 задача

Задачи

Промахи кэша

Часто рядом

массив 4 классика 4 собеседования 3 в проде 3 базы данных 2 матрица 2 оценка 2 замеры 2 амортизация 1 дерево 1 дерево поиска 1 внешняя память 1