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 ››

segunda-feira, 20 de junho de 2016

Minha monografia

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

Como prometido no post anterior, vou falar aqui um pouco sobre a minha monografia e disponibilizar todo o material que recolhi para a sua construção, juntamente com ela no formado PDF.

Mas, acho que é importante discutir uma questão antes jogar os links para download.

Porque falar sobre minha monografia aqui no blog, se a missão dele não é essa ? Isso não é um pouco de auto-promoção ?

Bem, auto-promoção é de fato, até porque estarei falando aqui sobre um trabalho que eu desenvolvi, logo isso se torna óbvio. Contudo, acho que mesmo sendo uma auto-promoção ainda está alinhado com a missão do blog.

A missão que temos aqui é propagar o conhecimento e, em parte deixar nossa marca no mundo, por mais que seja bem pequena. Quando eu venho falar de algo que eu fiz, ainda estou espalhando conhecimento mas, agora, o foco não estará em trabalhos de terceiros e sim, no meu.

Se você não se sente confortável com esse formato, eu entendo. Mas, se você está e quer saber mais sobre o que eu fiz, por favor entre e sente-se, pois vamos começar agora.

O meu trabalho consiste em um estudo comparativo de técnicas para prevenção de erros de ponteiro nulo. Se você não sabe o que é um erro de ponteiro nulo ou uma Null Pointer Exception, dê uma bela clicada aqui.

Escolhi esse tema porque gosto de assuntos mais voltados para a área de compiladores (costumo dizer que são assuntos mais undergrounds) e, tenho uma certa atração por esse tipo específico de erro. Essa atração é explicada pela forma que esse erro é gerado, a lógica de programação empregada pelo programador.

Então, para prever onde esse erro pode acontecer, foram desenvolvidas ferramentas para realizar esse trabalho. Uma das mais conhecidas é a FindBugs, desenvolvida pela Universidade de Maryland.

Recomendo muito o uso dela.

Cada uma delas emprega um certo tipo de técnica para inferir os locais onde podem ocorrer os erros de ponteiro nulo. O meu trabalho compara duas dessas técnicas, explicando-as e posteriormente, realizando testes e comparando seus resultados.

Para atingir a conclusão dele foram necessários 4 meses de pesquisa e muitas noites mal dormidas.

Dividi ele em cinco etapas:
  1. Introdução: Aqui eu contextualizei o trabalho, para que o leitor possa entender onde ele se encaixa e de qual realidade ele nasceu.
  2. Fundamentação teórica: Explico toda a teoria necessária que possamos entender como as técnicas das ferramentas funcionam.
  3. O estudo comparativo: Explico e detalho o experimento que farei tendo como apoio todo o conhecimento reunido nas seções anteriores.
  4. Resultados: Apresento os resultados da seção anterior.
  5. Conclusão: Apresento a conclusão e dou sugestões para trabalhos futuros.
Figura 1 - Eu e o meu trabalho
Agradeço todo o apoio de meus amigos, familiares e a vocês, meus queridos leitores. Sem vocês nada disso seria possível.

Links para download
Google Drive: https://drive.google.com/file/d/0BzDmhBY6luU6OUMzVXRvejQtX1E/view?usp=sharing
Dropbox: https://www.dropbox.com/s/dz37xpwjvz3cbv9/Minha%20monografia.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

Figuras
Figura 1 - acervo próprio
Leia Mais ››

quarta-feira, 1 de junho de 2016

Ausência, monografia e novidades

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

Hoje temos que conversar !

Na verdade, quero falar com vocês sobre a minha ausência no período Março até Maio. Primeiramente, peço desculpas pela falta de posts e pelo fato de apresentar uma justificativa só agora (01/06). Mas, tudo isso aconteceu devido à minha pós-graduação.

Durante esses meses eu precisei focar totalmente na minha monografia, para conseguir terminar meu MBA em Engenharia de Software pela UFRJ. Esse trabalho vem tomando o meu tempo desde de Janeiro, mas ele só aflorou em Março pois, foi o início do prazo para a montagem do trabalho.

Várias horas de pesquisa e de sono mal dormido foram necessárias para que eu atingisse o resultado que queria e entregasse o trabalho.

Valeu a pena tanto esforço ? Não dava para entregar algo mais enxugado e simples ?

Sim, valeu a pena cada segundo investido e entregar algo inferior não era uma opção. No fim, acabei ficando satisfeito com o que foi entregue, pois para o período de tempo que eu tinha, ou seja, 2 meses, consegui entregar algo bom e equilibrado.

Estou escrevendo esse texto para vocês, porque acho que é, de fato, minha obrigação dar essa explicação. Afinal de contas, vocês me acompanham, não estou sozinho aqui. Pretendo voltar ao meu ritmo normal e fazer o que gosto: estudar, escrever, jogar meu playstation 3 e malhar.

Pretendo fazer um post exclusivo sobre o meu trabalho na pós-graduação, habilitando para download minha monografia, no formato PDF, e todo o material teórico que recolhi. Quero explicar um pouco a vocês o que eu fiz, e caso alguém tenha conhecimento na área, sinta-se a vontade para abrir uma discussão sobre o assunto.

Também trago novidades !!!

Resolvi virar Youtuber !!
Figura 1 - HUE HUE BR

Andei pensando muito e cheguei a conclusão que investir vídeos para alguns dos nossos posts, vai ser uma boa. Acho que vai melhorar a nossa experiência. Alguns assuntos são muito extensos para serem lidos e esse formato tem ganhado espaço na internet. Cada vez mais pessoas postam vídeos, então porque nós não podemos estudar de forma divertida via vídeo ?

Aproveito o jabá e já deixo aqui o link para o canal, clique aqui ou dê uma olhada lá no final do post.

Se inscreva e dê laike !

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 ››