Оптимизации программного кода PYTHON методами теории графов

Аннотация

В данной научно-исследовательской работе представлен алгоритм, позволяющий автоматизировано проводить анализ кода на языке программирования PYTHON, на предмет нарушения основной парадигмы программирования – «недопустимость дублирования кода».

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

Полный текст

Введение

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

На текущий момент существует множество парадигм, обеспечивающих написание «чистого кода», в рамках данной статьи будет рассмотрен метод, позволяющий анализировать программный код на предмет нарушение одной, основной парадигмы, игнорирование которой присуще как новичкам, так и большим коллективам – «недопустимость дублирования кода».

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

Цель работы

Разработка метода, повышающего качество кода создаваемых программных средств.

Задачи работы

• Сформулировать самую часто нарушаемую парадигму проектирования кода;

• Ввести определение графовой модели кода;

• Определить переход правил написания кода к полученным графовым моделям;

• Реализовать алгоритм определения нарушения парадигмы [1].

Основная нарушаемая парадигма проектирования кода на Python

Недопустимость дублирующего кода

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

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

Графовая модель кода

Односвязный, ориентированный, граф G=(V,E), где V – конечное множество синтаксических конструкций данных и языка, E – конечное множество раскрашенных рёбер.

У рёбер существуют приоритеты, список которых приводится ниже в порядке убывания:

• вызов функций – оранжевый;

• цикличные действия – синий;

• действия по выполнению условия – зелёный, по невыполнению условия – красный;

• переход от команды к команде в порядке очерёдности – серый.

Определение перехода правил написания кода к полученным графовым моделям

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

Пример:

Рисунок 1. Код, реализующий поиск минимума из списка «list_1», максимума из «list_2» и вывод получившихся результатов на экран

Рисунок 2. Графовая модель,

построенная кода с рис. 1

Множество вершин (рис. 2), обозначенных одним цветом, представляют собой фрагмент. В данном случае явно наблюдаются повторы похожих конструкций для «зелёного» и «жёлтого» фрагментов. Выделяем два последовательных фрагмента кода (рис. 3).

Рисунок 3. Обобщение графовой модели с рис. 2

Для устранения повторяющегося кода вводим функцию «Function» (рис. 4). Здесь она вызывается дважды разными параметрами, при том, что определяется лишь единожды.

Рисунок 4. Предложение по оптимизации кода с рис. 1

Предлагаемый алгоритм

Для наглядности сразу приведём пример работы алгоритма.

1. Исходный граф представить в виде графовой модели

Рассмотрим для упрощения всё тот-же код с (рис. 3) и соответствующую ему графовую модель с (рис. 2).

2. Используя поиск [2 с. 10], находим схожие вершины и составляем новый граф:

1. В качестве исходной вершины выбираем исток;

2. Ищем непомеченные вершины, с которыми исходная будет иметь допустимое значение схожести;

3. При нахождении такой вершины, помечаем её, и переносим в новый граф, причём копируются так же рёбра (корме серых), ведущие к данной вершине из уже присутствующих в новом графе вершин;

4. Делаем очередную вершину исходной, согласно алгоритму обхода графа в глубину;

5. Повторяем шаги (b-d) до завершения обхода;

Рисунок 5. Новый граф, получившийся после выполнения шага II

3. В новом графе проводим анализ на предмет логической связности компонент:

1. Находим компоненту, содержащую наименьшее количество вершин;

2. Перебором осуществляем поиск схожей морфемы (например, имени используемой переменной), со всеми остальными не закрытыми компонентами, здесь имеем 3 случая:

1) если совпадений не найдено, то пометить ее как закрытую;

2) одно совпадение – присоединить эту компоненту к той, в которой найдено совпадение;

3) несколько совпадений – присоединить ко всем, в которых было найдено совпадение.

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

3. Повторяем шаги (а-b) до тех пор, пока не получим граф с множеством закрытых компонент.

Рисунок 6. Новый граф, получившийся после установления в нём логических связей в шаге III

4. С помощью поиска максимального общего подграфа между всевозможными компонентами, описанный в [3, c. 5], либо с помощью модифицированного алгоритма Хансера [4, c.10] получаем финальные подграфы;

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

В частном случае, они оказались самими компонентами.

Рисунок 7. Результат шага IV, наблюдаем 2 подграфа, что говорит нам о наличии дублирующего кода

Достоинства алгоритма

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

Выводы

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