Desenvolvimento de API para predição da complexidade de tempo de execução de códigos por meio de AutoML

Abstract

A análise da eficiência de um código é fundamental para a detecção de gargalos de desempenho e otimização do uso de recursos. O cálculo da complexidade do tempo de execução, referente ao período que um algoritmo leva para resolver determinado problema em função do tamanho da entrada, é um dos principais meios de medição desse parâmetro. Entretanto, de acordo com o Problema da Parada, cunhado por Martin Davis, é impossível elaborar um método geral para determinar se um programa irá parar ou executar indefinidamente. Portanto, também é impossível escrever um programa que estabeleça o tempo de execução de outro programa. Desse modo, é necessário trabalhar com aproximações para a classificação dessa complexidade. Técnicas de aprendizado de máquina vêm sendo empregadas para classificar a complexidade com base em características de código, como o número de estruturas condicionais e de loops aninhados. O banco de dados disponível para esse tipo de pesquisa é restrito, tanto em variedade quanto tamanho. Por isso, este trabalho expande o número de amostras atuais mesclando datasets de trabalhos relacionados com um dataset próprio, o Augustives. Esses bancos de dados são usados no treinamento de modelos com Autogluon, um método de aprendizado de máquina automatizado, que além de treinar uma variedade de técnicas, elabora também ensembles que as combinam em busca de maior acurácia. A partir dessa classificação, atingiu-se um máximo de 79,05% de acurácia para classe de complexidade e de 88,02% para eficiência. Por fim, o modelo que apresentou a melhor relação entre acurácia e tempo de resposta foi utilizado para a criação de uma API(Application Programming Interface) Rest, chamada RTCC, capaz receber um programa e retornar sua classe de complexidade e eficiência.

Analyzing the efficiency of a code is fundamental for detecting performance bottlenecks and optimizing the use of resources. The calculation of the runtime complexity, regarding the period taken by an algorithm to solve a given problem as a function of the input size, is one of the main ways of measuring this parameter. However, according to Martin Davis’ Halting Problem, it is impossible to develop a general method for determining whether a program will halt or run indefinitely. Therefore, it is also impossible to write a program that establishes the runtime of another program. Thus, it is necessary to work with approximations for the classification of this complexity. Machine learning techniques have been employed to classify the complexity based on code characteristics such as the number of conditional structures and nested loops. The available database for this type of research is limited, both in variety and size. Therefore, this work expands the number of current samples by merging datasets from related works with a proprietary dataset, named Augustives. These databases are used in models trained with Autogluon, an automated machine learning method that, in addition to training a variety of techniques, also constructs ensembles that combine them in search of higher accuracy. Through this classification, a maximum accuracy of 79.05% was achieved for the complexity class and 88.02% for efficiency. Finally, the model that showed the best trade-off between accuracy and response time was used to create a RESTful API (Application Programming Interface), called RTCC, capable of receiving a program and returning its complexity class and efficiency.