Olá Habr! Aprenda como implementar algoritmos eficientes com base nas estruturas de dados mais importantes da linguagem Java e como medir o desempenho desses algoritmos. Cada capítulo é acompanhado de exercícios para ajudar a consolidar o material.
- Aprenda a trabalhar com estruturas de dados, por exemplo, com listas e dicionários, entenda como eles funcionam.
- Escreva um aplicativo que leia páginas da Wikipedia, analise e forneça navegação pela árvore de dados resultante.
- Analise o código e aprenda como prever com que rapidez ele funcionará e quanta memória consumirá.
- Escreva classes que implementem a interface Map e use uma tabela de hash e uma árvore de pesquisa binária.
- Crie um mecanismo de pesquisa na web simples com seu próprio mecanismo de pesquisa: ele indexará as páginas da web, salvará seu conteúdo e retornará os resultados desejados.
Trecho "Caminhada na Árvore"
Neste capítulo, examinaremos um aplicativo de mecanismo de pesquisa que desenvolveremos ao longo do restante do livro. Eu (o autor) descrevo os elementos de um mecanismo de pesquisa e apresento o primeiro aplicativo, um robô de pesquisa que baixa e analisa páginas da Wikipedia. Este capítulo também apresenta uma implementação recursiva de pesquisa profunda e uma implementação iterativa usando o Deque de Java para implementar uma pilha de "último a entrar, primeiro a sair".
Motores de busca
Um mecanismo de pesquisa como o Google Search ou Bing aceita um conjunto de termos de pesquisa e retorna uma lista de páginas da Web que são relevantes para esses termos.
Você pode ler mais em
thinkdast.com , mas vou explicar o que você precisa à medida que avança.
Considere os principais componentes de um mecanismo de pesquisa.
- Coleta de dados (rastreamento). Você precisará de um programa que possa carregar uma página da web, analisá-la e extrair texto e links para outras páginas.
- Indexação Precisamos de um índice que permita encontrar uma consulta de pesquisa e as páginas que a contêm.
- Pesquisa (recuperação). Você precisa de uma maneira de coletar resultados do índice e determinar as páginas que são mais relevantes para os termos de pesquisa.
Vamos começar com o robô de pesquisa. Seu objetivo é detectar e carregar um conjunto de páginas da web. Para mecanismos de pesquisa como Google e Bing, o desafio é encontrar todas as páginas da Web, mas geralmente esses robôs são limitados a um domínio menor. No nosso caso, leremos apenas páginas da Wikipedia.
Como primeiro passo, criaremos um robô de pesquisa que lê a página da Wikipedia, encontra o primeiro link, vai para outra página e repete as etapas anteriores. Usaremos esse mecanismo de pesquisa para testar a hipótese Como chegar à filosofia. Diz:
"Ao clicar no primeiro link em minúscula no texto principal do artigo da Wikipedia e, em seguida, repetir essa ação para os artigos subseqüentes, é mais provável que você seja direcionado para uma página com um artigo sobre filosofia".
Você pode
ver esta hipótese e sua história em
thinkdast.com/getphil .
Testar uma hipótese permitirá que você crie as principais partes de um robô de pesquisa sem precisar ignorar a Internet inteira ou até a Wikipedia inteira. E acho que este exercício é bastante interessante!
Em vários capítulos, trabalharemos no indexador e depois seguiremos para o mecanismo de pesquisa.
Análise de HTML
Quando você carrega uma página da Web, seu conteúdo é gravado na HTML (HyperText Markup Language). Por exemplo, o seguinte é um documento HTML simples:
<!DOCTYPE html> <html> <head> <title>This is a title</title> </head> <body> <p>Hello world!</p> </body> </html>
Frases Este é um título e Olá, mundo! ("Olá, mundo!") - o texto que realmente aparece na página; outros elementos são tags indicando como o texto deve ser exibido.
Ao carregar uma página, nosso robô precisa analisar o código HTML para extrair texto e encontrar links. Para fazer isso, usaremos o jsoup, uma biblioteca Java de código aberto projetada para carregar e analisar (analisar) HTML.
O resultado da análise de HTML é uma árvore DOM (Document Object Model) contendo elementos do documento, incluindo texto e tags.
Uma árvore é uma estrutura de dados relacionada que consiste em vértices que representam texto, tags e outros elementos de um documento.
A relação entre os vértices é determinada pela estrutura do documento. No exemplo anterior, o primeiro nó, chamado raiz, é uma tag que inclui links para os dois vértices que ele contém e; esses nós são filhos do nó raiz.
Um nó tem um vértice filho e um nó tem um vértice filho
(parágrafo, do inglês. parágrafo). Na fig. 6.1 é uma representação gráfica desta árvore.
Cada vértice inclui links para seus nós filhos; além disso, cada nó contém um link para seu pai, para que você possa mover para cima e para baixo na árvore a partir de qualquer nó. A árvore DOM para páginas reais geralmente é mais complexa que o exemplo descrito.
A maioria dos navegadores possui ferramentas para verificar o DOM da página que você está visualizando. No Chrome, você pode clicar com o botão direito do mouse em qualquer parte da página da web e selecionar o item Ver código no menu exibido. No Firefox, você pode clicar com o botão direito do mouse e selecionar Explorar Item no menu de contexto. O Safari fornece a ferramenta Web Inspector, localizada em
thinkdast.com/safari . Instruções para Internet Explorer pode ser encontrada clicando no link:
thinkdast.com/explorer .
Na fig. A Figura 6.2 mostra uma captura de tela da árvore DOM da página da Wikipedia sobre
Java . O elemento destacado é o primeiro parágrafo do corpo do artigo, que está contido no elemento <div> com id = "mw-content-text". Usaremos esse identificador de elemento para determinar o corpo de cada artigo que enviarmos.
Aplicativo Jsoup
A biblioteca jsoup facilita o carregamento e a análise de páginas da web e a navegação na árvore do DOM. Por exemplo:
String url = "http://en.wikipedia.org/wiki/Java_(programming_language)"; // Connection conn = Jsoup.connect(url); Document doc = conn.get(); // Element content = doc.getElementById("mw-content-text"); Elements paragraphs = content.select("p");
O elemento Jsoup.connect aceita a URL como uma sequência e estabelece uma conexão com o servidor da Web; O método get carrega o código HTML, o analisa e retorna um objeto Document, que é um DOM.
Este objeto inclui métodos para navegar em uma árvore e selecionar nós. De fato, ele fornece tantos métodos que podem ser confusos. O exemplo a seguir demonstra duas maneiras de selecionar nós.
- getElementByld pega um parâmetro do tipo string e procura uma árvore para o elemento com o campo de ID correspondente. Após encontrá-lo, ele seleciona o nó <div id = "mw-conteúdo-texto" lang = "en" dir = "ltr" class = "mw-conteúdo-ltr"> que aparece em cada página da Wikipedia para identificar o elemento Um <div> contendo o corpo da página, diferente da barra de navegação lateral e de outros elementos.
- select pega uma String, percorre a árvore e retorna todos os elementos com tags correspondentes à String. Neste exemplo, ele retorna todas as tags de parágrafo que aparecem no conteúdo. O valor retornado é um objeto do tipo Elementos.
Antes de continuar, você deve revisar a documentação dessas classes para saber quais ações elas podem executar. As classes mais importantes são Element, Elements e Node, sobre as quais você pode ler clicando nos
links thinkdast.com/jsoupelt ,
thinkdast.com/jsoupelts e
thinkdast.com/jsoupnode .
A classe Node é a parte superior da árvore DOM. Existem várias subclasses que estendem o Node, incluindo Element, TextNode, DataNode e Comment. A classe Elements é uma coleção de objetos do tipo Element.
Na fig. 6.3 é um diagrama das classes UML mostrando os relacionamentos entre elas. Uma linha com uma seta vazia indica a extensão de uma classe para outra. Por exemplo, este gráfico indica que o Elements estende o ArrayList. Voltaremos aos diagramas de classe UML na seção com o mesmo nome no Capítulo 11.
Iterar sobre uma árvore DOM
Para facilitar sua vida, eu forneço uma classe WikiNodelterable que permite percorrer a árvore DOM. A seguir, um exemplo que mostra como usar esta classe:
Elements paragraphs = content.select("p"); Element firstPara = paragraphs.get(0); Iterable<Node> iter = new WikiNodeIterable(firstPara); for (Node node: iter) { if (node instanceof TextNode) { System.out.print(node); } }
Este exemplo começa com o momento em que o anterior parou. Ele seleciona o primeiro parágrafo em parágrafos e depois cria uma classe WikiNodeIterable que implementa a interface Iterable. Esta classe pesquisa em profundidade, criando nós na ordem em que aparecem na página.
No exemplo atual, exibimos Node apenas se for um TextNode e ignoramos seus outros tipos, em particular, objetos do tipo Element que representam tags. O resultado é um texto de parágrafo HTML simples, sem nenhuma marcação. Sua conclusão:
Java é uma linguagem de programação de computador de uso geral simultânea, baseada em classe, orientada a objetos [13] e projetada especificamente ...
Java é uma linguagem universal de programação de computadores, que é uma linguagem orientada a objetos baseada em classes, com a possibilidade de programação paralela [13] e é especialmente projetada ...
Pesquisa em profundidade
Existem várias maneiras de atravessar inteligentemente uma árvore. Começamos com uma pesquisa profunda (DFS). A pesquisa começa com a raiz da árvore e seleciona o primeiro nó filho. Se o último tiver filhos, o primeiro nó filho será selecionado novamente. Quando um pico sem filhos aparece, é necessário retornar, movendo a árvore para o nó pai, onde o próximo filho é selecionado, se houver. Caso contrário, você precisará retornar novamente. Quando o último nó raiz filho é examinado, a travessia é concluída.
Existem duas maneiras geralmente aceitas de implementar a pesquisa aprofundada: recursiva e iterativa. A implementação recursiva é simples e elegante:
private static void recursiveDFS(Node node) { if (node instanceof TextNode) { System.out.print(node); } for (Node child: node.childNodes()) { recursiveDFS(child); } }
Este método é chamado para todos os nós da árvore, iniciando na raiz. Se Nó for um TextNode, seu conteúdo será impresso. Se o Node tiver filhos, ele chamará recursiveDFS para cada um deles em ordem.
No exemplo atual, imprimimos o conteúdo de cada TextNode antes de visitar seus nós filhos, ou seja, este é um exemplo de passagem direta (pré-encomenda). Você pode ler sobre
soluções alternativas diretas, reversas (pós-encomenda) e simétricas (em ordem) acessando o link
thinkdast.com/treetrav . Para este aplicativo, a ordem de rastreamento não importa.
Ao
fazer chamadas recursivas, o recursiveDFS usa a pilha de chamadas (consulte
thinkdast.com/callstack ) para rastrear vértices filhos e processá-los na ordem correta. Como alternativa, você pode usar a estrutura de dados da pilha para rastrear nós; isso evitará recursão e iterará sobre a árvore iterativamente.
Pilhas em Java
Antes de explicar a versão iterativa da pesquisa em profundidade, examinarei a estrutura de dados da pilha. Começamos com o conceito geral da pilha e depois falamos sobre duas interfaces Java que definem os métodos da pilha: Stack e Deque.
Uma pilha é uma estrutura de dados do tipo lista: é uma coleção que mantém a ordem dos elementos. A principal diferença entre a pilha e a lista é que a primeira inclui menos métodos. Por convenção, a pilha fornece métodos:
- push, adicionando um elemento ao topo da pilha;
- pop, que executa a remoção e retorna o valor do elemento mais alto da pilha;
- espiar, retornando o elemento superior da pilha sem alterar a própria pilha;
- isEmpty, que indica se a pilha está vazia.
Como o pop sempre retorna o elemento superior, a pilha também é chamada de LIFO, que significa "último a entrar, primeiro a sair". Uma alternativa para a pilha é uma fila que retorna itens na mesma ordem em que foram adicionados, ou seja, “primeiro a entrar, primeiro a sair” ou FIFO.
À primeira vista, não está claro por que as pilhas e filas são úteis: elas não fornecem nenhum recurso especial que não pôde ser obtido das listas; de fato, eles têm ainda menos oportunidades. Então, por que não aplicar listas sempre? Há dois motivos para justificar pilhas e filas.
1. Se você se limitar a um pequeno conjunto de métodos (ou seja, uma pequena API), seu código ficará mais legível e menos propenso a erros. Por exemplo, ao usar uma lista para representar uma pilha, você pode excluir acidentalmente um item na ordem errada. Com a API da pilha, esse erro é literalmente impossível. E a melhor maneira de evitar erros é torná-los impossíveis.
2. Se a estrutura de dados fornecer uma API pequena, será mais fácil implementá-lo com eficiência. Por exemplo, uma maneira simples de implementar uma pilha é usar uma única lista. Empurrando um item para a pilha, o adicionamos ao topo da lista; popping um elemento, nós o removemos desde o início. Para uma lista vinculada, adicionar e remover desde o início é uma operação de tempo constante; portanto, essa implementação é eficaz. Por outro lado, APIs grandes são mais difíceis de implementar com eficiência.
Existem três maneiras de implementar a pilha em Java.
1. Aplique ArrayList ou LinkedList. Ao usar o ArrayList, lembre-se de adicionar e remover do final para que essas operações sejam executadas em tempo constante. Evite adicionar itens ao local errado ou excluí-los na ordem errada.
2. Java possui uma classe Stack que fornece um conjunto padrão de métodos de pilha. Mas essa classe é uma parte antiga do Java: é incompatível com o Java Collections Framework, que apareceu mais tarde.
3. Provavelmente, a melhor opção é usar uma das implementações da interface Deque, por exemplo, ArrayDeque.
Deque é formado a partir de uma fila dupla, o que significa "fila de mão dupla". Em Java, a interface Deque fornece métodos push, pop, peek e isEmpty, para que possa ser usada como uma pilha. Ele contém outros métodos, informações disponíveis em
thinkdast.com/deque , mas por enquanto não os usaremos.
Pesquisa de profundidade iterativa
A seguir está uma versão iterativa do DFS que usa ArrayDeque para representar uma pilha de objetos do tipo Node:
private static void iterativeDFS(Node root) { Deque<Node> stack = new ArrayDeque<Node>(); stack.push(root); while (!stack.isEmpty()) { Node node = stack.pop(); if (node instanceof TextNode) { System.out.print(node); } List<Node> nodes = new ArrayList<Node>(node. chiidNodesQ); Collections.reverse(nodes); for (Node child: nodes) { stack.push(chiid); } } }
O parâmetro root é a raiz da árvore que queremos ignorar, então começamos criando uma pilha e adicionando esse parâmetro a ela.
O loop continua até que a pilha esteja vazia. Cada passagem empurra o Node para fora da pilha. Se um TextNode for recebido, seu conteúdo será impresso. Em seguida, vértices filhos são adicionados à pilha. Para processar descendentes na ordem correta, você precisa empurrá-los para a pilha na ordem inversa; isso é feito copiando os vértices filhos para um ArrayList, reorganizando os elementos no local e repetindo o ArrayList revertido.
Uma das vantagens da versão detalhada da pesquisa detalhada é que é mais fácil implementar como um iterador em Java; como fazer isso é descrito no próximo capítulo.
Mas primeiro, uma observação final sobre a interface do Deque: além do ArrayDeque, o Java fornece outra implementação do Deque, nosso velho amigo LinkedList. O último implementa as duas interfaces: List e Deque. A interface resultante depende do seu uso. Por exemplo, ao atribuir um LinkedList a uma variável Deque:
Deqeue<Node> deque = new LinkedList<Node>();
Você pode aplicar métodos da interface Deque, mas nem todos os métodos da interface List. Atribuindo-o à variável List:
List<Node> deque = new LinkedList<Node>();
você pode usar os métodos de lista, mas nem todos os métodos de Deque. E atribuí-los da seguinte forma:
LinkedList<Node> deque = new LinkedList<Node>();
todos os métodos podem ser usados. Porém, ao combinar métodos de diferentes interfaces, o código será menos legível e mais suscetível a erros.
»Mais informações sobre o livro podem ser encontradas no
site do editor»
Conteúdo»
Trecho20% de desconto no cupom para
Java Fermenters -
Java