Optimization of software code PYTHON methods of graph theory

Cover Page

Cite item

Full Text

Abstract

This research paper presents a method that allows automated code analysis in the PYTHON programming language, for violations of the basic programming paradigm – "the inadmissibility of code duplication.

Full Text

Введение

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

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

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

Цель работы

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

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

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

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

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

  • Реализовать алгоритм определения нарушения парадигмы [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 подграфа, что говорит нам о наличии дублирующего кода

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

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

Выводы

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

×

About the authors

Alexander Petrov

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

Author for correspondence.
Email: alexpetrovpr@gmail.com
ORCID iD: 0000-0001-5933-3780
Russian Federation

Natalia Leonidovna Dodonova

Email: ndodonova@bk.ru
Russian Federation

References

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

Supplementary files

Supplementary Files
Action
1. JATS XML

Copyright (c) 2022 Proceedings of young scientists and specialists of the Samara University

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Proceedings of young scientists and specialists of the Samara University

ISSN 2782-2982 (Online)

Publisher and founder of the online media, journal: Samara National Research University, 34, Moskovskoye shosse, Samara, 443086, Russian Federation.

The online media is registered by the Federal Service for Supervision of Communications, Information Technology and Mass Communications, registration number EL No. FS 77-86495 dated December 29, 2023

Extract from the register of registered media

Regulation of the online media

Editor-in-chief: Andrey B. Prokof'yev, Doctor of Science (Engineering), associate professor,
head of the Department of Aircraft Engine Theory

2 issues a year

0+. Free price. 

Editorial address: building 22a, room 513, Soviet of Young Scientists and Specialists, 1, Academician Pavlov Street, Samara, 443011, Russian Federation.

Address for correspondence: room 513, building 22a, 34, Moskovskoye shosse, Samara, 443086, Russian Federation.

Tel.: (846) 334-54-43

e-mail: smuissu@ssau.ru

Domain name: VMUIS.RU (Domain ownership certificate), Internet email address: https://vmuis.ru/smus.

The previous certificate is a printed media, the journal “Bulletin of Young Scientists and Specialists of Samara University”, registered by the Office of the Federal Service for Supervision of Communications, Information Technologies and Mass Communications in the Samara Region, registration number series PI No. TU63-00921 dated December 27, 2017.

© Samara University

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies