terça-feira, 27 de dezembro de 2016

Questões de Concurso - Prova 304 - DataPrev Analista de Negócios 2016

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Se você chegou aqui agora e não está entendendo sobre o que é essa postagem, recomendo que você dê uma lida primeiro neste post aqui, e depois volte para continuar lendo. Para você que já sabe do que estou falando, vamos começar.

A prova que vamos analisar é a 304 - DataPrev Analista de Negócios 2016. Consegui selecionar três questões para debatermos, são elas:

Questão 43 - Fácil 😝

Questão 43 da prova 304 DataPrev Analista de Negócios
Figura 1 - Questão 43 da prova 304 DataPrev Analista de Negócios


Pare sua leitura por aqui, tome o seu tempo, leia calmamente a questão e tente encontrar a resposta. Conseguiu achar ?

Questão 43 - Resposta
Questão 43 respondida da prova 304 DataPrev Analista de Negócios
Figura 2 - Questão 43 respondida da prova 304 DataPrev Analista de Negócios
Entendamos a questão ! Se concentre nela !

A resposta correta é a opção E. Mas porque esta opção e não a opção D, por exemplo ? A questão fala sobre um dos benefícios da programação orientada a objetos, a abstração de classes e objetos. Isto é importante, pois ele será o delimitador para que não escolhamos a opção errada. Consequentemente a opção D se desqualifica, pois ela engloba a afirmação 3, onde esta cita a utilização de vários padrões conceituais durante todo o processo de criação de software e isto não está relacionado diretamente com a abstração de classes e objetos. Este momento é muito inicial no desenvolvimento de um sistema e esta afirmação cita de algo muito mais à frente.

A opção A também se desqualifica, pois engloba a afirmação 3, e a opção B também está errada,  mesmo não incluindo a afirmação 3, mas deixando de incluir uma afirmação que está correta, a 2. Esta está correta pois de fato a orientação a objetos traz essa característica. A possibilidade de modelar dados através de classes e objetos eleva o programador a um outro nível de desenvolvimento de software, permitindo que ele desenvolva um código mais limpo e fácil para manutenção e reuso.

A opção C deixa de lado a afirmação 1 o que a torna também errada. Através da orientação a objetos é possível criar estruturas de classes e interfaces conectadas entre si que tornem a reutilização de código maior. Polimorfismo e herança são ótimos exemplos deste caso.

Questão 44 - Médio 😑
Questão 44 da prova 304 DataPrev Analista de Negócios
Figura 3 - Questão 44 da prova 304 DataPrev Analista de Negócios
Mais uma vez tome o seu tempo e leia cuidadosamente a questão. Essa aí está moleza!

Sobre o que o enunciado se refere ? Simples ! Ele narra a situação onde existe uma classe abstrata e todas as classes que a estendem, se tornando assim filhas, são concretas.
Diagrama de classes de exemplo
Figura 4 - Diagrama de classes de exemplo
A Figura 4 exemplifica a situação que a questão narra. A classe Montadora é abstrata, logo ela não pode sofrer instanciação direta através do operador new. Então seus filhos entram em ação sendo representações concretas de um pai abstrato, onde em cada um é definido um comportamento particular, e eles sim podem ser instanciados. Tal comportamento é exemplificado pelo método montar().

Imagine o seguinte cenário: surgiu a necessidade de se trabalhar com dados reais, ou seja, centenas de montadoras, onde cada uma monta seus carros de formas completamente diferentes. Como representar isso? Uma única classe Montadora com todos as formas possíveis de se montar um carro não seria uma boa escolha, pois vc acabaria com uma classe com alguns milhares de linhas. Talvez modificações em uma parte do código poderiam criar bugs em outras, afetando assim a linha de montagem de outros automóveis.

Da forma mostrada pela Figura 4 é possível especializar a montagem de carros em classes diferentes e adicionar novas montadores sem mexer nas que já existem. Mas porque especializar ? Especializar é importante pois assim cada uma conhece sua forma de montar carros e não precisa conhecer o método empregado pelas outras ou de características gerais a todas montadoras. Tudo o que for comum a todas as montadoras pode ser posto na classe abstrata, e assim a classe especialista (concreta) se preocupa unicamente com sua responsabilidade no momento, montar carros.

Questão 44 - Resposta
Questão 44 respondida da prova 304 DataPrev Analista de Negócios
Figura 5 - Questão 44 respondida da prova 304 DataPrev Analista de Negócios
A questão pergunta qual é o conceito obtido quando se obtém novos exemplares a partir de uma representação abstrata. Este processo já foi citado nesta explicação, é a instanciação. Logo, a resposta correta é a opção B.

Questão 45 - Fácil 😝
Questão 45 da prova 304 DataPrev Analista de Negócios
Figura 6 - Questão 45 da prova 304 DataPrev Analista de Negócios
Respire fundo e tome o seu tempo.

Para responder esta pergunta precisaremos relembrar um conceito inicial da orientação a objetos, o encapsulamento. Muitas vezes é necessário restringir a visibilidade de características (atributos) e comportamentos (métodos) de uma classe, para que recursos externos não utilizem eles de forma indevida. A falta dessa atividade pode tornar o seu projeto de software fraco contra ataques de softwares maliciosos, pois estes podem ocasionar erros propositalmente levando assim a um travamento total do software. Segundo CHESS, BRIAN; WEST, JACOB o que torna o seu software fraco não são problemas de ambiente, como antivírus, firewall, etc.; mas sim erros arquiteturais como este.

Um ótimo exemplo desta situação é uma classe de acesso a banco de dados. Seus únicos comportamentos são: conectar e desconectar; e seus únicos atributos são: login, senha e o driver do banco. Reflita sobre a seguinte questão: qual seria a necessidade de tornar o login e senha do banco de dados visível para qualquer classe do sistema ? A resposta é simples: nenhuma. Neste momento o encapsulamento entra em ação.

É possível criar métodos que encapsulem estas informações. Para o atributo login, por exemplo, não é interessante fornecer uma forma que uma classe usuária possa obter qual login sendo utilizado no momento, mas talvez seria bom fornecer uma forma de se atribuir um login novo caso o default não funcione. Com o encapsulamento os métodos de acesso se tornam os únicos responsáveis pelos recursos que manipulam, sendo eles atributos ou métodos, formando assim um canal de acesso único.

Espero que com a explicação dada a resposta da questão se torne clara.

Questão 45 - Resposta
Questão 45 respondida da prova 304 DataPrev Analista de Negócios
Figura 7 - Questão 45 respondida da prova 304 DataPrev Analista de Negócios
As opções A, B, D e E são totalmente relacionadas ao encapsulamento, como já citado acima. A única que não é relacionada é a opção C, sendo ela a resposta final.

Com isso terminamos as questões da prova 304 - DataPrev Analista de Negócios. Espero que vocês tenham gostado desse novo formato, e se quiser sugiram provas e questões. 😁

Até a próxima ! 😘

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou, deixa uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

CHESS, BRIAN; WEST, JACOB; Secure Programming with Static Analysis; 2007
Leia Mais ››

Questões de Concurso - O início

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Este é o primeiro post de uma nova série de postagens aqui no blog. Sempre que você ver um post com o título começando com Questões de Concurso, já pode esperar algumas belas questões, suas respostas e explicações.

