замеры

SRT Алгоритм Интерполяционный поиск Прикинуть место по значениям на краях: log log n проб на равномерных ключах и до n — на неудобных. ≈ log₂ log₂ n в среднем, n в худшем 1 задача NUM Алгоритм Генераторы псевдослучайных чисел Откуда берутся «случайные» числа, почему плохой генератор видно по плоскостям и как его проверить. O(1) на число 2 задачи TEC Приём O-большое Как растёт работа вместе с данными: O, Ω и Θ, правила оценки кода и где асимптотика обманывает. оценка — по тексту программы 1 задача TEC Приём Быстрый ввод и вывод Миллион чисел за десятки миллисекунд вместо секунды: чтение целиком, буфер и одна запись вывода. O(размер входа) 1 задача TEC Приём Как честно измерить скорость Повторы, прогрев, медиана и минимум, timeit и testing.Benchmark — и типичные способы обмануть себя замером. повторов столько, чтобы замер шёл хотя бы десятую долю секунды 1 задача TEC Приём Данные, удобные кэшу Тот же алгоритм, другой порядок обращений к памяти: обход блоками, запас в строках и раскладка по полям. O-большое то же 1 задача TEC Приём Сколько операций в секунду Шаги алгоритма, делённые на скорость языка, — и вы знаете, уложится ли программа, ещё до того, как её написали. оценка — секунды в уме 1 задача TEC Приём Сложность по замерам Рост времени по замерам: наклон, проверка отношением, экспоненты — и где замер врёт. O(B) на попытку 1 задача TEC Приём Векторизация Вынести цикл из интерпретатора в операции над целыми массивами: что ускоряется в сотни раз и что не векторизуется. та же O(n), что у цикла 2 задачи TEC Приём Профилировщики Не гадать, где программа тратит время, а посмотреть: выборочный профилировщик, cProfile и pprof, граф пламени. доля функции ± √(p(1−p)/N) 1 задача TEC Приём Числа, которые стоит знать Кэш, память, диск и сеть отличаются в сотни раз — прикидка по этим числам показывает, что ускорять. прикидка — минута на салфетке 1 задача TEC Приём Амортизационный анализ Оценка всей последовательности операций, а не каждой: суммой, монетами и потенциалом — и где она не спасает. оценка на последовательность 2 задачи TEC Приём Как выбрать структуру данных Сначала список операций, потом структура: стоимость каждой операции в Python и Go на одной карте. зависит от выбора 1 задача TEC Приём Сколько займёт в памяти Байты на запись — и сразу видно, поместится ли миллиард: из чего складывается вес данных в Python и Go. прикидка — байты на запись × число записей 1 задача TEC Приём Предподсчёт и таблицы Посчитать ответы заранее и брать из таблицы: CRC-32 байтом за шаг вместо бита и где таблица перестаёт помогать. O(размер таблицы) один раз, затем O(1) на запрос 1 задача