SysSorting ProfessionalUm Assistente de Avaliação de Estratégias de Ordenação

Michel Alves dos Santos ∗

Dezembro de 2011

ConteúdoResumo 1

1 Introdução 11.1 Números Aleatórios . . . . . . . . . . 21.2 Estratégias de Ordenação . . . . . . 2

2 O Sistema 3

3 Componentes 33.1 LibraryTime . . . . . . . . . . . . . 33.2 LibraryRandom . . . . . . . . . . . . 43.3 LibrarySorting . . . . . . . . . . . . 43.4 MyGlWindowPlot . . . . . . . . . . 43.5 Element e ElementVector . . . . . . 4

4 Resultados 5

5 Conclusões 55.1 Trabalhos Futuros . . . . . . . . . . 5

Referências 5

ResumoNeste trabalho são apresentados alguns resul-

tados da construção de um assistente de avalia-ção de estratégias de ordenação, bem como a es-trutura desse mesmo assistente. Com o decorrerdo mesmo apresentaremos os componentes notó-rios e sua estrutura. Além disso apresentaremosuma motivação para concepção do mesmo. Umbom conhecimento sobre complexidade compu-tacional, geração de números pseudo-aleatóriose distribuições de probabilidade faz-se necessáriopara uma compreeensão mais apurada do cernedo trabalho. Essas exigências são impostas facea estrutura da biblioteca de geração de númerospseudo-aleatórios implementada que é modelada

∗Bacharelando em Ciência da Computação, Univer-sidade Federal do Estado de Alagoas (UFAL). E-mail:michel.mas@gmail.com. Disciplina: Engenharia de Soft-ware II. Docente Responsável: Arturo Hernández Do-mínguez.

através de funções de distribuição de probabili-dade que por sua vez descrevem a chance queum elemento tem de assumir um valor ao longode um espaço de valores.

Figura 1: Quadro de análises fornecido pelo assis-tente. Nesse quadro são exibidas as seguintes infor-mações: número de iterações, número de compara-ções e número de inversões executadas por uma de-terminada estratégia de ordenação escolhida. Essasinformações são aferidas para as amostras em estadodesordenado (em laranja), ordenado crescentemente(em verde) e ordenado decrescentemente (em azul).

1 IntroduçãoA análise e compreensão das estratégias de

ordenação são tarefas corriqueiras no processode aprendizagem de complexidade computacio-nal. Os métodos mais clássicos são debatidos esuas respectivas complexidades teóricas são con-frontadas, porém muitas vezes, não há um apro-fundamento e muitas características relevantesde determinadas técnicas são deixadas de ladonão ocorrendo um confrontamento prático des-ses métodos.

Além disso não existe disponível, ate o mo-mento, uma ferramenta gratuita para aferiçãoda complexidade das estratégias de ordenaçãoque leve em consideração a natureza das amos-tras a serem classificadas.

Para preencher essa lacuna propomos um As-sistente de Avaliação de Estratégias de Ordena-ção que possui como principais funcionalidadesa geração de aglomerados numéricos aleatórios,

1

a execução de determinadas estratégias sobre es-ses aglomerados e a exibição do esforço compu-tacional e temporal necessários a execução.

1.1 Números AleatóriosAs funções de retorno de números aleatórios

da maioria das linguagens não são adequadas.Por exemplo, a função rand() da linguagemC++ é uma Pseudo Random Number Generatormedíocre, pois usa o método de congruência li-near (Linear Congruential Generator ou LCG).O período de geração de sequências numéricas

para plataformas que utilizam LCG é da ordemde m = 232 ou m = 264 (onde m indica o pe-ríodo de geração em base de potências de 2). Aglibc por exemplo, usada pelo GCC (GNU Com-piler Collection1), possui uma periodicidade dem = 232 enquanto a biblioteca MMIX (criadapara processadores RISC de 64 bits por DonaldKnuth) possui uma periodicidade de m = 264.Para uma melhor geração de números aleató-

rios usamos outros métodos tais como o R250 eo Mersenne Twister. O R250 foi proposto por

Gerador PeriodicidadeLCG [glibc - gcc] 232

LCG [MMIX by Donald Knuth] 264

R250 2250 − 1

Mersenne Twister 219937 − 1