Mas que tipo de questão você vai trazer João ? Sempre trarei questões relacionados à programação, orientação a objetos, estruturas de dados e algoritmos. Todos esses assuntos já estamos discutindo aqui a um certo tempo, logo você tem um grande repositório de material para tirar suas dúvidas. 😊

Minha motivação para começar essa nova série foi trazer uma nova forma de conteúdo pro blog e agregar mais para a comunidade que é ou está focada em concursos públicos.

Este post, especificamente, será o catálogo de todas as postagens dessa nova série. Caso você queira fazer uma pesquisa em todas as provas já comentadas, pode dar uma olhada aqui.

Posts da série Questões de Concurso:

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.

E-mail: precisoestudarsempre@gmail.com
Leia Mais ››

segunda-feira, 19 de dezembro de 2016

WriteYourOwnGraph v2.0

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Estou muito feliz 😄 em dizer que através de muito esforço e trabalho, consegui concluir uma versão 2.0 da ferramenta WriteYourOwnGraph. Nesta versão foram adicionadas novas características, como:
  • Adição de arestas curvas através da curva cúbica de Bezier
  • Adição de títulos aos nós
  • Aperfeiçoamento da seleção de arestas
  • Adição do painel de propriedades
  • Adição do botão Reset na barra de ferramentas
  • Fix de alguns bugs
Versão 2.0 da ferramenta WriteYourOwnGraph
Figura 1 - Versão 2.0 da ferramenta WriteYourOwnGraph
Com o painel de propriedades é possível customizar os nós e arestas de seu grafo, adicionando títulos aos nós ou alternando entre arestas curvas e retas. O painel de camadas não teve seu funcionamento alterado, e a nova ferramenta adicionada no painel de ferramentas possibilita que o usuário possa reiniciar seu trabalho de forma ágil, limpando toda a área de trabalho.

É importante citar que houveram mudanças arquiteturais na ferramenta, pois agora é necessário o uso de um servidor de aplicações para que a WriteYourOwnGraph funcione. Isto se dá pelo fato do painel de propriedades ser carregado via AJAX. Realizei essa escolha visando o reuso e facilidade de manutenção das telas. Eu utilizei o Tomcat, mas sinta-se livre para utilizar qualquer servidor de sua vontade. Novas características e funcionalidades ainda estão por vir. Se você quiser acompanhar, entre no repositório GitHub da ferramenta (o link está no fim do post) e dê uma olhada na aba de Issues.  
Grafo com arestas curvas
Figura 2 - Grafo com arestas curvas
A Figura 2 mostra um grafo de três nós e duas arestas sendo essas duas curvas, onde a selecionada tem suas propriedades mostradas no painel.

Faça um teste em casa, me conte aqui nos comentários o resultado, e antes de tudo te desejo um feliz natal com muita felicidade para você e toda sua família. 😉 🎅🎄


Download do código-fonte
Release WriteYourOwnGraph v2.0: https://github.com/PrecisoEstudarSempre/WriteYourOwnGraph/releases/tag/2.0

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.

E-mail: precisoestudarsempre@gmail.com
Leia Mais ››

terça-feira, 29 de novembro de 2016

O código de Huffman

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Você já parou para pensar como os programas de compressão de dados, como WinZip, WinRar, GZIP, entre outros conseguem diminuir o tamanho de um arquivo ? Como será possível diminuir um arquivo de 1Gb para 600 Mb sem perder a informação contida ali ?

Em 1952, David A. Huffman criou o código de Huffman [1] com o intuito de construir um código binário de redundância mínima mais eficiente do que de seu professor, Roberto M. Fano [2]. Através de sua criação se tornou possível a realização de compressões utilizando combinações mínimas de códigos binários não redundantes, ou seja, que não se repetem.
Figura 1 - David Albert Huffman
Mas porque comprimir dados é algo tão importante ?

Pense na seguinte situação: você tem que enviar alguns dados via internet, mas sua conexão é instável, cai toda hora e você não pode enviar pacotes muito grandes, pois podem haver problemas de falta de informação. Então, o que você faz ? Não envia os dados ? Neste tipo de situação a compressão de dados pode ser uma bela mão na roda.

Para que possamos realizar a compressão dos dados utilizando o código de Huffman, devemos primeiro montar uma tabela com duas colunas. A primeira coluna contém os caracteres usados no texto enviado, e a segunda os códigos binários que representam cada caractere. Contudo, você lembra no início do post que eu citei que o código de Huffman é redundância mínima ? Essa redução de redundância significa que cada caractere se transforma em um código binário único.

Para fins de exemplo em todo o post utilizaremos o seguinte texto como exemplo:

"o rato roeu a roupa do rei de roma"

Para cada caractere utilizado um código binário único é associado a ele, ou seja, a letra "o" poderia ser 00, o "b" 10, ou o "a" 11. Porém, é importante ressaltar que nenhum código pode conter outro, por exemplo: se a letra "b" é 10, a letra "r" não pode ser 1000, pois se fosse haveria um problema grande no momento de descompressão. O que seria "r" e o que seria "b" ? Nenhum código pode ser unicamente 0 ou 1 também, pois isso eliminaria toda a gama de combinações binárias possíveis que começam com estes dois números.

Mas uma pergunta permanece: onde está a compressão nisso tudo ? Em modelos como ASCII ou o Unicode, todos os caracteres mapeados por tais possuem, respectivamente, 1 e 2 bytes. Então o nosso texto codificado em um desses modelos seria uma sequência de 0 e 1.

1 byte = 8 bits
2 bytes = 16 bits

A resposta se tornou clara. Se no melhor dos cenários, o modelo ASCII, mapeia cada caractere como 8 bits e conseguimos diminuir essa quantidade para 2 bits, está aí a compressão.

A tabela citada no parágrafo acima é o resultado final do algoritmo do código de Huffman, ela acaba atuando como uma cifra, pois através da mesma é possível comprimir e descomprimir qualquer caractere do texto enviado. Então, tais tarefas que pareciam ser extremamente complicadas acabam se tornando algo simples pois, somente precisamos ler cada caractere e achar seu correspondente binário para comprimir, e para o processo reverso, analisar cada binário e ver sua correspondência em caractere.

Mas como construir a tabela ? A resposta reside em uma árvore binária completa, onde nas folhas ficam os caracteres do nosso texto. Se você nunca leu nada sobre árvores binárias, clique aqui ou dê uma olhada na postagem feita aqui no blog sobre árvores binárias. O link estará no fim desse post.

Para montar a árvore é necessário analisar o texto a ser processado. Note que algumas letras se repetem como o "o", "i", "e", "b", entre outras. O primeiro passo que devemos tomar é montar uma relação de todas as letras usadas, onde cada uma deve vir acompanhada com a quantidade de vezes que se repete. A Tabela 1 mostra a relação montada para o texto de exemplo.

Tabela 1 - Mapa de caracteres com suas quantidades
Note que a relação está ordenada de forma ascendente pela quantidade de cada letra e isso é importante porque como veremos adiante está ordem é determinante para a execução do algoritmo. É de alta importância ressaltar que o caractere whitespace também é contabilizado na nossa análise, pois quando o texto for descomprimido queremos que o texto de saída seja igual ao de entrada. Com a relação pronta podemos montar a árvore binária, seguindo os passos abaixo.

