Pesquisa sobre Ordenação e Técnicas de Armazenamento: Introdução e Desafios

PESQUISA ORDENACAO E TECNICAS DE ARMAZENAMENTO UNIDADE 1 CONCEITUACAO DE PESQUISA ORDENACAO E ARMAZENAMENTO Luiz Ricardo Mantovani da Silva 15082023 2024 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 237 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento ee Introducgao g O volume de dados sempre foi um desafio na area de desenvolvimento de software De um lado os requisitos de usuarios exigem que as operades sejam mais detalhadas mais dados sejam coletados e armazenados e que mais analises sejam realizadas sobre esses dados Por outro lado os dispositivos vem sendo reduzidos Quais tecnologias poderiam descrever este cenario Celulares e tablets sao exemplos claros de que o processamento de dados precisara ser profundamente estudado pois embora sua capacidade seja grande se comparada com equipamentos do passado esses dispositivos ndo possuem a mesma capacidade que os computadores atuais E quando a situado exige desempenho e discrepancia Para enriquecer ainda mais o cenario 0 uso de dispositivos vestiveis smart watches e dispositivos embarcados é frequente e requer que os desenvolvedores de sistemas sejam habeis na solucdo de problemas de ocupaao de espaco e velocidade de processamento Como fazer quando o equipamento viabiliza apenas a utilizacdo de poucos recursos computacionais Considere por exemplo o sistema de controle de deslocamento de uma bicicleta ou patinete compartilhados Nao ha condigées de se embarcar um dispositivo com grande capacidade de processamento mas mesmo assim é necessario liberar e bloquear o veiculo apontar via geoposicionamento onde esta registrar o deslocamento saber que 0 usuario esta liberado saber que 0 veiculo esta bloqueado Sado inimeras operacées a serem executadas na bicicleta ou no patinete mas com recursos computacionais bastante limitados Se porém levarmos em conta somente os computadores convencionais PCs e notebooks mesmo com mais recursos 0 volume de dados processado é cada vez maior Portanto o desenvolvedor do software precisa estar atento as melhores técnicas para armazenamento busca e ordenaao de dados sendo capaz de aplicalas para a construcdo de funcionalidades altamente eficientes Vamos 1a 11 Conceitos sobre Pesquisa Ordenagao e Formas de Armazenamento das Informacoes Pesquisar dados é de forma geral uma busca por uma chave dentro de uma estrutura de armazenamento Essa estrutura por sua vez precisa estar minimamente organizada ordenada portanto para garantir a eficiéncia da busca O primeiro assunto a tratarmos é a pesquisa ou busca propriamente dita imagine a seguinte situacado queremos encontrar um amigo dentro de uma festa para facilitar a sua localizacao é interessante que conhecamos os habitos dele Certo E isto que acontece com os dados quando tentamos localizdlo em meio a milhées de informacées A tarefa pode ficar dificil e custosa do ponto de vista do processamento no entanto se aplicarmos métodos para localizar os dados que queremos poderemos encontralos em um tempo menor e com uma carga de processamento reduzida Esta é a tarefa dos algoritimos de busca muito utilizados no mundo da programacao PUGA RISSETTI 2004 A ordenacao dos dados é outra importante questdo que iremos tratar ordenar significa mudar a posiao dos elementos de uma lista colocandoos em uma determinada ordem Desta maneira os dados ordenados sao mais faceis de se localizar por exemplo a pesquisa em uma base de dados ordenada é muito mais rapida Os algoritmos para ordenacao de dados s4o as ferramentas utilizadas para organizar as informades o melhor método a ser utilizado depende muito do problema apresentado devendo ser adequado da melhor forma possivel De todos os métodos disponiveis 0 da bolha é considerado 0 modelo de ordenaado mais simples que existe porém pode ser utilizado em certos tipos de dados httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 337 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento A busca e ordenacdo dos dados esta intimamente ligado ao desempenho computacional mas outra relevante questdo sendo a mais importante é o armazenamento dos dados 111 Armazenamento de dados Armazenar dados reter os dados no computador de forma que sejam utilizados em processos mediante sua recuperacao e uso Ha duas formais gerais para armazenamento de dados Armazenamento interno que trata de manter os dados dentro das instancias do programa que esta sendo executado memoria ou armazenamento externo que trata de gravar os dados em objetos externos ao programa sendo executado como arquivos em disco ou bancos de dados e Armazenamento interno O armazenamento interno consiste em manter os dados na memoria do programa que esta em execucdo Assim cada instrucdo do programa pode acessar tais dados e processalos de acordo com a légica necessaria A estrutura mais elementar para armazenamento de dados é uma variavel de memoria que consiste em um espaco de memoria reservado para receber um determinado dado recebe um nome para referéncia 0 qual sera utilizado para processala MANZANO OLIVEIRA 2016 No entanto ha situagdes em que as variaveis sdo insuficientes Por exemplo um programa que recebe trés valores e os imprime ordenados poderia ser assim escrito AB sim nao BC BC sim nao sim nao a bc AC AC cba sim nao sim nao ac b c ab b a c bc a Figura 1 Fluxograma para ordenar trés variaveis Fonte Elaborada pelo autor 2019 PraCegoVer A Figura mostra uma um fluxograma que parte de 3 variaveis denominadas abc Em seguida é avaliado se A é superior a B Caso sim é avaliado se B é superior a C Caso sim temse a ordenagao de abc Caso nao é avaliado se A é superior a C Em caso afirmativo temse a ordenacdo acb Em caso negativo tem se a ordenacao cab Retomando o inicio do fluxograma se A nao for superior a B é feita avaliacdo se B é httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 437 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento superior a C Caso nado temse a ordenaao cba Caso sim avaliase se A é superior a C Caso sim temse a ordenacao bac Caso ndo temse a ordenaao bca Perceba que seis possiveis resultados seriam escritos no programa em questado ou melhor trés resultados No entanto no caso de o programa precisar ordenar 12 valores seriam escritos 12 resultados diferentes Ou seja 479001600 resultados Além disso seria dificil programar com dez nomes diferentes de variaveis pois teriamos que implementar grande quantidade de estruturas condicionais para verificar os valores SOUZA et al 2011 Precisamos de uma forma mais eficiente de tratar dados em conjunto Para isso existem os vetores que sao variaveis indexadas e permitem armazenar mais de um dado em uma estrutura Vetores variaveis indexadas unidimesionais Ao observar um prédio podese ver os andares referenciados por seus numeros primeiro andar segundo andar e assim sucessivamente Dentro de cada andar também encontramos salas que por sua vez também podem ser nomeadas por ntmeros sala um sala dois sala trés etc Esse é 0 conceito de variavel indexada unidimensional temse um conjunto de elementos do mesmo tipo que sao organizados conforme um sé nome no caso do nosso exemplo os andares ou salas e que sdo acessados por um numero indice 1 2 3 4 Indice do vetor Andares Andar Andar Andar Andar 1 2 3 4 Indice do vetor Salas Sala Sala Sala Sala Figura 2 Representacdo dos vetores prédio e andar Fonte Elaborada pelo autor 2019 PraCegoVer A Figura mostra dois vetores denominados Andares e Salas No caso de Andares ha quatro posiées indicando Andar 1 Andar 2 Andar 3 e Andar 4 em que os algarismos estado indicados como indice de vetores No caso de Salas também sdo apresentadas quatro categorias indicando Sala 1 Sala 2 Sala 3 e Sala 4 sendo que os algarismos também estado indicados como indices de vetores Se variarmos o nimero poderemos acessar a cada uma das salas dentro do vetor Salas como no algoritmo 1 Paraide 1 até 4 passo 1 faca escreva Salasi Fimpara Algoritmo 1 fragmento algoritmo um lao de repetiao para navegar no vetor Salas Por convencao as variaveis indexadas unidimensionais sao chamadas de vetores e podem ser de qualquer tipo de dados valido como textos ou inteiros Sua implementacao se da em Portugol da seguinte maneira Inteiro vetorn10 Criacao de um vetor de 10 inteiros vetorn 102030405060708090100 Atribuir 10 valores para o vetor Algoritmo 2 fragmento implementaao de um vetor de inteiros com 10 elementos httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 537 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento Afirmase que o vetorn é unidimensional por que possui uma sequencia de elementos alinhadas entre si no mesmo nivel assim para acessar qualquer dos elementos basta invocar o vetorn a partir de um indice valido Por exemplo Escreva vetorn3 Resultado 30 Algoritmo 3 fragmento acesso ao 3 elemento do vetorn Assim um vetor é capaz de armazenar blocos de dados mas com a restrido de que tais dados serdo sempre do mesmo tipo Um vetor de strings nao podera conter valores inteiros por exemplo ener eeeeeeee rere ener ener eee eee eee eee VOCE SABIA e Iterar significa navegar em uma estrutura de dados Para vetores por exemplo se trata de criar um lago de repeticdo que nos permita capturar cada elemento vi onde i é 0 indice sendo iterado A estrutura é constituida basicamente de um vetor vi onde v representa a variavel e o i a variavel indice do vetor que por exemplo é incrementada pelo laco de repeticao assim toda vez que o trecho do algoritmo dentro do laco é executado o valor de i é alterado e o vi recebe um novo valor ex v0 v1 v2 v3 ener eeeeeeee rere ener ener eee eee eee eee Os vetores sao estruturas de dados que servem para economia de cédigo ou seja uma forma de se atribuir a uma unica variavel diversos valores simplesmente utilizando um indice durante um processo de iterac6es Esta estrutura é muito utilizada em programacdo de computadores contribuindo para reducdo de cédigo e aumento de eficiéncia httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 637 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento De VAMOS PRATICAR Implemente um programa que receba 10 valores em um vetor de inteir isso exiba a soma desses valores a média o menor valor informado e valor informado Resolucao Pseudocddigo Var Comando que indica onde as variaveis serdo declaradas Valores vetor 110 de reais Declaragado da variavel Valores do tipo 10 posiées Soma Media real Declaracdo das variaveis Soma e Media do tipo real i maior menor inteiro Declarado das variaveis i maior e menor inteiro Inicio Comando que indica onde comecam as instrug6es Soma 0 Variavel recebendo valor inicial Para i 0 até 9 faca Inicio do laco de repetiao Ler Valoresi Comando para leitura de valores digitados no teclado Soma Soma Valoresi Variavel Soma recebendo o valor da c aritmética Se Valoresimenor Entaéo Estrutura condicional que reali comparacao verificando se a variavel Valoresi é que a variavel menor menor Valoresi Caso a condicdo seja verdadeira variavel recebendo o valor da variavel Valores i Fim Se Fim da estrutura condicional Se ValoresiJmaior Entao Estrutura condicional que reali comparacao verificando se a variavel Valoresi é que a variavel maior maior Valoresi Caso a condicdo seja verdadeira variavel maior re o valor da variavel Valores i Fim Se Fim da estrutura condicional Fim Para Fim da estrutura de repeticao Media Soma10 Variavel Media recebendo o resultado dé resultado de Soma 10 Mostrar O valor da média é Media Comando que exibe 0 valor da Média Mostrar O valor da soma é Soma Comando que exibe o valor da Soma Mostrar O maior valor é maior Comando que exibe o mai informado Mostrar O menor valor é menor Comando que exibe 0 men informado Fim Fim do programa httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 7137 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento eee e rere rere ee ee eee eee ee Matrizes vetores bidimensionais E possivel armazenar os dados em estruturas bidimensionais com linhas e colunas na forma de uma tabela de dados Essas estruturas sao na verdade vetores mas com uma dimensdo adicional Essas estruturas também sao chamadas de matrizes Matrizm Colunas 12 3 4 1 99 35 32 44 2 31 45 15 38 3 54 11 33 67 Figura 3 Representacdo de uma matriz Fonte Elaborada pelo autor 2019 PraCegoVer A Figura mostra uma matriz com 4 colunas e 3 linhas Na linha 1 constam os nimeros 99 coluna 1 25 coluna 2 32 coluna 3 e 44 coluna 4 Na linha 2 constam os nimeros 31 coluna 1 45 coluna 2 15 coluna 3 e 38 coluna 4 Na linha 3 constam os numeros 54 coluna 1 11 coluna 2 33 coluna 3 e 67 coluna 4 Assim como nos vetores unidimensionais 0 acesso aos elementos se dara mediante indices mas no caso a partir da coordenada linha coluna Por exemplo Escrever MatrizM23 Imprimir 0 contetido do elemento linha 2 coluna 3 Resultado 15 Algoritmo 4 fragmento acesso a um determinado elemento da Matrizm Para interagir em uma matriz implementamse dois contadores uma para as linhas e outro para as colunas mediante lacos aninhados um lao dentro do outro Por exemplo inteiro Matrizm34 bloco para carregar dados na matriz Para linha de 1 até 3 passo 1 facga Para coluna de 1 até 4 passo 1 facga Escrever Matrizmlinhacoluna Imprime o valor de cada célula Fimpara Fimpara Algoritmo 4 fragmento acesso aos elementos de uma matriz com lacos aninhados httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTPEORTE19unidade1ebookindexhtml 837 15082023 2024 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 937 De forma geral os vetores tem funcionalidade similar a tabelas armazenado os dados em linhas e colunas e permitindo sua leitura mediante coordenadas os ındices dos elementos Por isso durante suas pesquisas voce encontrara autores que se referirao a vetores como tabelas uma analogia adequada Em memoria os vetores sao representados de forma similar as variaveis mas cuja referencia esta indexada e aponta para mais de um espaço de memoria PraCegoVer A Figura mostra uma matriz de 1 coluna e 4 linhas para representar uma porçao de memoria denominada Memoria em que e indicada alocaçao da variavel A na segunda linha Ao lado direito dessa imagem e ilustrada uma outra matriz de 1 coluna e 5 linhas sendo que e indicada alocaçao de um vetor V abrangendo as linhas 23 e 4 Hash Table Uma tabela Hash Hashtable e uma estrutura que permite a rapida recuperaçao de dados indiferentemente do volume de dados armazenados nela Por essa razao tabelas hash sao amplamente utilizadas em ındices de banco de dados compiladores e sistemas de registro log de erros Diferente dos vetores e matrizes a tabela hash armazena dados organizandoos em pares de chavevalor keyvalue Em cada elemento podese armazenar por exemplo o nome de uma pessoa e seu numero de telefone essas estruturas sao chamadas entradas entries GOOGDRICH TAMASSIA 2013 Figura 4 Esquema de locaçao de memoria em variaveis e vetores Fonte Elaborada pelo autor baseada em SOUZA et al 2011 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento ee VOCE QUER VER e Vocé tem duvidas sobre vetores e matrizes e como sao utilizados na computaao No video do Grupo de Estudos de Educado a Distancia do Centro Paula Souza vocé podera aprender mais sobre estas estruturas de dados de uma forma didatica e com exemplos praticos Assista a este video clicando aqui httpswwwyoutubecomwatch v7i3YfiLy1vElistLLecA4jNMub1jeYn7rRegAindex2 t0s httpswwwyoutubecomwatch v7i3Yfily1vElistLLecA4jNMub1jeYn7rRegAindex2 t0s Se consideramos um vetor ilustrado na figura a seguir para localizar um determinado dado Ana podese utilizar uma estratégia de forca bruta percorrendo cada um dos elementos até que se encontre o elemento com a informacdo desejada Quanto maior o vetor mais tempo sera necessario para localizar o dado Texto nomes11 Jane Tim MiaSam Leo Ted Bea Lou Ana Max Zoe Para i de 0 até 10 passo 1 facga se nomesi Ana entao escreve i fimpara fimse Fimpara Algoritmo 5 fragmento buscar por Ana no vetor nomes mediante fora bruta httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 1037 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento 1 Bea Tim Leo Sam Mia Ted Jane Lou Max Ada Zoe 2 Bea Tim Leo Sam Mia Ted Jane Lou Max Ada Zoe ees 3 Bea Tim Leo Sam Mia Ted Jane Lou Max Ada Zoe 9 interagdes até encontrar o dado desejado Figura 5 Busca utilizando forga bruta Fonte Elaborada pelo autor 2019 PraCegoVer A Figura ilustra 3 linhas Em cada uma das 3 linhas aparecem 11 campos descritos como Bea Tim Leo Sam Mia Ted Jane Lou Max Ada Zoe Na linha 1 0 campo Bea esta destacado Na linha 3 o campo Tim esta destacado Na linha 3 0 campo Ada esta destacado Porém se o indice do elemento fosse previamente conhecido acessariamos diretamente o elemento sem percorrer os demais 1 Localizar Ana 2 Ana8 3 meuDado nomes8 Figura 6 Esquema ldgica para localizar dados dentro de uma tabela hash Fonte Elaborada pelo autor 2019 PraCegoVer A Figura mostra 3 comandos O Comando 1 indica a instruao Localizar Ana Em seguida ha uma seta partindo da instrucdo 1 para a instrudo 2 que indica Ana8 Na linha abaixo temse a instrudo 3 que indica meuDadonomes8 Funcao hash Ocorre que em uma tabela hash o indice dos dados é determinado mediante um calculo com os dados O que significa dizer que o indice do elemento esta relacionado com os dados armazenados Esse procedimento de determinacao do indice relativo a chave é executado por uma fungao hash hk Assim podese determinar o indice do elemento antes de realizar sua busca Para o termo Ana saberiamos de antem4o em qual elemento esta e ndo seria necessario percorrer toda a estrutura de dados para localizalo A determinacao do indice de acordo com os dados ocorre no momento de popular a tabela conforme figura a httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 1137 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento seguir Por exemplo Dado Mia Passo 1 Somar os valores do cédigo Ascii de cada caractere M77 i105 a97 Soma 279 Passo 2 Obter o resto da divisdo da soma pelo numero de elementos 27911 25 resto 4 Passo 3 Armazenar Mia no elemento 4 O mesmo ocorreria com Tim 29811 27 resto 1 0 1 2 3 4 5 6 T 8 9 10 Tim Mia Figura 7 O dado é inserido da tabela hash de acordo com um calculo Fonte Elaborada pelo autor 2019 PraCegoVer A Figura mostra uma tabela com 11 campos em 1 linha numerados acima de 0 a 10 Os campos 1 e 4 foram preenchidos com os nomes Tim e Mia respectivamente De VOCE O CONHECE e Donald Knuth nascido 10 de janeiro de 1938 nos Estados Unidos é cientista da computacdo e professor da Universidade de Stanford E considerado um dos criadores da analise de algoritmos precursor da programacao literaria desenvolveu o conceito de numero surreal dentre outros trabalhos que muito contribufram para o desenvolvimento da computado Para saber mais leia o livro The Art of Computer Programming KNUTH 1973 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 1237 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento Para a busca de um valor realizase 0 mesmo calculo o que determinara 0 elemento onde tal dado esta Bastando entdo recuperar o dado Por exemplo localizar Ada na tabela hash T Dado Ada 262 Mod 11 9 meuDado T9 O elemento 9 contem Ada Algoritmo 6 fragmento buscar por Ada na tabela hash T Colisdes De acordo com Googdrich e Tamassia 2013 Pode acontecer de diferentes chaves gerarem 0 mesmo indice Ada mod 11 9 Acb mod 11 9 Esse fendmeno é chamado colisdo e as tabelas hash os tratam de duas maneiras Arranjo em buckets ou Enderegamento aberto Arranjo em buckets O Arranjo em buckets é uma estrutura na qual cada célula da tabela hash é um contéiner para varios pares chavevalor Assim quando uma chave for entrada e 0 elemento do respectivo indice estiver ocupado o contéiner recebera esse novo par kv adicinandoo a uma lista de pares ilustrada pela figura a seguir 0 1 2 3 4 5 6 T 8 9 10 CN ECN CN LYN CYA CY CY oY CY oD OO 3C a 6 A 1 C 3 F 6 B 7 Q 3 Z Figura 8 Arranjo de buckets e entradas que geraram colis6es Fonte Elaborado pelo autor 2019 PraCegoVer A Figura mostra uma tabela com 1 linha e 11 campos numerados acima de 0 a 10 A partir de cada campo ha setas direcionadas para baixo apontando para buckets No bucket posicionado em 1 é indicado 1C No bucket posicionado em 3 é indicado 3C 3F e 3Z No bucket posicionado em 6 é indicado 6 A 6 B eno bucket posiciondo em 7 é indicado 7 Q Enderecamento aberto No enderecamento aberto ao encontrar um elemento que ja esteja ocupado a funao hash avana para o proximo elemento até localizar um espaco vago para a os dados A estratégia mais simples para enderecamento aberto é o teste linear Ao tentar inserir um item kv em uma posido Ai que esta ocupada onde i hk tentase de novo em Ai1 mod N Se essa posido também estiver ocupada tentase Ai2 mod N e assim sucessivamente até que se encontre um espaco vago como ilustrado na figura a seguir httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 1337 15082023 2024 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 1437 PraCegoVer a Figura mostra uma tabela com 1 linha e 7 campos numerados acima de 0 a 6 Nos campos 023 e 4 estao indicadas as letras XAV e T respectivamente Ha uma seta apontada para o campo 2 indicando novo elemento kB a ser inserido Ha tres setas do campo 2 para o 3 do campo 3 para o 5 e do campo 4 para 5 indicadas abaixo com a instruçao testar 3 vezes ate encontrar uma posiçao vazia No caso do endereçamento aberto a funçao de pesquisa que localiza o item a partir de sua chave tambem sera ligeiramente diferente Devese percorrer posiçoes consecutivas iniciando em Ahk ate encontrar o item com chave k ou um elemento vazio Figura 9 Inserçao em tabela hash com teste linear Fonte Elaborada pelo autor baseada em GOODRICH TAMASSIA 2013 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento wm Classe e métode para contar palavras com Uso de Hashtable af import javautil HashMap public class contadorpalavras public HashMapStrinag Integer contardString texto HashMapString Integer mapa new HashMapString Integer we A tabela hash tem uma String como chave um inteiro como valor Assim Cada palavra encontrada no texto tera uma entrada na tabela hash Eo seu valor representara a contagem de vezes que aparece no texto nf for String palavra i texto splitd ifmapagetpal avradlsnul1 A palavra foi encontrada na tabela hash Mapa putpalavra mapagetipalavradids fAdiciona 1 ao valor que acompanha palavra else Mapaputpalavra iM inserir 4 palavra pela primeira vez na tabela 3 return mapas bd wm Para testar o método que usa hash table Contar palavras wf import javautilMapEntrys public class testecontarpalavras public static void maintringZ args contadorpalavras cp new contadorpalavrast String texto a tabela hash armazena a palavra na forma de entrada A fugao hash determina o indice is ford Entrustring Integer entrada cpcontartextoentruset SustemoutprintindentradagetKey s entradagetValue Figura 10 Exemplo de implementaaAo Java para tabela hash PraCegoVer A figura mostra um trecho de cédigo de 44 linhas de programa Enumerando cada linha temos Linhat Linha 2 Classe e método para contar palavras Linha 3 com uso de Hashtable Linha 4 Linha 5 import javautil HashMap Linha 6 public class contadospalavras Linha 7 public HashMapStringInteger contar String texto Linha 8 HashMapString Integer mapa new HashMapString Integer httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 1537 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento Linha 9 Linha 10 A tabela hash tem uma String como chave e um inteiro como valor Linha 11 Assim cada palavra encontrada no texto tera uma entrada na tabela hash Linha 12 Eo seu valor representara a contagem de vezes que aparece no texto Linha 13 Linha 14 for String palavra textosplit Linha 15 ifmapagetpalavranull Linha 16 A palavra foi encontrada na tabela hash Linha 17 mapaputpalavramapagetpalavra1 Adiciona 1 ao valor que acompanha palavra Linha 18 Linha 19 else Linha 20 mapaputpalavra1inserir a palavra pela primeira vez na tabela Linha 21 Linha 22 Linha 23 return mapa Linha 24 Linha 25 Linha 26 Linha 27 Linha 28 Linha 29 Linha 30 Para testar o método que usa hash table Linha 31 Contar palavras Linha 32 Linha 33 import javautilMapEntry Linha 34 Linha 35 public class testecontarpalavras Linha 36 Linha 37 public static void mainStringargs Linha 38 contadorpalavras cpnew Contadorpalavras Linha 39 String texto a tabela hash armazena a palavra na forma de entrada A fundo hash determina o indice i Linha 40 for EntryString Integer entradacpcontartextoentrySet Linha 41 SystemoutprintInentradagetKey entradagetValue Linha 42 Linha 43 Linha 44 Armazenamento externo O volume de dados disponiveis cresce rapidamente e é um desafio permanente para o desenvolvimento de plataformas de software A variedade de aplicativos cada vez mais intensivos em dados incluindo bancos de dados simuladores calculos cientificos computacdo grafica multimidia sensores mensagens instantaneas e correio eletrénico s4o exemplos de situac6es em que o volume de dados sempre é alto Por exemplo 0 Google Earth tém varios Terabytes 1000 Gigabytes de tamanho O data warehouse de vendas da WalMart contém mais de meio Petabyte 500 Terabytes de dados O desafio aqui colocado esta em desenvolver algoritmos para processar esses dados ou entdo grande parte deles sera inutil Os computadores de uso geral organizam a memoria em diferentes niveis passando de meméorias internas de nivel mais baixo até a meméria externa de nivel mais alto ilustrado pela figura a seguir httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 1637 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento Armazenamento externo DO I l I l i Disco I rye 4 I magnetico I HD a I I ie I I Registradores Go 5S fs CPU 28 ge N 5a I E Memem a I l 1 estado I solido SSD I l I l Figura 11 Niveis da meméria em um computador convencional Fonte Elaborada pelo autor 2019 PraCegoVer A Figura mostra os itens Registradores CPU L2 Cache Memoria principal DRAM e um ultimo item chamado Armazenamento externo que contempla 2 campos Disco magnético HD e Mem Em estado s6lido SSD Entre cada um dos itens ha setas duplas A CPU Central Processing Unit Unidade Central de Processamento é considerada 0 coracado do computador é formada por unidade de controle unidade ldgica e Aritmética e pelos registradores ou seja memorias de alta velocidade que funcionam basicamente junto ao processador Um pouco mais distante do procesador temos a memoria cache que é mais lenta que os registradores porém muito mais rapida que a memoria RAM A memoria cache é utilizada para armazenar os dados mais utilizados pelo procesador em relagdo 4 memoria RAM como forma de ganho de desempenho A préxima memoria mais distante do processador é a memoria RAM sendo mais lenta que a memoria cache serve para armazenar os dados durante a execudo dos programas Em outras palavras todas estas memorias sao utilizadas pelo processador porém em grau de importancia temos primeiramente os registradores as memorias cache e a memoria RAM E importante sabermos que todas estas memorias sao consideradas internas primarias e volateis ou seja conservam as informag6es apenas enquanto o sistema estiver energizado e apresentam baixa capacidade de armazenamento Diferente a elas temos as memorias externas ou memorias secundarias também chamadas de memérias de massa capazes de armazenar grande quantidade de informac6es possuindo baixa velocidade de acesso temos como exemplo destas os discos magnéticos HDs e memorias em estado sdlido SSD httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTPEORTE19unidade1ebookindexhtml 1737 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento a CASO No mundo moderno o termo algoritmo vem se tornando natural para a maioria das pessoas sendo de extrema importancia para que os computadores realizem de forma adequada suas tarefas mas qual o melhor algoritmo Como classificalos Os algoritmos apresentam grau de importdancia relativa estando associados ao problema para o qual sao criados por exemplo os algoritmos de busca sequencial sao utilizados para sequéncia de dados desordenados Imagine uma busca sequencial exaustiva em uma série desordenada de milhées de elementos podendo haver necessidade de testar todos eles até encontrar o valor desejado Mas se a mesma sequéncia estiver ordenada entdo poderiamos aplicar o algoritmo de busca binaria muito mais rapido dividindo a série em duas e desprezando uma das partes testando apenas aquela onde estivesse o valor desejado A aplicabilidade deve ser analisada conforme o problema apresentado ou seja um determinado algoritmo pode ser excelente em dada situado e péssimo em outra ee A maioria das linguagens de programaao considera modelos de programacao nos quais a memoria consiste em um espaco de endereco uniforme cujo tempo de acesso é igual para todas as situagdées Embora essa suposido seja razoavel quando o conjunto de dados nao é grande ao processar grandes volumes de dados é importante lembrar que nem todas as memorias sdo construidas da mesma forma e portanto apresentardo diferentes comportamentos O tempo de acesso aos dados chamase laténcia e impacta de diferentes maneiras conforme a memoria vai sendo utilizada acessar dados nos niveis mais baixos da memoria é mais rapido Por exemplo carregar dados da memoria interna DRAM pode levar alguns nanosegundos mas a laténcia de acessar dados em um disco é de varios milissegundos 0 que é cerca de um milhao de vezes mais lento Nas solugdes que processam ou realizam EntradaSaida em grandes volumes de dados a laténcia se torna um gargalo e pode inclusive impedir o funcionamento em determinadas situacées VITTER 2008 Assim os algoritmos para processamento e especialmente pesquisa em arquivos externos devem ser construidos de maneira a lidar com as limitac6es impostas pela memoria interna que ndo tem espaco para todos os dados armazenados externamente Vitter 2008 coloca que os problemas de processamento e pesquisa em grandes volumes de dados se concentram em duas categorias httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 1837 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento Problemas em lotes nos quais nenhum pré processamento é realizado e todo o arquivo de itens de dados deve ser processado geralmente com o intuito de transmitir os dados passando pela memoria interna em uma ou mais etapas Problemas online nos quais 0 processamento é feito em resposta para uma série continua de Operacgodes de consulta respostas sao recebidas continuamente Uma técnica comum para problemas online é organizar os itens de dados por meio de indice um hierarquico de modo que apenas uma parcela pequena dos dados seja examinada em resposta a cada consulta Os arquivos consultados podem ser estaticos 0 que permite préprocessalos para respostas eficientes ou dindmicos nos quais as consultas sao realizadas simultaneamente a atualizacées como inseroes e exclusées Tipos de acessos As memorias internas conforme estudamos sdo muito importantes para o funcionamento dos computadores Atualmente existe uma grande variedade de memorias internas apresentando diversas caracteristicas dentre as quais o tipo de acesso Vejamos a seguir alguns tipos de acessos O computador 1é e grava segmentos contiguos de dados Os dados sao dispostos em Acesso espacos continuos e para realizar uma pesquisa 0 computador deve percorrer toda a sequencia estrutura até que o dado seja encontrado Entao o dado é carregado para a memoria principal e um passo caso seu tamanho seja pequeno suficiente para caber na memoria ou varios passos caso os dados sejam grandes e nao caibam na memoria A O computador precisa realizar pesquisas para descobrir onde os dados estado A cesso leatéri busca pode ser em qualquer posido da meméria As memérias que possuem este areatorto tipo de acesso podem ser chamadas de memorias de leitura e escrita E importante considerar que ha diferencas entre leitura e gravacdo Por exemplo dados que sejam gravados proximos ndo serao necessariamente lidos em sequéncia httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 1937 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento Arvores binarias BTrees As arvores bindarias combinam 0 acesso aleatério com 0 acesso sequencial Mantendo as chaves organizadas a arvore binaria permite e acesso aleatorio durante a descoberta de onde os dados estado Entdo uma leitura sequencial é realizada até que os dados terminem ou que 0 intervalo para leitura se esgote Lembrese Chaves sao as entradas de dados utilizadas para identificar um determinado item dentro da estrutura de dados Sao chamadas arvores binarias porque cada né da arvore pode se dividir em somente dois caminhos Dessa forma para encontrar uma chave basta 1 percorrer os nos perguntando se a chave foi encontrada 2 caso a chave nao seja encontrada se a chave for menor que o valor do no atual tomar o caminho da esquerda e repetir 0 passo 1 se a chave for maior que o valor do n6 atual tomar o caminho da direita e repetir 0 passo 1 Em todos os casos 0 uso da memoria externa leva a uma restrido no tocante a ordenacdo e pesquisa Uma ordenacao aleatoria significa que a gravacdo sera mais rapida pois nado é necessario determinar onde o dado deve ser gravado No entanto a pesquisa para leitura sera prejudicada porque a busca exigira mais processamento Uma ordenacdo sequencial dos dados gravados permite pesquisas mais rapidas mas ao gravar os dados sera necessdario determinar o local onde os dados serdo gravados e eventualmente movimentar o contetido de forma a criar 0 espaco correto para o dado Por exemplo e Dados gravados ACD e Novo dados B e Necessario criaro espaco paraBA CD e Entao gravaroBABCD O uso dos métodos adequados tanto para armazenamento quanto para ordenaao e pesquisa determinam a eficiéncia do sistema desenvolvido economizando recursos computacionais e consequentemente o custo de processamento dessas solucées 112 Pesquisa Pesquisar dados é uma tarefas mais comuns em desenvolvimento de software Aplicagdes para mensagens instantaneas podem procurar por contatos ou por contetidos Sistemas de localizagao buscam por caminhos mais curtos Um sistema empresarial busca dados no banco de dados Os algoritmos de pesquisa fazem parte do nosso diaadia e muitas vezes nao percebemos O desafio na pesquisa de dados é desenvolver a aplicacao de busca da maneira mais eficiente possivel de forma que os processos subsequentes nado sejam impactados por uma eventual demora Essa eficiéncia deve ser a preocupacdo permanente do desenvolvedor A evolucdo da ciéncia da computaao é marcada pelo aprimoramento dos algoritmos de pesquisa especialmente quando httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 2037 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento se considera que o volume de dados cresceu consideravelmente e que a complexidade dos processos é maior e que as pessoas tém menos tempo a perder De forma geral ha duas estratégias de pesquisa pesquisa sequencial e pesquisa binaria Pesquisa linear ou sequencial A pesquisa linear ou sequencial percorre todos os elementos de um vetor até encontrar a chave Entdo a posicdo do item é retornada Caso nado encontre a chave deve retornar um valor informando que nao teve sucesso na busca conforme figura a seguir Chave Mia Proximo Encontrou Pos4 Iniciar Om ea a Fim 0 1 2 3 4 5 Bea Tim Leo Sam Mia Ted Figura 12 Logica geral da busca sequencial Fonte Elaborada pelo autor 2019 PraCegoVer a Figura ilustra 1 tabela de 1 linha e 6 campos numerados acima de 0 a 5 denominados Bea Tim Leo Sam Mia e Ted com setas indo de0 a1 de1a2de2a3de3a4ede4a5 Anteriormente ao algarismo 0 ha a instrucdo Iniciar Acima do algarismo 1 ha a instruao Préximo Acima do algarismo 4 ha a instrudo Encontrou A partir do item 4 Mia segue uma seta para a descriado Pos4 e a indicaado de Fim Acima desta Figura ha a indicado Chave Mia Essa busca nao tem grande eficiéncia uma vez que se o vetor tiver n elementos é possivel que a busca requeira n iteragdes para encontrar a chave desejada No entanto esta é uma alternativa para os momentos em que os dados nAo estejam ordenados ou nenhum outro algoritmo seja viavel O pseudo cdédigo para a busca linear ou sequencial é Inicio Int chave retorno Retorno 1 Se a chave nao for encontrada retornar 1 Int vetor5 1121314151 Escreva Informe um valor para busca Leia chave Para i de 0 até 5 passo 1 faca Se vetorichave entao retorno i Fimpara Parar 0 laco de repetiao ao encontrar a primeira ocorréncia Fimse Fimpara Escreva Chave encontrada na posido retorno Fim Algoritmo 5 Pesquisa sequencial em um vetor unidimensional httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 2137 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento Pesquisa binaria A pesquisa binaria comea examinando o item do meio da lista ordenada e caso nAo seja o valor procurado podemos eliminar uma das metades Tratase de um algoritmo mais eficiente que a pesquisa linear por reduzir 0 espaco de busca consecutivamente restringindo as localizacées possiveis O uso mais comum da pesquisa binaria é buscar por uma chave em um vetor de dados Suponha um vetor v com um milhao de entradas numéricas Dada uma chave n uma pesquisa linear pode chegar no pior caso a um milhdo de operacées Se no entanto considerarmos a lista que deve estar ordenada dividindoa ao meio o valor procurado deve ser o elemento mediano ou estar em um dos dois segmentos obtidos reduzindo o espaco a Ser percorrido pela metade Uma vez que cada novo segmento sera dividido em dois a reducdo se amplia até que se encontre o valor desejado De forma geral dividese 0 vetor em duas partes e comparase o elemento mediano do vetor com o valor procurado se o elemento mediano for igual a chave retornase a posiao do elemento mediano terminase 0 programa se o elemento médio for menor que o valor procurado dividese a parte a direita do elemento mediano e comparase com 0 valor procurado se o elemento médio for maior que o valor procurado dividese a parte a esquerda do elemento mediano e comparase com 0 valor procurado repete até esgotar o numero de elementos ou até localizar o valor procurado As divis6es consecutivas reduzem o espaco de pesquisa como ilustrado na figura abaixo httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTPEORTE19unidade1ebookindexhtml 2237 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento IEW 30 fey oO 12 3 4 5 6 Wella 10 12 16 18 21 25 30 Elemento mediano Valor procurado Elemento mediano Valor procurado fiteies 4 65 6 Weltjam 21 25 30 Elemento mediano Valor procurado Elemento mediano Valor procurado fiteltsy 6 Valor ely Valor localizado Figura 13 Exemplo de uma pesquisa binaria PraCegoVer a Figura mostra uma pesquisa cuja chave é 30 Na base da Figura ha os campos indice e valor com valores 6 e 30 respectivamente indicando que 30 é 0 valor localizado Acima é indicada a descriao Elemento mediano Valor procurado Elemento medianovalor procurado A partir desta descrido ha uma seta indicando acima os campos indice com valores 356 e valor com valores 2125 e 30 sendo destacada a coluna com valores 5 indice e 25 valor Acima é indicada a descriao Elemento mediano valor procurado Elemento medianovalor procurado A partir desta descrido ha uma seta indicando acima os campos indice com valores 012345 e 6 e valor com valores 101216182125 e 30 As colunas nas quais constam indicevalor de 112 318 e 525 encontramse destacadas Para reduzir o vetor a ser pesquisado basta manter trés variaveis uma com o indice do meio do vetor uma com o indice do primeiro elemento do vetor e outra com o indice do ultimo elemento do vetor O algoritmo para a pesquisa binaria é escrito assim Inicio inteiro v5 10121618212530 chave tamanho inteiro inicio maior final resultado resultado 1 1 sera o valor resultante quando a chave nao for localizada chave 4 Pesquisar por 4 no vetor v tamanho 7 inicio 0 final tamanho1 0 indice do fim do vetor é sempre tamanho 1 enquanto inicio final faz meio inicio final 2 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 2337 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento se vmeio chave entdo resultado meio fimenquanto Finalizar o laco para terminar a busca fimse se vm chave entado inicio meio1 Desprezando o segmento a esquerda senao Final meio 1 Desprezando o segmento a direita fimse fimenquanto escrever resultado fim Algoritmo 6 exemplo de busca binaria E importante destacar que a busca bindaria requer impreterivelmente que os dados estejam ordenados De outra maneira nao funcionara 113 Ordenagdo Ordenar dados é a operacdo de alterar um vetor de forma que ele obedeca a uma determinada ordem AZEREDO 1996 A ordenacdo é uma das tarefas mais criticas relacionadas a pesquisa uma vez que varios métodos de pesquisa nao funcionam sem que os dados estejam previamente ordenados Além disso a ordenacdo acrescenta processamento a aplicacado requerendo que o desenvolvedor possua dominio sobre diferentes métodos para que a solucdo seja adequadamente eficiente Ha varios métodos para ordenado cada um deles voltado para diferentes situacdes e com diferentes desempenhos os mais frequentes s4o o Bubble Sort e 0 Quick Sort Bubble Sort O algoritmo Bubble Sort ou ordenagao por flutuaado também é conhecido como método da bolha O método consiste em percorrer diversas vezes o vetor e a cada passagem fazer flutuar para 0 topo o maior elemento da sequéncia dai o nome método da bolha Tratase de comparar um dos itens do vetor com todos os demais Quando o primeiro elemento é maior que o segundo efetuase a troca de posiées Essa comparacado é realizada repetidamente com cada um dos itens dos dados httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 2437 15082023 2024 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 2537 PraCegoVer A Figura apresenta um codigo com 11 linhas Enumerando cada linha temos Linha 1 int aux Linha 2 inte v 4132 Linha 3 forint i0 ivlengthi Linha 4 forint j0jvlengthj Linha 5 ifvivj Linha 6 auxvi Linha 7 vivj Linha 8 vj aux Linha 9 Linha 10 Linha 11 Linha 3 Para cada elemento em v percorrese i Linha 4 Para cada elemento em v percorrese j Linha 5 Se o valor de vi for menor que o valor de vj Linhas 67 8 Substituise vj por vi Ao executar o algoritmo temos 1ª iteração v 4 1 3 2 i 0 j 0 2ª iteraçao v 4 1 3 2 i 0 j 1 3ª iteraçao v 1 4 3 2 i 0 j 2 4ª iteraçao v 1 4 3 2 i 0 j 3 5ª iteraçao v 1 4 3 2 i 1 j 1 6ª iteraçao Figura 14 Bubble sort escrito em Java 15082023 2024 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 2637 v 1 4 3 2 i 1 j 2 7ª iteraçao v 1 3 4 2 i 1 j 3 8ª iteraçao v 1 2 4 3 i 2 j 2 9ª iteraçao v 1 2 4 3 i 2 j 3 10ª iteraçao v 1 2 3 4 i 3 j 3 Quick Sort O Quick Sort e um algoritmo que adota a estrategia de divisao e conquista ou seja o metodo consiste em dividir uma sequencia de valores em chaves onde as chaves menores devem preceder as maiores Posteriormente as sublistas devem ser ordenadas recursivamente ate que todos os valores estejam ordenados Observem os seguintes passos VAMOS PRATICAR Construa uma aplicaçao que ordene o vetor n mediante Bubble Sort Valores para n copie estes valores 9 20 17 10 18 25 25 15 2 15 17 17 16 11 3 11 25 16 12 22 2 16 21 27 27 18 1 29 16 10 0 2 2 26 19 9 12 24 20 3 16 4 4 1 25 6 25 10 29 20 17 23 3 26 0 30 4 20 7 11 11 19 21 4 24 13 9 22 6 28 29 28 22 10 17 3 1 1 18 2 3 11 12 28 28 7 30 25 17 28 5 12 Primeiro passo Escolher um elemento da lista chamado pivo Segundo passo Todos os elementos menores que o pivo devem ser rearranjados de modo a precede lo e os elementos maiores devem ser posicionados em seguida Terceiro passo Os elementos anteriores e posteriores devem ser recursivamnte ordenados 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento Tratase de um um algoritmo muito eficiente que reduz consideravelmente 0 tempo de ordenado podendo ser utilizado em grandes quantidades de dados Pre 114 Analise de complexidade O tempo de execucao de um algoritmo depende do quado demorado é para um computador executar as linhas de cédigo do algoritmo e isto depende da velocidade deste computador da linguagem de programacao e do compilador que traduziu o programa da linguagem de programacdo para o cédigo que executa diretamente no computador entre outros fatores Entretanto se desconsiderarmos a capacidade de processamento do computador ainda teremos a quantidade de iteragées e de transposiées que o algoritmo faz MANZANO LOURENCO MATOS 2015 Ainda de acordo com os autores essa avaliagdo de quanto o algoritmo requer do computador para rodar indiferentemente da capacidade do dispositivo é chamada analise de complexidade O primeiro aspecto a ser considerado é 0 tempo que 0 algoritmo leva para rodar de acordo com a quantidade de entradas no vetor de dados Para uma pesquisa linear o melhor caso sera quando a chave estiver na primeira posido e 0 pior caso sera quando a chave nao for localizada pois o algoritmo percorrera todos os elementos do vetor Logo a funao de crescimento da busca linear é n Ou seja o tempo de execucdo é diretamente proporcional ao niimero de elementos Para uma pesquisa binaria o melhor caso sera quando a chave estiver no elemento mediano do vetor e o pior caso sera quando a chave nao for localizada Mas por conta da légica da busca binaria dividindo o espaco de busca pela metade a cada iteracdo o numero de repetides é reduzido como apresentado no quadro abaixo Para o caso da busca binaria a funcdo de crescimento é logn logaritmo na base 2 den que é0 resultado matematico das divis6es consecutivas Numero de elementos Repeticoes 2 1 8 3 20 4 200 8 2000 11 2000000 21 2000000000 31 Quadro 1 Iteragdes necessarias piores casos para executar uma busca binaria Fonte Elaborado pelo autor 2019 PraCegoVer A Figura ilustra um Quadro com 2 colunas denominadas Numero de elementos e Repeticdes Na primeira coluna ha 7 linhas com os valores 282020020002000000 2000000000 Na segunda coluna ha 7 linhas com os valores 13481121 e 31 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTPEORTE19unidade1ebookindexhtml 2737 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento Essa diferenca entre as execucdes da busca linear e da busca binaria influencia diretamente no tempo de execucdo do algoritmo A analise de complexidade busca comparar 0 desempenho de diferentes algoritmos com a finalidade de determinar qual légica exige menos recursos Considerandose que 0 tempo de execucao Tn onde T é 0 tempo en é 0 ntimero de elementos processados necessitase de um modo para comparar a velocidade de crescimento de diferentes funcdes que sao a execucdo dos processos dos algoritmos de busca ou de ordenaao Essa comparacao é denominada comparacao assintotica E importante destacar que o tempo de execucdo também é influenciado por outros processos por exemplo a quantidade de decis6es if e os processos de troca de dados sAo0 somados ao tempo Assim uma equaao de tempo de execudo poderia ser Tn n 10 ou Tn n 3n 2 Entretanto convencionase que a parte relevante da fundo é 0 n pois a analise de complexidade se dedica a grandes volumes de elementos portanto a quantidade é importante Assim a funcdo de crescimento é reduzida Tn n 10 equivale a fn n Tn n 3n 2 equivale a fn n Funcoes decrescimento Total de Iteracées fn n5 100000000000 fn n 4n2 99999800 fn n 10000 2000 fn n 31 fn Logn 7 Quadro 2 Diferentes fundes de crescimento e seus respectivos resultados Fonte Elaborado pelo autor 2019 PraCegoVer A Figura ilustra um Quadro com 2 colunas denominadas Funées de crescimento e Total de Iterac6es Na coluna Funées de crescimento ha 5 linhas com as seguintes equaées fn n45 fn n43 4n2 fn n 10000 fn sqrtn fn Logn Na coluna Total de Iteragdes ha 5 linhas com os seguintes valores 100000000000 99999800 2000 31 7 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 2837 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento Observando o quadro acima com diferentes fungées percebese que algumas delas tem maiores velocidades de crescimento Para representar a complexidade estabelecese um limite que represente como a fundo de crescimento se comporta A notado O determina a ordem da funcdo e é uma das alternativas mais frequentes para essa representacao Escrevese Ofn A notagao O é dada por Sejam Tn e fn funées dos inteiros no conjunto real afirmase que Tn é Ofn se existem constantes positivas c e nog tais que Tn cfn para todo n 2 no Assim se considerarmos um algoritmo em que Tn n 1000 e fn n podemos criar um grafico para o intervalo até 50 elementos ilustrado na figura abaixo Tnn1000 fn 15000 10000 t Esta intersecgao demonstra que n21000 é On 5000 0 10 20 30 40 50 Figura 15 Grafico demonstrando que fn é On Ordem de n Fonte Elaborada pelo autor 2019 PraCegoVer A Figura mostra um grafico cujo eixo X apresenta valores de 01020304050 e o eixo y apresenta os valores de 0500010000 e 15000 Nele estado ilustradas duas funcées Uma das linhas no grafico esta indicada na cor azul que representa a funcao Tnn1000 A outra linha do grafico indicada na cor amarela representa a funcdo fn n2 No ponto em que as funcées se cruzam consta a informacdo Esta intersecc4o demonstra que n1000 é On Sempre que um algoritmo de ordenaao ou de busca for implementado devese considerar a sua eficiéncia mediante a avaliagdo da complexidade com a finalidade de determinar se ha alternativas mais eficientes para a solucao 12 Procedimentos de funcées e funcdes recursivas Os problemas relacionados a ordenaao e pesquisa sdo complexos e sua implementado requer em muitos casos a construao de inimeras linhas de cédigo No entanto 0 aumento das linhas de cdédigo traz em si dificuldades de manutenao do programa quando for necessario realizar um ajuste ou correao havera mais httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 2937 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento trabalho quanto mais linhas de cédigo forem implementadas Também ocorre o surgimento de cdédigo redundante blocos de procedimentos distribuidos no programa mas que tem a mesma finalidade Organizar o cédigo dos programas de forma que a manutencdo seja eficiente e nado haja codigos redundantes é uma boa pratica indispensavel atingida pela modularizaao e pela recursividade 121 Modularizagdo e reaproveitamento de codigo e funées A modularizacao do cédigo consiste em separar a l6gica de programaao em elementos distintos e com responsabilidades especificas Por exemplo um programa que realize operagées matematicas pode ser organizado de forma a simplificar seu uso mediante a construcdo de funédes reaproveitaveis SOUZA et al 2011 public class modularizacao public static void mainString args int a 109 int b 55 System out print nSoma somartab35 System outprint nSubtragao e somartab5 SystemoutprintinMultiplicagao somarfab3 Systemout printinDivisao ze somarab333 Se for necessario realizar uma operagao basta inmvocar a fungao desejada int c 1203 int d 45 SystemoutprintinMultiplicagao somartcd ffAs operagdes foram modularizadas em fungdes especial izadas public static int somarint a int b return atbg public static int subtrairint a int b return abi public static ant multiplicarint a int b return asby public static int dividirdint a int b return afb PraCegoVer A figura ilustra um cddigo de 26 linhas Enumerando cada linha temos Linha 1 public class modularizacao Linha 2 Linha 3 public static void mainString args Linha 4 int a10 Linha 5 int b5 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 3037 15082023 2024 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 3137 Linha 6 SystemoutprintlnSoma somarab Linha 7 SystemoutprintlnSubtraçao somarab Linha 8 SystemoutprintlnMultiplicaçao somarab Linha 9 SystemoutprintlnDivisao somarab Linha 10 Se for necessario realizar uma operaçao basta invocar a funçao desejada Linha 11 int c 120 Linha 12 int d 4 Linha 13 SystemoutprintlnMultiplicaçao somarcd Linha 14 Linha 15 As operaçoes foram modularizadas em funçoes especializadas Linha 16 public static int somar int a int b Linha 17 return a b Linha 18 Linha 19 public static int subtrairint a int b Linha 20 return ab Linha 21 public static int multiplicarint a int b Linha 22 return ab Linha 23 public static int dividerint a int b Linha 24 Return ab Linha 25 Linha 26 Repare que cada modulo recebe dois argumentos numeros inteiros processa os dados e retorna o resultado Esse retorno e capturado na instruçao que invocou chamou a funçao VAMOS PRATICAR 1 Crie uma funçao que receba duas strings e retorne sua concaten concatv1 v2 retornara v1 v2 2 Agora crie um programa que receba o nome e o sobrenome do usu duas variaveis diferentes e as concatene mostre na tela ou no console 3 Altere a ordem da concatenaçao dentro da funçao v2 v1 4 Rode o programa do passo dois novamente Veja a diferença 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento A cada vez que o programa principal precisa realizar uma operacdo matematica basta chamar a funcdo necessaria DEITEL DEITEL 2015 Por outro lado se precisarmos alterar a légica de alguma das funcées essa alteracdo de cédigo se dara uma vez e sera refletida em todos os procedimentos que utilizem tal funao 122 Recursividade Muitos algoritmos executam o mesmo procedimento repetidas vezes até que uma condiao de parada seja alcangada Por exemplo 0 calculo do fatorial de um ntimero n 414x3x2x124 Observado atentamente o fatorial é 4 4x 41 x 81 x 21 24 Uma possivel implementacdo do fatorial utilizando funcées é public class fatorial public static void maintringl args system out prantinatorial 43934 fFungao para reaproveitar o calculo do fatorial public static int fatorialdint nj fordint 1 mg ils 13 nen 1135 return mg 2 PraCegoVer a figura mostra um cédigo de 14 linhas Enumerando cada linha temos Linha 1 public class fatorial Linha 2 Linha 3 public static void mainString args Linha 4 Systemoutprintlnfatorial4 Linha 5 Linha 6 Linha 7 Funcdo para reaproveitar o calculo fatorial Linha 8 public static int fatorial int n Linha 9 forintn i1 i Linha 10 nni1 Linha 11 Linha 12 return n httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 3237 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento Linha 13 Linha 14 VOCE QUER LER e A recursividade vem sendo aplicada largamente na programacdo de computadores para resolver problemas complexos No artigo A Historia da Ciéncia e o ensino da recursividade As torres de Hanoi vocé encontrara um estudo sobre a natureza da recursividade e algumas de suas aplicagdes Leia o artigo completo neste link httpsrevistaspucspbrhcensinosearchsearch simpleQueryrecursividadesearchFieldquery httpsrevistaspucspbrhcensinosearchsearch simpleQueryrecursividadesearchFieldquery eee eeeeeeeeeeeeeeeeeeeeee rere rere eeeeeeeeeeeeeee eee eee eee ee Uma fundo recursiva um procedimento que chama a si mesmo resolvendo problemas sucessivamente simplificando o problema até que se atinja uma condicao de parada A estrutura de uma fundo recursiva consiste no processamento de um caso base que significa 0 final da pilha de execu6es e 0 processamento recursivo que é chamada para ela mesma com o problema simplificado httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 3337 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento Funcao Recurr int n Inicio Caso base n 0 Recursividade n1 Execucdo Recebe n Int x 10 ie Int final recurx n0 Retornan Recurrn L Fim Figura 16 Esquema légico de uma fungado recursiva Fonte Elaborada pelo autor 2019 PraCegoVer a Figura ilustra um fluxograma que parte do campo Inicio a partir do qual ha uma seta direcionada ao campo Recebe n nn1 Deste campo parte a seta direcionada para o campo n0 A partir deste campo ha dois caminhos possiveis O primeiro segue para o campo Recurrn Ja o segundo segue para o campo Retorna n e posteriormente para o campo Fim Na Figura ainda consta a descrido da Funcao Recurr int n Caso base n0 Recursividade n1 Também ha de Execucao Int x 10 Int final recur x A fungao recurr ilustrada na figura acima 6 um exemplo simples que tem por finalidade subtrair um valor até que ele chegue em 0 zero Ao chegar em 0 zero a fundo para e retorna n este 0 caso base Enquanto o valor de n for maior que 1 a funcdo recurr é chamada novamente O cédigo para a funcdo recurr é public class recursividadae public static void mainString args inti 10 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 3437 15082023 2024 Pesquisa Ordenação e Técnicas de Armazenamento httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 3537 Systemoutprintlnrecurri public static int recurrint n n n1 ifn0 return recurrn return n Entao a mesma tecnica pode ser aplicada para resoluçao do fatorial de n n uma vez que a cada chamada subtraise 1 e o caso base e n 1 ZIVIANI 2012 public class fatorialrecursivo public static void mainString args int numero 8 int fat fatorialnumero Systemoutprintlnfat public static int fatorialint n if n0 return 1 0 e igual a 1 return nfatorialn1 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento VAMOS PRATICAR e 1 Implemente a sua fungao recursiva para calculo fatorial 2 A seqiiéncia de Fibonacci um modelo famoso por representa estruturas naturais Ela se da pela equacao f n1 n2 11 2 35 3455 89 144 Tratase de um problema perfeito para solugdo recursiva Dado que o caso base én 2 implemente uma funao recursiva para a se de Fibonacci O programa principal deve ter a seguinte estrutura for int i 0i 30 i Systemoutprinti fiboi A funcao recursiva é um procedimento simples porém poderoso capaz de minimizar o cédigo resolvendo questées complexas O programador que souber utilizar adequadamente este recurso elevara sua capacidade criativa e certamente se tornara um profissional mais valorizado Sintese Concluimos a unidade abordando busca ordenado e armazenamento de informaées sendo apresentada a importancia do tema no contexto atual facilitando a construcdo de uma visdo critica sobre a realidade computacional Nesta unidade vocé teve a oportunidade de compreender o que é busca de dados no que consiste e para que serve observando exemplos praticos conhecer métodos de ordenacao cujas caracteristicas ficaram bem evidenciadas facilitando sua visdo critica entender as técnicas de armazenamento de dados e os diferentes tipos de memorias compreender complexidade de algoritmos httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTIPEORTE19unidade1ebookindexhtml 3637 15082023 2024 Pesquisa Ordenagao e Técnicas de Armazenamento Clique para baixar o conteudo deste tema Bibliografia AZEREDO P A Métodos de Classificagdo de Dados e Analise de suas Complexidades Rio de Janeiro Campus 1996 COSTA E B L A Hist6ria da Ciencia e o Ensino da Recursividade As torres de Hanoi Historia da Ciéncia e Ensino Construindo interfaces v 4 p 38 48 2011 Disponivel em httpsrevistaspucspbrhcensino articleview54895768httpsrevistaspucspbrhcensinoarticlevie w54895768 httpsrevistaspucspbrhcensino articleview54895768 Acesso em 01102019 DEITEL P DEITEL H Java Como Programar 8 ed Sado Paulo Pearson 2015 FEOFILOFF P Algoritmos em linguagem C Rio de Janeiro Elsevier 2008 GOODRICH M T TAMASSIA R Estruturas de Dados e Algoritmos em Java 5 ed Porto Alegre Bookman 2013 GOVERNO DO ESTADO DE SAO PAULO Centro Paula Souza Grupo de Estudos de Educagao a Distancia Informatica Médulo I Agenda 15 L6gica de Programagao Vetores e Matrizes 1309 min Canal GEEaD CPS 2014 Disponivel em httpswwwyoutubecomwatch v7i3Yfily lvElistLLecA4jNMub1jeYn7rRegAindex2t0shttpswwwyoutubecomwatch v7i3Yfily 1vElistLLecA4jNMub1jeYn7rRegAindex2t0s httpswwwyoutubecomwatch v7i3Yfily 1vElistLLecA4jNMub1jeYn7rRegAindex2t0s Acesso em 01102019 KNUTH D E The Art of Computer Programming v 1 2 ed Massachusetts AddisonWesley 1973 MORAIS I S et al Algoritmo e programacao engenharia Porto Alegre SAGAH 2018 MANZANO J A N G LOURENCO A E MATOS E Algoritmos Técnicas de Programacdo 2 ed Sao Paulo Erica 2015 MANZANO J A N G OLIVEIRA J F Algoritmos l6gica para desenvolvimento de programacao de computadores 28 ed Sao Paulo Erica 2016 RIBEIRO J A Introducdo a programacado e aos algoritmos 1 ed Rio de Janeiro LTC 2019 SOUZA M A F GOMES M M SOARES M V CONCILIO R Algoritmos e légica de programagao Um texto introdutorio para a engenharia 3 ed Sado Paulo Cengage Learning 2011 VITTER J S Algorithms and Data Structures for External Memory Boston Now Plubishers 2008 ZIVIANI N Projeto de Algoritmos com implementacgées em JAVA e C Sdo Paulo Cengage Learning 2012 httpscodelyfmucontents3amazonawscomMoodleEADConteudoCTPEORTE19unidade1ebookindexhtml 3737