Tabela 1: Para testar os limites teóricos das es-tratégias de ordenação e verificar a robustez dasmesmas, os números empregados devem possuirnatureza e origem ‘aleatórias’. Na corrente ta-bela são exibidos alguns geradores de númerospseudo-aleatórios e seus respectivos períodos degeração.

(Kirkpatrick & Stoll, 1981) em 1981. Ele per-mite períodos muito longos de geração de nú-meros aleatórios sem que o ciclo de repetiçõesse reinicie, o que é uma característica muito de-sejada em simulações que trabalham com umgrande número de chamadas ao Gerador de Nú-meros Pseudo-Aleatórios(GNPA), tal como assimulações Monte Carlo. Além disso, possuiuma boa performance, permitindo que simula-ções sejam realizadas em tempo real. O períodode geração do R250 é de quase m = 2250 − 1.R250 é conhecido como um Registrador de Res-

1Conjunto de compiladores de linguagens de progra-mação produzido pelo projeto GNU.

posta de Deslocamento Generalizado ou GFSR(Generalized Feedback Shift Register).O Mersenne Twister é um gerador de núme-

ros aleatórios relativamente novo proposto em1997 por (Matsumoto & Nishimura, 1998). OMersenne Twister é um GFSR com compri-mento de 624 e deslocamento de 397 semelhanteem espírito ao R250. Possui um surpreendenteperíodo de 219937 − 1. O cerne do método sebaseia em recorrência matricial linear sobre umcorpo binário F2, provendo uma geração rápidae de alta qualidade de números aleatórios.

Outros métodos de geração de números alea-tórios baseados em distribuição numérica tam-bém foram utilizados como o Box-Muller (distri-buição polar) o método da distribuição de Pois-son, entre outros (ver figura 2).

Figura 2: Distribuições disponibilizadas pelo com-ponente LibraryRandom. Os métodos de Congruên-cia Linear, R250 e Mersenne Twister são baseadasna distribuição uniforme.

1.2 Estratégias de OrdenaçãoOrdenação é o ato de se colocar os elemen-

tos de uma sequência de informações, ou dados,em uma ordem predefinida. O termo técnicoem inglês para ordenação é sorting, cuja tra-dução literal é ‘classificação’. Algumas ordenssão facilmente definidas. Por exemplo, a ordemnumérica, ou a ordem alfabética (crescentes oudecrescentes). Contudo, existem ordens, espe-cialmente de dados compostos, que podem sernão triviais de se estabelecer. Um algoritmo queordena um conjunto ou sequência de elementos(geralmente representado por um vetor), é cha-mado de um algoritmo de ordenação ou estra-tégia de ordenação. Entre os mais importantes,podemos citar o bubble sort (ou ordenação por

2

flutuação), heap sort (ou ordenação por amonto-amento), insertion sort (ou ordenação por inser-ção), merge sort (ou ordenação por intercalação)e o quicksort (ou ordenação rápida).Existem várias razões para se ordenar uma

sequência. Uma delas é a possibilidade se aces-sar seus dados de modo mais eficiente.Algoritmos de ordenação estam entre os mais

importantes da Ciência da Computação. A im-portância desses algoritmos está relacionada àaplicação dos mesmos em diferentes tipos deproblemas. Por isso, determinar o uso ade-quado dos algoritmos de ordenação é fundamen-tal. Para isso faz-se necessário o estudo de suascomplexidades de tempo para aferir qual a me-lhor estratégia para determinadas instâncias deum problema. Sendo complexidade do tempo deum problema o número de passos que se tomapara resolver uma instância de um problema, apartir do tamanho da entrada utilizando o algo-ritmo mais eficiente à disposição.Intuitivamente, caso se tome uma instância

com entrada de longitude n que pode resolver-se em n2 passos, se diz que esse problema temuma complexidade em tempo de O(n2). Supos-tamente, o número exato de passos depende damáquina em que se programa, da linguagem uti-lizada e de outros fatores. Para não ter que falardo custo exato de um cálculo se utiliza a no-tacão assimptótica. Quando um problema temcusto dado em tempo O(n2) em uma configura-ção de computador e linguagem, este custo seráo mesmo em todos os computadores, de maneiraque esta notação generaliza a noção de custo in-dependentemente do equipamento utilizado.O assistente de ordenação proposto utiliza-se

de um componente que agrega várias estratégiasde ordenação de várias ordens de complexidade,indo desde algoritmos quadráticos como o bubblee o insertion até algoritmos log-lineares como omerge (figura 3).

2 O SistemaA ferramenta foi concebida para verificar o

número de instruções executadas em aglome-rados numéricos desordenados, ordenados cres-centemente e decrescentemente, além do tempoconsumido nessas operações. A ferramenta pos-sui as seguintes funcionalidades: Geração deaglomerado numérico aleatório; Escolha da dis-tribuição para geração do aglomerado numérico;Escolha da estratégia de ordenação. Mais infor-

Figura 3: Algoritmos de ordenação disponibiliza-dos pelo componente LibrarySorting. Esses algorit-mos foram implementados e avaliados confrontandosuas respectivas complexidades teóricas e suas apli-cações práticas.

mações estruturais a respeito das classes compo-nentes e diagramação da interface gráfica podemser adquiridas no final deste trabalho.

3 ComponentesLogo a seguir serão apresentados alguns com-

ponentes notórios do sistema. Tratam-se detrechos de código intercambiáveis que possuemcomo objetivo atender a problemas de amplo es-copo e corriqueiramente recorrentes. Uma defi-nição com um caráter mais teorético seria a se-guinte: ‘componente de software é o termo utili-zado para descrever o elemento de software queencapsula uma série de funcionalidades.’

Um componente é uma unidade indepen-dente, que pode ser utilizado com outros compo-nentes para formar um sistema mais complexo.Em programação orientada a objetos um com-ponente é a classe que implementa uma interfacee é autônomo em relação a outros componen-tes do sistema. Um sistema de software podeser formado inteiramente somente por compo-nentes, pois estes se interligam através de suasinterfaces. Este processo de comunicação entrecomponentes é denominado composição.

3.1 LibraryTimeO componente LibraryTime foi construído

com o intuito de encapsular chamadas de baixonível ao sistema de medição de tempo nativo.O componente possui uma interface simples epode ser utilizado em qualquer solução de soft-ware que requeira uma métrica para estimar acomplexidade temporal de determinada tarefa.

3

Podemos visualizar um diagrama estrutural docomponente através da figura 4.

Figura 4: Diagrama de classe do componente Li-braryTime e suas respectivas operações. A estruturaclock_t que realiza essa composição é proveniente dabiblioteca ctime.

Em nosso assistente o componente foi uti-lizado para executar aferições sobre o esforçocomputacional necessário para realização de de-terminadas tarefas. As respectivas complexida-des teóricas foram confrontadas levando em con-sideração o tempo necessário para sua execuçãocompleta e o tempo consumido (figura 5).

Figura 5: Aplicação do componente. Tempos ob-tidos através da geração pseudo-aleatória e aplica-ção do algoritmo shell sort em aglomerado numéricocom cardinalidade igual a 100000.

3.2 LibraryRandomO componente LibraryRandom foi construído

com o intuito de encapsular métodos para a ob-tenção de números pseudo-aleatórios. A inter-face desse componente é moderadamente sim-ples mas requer do desenvolvedor conhecimentoprévio sobre distribuições de probabilidade paraum aproveitamento mais apurado. O diagramapode ser visualizado através da figura 8

3.3 LibrarySortingO componente LibrarySorting foi construído

com o intuito de encapsular métodos de orde-nação das mais variadas ordens de complexi-dade afim de se obter um embate através de seucomportamento no que tange o esforço compu-tacional necessário para execução dos mesmos.O componente é facilmente extensível e sua in-terface relativamente simples. Para elaboração

desse componente utilizamos o padrão strategy.Através da figura 10 podemos visualizar o dia-grama estrutural do mesmo.

3.4 MyGlWindowPlotO componente MyGlWindowPlot foi cons-

truído com o intuito de se obter um controle ouwidget que fosse capaz de desenhar pontos emuma área de desenho fornecida pela bibliotecaOpenGL. O componente foi desenvolvido atravésda extensão da classe de emulação de uma janelaOpenGL através da biblioteca FLTK. As chama-das internas são construídas através de puro có-digo OpenGL fazendo com que as mesmas pos-sam ser facilmente portadas para qualquer outraplataforma de construção de interfaces gráficas(e.g. gtk, QT, .NET). Através da figura 9 pode-mos visualizar o componente em ação.