Passo 1: Utilizando a Tabela 1, transforme todas as letras e suas respectivas quantidades em raízes de árvores binárias. Por uma questão de simplicidade de representação iremos utilizar essa bolinhas para representar os nós da árvore e o número abaixo de cada uma é a quantidade de repetição de cada letra.
Figura 2 - Passo 1 da construção da árvore binária de Huffman
Passo 2: Pegue os dois primeiros nós, e transforme eles em filhos de um novo nó, onde a quantidade de repetição desse novo nó é a soma das quantidades de seus filhos. Como este novo pai não possui caractere, seu conteúdo será em branco. Lembre-se de como as árvores binárias funcionam, menores à esquerda e maiores à direita.
Figura 3 - Passo 2 da construção da árvore binária de Huffman
Passo 3: Reordene os nós pela quantidade de repetição de forma ascendente.
Figura 4 - Passo 3 da construção da árvore binária de Huffman
Passo 4 até 10: Repita os passos 2 e 3 até que sobre somente um único nó.
Figura 5 - Passo 4 da construção da árvore binária de Huffman
Figura 6 - Passo 5 da construção da árvore binária de Huffman
Figura 7 - Passo 6 da construção da árvore binária de Huffman

Figura 8 - Passo 7 da construção da árvore binária de Huffman
Figura 9 - Passo 8 da construção da árvore binária de Huffman
Figura 10 - Passo 9 da construção da árvore binária de Huffman
Figura 11 - Passo 10 da construção da árvore binária de Huffman
Não há muito o que explicar aqui, pois as imagens já fazem esse trabalho. Note que o processo de criação da árvore de Huffman é algo bem simples e como resultado todos os caracteres acabam virando nós folha. Lembre-se deste fato, pois ele será de extrema importância na montagem da implementação em Java do nosso algoritmo.

Visto que já abordamos o processo de criação da árvore, podemos começar a abordar o processo de criação da sequência binária. É bem simples de fato. Para cada caminho à esquerda tomado é acumulado 0 ao resultado final, e para cada caminho à direita é acumulado 1. Então, utilizando a Figura 11 podemos concluir que o caractere 'e' é igual à 000, o 'a' 001, o 'p' 10101 e assim segue até o último. Faça o teste, gere todos os códigos de todos os caracteres e conclua que o que foi dito no início do post é de fato verdade. Nenhum código consegue ser contido em outro, por isso é importante que os caracteres sejam as folhas desta árvore.

Como já disse em outras postagens, utilizo Java para a implementação do que estou abordando por uma questão de afinidade, mas nada impede que você recrie a mesma situação na linguagem de sua preferência. Vamos analisar o código parte por parte. 

A classe HuffmanNode dispensa comentários complexos. Ela é uma simples classe com alguns atributos e getters e setters. Dentre estes atributos os que merecem mais atenção são: isLeaf e frequency. O primeiro representa um booleano que determina se um nó é folha ou não, criado para tornar a leitura do código melhor. O segundo é a frequência de repetição já citada anteriormente. Os demais atributos são os que tornam a classe um nó de uma árvore binária, ou seja, uma referência para um possível filho à esquerda ou à direita e um valor inteiro para o conteúdo.

Note que eu disse "valor inteiro" e não "caractere". Porque isto acontece se nossa árvore contém letras nas extremidades ? Em Java, e acredito também que em outras linguagens, é possível transformar valores inteiros em caracteres e vice-versa. Isto se dá pelo fato de todo caractere ser internamente um número na tabela ASCII ou no modelo Unicode. Deixarei na seção Outros links o link para a tabela ASCII, onde é possível ver todos os códigos numéricos de todos os caracteres. Faça o teste em casa. 😀

Preferi utilizar esta abordagem por uma questão de conforto, pelo fato de que é difícil identificar onde está o nó space, e também é uma forma de "marcar" os nós sem conteúdo. Veremos este ponto adiante.

Abaixo, a classe que representa a árvore.


Se concentre nos seguintes tópicos listados abaixo:
  • O atributo root - Representa a raiz da nossa árvore. É através dela que começamos qualquer busca. É a única referência existente a um nó.
  • Método getCharFrequency - Monta a relação de caracteres e suas respectivas quantidades de repetição, assim como a Tabela 1 também mostra. Esta relação serve de entrada para a montagem da árvore.
  • Método createBinaryMap - Monta uma relação de caracteres e suas respectivas sequências binárias, onde as sequências somente serão alimentadas após o processamento da árvore. Esta relação é o resultado do processamento feito pela árvore.
  • Método initializeTree - Cria a lista de raízes.
  • Método createTree - Executa todo o procedimento explicado pelas Figuras 2 até 11. Seu parâmetro de entrada é a lista gerada pelo método initializeTree.
  • Método crypt(String nonCryptedText) - Representa a interface pública para a compressão de dados. Sua responsabilidade é receber um texto não comprimido, realizar a compressão e retornar sua versão compactada.
  • Método crypt(HuffmanNode root, String currentBinary, Map binaryMap) - Versão sobrecarrega do método crypt. Realiza a busca recursiva na árvore, começando da raiz e indo até as folhas. Os três parâmetros são necessários, pois como é baseado em recursividade, o parâmetro root é atualizado constantemente, a atual sequência binária também é atualizada de acordo com o caminho tomado, e o mapa é utilizado para armazenar a sequência a partir do momento que uma folha é atingida. Note que este método não procura somente um único caractere, e sim todos. A árvore é vasculhada completamente.
  • Método decrypt - Sua responsabilidade é receber um texto comprimido e retornar sua versão descompactada. Tal é realizado utilizando a tabela resultado montada no processo de compressão.
Como utilizar ?


Note que a utilização é bem simples. Caso você queira comparar resultados de tamanho de arquivo antes e depois da compactação, siga as seguintes instruções:
  1. Visite o site http://br.lipsum.com/
  2. Gere um texto com 1000 palavras
  3. Guarde esse texto um novo arquivo txt
  4. Gere o código binário a partir do texto através de algum conversor online. Guarde o resultado em um novo arquivo txt
  5. Inicie o programa de compactação passando como entrada o texto gerado
  6. Aguarde pelo resultado, copie o código binário compactado gerado e cole em um novo arquivo txt 
  7. Analise o tamanho dos dois arquivos, a versão binária não compactada e a compactada, e veja a diferença de tamanho entre eles. Caso você fique com dúvidas sobre a integridade do conteúdo compactado, realize a descompressão e compare os resultados. O texto descompactado deve ser igual ao gerado pelo site da etapa 1.
Seguindo estas instruções, obtive o resultado mostrado pela Figura 12.

Figura 12 - Comparação de tamanho de arquivos

Terminamos !!! 😆👍

Baixe o código nos links abaixo e deixe aí sua opinião.

Download do código-fonte

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.

E-mail: precisoestudarsempre@gmail.com
Referências

[1] LAFORE, ROBERT; Estruturas de dados e algoritmos em Java; 2004

Leia Mais ››

quarta-feira, 9 de novembro de 2016

Executando um case insensitive match em strings

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Algumas vezes já estive em situações em que precisava aplicar uma expressão regular em textos que desconhecia como era o emprego de letras maiúsculas e minúsculas, ou seja, não era possível determinar a forma do texto. Então, cheguei a um impasse: o que fazer ?

Eis aqui algumas opções que pensei:
  1. Transformar todas as letras do texto em minúsculas.
  2. Transformar todas as letras do texto em maiúsculas.
  3. Modificar minha expressão regular para ser case-insensitive.
Mas o que é case-insensitive ? É tudo aquilo que não diferencia maiúscula de minúscula, e vice-versa. Então, neste tipo de análise "PRECISO ESTUDAR SEMPRE" é igual a "preciso estudar sempre", que é igual a "Preciso Estudar Sempre" e assim por diante. Já o seu caso contrário, o case-sensitive, diferencia. Então, no nosso exemplo todas as palavras seriam consideradas diferentes umas das outras.

Case-sensitive = Diferencia maiúsculo de minúsculo
Case-insensitive = Não diferencia maiúsculo de minúsculo

Transformar todas as letras do texto em maiúsculas ou minúsculas me obrigaria a mapear todos os pontos que a leitura do texto era feita. Se houvessem muitos pontos, isso exigiria muitas modificações e muitas modificações exigem muitos testes. Então no final, o que era para ser algo fácil se tornou algo, talvez, um pouco complicado.

A única opção que resta é modificar a expressão regular, mas como fazer isso ? Mapear todos os intervalos de letras com maiúsculas e minúsculas, por exemplo [a-zA-Z], não é a melhor solução, pois se a expressão for muito grande com muitos intervalos podemos ter o mesmo problema que teríamos adotando a primeira ou segunda opção. Muitas modificações e talvez alguns erros.

Através de pesquisa consegui chegar a melhor solução. Em Java, assim como em outras linguagens, a respectiva API de expressões regulares oferece uma flag para case-insensitive. Como já citei em outros posts que possuo mais intimidade com a linguagem Java, mostrarei a aplicação dessa solução nesta plataforma, mas nada impede que você ache a mesma solução na linguagem de sua preferência.

1:  import java.util.regex.Pattern;  
2:    
3:  class CaseInsensitivePattern {  
4:       public static void main(String[] args) {  
5:            //Primeira forma de aplicação através da constante provida pela própria API.  
6:            System.out.println("Case insensitive match via constant: " + Pattern.compile("^([a-z]*\\s*)*$",Pattern.CASE_INSENSITIVE).matcher("PrEcIsO eStUdAr SeMpRe").matches());  
7:            System.out.println("Case sensitive match via constant: " + Pattern.compile("^([a-z]*\\s*)*$").matcher("PrEcIsO eStUdAr SeMpRe").matches());  
8:    
9:            //Segunda forma de aplicação através de uma flag na própria regex.  
10:            System.out.println("Case insensitive match via String: " + "PrEcIsO eStUdAr SeMpRe".matches("(?i)^([a-z]*\\s*)*$"));  
11:            System.out.println("Case sensitive match via String: " + "PrEcIsO eStUdAr SeMpRe".matches("^([a-z]*\\s*)*$"));  
12:       }  
13:  }  

Note que forneci através do exemplo duas formas de executar uma expressão regular em case-insensitive. Nas linhas 6 e 7, apresento abordagens de uso da constante Pattern.CASE_INSENSITIVE, da classe Pattern, a qual simboliza que a dada expressão deve ser executada na forma configurada. Respectivamente, uma executa um case insensitive match e a outra um case sensitive match.

Nas linhas 10 e 11, utilizo uma outra abordagem. É possível embutir na própria expressão regular uma flag sinalizando que esta deve realizar uma case insensitive match. Tal é atingido através da flag (?i).

Entre essas duas abordagens apresentadas. Qual utilizar ?

Como sempre digo aqui, não existem balas de prata. Quem vai determinar a melhor solução é a sua necessidade. Talvez, para alguma situação é melhor transformar o texto para maiúsculo ou minúsculo do que modificar a regex, ou para outras situações é mais vantajoso trabalhar em cima da expressão. Contudo, para modificações na expressão, entre as duas opções apresentadas, eu ficaria com a segunda pelo motivo dessa ser mais desacoplada. Seria possível assim configurar minha expressão em um arquivo externo (txt, properties, etc.) e não precisar modificar meu programa principal. Caso algum erro aconteça, eu sei que o único ponto possível seria neste arquivo.

É possível configurar mais de uma flag nas duas abordagens, por exemplo, se é desejado executar case insensitive match em uma string que possua caracteres acentuados, ou um multiline. Por padrão a flag (?i) não cobre casos de caracteres Unicode. Para tal é necessário utilizar em conjunto a flag (?u), resultando em (?iu).

Deixarei neste post referências para outros dois posts, onde falo sobre a opção multiline e caracteres Unicode, e uma ferramenta muito boa para validação de expressões regulares.

Para baixar o código:
Link do repositório GitHub: https://github.com/PrecisoEstudarSempre/CaseInsensitivePattern.git
Link do GoogleDrive: https://drive.google.com/file/d/0BzDmhBY6luU6V2ZoSjFpUmRCYlk/view?usp=sharing
Link do Dropbox: https://www.dropbox.com/s/uv4vgwxnamteujt/CaseInsensitivePattern.rar?dl=0

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA
Leia Mais ››

quinta-feira, 27 de outubro de 2016

Avaliando blocos de texto com expressões regulares

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Como todos sabemos, a leitura tradicional de um arquivo em qualquer linguagem de programação é a criação de um ponteiro em memória para uma representação do arquivo. Após isso, é aberta uma conexão de leitura/escrita e a partir daí toda a mágica que já conhecemos acontece. Se o seu programa deseja ler ou escrever informações do ou no arquivo, ele consegue. Contudo, devemos agora nos concentrar mais no processo de leitura de arquivos.

Geralmente, ele acontece linha a linha e a linguagem de programação usada para tal tarefa oferece métodos para recuperar esta em forma de string. Com o dado em nossas mãos podemos fazer o que quiser, por exemplo: aplicar uma expressão regular, concatenar dados, realizar análises e etc. Se concentre no primeiro exemplo, a aplicação de uma expressão regular.

Este assunto aqui no blog não é nenhuma novidade, pois já estudamos em outros post diversas expressões regulares ou regexs para infinitas utilidades. Mas, e se desejássemos capturar um bloco de texto oriundo de um arquivo através delas ? Como faríamos ?

A princípio parece uma tarefa que dá um nó na cabeça, pois como já citamos nos parágrafos acima a leitura acontece linha a linha, e isso não vai mudar. Então, precisamos de uma lógica boa que consiga capturar este bloco através de várias expressões passadas para ele.

Para a solução deste problema, utilizarei mais uma vez a linguagem de programação Java pois possuo um alto nível de afinidade com ela, mas esta solução é estendível para qualquer uma.

Antes de montar o algoritmo precisamos chegar a um acordo de como será nossa estrutura de regexs. Para que um bloco inteiro, onde quem define a quantidade de linhas desse bloco é a sua necessidade, possa ser capturado, precisamos mapear como é cada linha. Então, para fins de estudos utilizaremos um arquivo XML, pois este tipo de arquivo possui uma estrutura hierárquica que neste momento nos facilita a enxergar a solução. Então, no fim teremos.

Arquivo precisoestudarsempre.xml

 precisoestudarsempre.xml  
   
 <blog>  
      <nome>Preciso Estudar Sempre</nome>  
      <email>precisoestudarsempre@gmail.com</email>  
      <descricao>Melhor blog do mundo :)</descricao>  
 </blog>  

Nossas expressões regulares:

 private final String[] arrayOfRegex = {"<nome>([a-zA-Z]+\s*)*</nome>",  
                                              "<email>.*</email>",  
                                              "<descricao>.*</descricao>"};  

IMPORTANTE: É importante deixar claro aqui que neste post não destrincharei cada regex como já fiz em outros post. Nosso foco aqui é o algoritmo e não o estudo de expressões. Deixarei no fim do post vários links para outros post aqui do blog onde já expliquei várias vezes como e o que são as expressões regulares.

Agora que já montamos o nosso arquivo e sua respectiva estrutura de regexs, já temos o necessário para construir nosso algoritmo.

 private void evaluateTextBlockRegex(BufferedReader bf){  
   try{  
     int regexCounter;  
     int lineNumber;  
     regexCounter = lineNumber = 0;  
     boolean isMatchedRegex = true;  
     Pattern pattern = null;  
             
     while (bf.ready()) {  
       String line = bf.readLine();  
       lineNumber++;          
   
       if(regexCounter == arrayOfRegex.length){  
         //só para pular linha  
         System.out.println();  
         regexCounter = 0;            
       }                  
       while (isMatchedRegex) {  
         String regex = arrayOfRegex[regexCounter];  
           
         try {  
           pattern = Pattern.compile(regex);  
           Matcher matcher = pattern.matcher(line);  
           isMatchedRegex = matcher.find();                                          
           if(isMatchedRegex){  
             //exibo a linha capturada  
             System.out.println("Linha " + lineNumber + " capturada: " + line);                
             regexCounter++;  
             break;  
           }  
         } catch (java.util.regex.PatternSyntaxException pse) {  
           //talvez que a regex não seja compilada  
           isMatchedRegex = false;  
         }  
       }          
       if(!isMatchedRegex){            
         isMatchedRegex = true;  
         regexCounter = 0;  
       }          
     }  
   } catch(java.io.IOException e){  
     System.out.println("An I/O error occurs!");  
   }  
 }  

O funcionamento dele é o seguinte: o arquivo é lido linha após linha, e para cada uma é testada sempre a primeira regex. Caso esta tenha sucesso, o contador regexCounter é incrementado e uma nova linha é carregada na variável line, e assim o algoritmo testa a segunda regex, repetindo este processo até o array de regex chegar ao seu fim. Para que um bloco de texto seja capturado a correspondência entre linhas do arquivo e expressões regulares devem ser linha a linha, ou seja, a primeira regex corresponde a primeira linha do bloco e assim sucessivamente. A figura 1 esclarece tal relacionamento.
Figura 1 - Relacionamento linha - regex
Após todas as linhas terem sido relacionados com suas respectivas regexs, regexCounter é zerado para que o aglomerado de regex procure novamente por novas correspondências. Este é necessário para que seja possível acessar a próxima expressão do array. A flag booleana isMatchedRegex é necessária pois podem existir casos onde somente algumas linhas correspondem e outras não. Quando uma que não corresponde for avaliada, a análise precisa ser reiniciada, ou seja, é iniciada mais uma vez a procura por um bloco de texto compatível.

Todo este procedimento citado neste dois últimos parágrafos se repetem até o final do arquivo.

Para um bom conhecedor de Java uma pergunta pode surgir. Porque não usar a opção multiline da classe Pattern ? Sim, é verdade, existe uma opção pronta para este tipo de avaliação. Contudo, como no nosso caso estamos recuperando texto direto de um arquivo seria necessário transformar todo o arquivo em uma única string, para depois poder usar tal artifício. Tal processo pode apresentar problemas de tamanho de memória visto que o arquivo pode ser muito grande. Um outro ponto que torna nosso algoritmo mais interessante é que ele se encaixa mais facilmente em abordagens tradicionais da leitura de arquivos. Através de pesquisa é possível coletar relatos que esta opção traz problemas para programas que operam em multiplataformas, visto que cada plataforma tem um caractere de quebra de linha próprio. Lembra que já falamos disso aqui ?

Como eu sempre digo, não existem balas de prata. Não existe uma única solução correta. Devemos medir os prós e contras, e assim tomar nossa decisão.

Bem amigos, acabamos mais um post. Espero que vocês tenham gostado.

Baixe o código-fonte
Link do GitHub: https://github.com/PrecisoEstudarSempre/EvaluateTextBlockRegex.git
Link no Dropbox: https://www.dropbox.com/sh/trgchzdjr198ja7/AABCqIPsGPe15OC43IKKxiAga?dl=0
Link no GoogleDrive: https://drive.google.com/drive/folders/0BzDmhBY6luU6ZUR1d0tXRk91QkU?usp=sharing

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA



Non-break space, já ouviu falar ? - Regex em Java - http://precisoestudarsempre.blogspot.com.br/2015/11/non-break-space-ja-ouviu-falar-regex-em.html



Leia Mais ››

domingo, 16 de outubro de 2016

O que você sabia sobre tamanhos de strings talvez não está tão certo assim.

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Inicio este post com uma pergunta. Para a string abaixo, qual seria seu tamanho ?

 joão  

Embora pareça simples, não a subestime, pois se você pensou que a resposta seria 4, talvez esteja errado. Sim, você não leu errado, esta string de fato pode não possuir tamanho 4 embora possua quatro caracteres.

Porque isso acontece ?

Antes de responder a essa pergunta, explicarei qual foi a minha motivação para escrever esse post. Uma vez trabalhei em um sistema web feito em Java que possuía um formulário HTML e em um dos campos a validação de tamanho estava acusando que estávamos enviando uma string maior que permitido. Estudando o problema, descobrimos que isso acontecia porque uma das letras possuía um acento. Agora que já contextualizamos toda situação, devemos voltar para a busca de uma resposta para a nossa pergunta.

Quando desejamos descobrir o tamanho de uma string em Java utilizamos o método length(). Se dermos uma olhada na documentação dele veremos o seguinte:
Returns the length of this string. The length is equal to the number of Unicode code units in the string.
OBSERVAÇÃO: A linguagem Java está sendo usado neste post como uma forma dar corpo ao estudo do nosso problema e consequentemente da solução dele. Tal situação também pode estar ser encontrada em outras linguagens.

Então, o método length() não trabalha da forma que pensamos. Ele não conta caracteres, e sim Unicode code units. Como o próprio nome já diz, eles são unidades de códigos Unicode e quem dita o tamanho de cada unidade dessa é o tipo de encoding usado.

Um encoding é uma forma de representação de uma caractere. Cada tipo possui definições diferentes, onde nestas constam os caracteres que são aceitos e suas respectivas posições na tabela ASCII. No nosso problema o que acontecia era que o encoding type utilizado no envio do texto do browser para o servidor não aceitava caracteres com acentos.

Um dos encoding type mais conhecidos e utilizados é o UTF-8, onde ele define que um Unicode code point que vai de 0 à 127 na tabela ASCII é armazenado em uma code unit de 8 bits, e os que estão acima disso podem ser armazenados em 2, 3 ou até 6 bytes. Sua fama se deve ao fato de ele aceitar caracteres com acentos.

