аккаунты пользователей (donk666, AnnaVyy, tmttmt) donk666-student1 AnnaVyy-student2 tmttmt-student3 Я donk666 был student2 у AnnaVyy

📚 Документация: Анализатор производительности алгоритмов 📋 Содержание Обзор проекта

Архитектура системы

Структура репозитория

Подробное описание классов

Алгоритмы реализации

Инструкция по запуску

Тестирование и валидация

🎯 Обзор проекта Цель проекта Создание инструмента для сравнительного анализа производительности алгоритмов поиска и сортировки на целочисленных массивах.

Основные возможности ✅ Реализация 5 базовых алгоритмов

✅ Измерение времени выполнения с точностью до миллисекунды

✅ Подсчет операций сравнения

✅ Поддержка массивов от 100 до 100,000 элементов

✅ Генерация случайных и отсортированных данных

✅ Сравнительный анализ алгоритмов

✅ Консольный интерфейс с меню

Технические характеристики Язык: C# (.NET)

Платформа: Кроссплатформенный (Windows/Linux/macOS)

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

Лицензия: MIT

🏗️ Архитектура системы Диаграмма классов text ┌─────────────────────────────────────────────────────────────┐ │ Algorithm (abstract) │ ├─────────────────────────────────────────────────────────────┤ │ + Comparisons: int │ │ + ElapsedMs: long │ │ + Name: string (abstract) │ │ + Execute(): void │ │ # RunAlgorithm(): void (abstract) │ │ # Compare(a, b): int │ └──────────┬──────────────────────────────────────────────────┘ │ ├──────────────────────────────────────────────────┐ │ Search Algorithms │ ├──────────────────────────────────────────────────┤ │ ┌────────────────┐ ┌──────────────────────────┐ │ │ │ LinearSearch │ │ BinarySearch │ │ │ │ - array: int[] │ │ - array: int[] │ │ │ │ - target: int │ │ - target: int │ │ │ │ + ResultIndex │ │ + ResultIndex │ │ │ └────────────────┘ │ - IsSorted(): bool │ │ │ └──────────────────────────┘ │ │
└──────────────────────────────────────────────────┐ Sorting Algorithms │ ┌──────────────────────────────────────────────────┤ │ ┌────────────────┐ ┌────────────────┐ ┌────────┐ │ │ │ BubbleSort │ │ QuickSort │ │MergeSort│ │ │ │ - sorted: int[]│ │ - sorted: int[]│ │-sorted │ │ │ │ │ │ - Sort(): void │ │-Merge() │ │ │ │ │ │ - Partition() │ │-MergeSort│ │ │ └────────────────┘ └────────────────┘ └────────┘ │ └──────────────────────────────────────────────────┘ Принципы проектирования Принцип единственной ответственности - каждый класс делает одну вещь

Открытость/закрытость - алгоритмы расширяемы через наследование

Наследование и полиморфизм - единый интерфейс для всех алгоритмов

Инкапсуляция - детали реализации скрыты

📁 Структура репозитория text AlgorithmPerformanceAnalyzer/ ├── 📁 src/ # Исходный код │ └── AlgorithmAnalyzer.csproj # Файл проекта │ └── Program.cs # Основной файл с полной реализацией │ ├── 📁 docs/ # Документация │ └── SPECIFICATION.md # Техническая спецификация │ └── API_REFERENCE.md # Справочник по API │ └── ALGORITHMS.md # Описание алгоритмов │ ├── 📁 tests/ # Тесты │ ├── UnitTests/ │ │ └── AlgorithmTests.cs # Модульные тесты │ └── PerformanceTests/ │ └── BenchmarkTests.cs # Тесты производительности │ ├── 📁 examples/ # Примеры использования │ ├── BasicUsage.cs # Базовые примеры │ ├── AdvancedComparison.cs # Продвинутое сравнение │ └── CustomAlgorithms.cs # Пример добавления алгоритмов │ ├── 📁 scripts/ # Вспомогательные скрипты │ ├── build.sh # Скрипт сборки │ ├── run_tests.sh # Скрипт запуска тестов │ └── benchmark.py # Скрипт для анализа результатов │ ├── 📁 results/ # Результаты тестирования │ ├── sample_output.txt # Пример вывода программы │ └── performance_data.csv # CSV с результатами │ ├── 📁 config/ # Конфигурационные файлы │ └── appsettings.json # Настройки приложения │ ├── README.md # Основная документация ├── LICENSE # Лицензия MIT ├── .gitignore # Git ignore файл └── CHANGELOG.md # История изменений 📖 Подробное описание классов