3.5 Element e ElementVectorOs componentes Element e ElementVector

constituem as classes do domínio do problemaque são intercambiáveis entre os demais comp-nentes. Element constitui uma classe para ar-mazenamento das caracteristicas de um deter-minado elemento que será foco das operações dosistema. ElementVector comporta-se como umalista, porém diferente dos demais conteiners con-vencionais implementa operações de verificaçãode minimalidade, maximalidade e ordenação. Aclassificação dos elementos através de ordenaçãointerna necessita de um predicado de ordenaçãodevido as características internas dos gabaritos(ou templates) da linguagem adotada.

Figura 6: Diagrama de classe dos componentes Ele-ment e ElementVector e suas respectivas operações.

4

ClassificaçãoAlgoritmo TempoBubble 166.785sGnome 158.188sShaker 143.156sComb 142.328sInsertion 81.765sSelection 68.204sShell 1.281sHeap 1.235sQuick 1.234sMerge 1.375s

Tabela 2: Quadro de ranqueamento das estra-tégias de ordenação. Os tempos foram obtidosatravés da aplicação dos respectivos algoritmosem aglomerados numéricos aleatórios com car-dinalidade igual a 100000.

4 ResultadosA seguir serão apresentados resultados obti-

dos através da concepção da ferramenta (tabela2 e figura 7). Todos os testes foram executadossobre aglomerados numéricos com cardinalidadeigual a 105. Os resultados exibidos referem-se amédia de tempo de 15 execuções consecutivas decada estratégia levando em consideração a amos-tra desordenada, ordenada de maneira crescentee ordenada de maneira decrescente, ou seja:

Ttotal =

m∑i=1

(td + toc + tod)

m(1)

Onde td é o tempo necessário para execuçãodo método sobre a amostra desordenada, toc otempo para execução sobre a amostra ordenadade forma crescente, tod o tempo para execuçãosobre a amostra ordenada de forma descrescentee Ttotal a média de tempos após m execuções.

5 ConclusõesAtravés da concepção do assistente pudemos

analisar tanto de maneira teórica quanto prá-tica o desempenho das estratégias de ordenaçãomais clássicas. Dentre várias observações salien-tamos que algoritmos de ordenação quadráticospossuem baixa complexidade de implementaçãoporém pecam no quesito desempenho, enquantoalgoritmos de ordenação do tipo ‘dividir-para-conquistar’ são as melhores opções, porém de-vemos estar atentos aos casos degenerativos.

Bubble Gnome Shaker Comb Insertion Selection Shell Heap Quick Merge

050

100

150

Algoritmos

BubbleGnomeShakerCombInsertionSelectionShellHeapQuickMerge

Figura 7: Gráfico em barras relativo ao ranquea-mento das estratégias de ordenação. É notória apercepção de que algoritmos quadráticos de or-denação podem possuir baixa complexidade deimplementação porém pecam no quesito desem-penho.

5.1 Trabalhos FuturosComo possíveis extensões da ferramenta po-

demos destacar a implementação de ordenaçãomulti-thread com o uso do paralelismo, a in-serção de gráficos de desempenho acumulativo,a execução de processos distribuídos através deum middleware e a transformação das estraté-gias de ordenação em plugins.

ReferênciasBooch, G., J., R. & Jacobson, I. (2006), UML: Guia

do Usuário, Vol. 1, 2 ed., Editora Campus.

Kirkpatrick, S. & Stoll, E. (1981), ‘A very fastshift-register sequence random number genera-tor’, Journal of Computational Physics 40, 517–526.

Larman, C. (2000), Utilizando UML e padrões: Umaintrodução à análise e ao projeto orientados a ob-jetos, 1 ed., Bookman.

Matsumoto, M. & Nishimura, T. (1998), ‘Mer-senne twister: A 623-dimensionally equidistribu-ted uniform pseudorandom number generator’,ACM Transactions on Modeling and ComputerSimulation 8, 3–30.

Sommerville, I. (2007), Engenharia de Software, 8ed., Pearson Addison Wesley.

5

Figura 8: Diagrama de classe do componente LibraryRandom e suas respectivas operações. Observe queas estratégias para obtenção de números pseudo-aleatórios estam aglomeradas dentro de um namespace.

Figura 9: O OpenGL (Open Graphics Library) é uma API livre utilizada na computação gráfica, paradesenvolvimento de aplicativos gráficos, ambientes 3D, jogos, entre outros. O OpenGL é um conjunto dealgumas centenas de funções, que fornecem acesso a praticamente todos os recursos do hardware de vídeo.Internamente, ele age como uma máquina de estados, que de maneira bem específica dizem ao OpenGL oque fazer. O OpenGL fornece um conjunto poderoso de comandos, mas restrito apenas ao desenho. Váriasbibliotecas existem para facilitar a manipulação de outros aspectos da aplicação, como GLU e GLUT.

6

Figura 10: Diagrama de classe do componente LibrarySorting e suas respectivas operações. Observeque as estratégias estam disponibilizadas utilizando o padrão strategy. A classe AbstractSorting abriga adeclaração de todos os métodos responsáveis pela aferição do esforço computacional de um determinadométodo. Entre os métodos quadráticos implementados estam o bubble, o gnome, o shaker, o comb, o inser-tion e o selection. Dentre os não-quadráticos estam o shell, o heap, o quick e o merge. Outras estratégiaspodem ser implementadas, tais como: Cocktail sort, Odd–even sort, Stooge sort, Bogosort, Smoothsort,Cartesian tree sort, Tournament sort, Cycle sort, Tree sort, Library sort, Patience sorting, Polyphasemerge sort, Strand sort, American flag sort, Bead sort, Bucket sort, Burstsort, Counting sort, Pigeonholesort, Proxmap sort, Radix sort, Flashsort, Bitonic sorter, Batcher odd–even mergesort, Pairwise sortingnetwork, Timsort, Introsort, Spreadsort, UnShuffle sort, JSort, Spaghetti sort, Topological sorting e oPancake sorting.

Figura 11: Fluxograma de interação com o sistema. Através desse fluxograma podemos notar que ainteração com o mesmo é a mais simples possível, exigindo do utilizador apenas alguns passos mínimos.

7

Figura 12: Diagrama de arquitetura em camadas do sistema. A camada de visão é fornecida através douso do kit de construção de interfaces gráficas FLTK. Com esse kit construímos os objetos MyApplication eMyGlWindowPlot. Na camada de controle encontram-se os objetos do domínio (Element e ElementVector)e os serviços (LibraryTime, LibraryUtils, LibraryRandom e LibrarySorting) e finalmente na camada demodelo se encontra o repositório de definição de amostras (arquivos .rnd).

Figura 13: Principais botões da interface gráfica do usuário. Da esquerda para direita temos: o comandode geração de amostras, o comando de execução do método de ordenação, uma lista de escolha do mé-todo, uma lista de escolha de distribuições e finalmente uma lista de escolha para as ordens de avaliação(aleatória, crescente e decrescente).

Figura 14: Seção timeline onde são exibidos os tempos necessários para execução de uma determinadaestratégia de ordenação sobre aglomerado numérico desordenado, ordenado crescentemente e ordenadodecrescentemente. Ao final são exibidos o tempo de geração da amostra e o tempo total de ordenaçãopara as três ordens anteriormente citadas.

8

Figura 15: Seções Listas de Elementos, Limites Numéricos, Rótulos, Métodos Executados e Gráfico deTempo. Na seção Listas de Elementos são apresentadas as listas de elementos desordenados e ordenados.Na seção Limites Numéricos o usuário tem a possibilidade de estabelecer os limites numéricos de geraçãodos aglomerados. Na seção Rótulos são exibidos os significados das cores empregadas para identificar oselementos de aferição. Na seção Métodos Executados são exibidos os métodos de geração dos aglomeradosnuméricos e a estratégia de ordenação escolhida. Em Gráfico de Tempo são exibidos os tempos gastospara execução do método de ordenação para as três ordens.

Figura 16: Menus cortina disponibilizados pela aplicação. Da esquerda para a direita: Arquivos, Ações,Ferramentas e Ajuda. Através desses widgets o usuário pode ter acesso a outras funcionalidades do sistema.

Figura 17: Uma visão geral da aplicação. A corrente figura exibe de maneira integral o assitente proposto,que possui como principal intuito verificar o número de instruções executadas em aglomerados numéricosdesordenados, ordenados crescentemente e decrescentemente, além do tempo consumido nessas operações.

9