Note que agora introduzimos um novo elemento no nosso estudo, o code point. Na terminologia de encoding um code point é qualquer valor numérico que compõe o espaço de um código. O esquema de encoding de caracteres ASCII compreende 128 code points, o Extended ASCII define 256 code points e o Unicode compreende 1114112 code points. Neste último, um code point é representado visualmente pelo símbolo U+ seguido de uma representação hexadecimal do caractere.

A solução para problemas como este é sempre definir o encoding type do seu IO, seja ela uma página HTML, um arquivo, ou algum outro tipo de stream. Um exemplo claro da falta de definição de encoding type é quando você recebe aquele spam chinês ou indiano e quando vai abrir aparecem várias caixinhas ou pontos de interrogação. Um teste que pode ser feito em casa é criar uma página HTML qualquer, não definir o enconding da página e por um texto com acentos. Quando você for abrir essa página em seu browser notará que no lugar dos caracteres com acentos, aparecerão caracteres estranhos. Isto acontece devido ao fato do browser não saber como ele deve processar aquele texto, então ele processa da forma que ele bem achar correto.

Se você quiser entender mais da história do Unicode, recomendo fortemente a leitura do post "The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!)". Vale a pena a leitura.

Talvez você tenha notado que nos primeiros parágrafos eu disse que a string em questão podia não ter tamanho 4. Em algumas ocasiões ela pode apresentar tamanho 5. Isso se tornou uma grande curiosidade que me estimulou para obter mais respostas para a construção deste post. Faça o seguinte teste:

Crie uma classe Java com o mesmo conteúdo abaixo, compile e rode este programa pelo cmd do windows.

 class StringLength {  
      public static void main(String[] args) {            
           String s = "joão";  
           System.out.println("Nossa string:" + s);  
           System.out.println("O tamanho(length) da nossa string: " + s.length());  
      }       
 }  

Para compilar e rodar o programa pelo cmd utilize os seguintes comandos:

 javac StringLength.java                        //para compilar  
 java StringLength                             //para executar  

Acredito que o resultado será algo desse tipo.

Figura 1 - Resultado do primeiro teste
Quando me deparei com este resultado fiquei me perguntando duas coisas: porque a string apareceu com os caracteres quebrados e porque o length é 5 ?? Através de muita pesquisa consegui a resposta para a primeira pergunta. O code page default da console do windows é o Multilingual (encoding Latin I) e possui o código 850, então caímos no mesmo problema que estudamos acima. Este code page não consegue processar caracteres com acentos. Então devemos mudar para o code page 65001 (UTF-8), através do comando chcp 65001.
Figura 2 - Resultado do segundo teste
Agora para piorar mais ainda nossa situação, crie uma classe Java com o código acima em um projeto do Eclipse IDE. Se o seu resultado foi o mesmo que o meu você também deve estar com a mesma dúvida.
Figura 3 - Resultado do terceiro teste
PORQUE OS LENGTHS DAS STRING SÃO DIFERENTES SE O CÓDIGO JAVA É O MESMO ?

Bem, eu ainda não tenho a resposta para esta pergunta, por isso conto com vocês. Se puderem me ajudar, deixe nos comentários a resposta para este problema. A minha opinião é que a IDE leva em conta o encoding type padrão do Java (UTF-16) na exibição em seu console interno e o console do windows não leva, mas isso é a minha opinião. Quero ouvir a de vocês.

Link do GitHub: https://github.com/PrecisoEstudarSempre/StringLength.git

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/

Referências:

The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!) - http://www.joelonsoftware.com/articles/Unicode.html

What is a Unicode code unit and a Unicode code point - https://coderanch.com/t/416952/java/java/Unicode-code-unit-Unicode-code

Documentação da classe String - https://docs.oracle.com/javase/7/docs/api/java/lang/String.html

Documentação oficial Unicode - http://www.unicode.org/versions/Unicode9.0.0/ch03.pdf#G7404

Unicode and .NET - http://csharpindepth.com/Articles/General/Unicode.aspx

encodings - different result between codePointCount and length - http://stackoverflow.com/questions/20162239/encodings-different-result-between-codepointcount-and-length

Comando Chcp - https://technet.microsoft.com/pt-br/library/bb490874.aspx

What encoding/code page is cmd.exe using - http://stackoverflow.com/questions/1259084/what-encoding-code-page-is-cmd-exe-using

What is the character encoding of String in Java? - http://stackoverflow.com/questions/4453269/what-is-the-character-encoding-of-string-in-java

Code Page Identifiers - https://msdn.microsoft.com/pt-br/library/windows/desktop/dd317756(v=vs.85).aspx
Leia Mais ››

sábado, 1 de outubro de 2016

Desenvolvi o WriteYourOwnGraph

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Vou começar esse post com uma ótima notícia. Desenvolvi uma ferramenta gratuita para o desenvolvimento de grafos.
Figura 1 - A reação de vocês

Meu planejamento para esta primeira versão dessa nova empreitada é disponibilizar o código construído no GitHub e depois transformá-lo em uma ferramenta web, onde você de qualquer parte do mundo possa acessar, construir seu grafo e exportar ele em forma de imagem, HTML, etc.

Mas da onde veio a motivação para construir o WriteYourOwnGraph ? Como tudo começou ? Muito tempo atrás estudei para uma prova de certificação de HTML 5 e acabei me dando mal, mas derrotas para um outro dia. Um dia lembrei que a especificação do HTML 5 possui diversas novas APIs e uma delas é para a criação de desenhos vetoriais, chamada SVG. Com ela é possível a criação de inúmeras formas geométricas. Agora, tudo o que eu precisava saber era como construir nós e arestas com ela. Para minha sorte, tais elementos se resumem a pequenas circunferências e linhas retas, respectivamente. Então, só o que eu precisava fazer era estudar a especificação da API e tudo ganharia forma.

Feito isso, a ferramenta WriteYourOwnGraph nasceu e adquiriu sua humilde versão 1.0 finalizada com sucesso. Pelo fato de ter sido construída com HTML 5, Javascript + JQuery e CSS é rápida e não é necessário instalar nada para executá-la na sua máquina, só basta o seu navegador. Então, é com muita felicidade que lhes apresento a primeira ferramenta desenvolvida pelo blog Preciso Estudar Sempre para o estudo e construção de grafos.
Figura 2 - Nossa que maravilha
Para executar a ferramenta, abra a página graph.html.

Se você usou e sentiu falta de algo, por favor não poupe palavras e escreva tudo o que pensa nos comentários. Faça parte da evolução.

Para baixar o código-fonte, clique aqui.

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Lista de figuras:
Figura 1 -  http://i.giphy.com/5Zesu5VPNGJlm.gif
Figura 2 - http://i.giphy.com/k7xgyFqsruqqc.gif
Leia Mais ››

quarta-feira, 17 de agosto de 2016

A criação de Donald Shell, o algoritmo ShellSort

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Em 1959, o cientista Donald Shell descobriu algo que mudaria para sempre o mundo. Nesta data, foi descoberto o algoritmo de ordenação conhecido como ShellSort. Ele tem como base um outro algoritmo já visto aqui no blog, o InsertionSort. Clique aqui para dar uma olhada, caso você não conheça.
Figura 1 - Donald L. Shell
A ordenação de Shell é boa para vetores de tamanho médio, talvez com até alguns milhares de itens, dependendo da particular implementação. Não é tão rápido quanto QuickSort (veremos aqui um dia) e outras ordenações O(N*logN), portanto, não é ótima para grandes massas de dados. Contudo, é muito mais rápida que as ordenações O(N²) como o SelectionSort (também não vimos ainda) e InsertionSort. O desempenho no pior caso não é muito pior que o do médio caso. Sua implementação é fácil, tornando seu código curto e simples. (Lafore R.)