Базовый класс Algorithm csharp public abstract class Algorithm { // Свойства для измерения производительности public int Comparisons { get; protected set; } // Количество сравнений public long ElapsedMs { get; protected set; } // Время выполнения в мс public abstract string Name { get; } // Название алгоритма

// Методы измерения времени protected Stopwatch sw = new Stopwatch(); protected void StartTimer() => sw.Restart(); protected void StopTimer() { sw.Stop(); ElapsedMs = sw.ElapsedMilliseconds; }

// Основной метод выполнения public void Execute() { Comparisons = 0; // Сброс счетчика StartTimer(); // Начало измерения RunAlgorithm(); // Выполнение алгоритма StopTimer(); // Конец измерения }

// Абстрактный метод для реализации алгоритма protected abstract void RunAlgorithm();

// Метод для подсчета сравнений protected int Compare(int a, int b) { Comparisons++; // Инкремент счетчика return a.CompareTo(b); // Стандартное сравнение } }
Класс LinearSearch csharp public class LinearSearch : Algorithm { private readonly int[] array; // Массив для поиска private readonly int target; // Искомое значение public int ResultIndex { get; private set; } = -1; // Результат поиска

public override string Name => "Линейный поиск";

// Алгоритм: O(n) в худшем случае // Проходит по массиву последовательно // Подходит для любых массивов protected override void RunAlgorithm() { for (int i = 0; i < array.Length; i++) { if (Compare(array[i], target) == 0) { ResultIndex = i; // Найден элемент return; } } // Если элемент не найден, ResultIndex остаётся -1 } }
Класс BinarySearch csharp public class BinarySearch : Algorithm { // Особенности: // - Работает ТОЛЬКО с отсортированными массивами // - Использует принцип "разделяй и властвуй" // - Время выполнения: O(log n)

private static bool IsSorted(int[] arr) { for (int i = 1; i < arr.Length; i++) if (arr[i] < arr[i - 1]) return false; return true; }

protected override void RunAlgorithm() { int left = 0, right = array.Length - 1;
```
 while (left <= right)
 {
     // Находим средний элемент
     int mid = left + (right - left) / 2;
     int cmp = Compare(array[mid], target);
     
     if (cmp == 0) { ResultIndex = mid; return; }
     if (cmp < 0) left = mid + 1;   // Искомое справа
     else right = mid - 1;          // Искомое слева
 }
```
} }
Класс BubbleSort csharp public class BubbleSort : Sorter { // Алгоритм: // 1. Проходит по массиву // 2. Сравнивает соседние элементы // 3. Меняет местами если нужно // 4. Повторяет пока есть обмены

// Оптимизация: флаг swapped // Если за проход не было обменов - массив отсортирован // Сложность: O(n²) в худшем случае // Память: O(1) - сортировка на месте

protected override void RunAlgorithm() { bool swapped;
```
 for (int i = 0; i < sorted.Length - 1; i++)
 {
     swapped = false;
     for (int j = 0; j < sorted.Length - i - 1; j++)
     {
         if (Compare(sorted[j], sorted[j + 1]) > 0)
         {
             // Обмен элементов
             int temp = sorted[j];
             sorted[j] = sorted[j + 1];
             sorted[j + 1] = temp;
             swapped = true;
         }
     }
     if (!swapped) break;  // Массив отсортирован
 }
```
} }
Класс QuickSort csharp public class QuickSort : Sorter { // Алгоритм Тони Хоара: // 1. Выбираем опорный элемент (pivot) // 2. Разделяем массив на две части // 3. Рекурсивно сортируем части // 4. Объединяем результаты

// Особенности реализации: // - Используется последний элемент как pivot // - In-place сортировка // - Рекурсивная реализация // - Средняя сложность: O(n log n)

private int Partition(int low, int high) { int pivot = sorted[high]; // Опорный элемент int i = low - 1; // Индекс меньшего элемента
```
 for (int j = low; j < high; j++)
 {
     if (Compare(sorted[j], pivot) <= 0)
     {
         i++;
         // Обмен элементов
         int temp = sorted[i];
         sorted[i] = sorted[j];
         sorted[j] = temp;
     }
 }
 
 // Помещаем pivot на правильное место
 int temp2 = sorted[i + 1];
 sorted[i + 1] = sorted[high];
 sorted[high] = temp2;
 
 return i + 1;
```
} }
Класс MergeSort csharp public class MergeSort : Sorter { // Алгоритм Джона фон Неймана: // 1. Делим массив пополам // 2. Рекурсивно сортируем половины // 3. Объединяем отсортированные половины

// Особенности: // - Стабильная сортировка // - Время выполнения: O(n log n) // - Требует дополнительной памяти O(n) // - Хорошо подходит для связных списков

private int[] Merge(int[] left, int[] right) { int[] result = new int[left.Length + right.Length]; int i = 0, j = 0, k = 0;
```
 // Слияние двух отсортированных массивов
 while (i < left.Length && j < right.Length)
 {
     result[k++] = Compare(left[i], right[j]) <= 0 
         ? left[i++] 
         : right[j++];
 }
 
 // Добавляем оставшиеся элементы
 while (i < left.Length) result[k++] = left[i++];
 while (j < right.Length) result[k++] = right[j++];
 
 return result;
```
} } 🔧 Алгоритмы реализации Генерация данных csharp static int[] GenerateArray(int size, bool sorted) { int[] arr = new int[size];

if (sorted) { // Отсортированный массив: 0, 1, 2, ..., size-1 for (int i = 0; i < size; i++) arr[i] = i; } else { // Случайный массив: значения от 0 до 2*size for (int i = 0; i < size; i++) arr[i] = rnd.Next(size * 2); }

return arr; } Измерение производительности csharp // Подход: // 1. Сброс счетчиков // 2. Запуск таймера высокой точности // 3. Выполнение алгоритма // 4. Остановка таймера // 5. Запись результатов

// Используется System.Diagnostics.Stopwatch // Точность: 100 наносекунд (0.0001 мс) // Не зависит от системных часов Обработка ошибок csharp // Проверка размера массива if (size < 100 || size > 100000) throw new ArgumentException("Размер должен быть 100-100000");

// Проверка для бинарного поиска if (!IsSorted(array)) throw new InvalidOperationException("Массив должен быть отсортирован");

// Проверка на null if (array == null) throw new ArgumentNullException(nameof(array)); 🚀 Инструкция по запуску Требования .NET SDK 6.0 или выше

Windows/Linux/macOS

500 МБ свободной памяти

Процессор с поддержкой 64-бит

Сборка и запуск bash

Клонирование репозитория

git clone https://github.com/yourusername/AlgorithmAnalyzer.git cd AlgorithmAnalyzer

Сборка проекта

dotnet build

Запуск приложения

dotnet run

Альтернатива: компиляция в exe

dotnet publish -c Release -r win-x64 --self-contained ./bin/Release/net6.0/win-x64/AlgorithmAnalyzer.exe Пример использования text

Запустите программу
Выберите тип теста:
- 1: Тестирование поиска
- 2: Тестирование сортировки
- 3: Сравнение всех алгоритмов
Введите размер массива (100-100000)
Выберите тип данных (случайные/отсортированные)
Наблюдайте результаты Пример вывода text Алгоритм | Время(мс) | Сравнения | Эффективность

Линейный поиск | 1.23 | 50,000 | Хорошая Бинарный поиск | 0.02 | 16 | Отличная Пузырьковая | 452.67 | 49,995,000 | Низкая Быстрая | 2.34 | 142,567 | Отличная Слиянием | 3.12 | 120,456 | Отличная 🧪 Тестирование и валидация Тестовые сценарии Сценарий Входные данные Ожидаемый результат Маленький массив size=100 Все алгоритмы < 10 мс Средний массив size=10,000 Видна разница в производительности Большой массив size=100,000 QuickSort/MergeSort < 1 сек Отсортированные данные sorted=true BinarySearch работает Граничные значения size=100, 100000 Корректная обработка Валидация результатов Корректность сортировки: проверка отсортированности массива

Корректность поиска: проверка найденного индекса

Счетчик сравнений: сравнение с теоретическими значениями

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

Метрики качества кода Покрытие тестами: > 90%

Сложность кода: Cyclomatic Complexity < 10

Соблюдение стандартов: C# Coding Conventions

Обработка ошибок: Graceful degradation

📊 Анализ сложности алгоритмов Теоретическая сложность Алгоритм Лучший случай Средний случай Худший случай Память LinearSearch O(1) O(n) O(n) O(1) BinarySearch O(1) O(log n) O(log n) O(1) BubbleSort O(n) O(n²) O(n²) O(1) QuickSort O(n log n) O(n log n) O(n²) O(log n) MergeSort O(n log n) O(n log n) O(n log n) O(n) Практические рекомендации До 1,000 элементов: любой алгоритм подходит

1,000-10,000 элементов: избегать BubbleSort

10,000-100,000 элементов: использовать QuickSort/MergeSort

Поиск в отсортированных данных: всегда BinarySearch

Стабильность важна: использовать MergeSort

🔮 Возможности расширения Планируемые улучшения Добавление новых алгоритмов:

HeapSort

InsertionSort

SelectionSort

TimSort

Визуализация:

Графики времени выполнения

Анимация работы алгоритмов

Интерактивная демонстрация

Экспорт данных:

CSV/JSON форматы

PDF отчеты

Интеграция с Excel

Веб-интерфейс:

REST API

Веб-приложение

Мобильное приложение

Как добавить новый алгоритм csharp public class NewAlgorithm : Algorithm { public override string Name => "Новый алгоритм";

protected override void RunAlgorithm()
{
    // Реализация алгоритма
    // Используйте Compare() для подсчета сравнений
}

}

// Использование: var algo = new NewAlgorithm(array); algo.Execute(); Console.WriteLine($"Время: {algo.ElapsedMs} мс");

team-work-it-donk666

Описание

Языки

donk666
Запрос на слияние 'feature' (#2) из feature в master
4 месяца назад
5a76cf0

Клонирование репозитория

Сборка проекта

Запуск приложения

Альтернатива: компиляция в exe

team-work-it-donk666

Описание

Языки

donk666Запрос на слияние 'feature' (#2) из feature в master 4 месяца назад5a76cf0

Клонирование репозитория

Сборка проекта

Запуск приложения

Альтернатива: компиляция в exe

donk666
Запрос на слияние 'feature' (#2) из feature в master
4 месяца назад
5a76cf0