Оптимизации программного кода 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).

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

 

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

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

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

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

 

 

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

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

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

Выводы

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

×

Об авторах

Александр Владимирович Петров

Самарский Национальный Исследовательский Университет

Автор, ответственный за переписку.
Email: alexpetrovpr@gmail.com
ORCID iD: 0000-0001-5933-3780
Россия

Наталья Леонидовна Додонова

Email: ndodonova@bk.ru
Россия

Список литературы

  1. Бураков В.В. Моделирование и идентификация дефектов объектно-ориентированного программного кода, изв. вузов. приборостроение. 2014. Т. 57, № 11.
  2. Ullmann J. R. An algorithm for subgraph isomorphism. J. ACM, 1976.
  3. Погребной А.В. Выделение общей части в версиях исходного кода программ, представленного графовой моделью, доклады ТУСУР, 2018, том 21, № 3.
  4. Савельев А.С. Алгоритмы поиска максимальной общей подструктуры набора молекул, 2007.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML

© Вестник молодых учёных и специалистов Самарского университета, 2022

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution-ShareAlike 4.0 International License.

Вестник молодых учёных и специалистов Самарского университета

Сетевое издание, журнал

ISSN 2782-2982 (Online)

Учредитель и издатель сетевого издания, журнала: федеральное государственное автономное образовательное учреждение высшего образования «Самарский национальный исследовательский университет имени академика С.П. Королева» (Самарский университет), Московское шоссе, 34, 443086,  Самарская область, г. Самара, Российская Федерация.

Сетевое издание зарегистрировано Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций, регистрационный номер ЭЛ № ФС 77-86495 от 29.12.2023

Выписка из реестра зарегистрированных СМИ

Устав сетевого издания

Главный редактор: Андрей Брониславович Прокофьев, доктор технических наук, доцент, заведующий кафедрой теории двигателей летательных аппаратов

2 выпуска в год

0+. Цена свободная. 

Адрес редакции: 443011, Самарская область, г. Самара, ул. Академика Павлова, д. 1, Совет молодых учёных и специалистов, каб. 513 корпуса 22 а.

Адрес для корреспонденции: 443086, Самарская область, г. Самара, Московское шоссе, 34, Самарский национальный исследовательский университет (Самарский университет), 22а корпус, каб. 513.

Тел: (846) 334-54-43

e-mail: smuissu@ssau.ru

Доменное имя: VMUIS.RU (справка о принадлежности домена)электронный адрес в сети Интернет:  https://vmuis.ru/smus.

Прежнее свидетельство – периодическое печатное издание, журнал «Вестник молодых учёных и специалистов Самарского университета», зарегистрировано Управлением Федеральной службы по надзору в сфере связи, информационных технологий и массовых коммуникаций по Самарской области, регистрационный номер серии ПИ № ТУ63-00921 от 27 декабря 2017 г.

© Самарский университет

 

Данный сайт использует cookie-файлы

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

О куки-файлах