O algoritmo citado como base do algoritmo ShellShort possui um problema: cópias demais. Imagine uma situação, onde em um conjunto um pequeno item está bem à direita, onde os itens grandes devem estar. Para mover esse pequeno item para seu devido lugar à esquerda, todos os itens intermediários, ou seja, os do meio desse intervalo, tem que ser deslocados em um espaço para a direita. Esse passo consome cerca de N cópias, apenas para um item. Nem todos os itens tem que ser movidos em N espaço completos, mas o item médio tem que ser movido em N/2 espaços, que tem N*N/2 deslocamentos para um total de N²/2 cópias. Logo, o desempenho dessa ordenação é O(N²) e isto é um grande problema. (Lafore R.)

E se existisse alguma forma de mover os itens menores para a esquerda sem mover os maiores para à direita ? Se sim, seria tal solução possível ?

Sim, é possível e é aqui onde a ordenação Shell ganha espaço. Seu segredo não é ordenar de forma direta como a ordenação Bolha faz, mas sim deixar o vetor quase ordenado para que a ordenação por inserção termine o trabalho. Mas como ele faz isso ?

Para que ele possa criar um vetor quase ordenado, ele precisa criar antes sub-vetores ordenados, os quais são independentes entre si. Tais são gerados através do uso de espaçamento entre elementos, também conhecido como incremento, e é normalmente conhecido pela letra h. Neste momento nossa cabeça com certeza se enche com mais dúvidas, pois ainda não temos idéia de como é esse espaçamento e como ele é gerado.

Figura 2 - Criação dos sub-vetores através do uso da técnica de espaçamento
Vamos entrar depois nos detalhes de como o espaçamento é gerado. Por enquanto, vamos definir que nosso h é 4, representado no passo 1. Note que no passo adiante, passo 2, três elementos são marcados pela cor vermelha no vetor e a distância entre eles é justamente o valor de h. Após marcados, o sub-conjunto ou sub-vetor é criado, e já pode ser ordenado através da troca de lugar de seus elementos, assim o passo 3 é representado. Este processo de marcação, criação do sub-vetor e ordenação se repete por todo o vetor, de tal forma que após o primeiro sub-conjunto ter sido finalizado todas as posições anteriormente marcados são acrescidas de uma casa à direita. Tal processo termina quando não existem mais elementos no vetor para formar sub-conjuntos, e assim, ganha vida os passos 4, 5, 6, 7 e 8.

Note que alguns sub-vetores não precisaram sofrer ordenação visto que, pela ordem natural de seus elementos eles já estavam ordenados entre si, e que alguns sub-conjuntos somente possuem dois elementos. Isto acontece pelo fato de que se contarmos quatro casas iniciando do último elemento marcado iremos ultrapassar o tamanho do vetor, logo se referindo a uma posição que não existe.

Contudo, e se o nosso vetor aumentasse de tamanho ? Nosso h continuaria sendo 4 ? E antes de pensarmos nisso, quem sugeriu este valor para esta variável ? Foi achismo ou fundamentado ? Bolacha ou biscoito ?

Se você acha que o valor 4 foi atribuído para h por um simples chute meu, não queria te dizer mas você está enganado. Tal foi gerado através da seguinte fórmula recursiva: h = 3*h + 1, onde inicialmente h=1 e, é conhecida como sequência de intervalo ou lacuna. A particular sequência mostrada é atribuída a Knuth (Lafore R.). É importante ressaltar que existem outras abordagens para geração da sequência de intervalos, mas nesta implementação do algoritmo de ordenação Shell utilizaremos essa.

No algoritmo de ordenação, a fórmula que gera a sequência é usada primeiro em um laço curto para descobrir o intervalo inicial. O valor 1 é usado para o primeiro valor de h e a fórmula já apresentada é aplicada para gerar a sequência 1,4,13,40,121,364, etc. Esse processo termina quando o intervalo se torna maior que o vetor. Para um vetor com 1000 elementos, o sétimo número da sequência, 1093, é grande demais. Assim, começamos o processo de ordenação com o sexto número maior, criando uma ordenação em 364. Então, a cada vez no laço externo da rotina de ordenação, reduzimos o intervalo usando o inverso da fórmula dada anteriormente: h = (h-1) / 3. (Lafore R.)

Essa fórmula inversa gera a sequência inversa 364,121,40,13,4,1. Começando com 364, cada um desses números é usado para a ordenação do vetor. Quando o vetor tiver sido ordenado em 1, o algoritmo terá terminado. (Lafore R.)

Antes de analisarmos o algoritmo uma última pergunta ainda não foi respondida. Porque a ordenação Shell é muito mais rápida que a ordenação por inserção na qual ele é baseada ? Quando h é grande, o número de itens por passagens (trocas) é pequeno e os itens se movem em longas distâncias (como visto acima). Isto é muito eficiente. Quando h fica menor, o número de itens por passagem aumenta, mas os itens já estão mais próximos de suas posições ordenadas finais, o que é mais eficiente para a ordenação por inserção. É a combinação dessas tendências que torna a ordenação Shell tão eficiente.(Lafore R.)

Eis nossa implementação em Java.

1:  private void shellSort(int[] array){  
2:       int begInterv, endInterv, h=1, temp;            
3:         
4:       while(h<=nElems/3){  
5:            h = h*3 +1;  
6:       }  
7:         
8:       while(h>0){  
9:            for (endInterv = h; endInterv < array.length; endInterv++) {  
10:                 temp = array[endInterv];  
11:                 begInterv = endInterv;  
12:                   
13:                 while (begInterv > h-1 && array[begInterv-h] >= temp) {  
14:                      array[begInterv] = array[begInterv-h];  
15:                      begInterv -= h;  
16:                 }  
17:                 array[begInterv] = temp;  
18:            }  
19:            h = (h-1)/3;  
20:       }  
21:  }  

Alguns pontos que valem a pena dar atenção.

Linha 4 até 6: Cria as partições baseado na sequência de intervalos de Knuth.
Linha 13 até 17: Algoritmo Insertion Sort já visto outrora.
Linha 13: O h-1 representa o fim do intervalo, e inner-h o valor dentro do intervalo.
Linha 15: Decrementa para percorrer outros intervalos.
Linha 19: Isto é feito para diminuir o tamanho das partições até chegar a 1.

Um mistério reside em torno da eficiência dessa ordenação, pois somente em casos especiais é possível averiguar tal. Com base em experimentos, existem várias estimativas que variam de O(N3/2)a O(N7/6), onde Nx/y representa a raiz y de N elevado a X, ou y√Nx . Assim se N for 100, N3/2 será a raiz quadrada de 1003, que é 1000. (Lafore R.)

E assim adicionamos mais um algoritmo para o nosso canivete de algoritmos de ordenação. Se você não sabe do que estou falando, dê uma clicada aqui e fique por dentro.

Para baixar o projeto utilize um dos links abaixo.

Link do Dropbox: https://www.dropbox.com/sh/8d5em1y1j9upke0/AAAvLf_sPeS4HRSBPH6YNHfra?dl=0
Link do GoogleDrive: https://drive.google.com/folderview?id=0BzDmhBY6luU6aThjTmx3OXNlUnM&usp=sharing

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.

