# Веб-презентация ## Замеры времени и памяти алгоритмов в Python ### Общая идея презентации Это не обычная лекция с последовательным чтением текста. Вся презентация строится вокруг одного повторяющегося сценария: **ПРЕДСКАЖИ → ЗАПУСТИ → ИЗМЕРЬ → СРАВНИ → ОБЪЯСНИ** Студенты уже изучили: * `T(n)`; * `S(n)`; * нотацию `O`; * `O(1)`; * `O(n)`; * `O(n²)`. Поэтому не нужно повторно подробно объяснять Big O. Главная задача занятия: > Научиться связывать теоретическую оценку алгоритма с реальными измерениями времени и памяти. --- # Слайд 1. От Big O к реальному коду ## Заголовок Мы уже умеем предсказывать рост алгоритма ## Основной текст На прошлом занятии мы рассматривали: **T(n)** — как растёт объём работы. **S(n)** — как растёт дополнительная память. И описывали алгоритмы: `O(1)` `O(n)` `O(n²)` Но теперь возникает практический вопрос: > Если алгоритм имеет `O(n)`, увидим ли мы это при реальном запуске Python-кода? ## Layout Экран разделён на две части. Слева крупно: ```text T(n) = O(n) S(n) = O(1) ``` Справа: ```text 0.0048 sec 17.2 MB ``` Между блоками стрелка: **ТЕОРИЯ → ЭКСПЕРИМЕНТ** --- # Слайд 2. O(n) — это не секунды ## Заголовок Big O не говорит, сколько секунд работает программа ## Текст `O(n)` означает: > При росте размера входных данных объём работы алгоритма растёт примерно пропорционально `n`. Но конкретное время зависит ещё и от: * процессора; * версии Python; * реализации алгоритма; * структуры данных; * нагрузки системы. ## Акцент Не путать: ```text O(n) ``` и ```text 0.03 секунды ``` ## Layout Две большие карточки. ### THEORY **O(n)** Характер роста. ### MEASUREMENT **0.0317 sec** Конкретный эксперимент. --- # Слайд 3. Сначала прогноз ## Заголовок Что произойдёт, если увеличить n? ## Код Файл: `01_linear_function.py` ```python def calculate(n): total = 0 for i in range(n): total += i return total ``` ## Вопрос №1 Какова временная сложность? ### Интерактивные кнопки `O(1)` `O(n)` `O(n²)` После выбора показать: **Правильно: O(n)** ## Вопрос №2 Если увеличить: ```text n = 100 000 ``` до: ```text n = 1 000 000 ``` во сколько раз примерно увеличится объём работы? ### Варианты `≈ ×1` `≈ ×10` `≈ ×100` Правильный ответ: `≈ ×10` ## Layout Слева код. Справа вопросы. Ответы появляются только после клика. --- # Слайд 4. Как это проверить? ## Заголовок Нам нужен эксперимент ## Текст Сделаем четыре запуска: ```text 10 000 100 000 1 000 000 10 000 000 ``` Для каждого измерим реальное время выполнения. Затем сравним: > Похож ли рост времени на тот, который мы ожидали от `O(n)`? ## Визуал ```text КОД ↓ ПРОГНОЗ ↓ n увеличивается ↓ ЗАМЕР ↓ СРАВНЕНИЕ ``` --- # Слайд 5. perf_counter() ## Заголовок Как измерить время выполнения? ## Код ```python from time import perf_counter ``` Простейшая схема: ```python start = perf_counter() # код finish = perf_counter() elapsed = finish - start ``` ## Текст `perf_counter()` — высокоточный таймер. Нас интересует не значение таймера само по себе, а разница: ```python finish - start ``` ## Layout Сверху короткий текст. Снизу горизонтальная временная шкала: ```text START ───── выполнение функции ───── FINISH ``` Под ней: ```python elapsed = finish - start ``` --- # Слайд 6. Первый реальный замер ## Заголовок Замеряем алгоритм O(n) ## Файл `02_first_measurement.py` ## Код ```python from time import perf_counter def calculate(n): total = 0 for i in range(n): total += i return total n = 1_000_000 start = perf_counter() calculate(n) elapsed = perf_counter() - start print(f"{elapsed:.6f} sec") ``` ## Практика Студенты запускают код. ## Элемент интерфейса Поле: ```text Мой результат: __________ sec ``` Кнопки: **Скопировать код** **Скачать 02_first_measurement.py** ## Важно Не показывать заранее «правильное» время. На разных компьютерах оно будет разным. --- # Слайд 7. Главное — рост, а не одно число ## Заголовок Один замер почти ничего не говорит ## Код Файл: `03_growth_experiment.py` ```python from time import perf_counter def calculate(n): total = 0 for i in range(n): total += i return total sizes = [ 10_000, 100_000, 1_000_000, 10_000_000, ] for n in sizes: start = perf_counter() calculate(n) elapsed = perf_counter() - start print( f"n={n:>10} | " f"time={elapsed:.6f}" ) ``` ## Таблица рядом | n | Моё время | | ---------: | --------: | | 10 000 | | | 100 000 | | | 1 000 000 | | | 10 000 000 | | ## Главный вопрос Что происходит со временем при увеличении `n` примерно в 10 раз? --- # Слайд 8. Связываем эксперимент с O(n) ## Заголовок Что мы увидели? ## Текст Конкретные значения могут отличаться. Например, условно: ```text 10 000 → быстро 100 000 → больше 1 000 000 → ещё больше 10 000 000 → значительно больше ``` Нас интересует не точное число секунд. Нас интересует: > Характер роста. Если время растёт примерно вместе с `n`, эксперимент согласуется с нашей оценкой: **T(n) = O(n)** ## Акцент Большая надпись: **Big O мы не измеряем секундомером.** Мы экспериментально проверяем, соответствует ли поведение программы нашей модели. --- # Слайд 9. Один запуск может обмануть ## Заголовок Почему время каждый раз немного разное? ## Показать пример ```text 0.0312 sec 0.0297 sec 0.0324 sec 0.0418 sec 0.0305 sec ``` ## Текст На результат влияют: * фоновые приложения; * операционная система; * загрузка CPU; * системные процессы; * случайные задержки. Поэтому один запуск — ненадёжное измерение. ## Интерактив Кнопка: **Запустить ещё раз** После клика значения слегка меняются. Можно использовать демонстрационные случайные значения только как визуальную имитацию интерфейса, не выдавая их за реальные измерения пользователя. --- # Слайд 10. Несколько повторений ## Заголовок Создадим нормальный измеритель ## Файл `measurements.py` ## Код ```python from time import perf_counter from statistics import median def measure_time(func, *args, repeats=7): measurements = [] for _ in range(repeats): start = perf_counter() func(*args) elapsed = perf_counter() - start measurements.append(elapsed) return median(measurements) ``` ## Текст Мы: 1. запускаем функцию несколько раз; 2. сохраняем результаты; 3. берём медиану. Медиана уменьшает влияние случайного очень медленного запуска. ## Layout Код занимает 60% экрана. Справа небольшая схема: ```text 7 запусков ↓ 7 результатов ↓ median ↓ одно значение ``` --- # Слайд 11. Измеряйте только нужную операцию ## Заголовок Честный эксперимент нужно изолировать ## Левая часть — неправильно ```python start = perf_counter() numbers = list(range(1_000_000)) result = -1 in numbers elapsed = perf_counter() - start ``` Подпись: **Измеряем создание списка + поиск** ## Правая часть — правильно ```python numbers = list(range(1_000_000)) start = perf_counter() result = -1 in numbers elapsed = perf_counter() - start ``` Подпись: **Измеряем только поиск** ## Главная мысль Если сравниваем поиск — подготовку данных делаем заранее. --- # Слайд 12. Лаборатория роста ## Заголовок Теперь проверим O(1), O(n) и O(n²) ## Текст Для каждого алгоритма одинаковый порядок: ### 1 Определяем Big O. ### 2 Прогнозируем поведение. ### 3 Увеличиваем `n`. ### 4 Измеряем. ### 5 Сравниваем теорию и эксперимент. ## Layout Три крупные карточки: **O(1)** Доступ по индексу. **O(n)** Линейный поиск. **O(n²)** Вложенные циклы. --- # Слайд 13. Эксперимент O(1) ## Заголовок Доступ к элементу списка ## Файл `04_constant_access.py` ## Код ```python def get_middle(numbers): index = len(numbers) // 2 return numbers[index] ``` ## Вопрос Если список увеличится: ```text 1 000 ↓ 1 000 000 ``` нужно ли пройти миллион элементов, чтобы получить элемент по известному индексу? ### Кнопки **Да** **Нет** Ответ: **Нет** Доступ по индексу списка: `O(1)` --- # Слайд 14. Проверяем O(1) ## Код ```python for n in [ 1_000, 10_000, 100_000, 1_000_000, ]: numbers = list(range(n)) elapsed = measure_time( get_middle, numbers, repeats=100 ) print( f"n={n:>8} | " f"time={elapsed:.10f}" ) ``` ## Текст Для очень быстрых операций измерения будут шумными. Не ожидаем идеально одинаковых значений. Важно другое: > Рост размера списка не должен приводить к пропорциональному росту времени доступа. ## Визуал Небольшой график почти горизонтального характера. --- # Слайд 15. Эксперимент O(n) ## Заголовок Линейный поиск ## Файл `05_linear_search.py` ## Код ```python def linear_search(numbers, target): for number in numbers: if number == target: return True return False ``` ## Вопрос Какова сложность поиска в худшем случае? ### Кнопки `O(1)` `O(n)` `O(n²)` После выбора: **O(n)** --- # Слайд 16. Почему ищем -1? ## Заголовок Создаём худший сценарий ## Код ```python numbers = list(range(1_000_000)) result = linear_search( numbers, -1 ) ``` ## Текст Список содержит: ```text 0 1 2 3 ... 999999 ``` Значения `-1` нет. Поэтому алгоритм не завершится раньше времени. Он проверит весь список. ## Акцент **Нам нужен контролируемый эксперимент.** --- # Слайд 17. Измеряем O(n) ## Код ```python for n in [ 10_000, 100_000, 1_000_000, ]: numbers = list(range(n)) elapsed = measure_time( linear_search, numbers, -1 ) print( f"n={n:>10} | " f"time={elapsed:.6f}" ) ``` ## Таблица | n | Время | | --------: | ----: | | 10 000 | | | 100 000 | | | 1 000 000 | | ## Интерактив Студент сначала заполняет прогноз: ```text Если n ×10 → время примерно __________ ``` После запуска сравнивает прогноз с результатом. --- # Слайд 18. Эксперимент O(n²) ## Заголовок Вложенные циклы ## Файл `06_quadratic.py` ## Код ```python def process_pairs(n): counter = 0 for i in range(n): for j in range(n): counter += 1 return counter ``` ## Вопрос Если: ```text n = 100 ``` сколько раз выполнится: ```python counter += 1 ``` ## Ответ после клика ```text 100 × 100 = 10 000 ``` --- # Слайд 19. Что будет при удвоении n? ## Заголовок Сначала считаем, потом запускаем ## Визуал ```text n = 100 100² = 10 000 ``` ↓ `n ×2` ```text n = 200 200² = 40 000 ``` ## Вывод Размер входа: `×2` Количество работы: `×4` ## Большой акцент **O(n²)** --- # Слайд 20. Проверяем квадратичный рост ## Код ```python for n in [ 100, 200, 400, 800, ]: elapsed = measure_time( process_pairs, n, repeats=5 ) print( f"n={n:>4} | " f"time={elapsed:.6f}" ) ``` ## Таблица | n | Время | Рост относительно предыдущего | | --: | ----: | ----------------------------: | | 100 | | | | 200 | | | | 400 | | | | 800 | | | ## Главный вопрос При удвоении `n` похоже ли увеличение времени на `×4`? Не требовать идеального коэффициента. --- # Слайд 21. Теперь видна разница ## Заголовок Одинаковое увеличение n — разный результат ## Визуал Большой график: * `O(1)` — практически горизонтально; * `O(n)` — постепенно вверх; * `O(n²)` — резко вверх. ## Текст На маленьких данных разница может казаться незначительной. Но при росте `n` алгоритмы начинают расходиться всё сильнее. ## Большой вывод > Big O особенно важен не для сегодняшнего размера данных, а для будущего роста. --- # Слайд 22. Big O ≠ абсолютная скорость ## Заголовок Два O(n) могут работать с разной скоростью ## Код A ```python def manual_sum(numbers): result = 0 for number in numbers: result += number return result ``` ## Код B ```python def builtin_sum(numbers): return sum(numbers) ``` ## Вопрос Какая сложность? ### Ответ Оба варианта: **O(n)** --- # Слайд 23. Измеряем два O(n) ## Код ```python numbers = list(range(1_000_000)) manual_time = measure_time( manual_sum, numbers ) builtin_time = measure_time( builtin_sum, numbers ) print( f"manual: {manual_time:.6f}" ) print( f"sum(): {builtin_time:.6f}" ) ``` ## Текст Обе реализации имеют линейный характер роста. Но встроенная реализация обычно работает быстрее. ## Вывод Big O не показывает: * постоянные коэффициенты; * оптимизации реализации; * стоимость отдельных операций. Он показывает **масштабирование**. --- # Слайд 24. Инженерная задача: миллион ID ## Заголовок Нужно много раз проверять наличие пользователя ## Ситуация В программе хранится: ```text 1 000 000 ID ``` Нужно постоянно выполнять: > Есть ли ID в наборе? ## Вариант A ```python users_list = list( range(1_000_000) ) -1 in users_list ``` ## Вариант B ```python users_set = set( range(1_000_000) ) -1 in users_set ``` ## Интерактив Вопрос: **Какой вариант быстрее при большом количестве поисков?** `list` `set` --- # Слайд 25. list против set ## Заголовок Одна задача — разные структуры данных ## Текст ### list Поиск элемента: **O(n)** в худшем случае. ### set Проверка принадлежности: **O(1) в среднем.** Важно: Это средняя ожидаемая сложность хеш-таблицы. ## Код Файл: `07_list_vs_set.py` ```python numbers_list = list( range(1_000_000) ) numbers_set = set( numbers_list ) def search_list(): return -1 in numbers_list def search_set(): return -1 in numbers_set print( "list:", measure_time( search_list, repeats=20 ) ) print( "set:", measure_time( search_set, repeats=20 ) ) ``` --- # Слайд 26. Значит set всегда лучше? ## Заголовок Мы измерили только время ## Текст `set` ускорил поиск. Но за это приходится платить. Хеш-таблица требует дополнительную память. Возвращаемся к тому, что уже изучали: ```text T(n) ``` и ```text S(n) ``` До сих пор экспериментально проверяли только `T(n)`. Теперь займёмся `S(n)`. ## Layout Слева: **T(n) ✓** Справа: **S(n) ?** --- # Слайд 27. Два одинаковых результата ## Заголовок Можно решить задачу одинаково по времени, но по-разному по памяти ## Код A ```python def version_a(n): squares = [] for i in range(n): squares.append(i * i) return sum(squares) ``` ## Код B ```python def version_b(n): total = 0 for i in range(n): total += i * i return total ``` ## Вопросы Обе функции дают одинаковый результат? **Да.** Обе имеют линейное время? **Да: O(n).** А память? Не показывать ответ сразу. --- # Слайд 28. Анализируем S(n) ## Заголовок Что хранится в памяти? ## Левая часть ### version_a Создаётся список: ```text 0 1 4 9 16 25 ... ``` Чем больше `n`, тем больше список. **S(n) = O(n)** ## Правая часть ### version_b Хранятся только: ```text i total ``` Количество дополнительных переменных практически не растёт. **S(n) = O(1)** ## Вывод По времени: ```text O(n) vs O(n) ``` По памяти: ```text O(n) vs O(1) ``` --- # Слайд 29. tracemalloc ## Заголовок Теперь измерим память ## Код ```python import tracemalloc ``` ## Основная схема ```python tracemalloc.start() # выполняемый код current, peak = ( tracemalloc.get_traced_memory() ) tracemalloc.stop() ``` ## Текст Нас особенно интересует: ```python peak ``` Это максимальный объём отслеживаемой памяти во время эксперимента. ## Важно `tracemalloc` отслеживает выделения памяти Python. Это не полный измеритель всей памяти операционной системы или процесса. --- # Слайд 30. Измеритель памяти ## Файл `measurements.py` Добавить: ```python import tracemalloc def measure_memory(func, *args): tracemalloc.start() result = func(*args) current, peak = ( tracemalloc.get_traced_memory() ) tracemalloc.stop() return result, peak ``` ## Использование ```python _, peak = measure_memory( version_a, 1_000_000 ) print( f"{peak / 1024 / 1024:.2f} MB" ) ``` ## Layout Слева код функции. Справа: ```text BYTES ↓ / 1024 KB ↓ / 1024 MB ``` --- # Слайд 31. Измеряем две реализации ## Заголовок Теория против реальной памяти ## Код ```python n = 1_000_000 _, memory_a = measure_memory( version_a, n ) _, memory_b = measure_memory( version_b, n ) print( "A:", memory_a / 1024 / 1024, "MB" ) print( "B:", memory_b / 1024 / 1024, "MB" ) ``` ## Таблица | Решение | T(n) | S(n) | Peak Memory | | --------- | ---- | ---- | ----------: | | version_a | O(n) | O(n) | | | version_b | O(n) | O(1) | | ## Интерактив Студенты сначала прогнозируют, какая версия потребует больше памяти. Затем запускают. --- # Слайд 32. Python-пример: list vs generator ## Заголовок Ещё один способ увидеть S(n) ## Вариант A ```python def with_list(n): return sum( [i * i for i in range(n)] ) ``` ## Вариант B ```python def with_generator(n): return sum( i * i for i in range(n) ) ``` ## Визуал ### LIST ```text создать все значения ↓ хранить все значения ↓ sum() ``` ### GENERATOR ```text создать одно ↓ передать sum() ↓ следующее ↓ ... ``` ## Вывод Промежуточный список: **O(n) памяти** Генератор: **примерно O(1) дополнительной памяти** --- # Слайд 33. Время против памяти ## Заголовок Time–Space Tradeoff ## Текст Иногда более быстрое решение требует больше памяти. Иногда экономия памяти увеличивает стоимость вычислений. Например: ### list Поиск медленнее. Структура проще. ### set Поиск значительно быстрее в среднем. Но требуется память для хеш-таблицы. ## Визуал Весы: ```text TIME ⚖ MEMORY ``` ## Главный термин **Time–Space Tradeoff** Компромисс между временем и памятью. --- # Слайд 34. Финальная задача: поиск дубликатов ## Заголовок Теперь применим всё сразу ## Ситуация Есть список ID. Нужно определить: > Есть ли хотя бы один повторяющийся ID? Есть два решения. Сначала ничего не запускать. Для каждого определить: ```text T(n) S(n) ``` --- # Слайд 35. Решение A ## Заголовок Сравнить каждую пару ## Файл `08_duplicates_nested.py` ## Код ```python def has_duplicates_nested(numbers): n = len(numbers) for i in range(n): for j in range(i + 1, n): if numbers[i] == numbers[j]: return True return False ``` ## Интерактив Заполнить: ```text T(n) = ______ S(n) = ______ ``` ## Ответ после клика В худшем случае: ```text T(n) = O(n²) S(n) = O(1) ``` --- # Слайд 36. Решение B ## Заголовок Запоминать уже встреченные значения ## Файл `09_duplicates_set.py` ## Код ```python def has_duplicates_set(numbers): seen = set() for number in numbers: if number in seen: return True seen.add(number) return False ``` ## Интерактив ```text T(n) = ______ S(n) = ______ ``` ## Ответ В среднем: ```text T(n) = O(n) S(n) = O(n) ``` --- # Слайд 37. Сначала прогноз ## Заголовок Как поведут себя два решения? ## Таблица | Решение | T(n) | S(n) | | ------- | -------------- | ---- | | nested | O(n²) | O(1) | | set | O(n) в среднем | O(n) | ## Вопрос №1 Если увеличить `n` в два раза, какое решение начнёт замедляться значительно сильнее? Ответ: **nested** ## Вопрос №2 Какое решение потребует больше дополнительной памяти? Ответ: **set** --- # Слайд 38. Финальный эксперимент ## Файл `10_final_experiment.py` ## Код ```python def create_unique_data(n): return list(range(n)) sizes = [ 500, 1_000, 2_000, 4_000, ] for n in sizes: numbers = create_unique_data(n) nested_time = measure_time( has_duplicates_nested, numbers, repeats=3 ) set_time = measure_time( has_duplicates_set, numbers, repeats=5 ) print( f"{n=} | " f"nested={nested_time:.6f} | " f"set={set_time:.6f}" ) ``` ## Таблица | n | nested | set | | ----: | -----: | --: | | 500 | | | | 1 000 | | | | 2 000 | | | | 4 000 | | | ## Текст Используем список без дубликатов. Так оба алгоритма не смогут завершиться раньше после нахождения повторения. --- # Слайд 39. Какое решение лучше? ## Заголовок Ответ зависит от требований ## Левая карточка ### Nested loops **T(n): O(n²)** **S(n): O(1)** Плюс: минимальная дополнительная память. Минус: плохо масштабируется по времени. ## Правая карточка ### Set **T(n): O(n) в среднем** **S(n): O(n)** Плюс: намного лучше масштабируется по времени. Минус: требует дополнительную память. ## Финальный вопрос Что важнее в конкретной системе: **время или память?** --- # Слайд 40. Правильный алгоритмический эксперимент ## Заголовок Как теперь исследовать алгоритм ## Визуал Большая вертикальная схема: ```text 1. ПРОЧИТАТЬ КОД ↓ 2. ОПРЕДЕЛИТЬ T(n) И S(n) ↓ 3. СФОРМУЛИРОВАТЬ ПРОГНОЗ ↓ 4. ПОДГОТОВИТЬ ДАННЫЕ ↓ 5. ПРОВЕСТИ ЗАМЕР ↓ 6. УВЕЛИЧИТЬ n ↓ 7. СРАВНИТЬ РЕЗУЛЬТАТЫ ↓ 8. ОБЪЯСНИТЬ ПОВЕДЕНИЕ ``` ## Главная мысль **Сначала анализ. Потом измерение.** --- # Слайд 41. Ошибки при замерах ## Заголовок Что может испортить эксперимент? ## Карточки ### Один запуск Слишком много случайного шума. ### Слишком маленькие данные Разница между алгоритмами может быть незаметна. ### Лишний код внутри замера Измеряем не только интересующую операцию. ### Разные входные условия Сравнение становится нечестным. ### Сравнение абсолютных секунд разных компьютеров Аппаратное обеспечение отличается. ### Вывод Big O только по секундам Эксперимент не заменяет математический анализ. --- # Слайд 42. Что мы сегодня измерили ## Заголовок Собираем всё вместе ## Таблица | Операция | T(n) | S(n) | | ------------------------ | -------------- | ---- | | доступ по индексу list | O(1) | O(1) | | линейный поиск | O(n) | O(1) | | вложенные циклы | O(n²) | O(1) | | ручная сумма | O(n) | O(1) | | `sum()` | O(n) | O(1) | | поиск в list | O(n) | O(1) | | поиск в set | O(1) в среднем | — | | список квадратов | O(n) | O(n) | | последовательный подсчёт | O(n) | O(1) | | поиск дублей через пары | O(n²) | O(1) | | поиск дублей через set | O(n) в среднем | O(n) | ## Важно Для `set` отдельно проговорить: сама структура данных требует памяти `O(n)`. --- # Слайд 43. Что нужно уметь после пары ## Заголовок Проверь себя ## Чек-лист Я умею: * определять `T(n)` простого алгоритма; * определять `S(n)`; * делать прогноз до запуска; * измерять время через `perf_counter()`; * выполнять несколько повторов; * использовать медиану; * правильно отделять подготовку данных от измеряемой операции; * измерять Python-выделения памяти через `tracemalloc`; * сравнивать алгоритмы по времени и памяти; * объяснять time–space tradeoff. ## Интерактив Чекбоксы можно нажимать прямо на слайде. --- # Слайд 44. Финальная мысль ## Заголовок Не спрашивайте только «быстро ли работает?» ## Текст У хорошего анализа алгоритма минимум четыре вопроса: ### Как быстро он работает сейчас? ### Как время изменится при росте данных? ### Как будет расти потребление памяти? ### Что произойдёт, если данных станет в 10 или 100 раз больше? ## Финальный визуал Крупно: ```text BIG O + MEASUREMENTS + EXPERIMENT = ПОНИМАНИЕ АЛГОРИТМА ``` Под ним: **ПРЕДСКАЖИ → ИЗМЕРЬ → ОБЪЯСНИ** --- # Блок файлов на сайте На веб-презентации сделать отдельную кнопку: **Скачать файлы занятия** Структура: ```text algorithm_measurements/ │ ├── measurements.py │ ├── 01_linear_function.py ├── 02_first_measurement.py ├── 03_growth_experiment.py ├── 04_constant_access.py ├── 05_linear_search.py ├── 06_quadratic.py ├── 07_list_vs_set.py ├── 08_duplicates_nested.py ├── 09_duplicates_set.py └── 10_final_experiment.py ``` --- # Файл measurements.py ```python from time import perf_counter from statistics import median import tracemalloc def measure_time(func, *args, repeats=7): measurements = [] for _ in range(repeats): start = perf_counter() func(*args) elapsed = perf_counter() - start measurements.append(elapsed) return median(measurements) def measure_memory(func, *args): tracemalloc.start() result = func(*args) current, peak = ( tracemalloc.get_traced_memory() ) tracemalloc.stop() return result, peak ``` --- # Требования к дизайну веб-презентации ## Код Каждый блок кода должен иметь: * название файла; * подсветку Python; * кнопку «Скопировать»; * кнопку «Скачать .py» там, где файл используется в практике; * крупный шрифт; * номера строк только в больших примерах. Не помещать огромные блоки кода в маленькие карточки. --- ## Интерактивные вопросы Использовать кнопки: ```text O(1) O(n) O(n²) ``` или: ```text ×2 ×4 ×10 ``` Правильный ответ не показывать до выбора. После ответа: * правильный вариант подсветить; * дать объяснение максимум в 1–2 предложениях. --- ## Эксперименты Все экспериментальные слайды строить одинаково: ```text КОД ↓ ПРОГНОЗ ↓ ЗАПУСК ↓ ТАБЛИЦА ↓ ВЫВОД ``` Это должен быть повторяющийся визуальный паттерн всей презентации. --- ## Таблицы результатов Не заполнять заранее фальшивыми точными значениями времени. Использовать пустые поля: ```text 0.________ sec ``` или позволить студенту вводить своё значение. Причина: реальные результаты зависят от компьютера. --- ## Графики Использовать графики только для объяснения характера роста. Главный график: ```text O(1) O(n) O(n²) ``` Не строить графики с выдуманными benchmark-значениями. Если веб-презентация умеет принимать значения студента, можно строить график динамически по введённым результатам. --- ## Навигация Внизу каждого практического блока отображать текущий этап: ```text ПРОГНОЗ → ЗАМЕР → СРАВНЕНИЕ → ВЫВОД ``` Текущий этап подсвечивать. --- # Рекомендуемый ритм пары ## 0–10 минут Слайды 1–8. Связь Big O с реальными измерениями. Первый `perf_counter()`. --- ## 10–20 минут Слайды 9–11. Почему одному замеру нельзя верить. `measure_time()`. Правила корректного эксперимента. --- ## 20–45 минут Слайды 12–21. Практические эксперименты: `O(1)` `O(n)` `O(n²)` --- ## 45–55 минут Слайды 22–25. Почему одинаковый Big O не означает одинаковую скорость. `list` против `set`. --- ## 55–70 минут Слайды 26–32. Переход от `T(n)` к `S(n)`. `tracemalloc`. Список и генератор. --- ## 70–80 минут Слайды 33–39. Time–Space Tradeoff. Финальная задача с дубликатами. --- ## 80–90 минут Слайды 40–44. Общий алгоритм исследования. Ошибки. Итоги. Короткая самостоятельная проверка. --- # Главная педагогическая идея Не преподавать: > perf_counter → tracemalloc → набор функций. Преподавать: > У нас есть гипотеза о поведении алгоритма. Как проверить её на практике? Каждый новый инструмент появляется только тогда, когда он нужен для ответа на возникший вопрос. Главная формула всей веб-презентации: # ПРЕДСКАЖИ → ИЗМЕРЬ → ОБЪЯСНИ