Система статистического анализа сложностей алгоритмов на C#

Клиент и задача

Теоретические оценки сложности алгоритмов бывают неприменимы на практике, если они опираются на латентные свойства объектов: численные характеристики, которые становятся доступными только после построения искомого объекта. В такой ситуации представляется перспективным один из вариантов эмпирического подхода — проведение вычислительных экспериментов и построение на основе обработки их результатов абсолютных и относительных статистических оценок времени исполнения конкурирующих алгоритмов. Для научного проекта лаборатории СПИИРАН требовалось создать инструмент, позволяющий проводить эмпирические оценки алгоритмов построения алгебраических байесовских сетей.

Технологии и решения

Для проведения статистических экспериментов, был создан комплекс программ и юнит-тестов на C#: генератор данных для экспериментов и анализатор результатов экспериментов. Численные результаты записывались в выходной файл и визуализировались.

Результаты

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

Скриншоты

Визуализация отношений скоростей работы алгоритмов
Визуализация отношений скоростей работы алгоритмов
Визуализация отношений скоростей работы алгоритмов
Визуализация отношений скоростей работы алгоритмов
Визуализация отношений скоростей работы алгоритмов
Визуализация отношений скоростей работы алгоритмов
Визуализация распределения
Визуализация распределения
Визуализация гистограммы
Визуализация гистограммы
Визуализация в виде двумерного графика
Визуализация в виде двумерного графика
Визуализация в виде двумерного графика с врезкой
Визуализация в виде двумерного графика с врезкой
Визуализация в виде двумерного графика с врезкой
Визуализация в виде двумерного графика с врезкой