E-mail: precisoestudarsempre@gmail.com

Referências
Lafore R.; ESTRUTURAS DE DADOS E ALGORITMOS EM JAVA; 2004

Figuras:
Figura 1 - http://goodnewsmag.org/wp-content/uploads/2015/11/shell2.jpg
Figura 2 - Criação própria
Leia Mais ››

quarta-feira, 6 de julho de 2016

Entrando em várias realidades com recursividade

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Você já viu o filme "Inception" ou, em português "A Origem" ?
Figura 1 - Filme Inception
Tá .... você que acompanha o blog deve estar se perguntando porque eu estou falando sobre esse filme, se o nosso foco aqui é outro.

Calma !!! Não viramos um blog de cinema, mas recomendo fortemente que você veja esse filme.

Se você viu, sabe que ele é bom, mas se não, fique tranquilo pois não darei spoilers. O filme trata sobre pessoas que conseguem sonhar e dentro deles, conseguem sonhar novamente. Resumidamente, eles sonham que estão sonhando e podem fazer isso de infinitamente.

Mas então ... o que isso tem haver conosco ? Onde isso se encaixa ?
Existe uma técnica de programação que utiliza esse mesmo conceito.
Sim, você não leu errado, e não, não iremos criar programas que são capazes de sonhar, pois caso fizéssemos a Skynet seria uma realidade.

Essa técnica se chama recursividade.
Figura 2 - Cena do filme Exterminador do futuro
A recursividade é algo mágico na computação. Ela nos permite abordar problemas de uma forma completamente diferente, mas deve ser usada com sabedoria, pois como já discutimos aqui, não existem balas de prata. Devemos saber quando e onde aplicar nossos novos conhecimentos.

Na computação existe uma técnica para abordar problemas, conhecida como "dividir para conquistar". Ela define que para um problema P muito grande, onde não é possível resolvê-lo de uma vez só, devemos dividi-lo por 2. Se essas metades (P/2) ainda forem grandes, devemos dividi-los novamente por 2, gerando P/4. Esse processo deve ser repetido até o momento em que o problema se torne pequeno o bastante para poder ser resolvido. A partir disso, a mesma solução é aplicada para todas as partículas geradas.

Mas o que determina quando devemos parar de dividir o problema ?

O caso base de uma solução recursiva é a parte responsável por essa tarefa. Toda abordagem recursiva deve possuir um caso base, pois caso contrário um loop infinito seria gerado. Contudo, como é possível construir um programa com tais características ?

Para que um algoritmo possa ter a inteligência recursiva, ele precisa implementar o seu caso base e para a divisão do problema, ele deve realizar chamadas a si mesmo. Porém, isso não soa errado? Como um método ou função vai se chamar ?

Ao contrário do que a maioria pensa, uma chamada à um método ou função é nada mais que uma transferência de controle de um método de origem para um de destino. No caso de uma chamada recursiva, é uma transferência para o seu próprio início.

Vamos analisar o seguinte exemplo !

Você quer criar um programa que calcule fatoriais para números inteiros positivos. É sabido que o fatorial de um número é a multiplicação dele por seus antecessores e que o fatorial de 0 é 1. Logo, 5! (lê-se cinco fatorial) é igual a 5 * 4 * 3 * 2 * 1, por exemplo.

No nosso programa não podemos engessar nossas soluções. Devemos ser capazes de receber um número e retornar seu fatorial, mas como fazer isso se não sabemos qual número será ? Contudo, se pararmos para pensar, chegamos a conclusão que um fatorial de um número n é igual a n multiplicado pelo fatorial de (n-1). Logo, é possível afirmar que 5! = 5 * 4!.

Mas, qual é o valor de 4! ? Utilizando o mesmo conceito, sabemos que 4! = 4 * 3!. Então, quando paramos ? Qual é o número que não precisa ser multiplicado pelo seu antecessor para que saibamos seu fatorial ? A resposta é clara, o número procurado é o 0. Acabamos de estabelecer o nosso caso base. Cada problema que pode ser resolvido de forma recursiva tem o seu. Cabe a você analisar e encontrá-lo.

Já podemos montar o nosso algoritmo recursivo, pois já sabemos quando devemos dividir o problema e quando devemos parar.

1:  public int fatRecursive(int valor){  
2:       if(valor == 0){  
3:            return 1;  
4:       }  
5:       return valor * fatRecursive(valor-1);  
6:  }  

Note que na linha cinco multiplicamos a variável valor pela chamada recursiva de fatRecursive, a qual recebe como parâmetro valor-1. Para que possamos entender melhor como nosso método funciona, vamos chamar essa primeira execução de e1. A partir da chamada, uma nova execução é feita, começando do início, gerando e2. Lembre-se que e1 ainda não terminou. Ela ainda está presa na linha cinco, pois está esperando e2 terminar.

A partir de e2 é gerado e3, e dessa forma são geradas outras execuções até o nosso caso base ser atingido. No momento em que é alcançado, as execuções que outrora estavam indo para frente agora voltam pelo caminho que fizeram e a última execução desbloqueia sua anterior, ou seja, se a última execução era e5, ela desbloqueia e4, que desbloqueia e3 e esse processo é repetido até e1, finalizando assim a execução completa do programa.

Agora que já temos total entendimento de como uma lógica recursiva funciona, nós devemos refletir sobre a seguinte questão: é possível resolver um problema recursivo com laços de repetição ? Alguns problemas sim mas, outros não.

Para o problema acima, poderíamos ter utilizado o seguinte código.

1:  public int fatNonRecursive(int valor){  
2:       int valorFat=1;  
3:       for (int i=1; i<=valor; i++) {  
4:            valorFat = valorFat * i;  
5:       }  
6:       return valorFat;  
7:  }  

E aí !? Qual usar ?

Como eu disse anteriormente, não existem balas de prata. Não existe maneira alguma de afirmar que a recursão é melhor que os laços de repetição, ou vice e versa. Cada abordagem tem suas características. Como nosso exemplo é algo bem simples, para fins de estudo, não justifica o uso da recursividade. A recursão é geralmente usada porque simplifica um problema conceitualmente, não porque é mais eficiente. Utilizá-la resulta em overhead, visto que várias chamadas ao mesmo método são feitas, causando assim uma lentidão se comparada à abordagem com laços (Lafore R.).

Deixo aqui disponível para download outros exemplos de algoritmos recursivos, são eles:

  • Algoritmo de potenciação numérica
  • Algoritmo para geração de palavras ao contrário
  • Algoritmo para solução do problema das torres de Hanoi
  • Algoritmo para cálculo de fatoriais

Vale a pena dar uma olhada.

Link do Dropbox: https://www.dropbox.com/s/cwwe0cr0idzaprn/AlgoritmosRecursivos.zip?dl=0
Link do GoogleDrive:https://drive.google.com/file/d/0BzDmhBY6luU6WVFkQUhTY3h6aHc/view?usp=sharing

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, me mande um e-mail ou, na nossa página do facebook.

E-mail: precisoestudarsempre@gmail.com

Referências
Lafore R.; ESTRUTURAS DE DADOS E ALGORITMOS EM JAVA; 2004

Imagens:
Leia Mais ››