Методические указания к лр3

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

Цель работы

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

Задачи лабораторной работы

1.               Провести ручное профилирование ключевых функций системы

2.               Использовать профайлер для сбора детальной статистики выполнения

3.               Определить функцию с наибольшим временем выполнения

4.               Выполнить очистку и предобработку собранных данных измерений

5.               Определить вычислительную сложность проблемного алгоритма

6.               Предложить способ оптимизации

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

8.               Провести повторное профилирование оптимизированной системы

9.               Сравнить результаты "до" и "после" оптимизации

10.            Подготовить очищенный набор данных для лабораторной работы №4

Этап 1. Сбор данных профилирования

1.1. Ручное профилирование

Запустите систему из лабораторной работы №2 для трёх объёмов данных:

N₁ = 100 записей

N₂ = 1000 записей

N₃ = 10000 записей

Для каждой операции (минимум 3 операции) выполните минимум 5 замеров. Зафиксируйте результаты в таблицу:

Таблица 1. Сырые данные ручного профилирования

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

1.2. Инструментальное профилирование

Обратите особое внимание на:

-                 Функции с наибольшим совокупным временем выполнения

-                 Функции с наибольшим количеством вызовов

-                 Цепочки вызовов, ведущие к проблемам

Запустите профайлер (cProfile для Python, Visual Studio Profiler для C# и т.д.) и сохраните результаты в файл:

-                 Для Python: python -m cProfile -o profile_results.prof main.py

-                 Для C#: использовать Diagnostic Tools с экспортом результатов

-                 Для Java: экспорт из VisualVM в CSV

Сохраните следующие метрики для каждой функции:

-                 Общее время выполнения (cumulative time)

-                 Количество вызовов

-                 Среднее время на один вызов

Этап 2. Первичная обработка данных (подготовка к ЛР4)

2.1. Обнаружение и классификация пропусков

Проанализируйте собранные данные на наличие пропущенных значений:

2.2. Обработка выбросов

Выбросы в данных производительности возникают из-за:

-                 Работы сборщика мусора

-                 Фоновых процессов операционной системы

-                 Прогревных эффектов (первый запуск после холодного старта)

-                 Кэширования данных (аномально быстрые замеры)

Для обнаружения выбросов используйте метод межквартильного размаха (IQR)*:

Межквартильный размах (Interquartile Range, IQR) — это мера разброса данных, определяемая как разница между третьим (Q3) и первым (Q1) квартилями распределения. Фактически IQR охватывает центральные 50% данных, отсекая 25% нижних и 25% верхних значений




1.     Для каждого набора замеров (фиксированная операция + фиксированный размер данных) вычислите:

Q1 (первый квартиль) — 25-й процентиль

Q3 (третий квартиль) — 75-й процентиль

IQR = Q3 - Q1

2.     Определите границы нормальных значений:

Нижняя граница = Q1 - 1.5 * IQR

Верхняя граница = Q3 + 1.5 * IQR

3.     Значения за пределами этих границ считаются выбросами и подлежат обработке.

Таблица 2. Анализ выбросов

2.3. Стратегия обработки выбросов

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

Рекомендации по обработке выбросов

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

Задачи: Определить аномалии и скорректировать их.

Алгоритм использования:

-                 Обнаружение:

-                 Визуальные методы: Ящик с усами, гистограммы.

-                 Статистические методы:

-                 Метод межквартильного размаха: Выбросами считаются значения, выходящие за пределы [Q1 - 1.5 * IQR, Q3 + 1.5 * IQR].

-                 Метод Z-отклонения: Выбросами считаются значения, чей модуль Z-оценки больше 3 (при нормальном распределении).

Обработка:

Удаление (если выбросы — результат ошибки).

Замена на граничные значения.

Замена на среднее или медиану.

Рекомендуемые инструменты Python:

2.4. Обработка дубликатов (при наличии)

Цель: Исключить искажение результатов анализа за счет повторяющихся записей.

Задачи: Найти и удалить полностью дублирующиеся строки или строки, дублирующиеся по ключевым полям.

Алгоритм использования:

Поиск: Выявление дубликатов во всем наборе данных или по заданным столбцам.

Анализ: Просмотр найденных дубликатов для принятия решения.

Удаление: Удаление всех повторяющихся записей, кроме первого или последнего вхождения.

2.5. Агрегация данных

После очистки выбросов вычислите для каждой операции и каждого объёма данных:

-                 Среднее время (среднее арифметическое очищенных замеров)

-                 Медиану (устойчивая к выбросам метрика)

-                 Стандартное отклонение (разброс значений)

-                 Доверительный интервал (для оценки точности)

Таблица 3. Агрегированные данные после очистки

Этап 3. Анализ алгоритмической сложности

3.1. Определение проблемной функции

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

-                 Наибольшее общее время выполнения

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

3.2. Определение вычислительной сложности

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

Вычислите коэффициенты роста:

-                 При увеличении данных с 100 до 1000 (в 10 раз):
Коэффициент роста времени = T(1000) / T(100) = 50.0 / 5.75 ≈ 8.7

-                 При увеличении данных с 1000 до 10000 (в 10 раз):
Коэффициент роста времени = T(10000) / T(1000) = 507.5 / 50.0 ≈ 10.15

 

 

Интерпретация коэффициентов:

3.3. Построение графика сложности

Постройте график зависимости T(n) на логарифмической шкале. Наклон линии укажет на степень сложности.

Пример построения графика сложности

Возьмём данные для проблемной функции "Поиск по автору" после очистки от выбросов:

 

Строим обычный график по этим данным графика в обычном масштабе

Построение графика в логарифмической шкале

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

Шаг 1. Вычисление логарифмов

Возьмём десятичные логарифмы (log₁₀) или натуральные (ln). Для примера используем log₁₀.

Шаг 2. Построение графика в логарифмической шкале

Строим график:

-                 По оси X — log₁₀(N)

-                 По оси Y — log₁₀(T)

Шаг 3. Выводим линейный тренд

Интерпретируем коэффициент при х

 

Этап 4. Диагностика и исправление проблем и подготовка данных для оптимизации

4.1. Анализ причин медленной работы

На основе кода из ЛР2 и результатов профилирования определите причину:

4.2. Оптимизация и повторное профилирование

Варианты оптимизации

На основе выявленной сложности предложите способ оптимизации:

Выполнить повторно все шаги этапов 2 и 3

4.3. Подготовка данных для ЛР4

Сформируйте итоговый набор данных, который будет использоваться в лабораторной работе №3:

Пример

dataset_performance.csv

------------------------------------------------

timestamp,operation,data_size,raw_time,cleaned_time,is_outlier,cpu_usage,memory_usage

2023-10-01 10:00:05,search,100,5,5,False,12.3,45.2

2023-10-01 10:00:06,search,100,6,6,False,12.5,45.3

2023-10-01 10:00:07,search,100,22,7,True,45.8,67.1

 

Признаки:

-                 timestamp — время замера

-                 operation — название операции

-                 data_size — объём данных

-                 raw_time — сырое время замера

-                 cleaned_time — время после очистки (или NaN для удалённых)

-                 is_outlier — флаг выброса (True/False)

-                 cpu_usage — загрузка CPU во время замера (если измеряли)

-                 memory_usage — использование памяти