Hola Habr! Aprenda cómo implementar algoritmos eficientes basados en las estructuras de datos más importantes en el lenguaje Java, y cómo medir el rendimiento de estos algoritmos. Cada capítulo va acompañado de ejercicios para ayudar a consolidar el material.
- Aprenda a trabajar con estructuras de datos, por ejemplo, con listas y diccionarios, entienda cómo funcionan.
- Escriba una aplicación que lea páginas de Wikipedia, analice y proporcione navegación a través del árbol de datos resultante.
- Analice el código y aprenda a predecir qué tan rápido funcionará y cuánta memoria consumirá.
- Escriba clases que implementen la interfaz Map y use una tabla hash y un árbol de búsqueda binario.
- Cree un motor de búsqueda web simple con su propio motor de búsqueda: indexará páginas web, guardará su contenido y devolverá los resultados deseados.
Extracto "Caminata por el árbol"
En este capítulo, veremos una aplicación de motor de búsqueda que desarrollaremos a lo largo del resto del libro. Yo (el autor) describo los elementos de un motor de búsqueda y presento la primera aplicación, un robot de búsqueda que descarga y analiza páginas de Wikipedia. Este capítulo también presenta una implementación de búsqueda profunda recursiva y una implementación iterativa usando Deque de Java para implementar una pila de "último en entrar, primero en salir".
Buscadores
Un motor de búsqueda como Google Search o Bing acepta un conjunto de términos de búsqueda y devuelve una lista de páginas web que son relevantes para estos términos.
Puede leer más en
thinkdast.com , pero le explicaré lo que necesita a medida que
avanza .
Considere los componentes principales de un motor de búsqueda.
- Recolección de datos (rastreo). Necesitará un programa que pueda cargar una página web, analizarla y extraer texto y cualquier enlace a otras páginas.
- Indexación Necesitamos un índice que nos permita encontrar una consulta de búsqueda y las páginas que la contienen.
- Búsqueda (recuperación). Necesita una forma de recopilar resultados del índice y determinar las páginas que son más relevantes para los términos de búsqueda.
Comencemos con el robot de búsqueda. Su propósito es detectar y cargar un conjunto de páginas web. Para los motores de búsqueda como Google y Bing, el desafío es encontrar todas las páginas web, pero a menudo estos robots se limitan a un dominio más pequeño. En nuestro caso, solo leeremos páginas de Wikipedia.
Como primer paso, crearemos un robot de búsqueda que lea la página de Wikipedia, encuentre el primer enlace, vaya a otra página y repita los pasos anteriores. Utilizaremos este motor de búsqueda para probar la hipótesis de llegar a la filosofía. Dice:
"Al hacer clic en el primer enlace en minúscula en el texto principal del artículo de Wikipedia y luego repetir esta acción para los artículos posteriores, lo más probable es que lo lleven a una página con un artículo sobre filosofía".
Puede
ver esta hipótesis y su historia en
thinkdast.com/getphil .
Probar una hipótesis le permitirá crear las partes principales de un robot de búsqueda sin necesidad de omitir todo Internet o incluso toda Wikipedia. ¡Y creo que este ejercicio es bastante interesante!
En varios capítulos, trabajaremos en el indexador y luego pasaremos al motor de búsqueda.
Análisis HTML
Cuando carga una página web, su contenido se escribe en el Lenguaje de marcado de hipertexto (HTML). Por ejemplo, el siguiente es un documento HTML simple:
<!DOCTYPE html> <html> <head> <title>This is a title</title> </head> <body> <p>Hello world!</p> </body> </html>
Frases Este es un título y ¡Hola mundo! ("¡Hola, mundo!"): El texto que realmente aparece en la página; otros elementos son etiquetas que indican cómo se debe mostrar el texto.
Al cargar una página, nuestro robot necesita analizar el código HTML para extraer texto y encontrar enlaces. Para hacer esto, usaremos jsoup, una biblioteca Java de código abierto diseñada para cargar y analizar (analizar) HTML.
El resultado del análisis HTML es un árbol DOM (Modelo de objeto de documento) que contiene elementos de documento, incluidos texto y etiquetas.
Un árbol es una estructura de datos relacionada que consta de vértices que representan texto, etiquetas y otros elementos de un documento.
La relación entre los vértices está determinada por la estructura del documento. En el ejemplo anterior, el primer nodo, llamado raíz, es una etiqueta que incluye enlaces a los dos vértices que contiene y; Estos nodos son hijos del nodo raíz.
Un nodo tiene un vértice hijo y un nodo tiene un vértice hijo
(párrafo, del inglés. párrafo). En la fig. 6.1 es una representación gráfica de este árbol.
Cada vértice incluye enlaces a sus nodos secundarios; Además, cada nodo contiene un enlace a su padre, por lo que puede subir y bajar el árbol desde cualquier nodo. El árbol DOM para páginas reales suele ser más complejo que el ejemplo descrito.
La mayoría de los navegadores tienen herramientas para verificar el DOM de la página que está viendo. En Chrome, puede hacer clic con el botón derecho en cualquier parte de la página web y seleccionar el elemento Ver código en el menú que aparece. En Firefox, puede hacer clic con el botón derecho y seleccionar Explorar elemento en el menú contextual. Safari proporciona la herramienta Web Inspector, que se encuentra en
thinkdast.com/safari . Las instrucciones para Internet Explorer se pueden leer haciendo clic en el enlace:
thinkdast.com/explorer .
En la fig. La Figura 6.2 muestra una captura de pantalla del árbol DOM para la página de Wikipedia sobre
Java . El elemento resaltado es el primer párrafo del cuerpo del artículo, que está contenido en el elemento <div> con id = "mw-content-text". Usaremos este identificador de elemento para determinar el cuerpo de cada artículo que carguemos.
Aplicación Jsoup
La biblioteca jsoup facilita cargar y analizar páginas web y navegar por el árbol DOM. Por ejemplo:
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");
El elemento Jsoup.connect acepta la URL como una cadena y establece una conexión con el servidor web; El método get carga el código HTML, lo analiza y devuelve un objeto Document, que es un DOM.
Este objeto incluye métodos para navegar por un árbol y seleccionar nodos. De hecho, proporciona tantos métodos que puede ser confuso. El siguiente ejemplo muestra dos formas de seleccionar nodos.
- getElementByld toma un parámetro de tipo de cadena y busca un árbol para el elemento con el campo de identificación correspondiente. Una vez encontrado, selecciona el nodo <div id = "mw-content-text" lang = "en" dir = "ltr" class = "mw-content-ltr"> que aparece en cada página de Wikipedia para identificar el elemento Un <div> que contiene el cuerpo de la página, a diferencia de la barra de navegación lateral y otros elementos.
- select toma una cadena, atraviesa el árbol y devuelve todos los elementos con etiquetas que coinciden con la cadena. En este ejemplo, devuelve todas las etiquetas de párrafo que aparecen en el contenido. El valor de retorno es un objeto de tipo Elementos.
Antes de continuar, debe revisar la documentación de estas clases para saber qué acciones pueden realizar. Las clases más importantes son Elemento, Elementos y Nodo, sobre los cuales puede leer haciendo clic en los
enlaces thinkdast.com/jsoupelt ,
thinkdast.com/jsoupelts y
thinkdast.com/jsoupnode .
La clase Node es la parte superior del árbol DOM. Hay varias subclases que extienden Node, incluyendo Element, TextNode, DataNode y Comment. La clase Elements es una colección de objetos de tipo Element.
En la fig. 6.3 es un diagrama de las clases UML que muestra las relaciones entre ellas. Una línea con una flecha vacía indica la extensión de una clase a otra. Por ejemplo, este gráfico indica que Elements extiende ArrayList. Volveremos a los diagramas de clase UML en la sección del mismo nombre en el Capítulo 11.
Iterar sobre un árbol DOM
Para hacerte la vida más fácil, proporciono una clase WikiNodelterable que te permite caminar a través del árbol DOM. El siguiente es un ejemplo que muestra cómo usar esta clase:
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 ejemplo comienza con el momento en que se detuvo el anterior. Selecciona el primer párrafo en párrafos y luego crea una clase WikiNodeIterable que implementa la interfaz Iterable. Esta clase busca en profundidad, creando nodos en el orden en que aparecen en la página.
En el ejemplo actual, mostramos Node solo si es un TextNode e ignoramos sus otros tipos, en particular, los objetos de tipo Element que representan etiquetas. El resultado es un texto de párrafo HTML sin ningún marcado. Su conclusión:
Java es un lenguaje de programación de computadora de propósito general que es concurrente, basado en clases, orientado a objetos [13] y específicamente diseñado ...
Java es un lenguaje de programación de computadora universal, que es un lenguaje orientado a objetos basado en clases, con la posibilidad de programación paralela [13] y está especialmente diseñado ...
Búsqueda de profundidad
Hay varias formas de atravesar inteligentemente un árbol. Comenzamos con una búsqueda de profundidad primero (DFS). La búsqueda comienza con la raíz del árbol y selecciona el primer nodo secundario. Si este último tiene hijos, el primer nodo hijo se selecciona nuevamente. Cuando aparece un pico sin hijos, debe regresar, moviendo el árbol hacia el nodo principal, donde se selecciona el próximo hijo, si lo hay. De lo contrario, debe volver de nuevo. Cuando se examina el último nodo raíz secundario, se completa el recorrido.
Hay dos formas generalmente aceptadas de implementar una búsqueda en profundidad: recursiva e iterativa. La implementación recursiva es simple y 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 se llama para cada nodo en el árbol, comenzando en la raíz. Si Node es un TextNode, se imprime su contenido. Si Node tiene hijos, llama a recursiveDFS para cada uno de ellos en orden.
En el ejemplo actual, imprimimos el contenido de cada TextNode antes de visitar sus nodos secundarios, es decir, este es un ejemplo de recorrido directo (pre-orden). Puede leer acerca de las
soluciones directas, inversas (post-orden) y simétricas (en orden) en el enlace
thinkdast.com/treetrav . Para esta aplicación, el orden de rastreo no importa.
Al
realizar llamadas recursivas, recursiveDFS utiliza la pila de llamadas (consulte
thinkdast.com/callstack ) para rastrear los vértices secundarios y procesarlos en el orden correcto. Alternativamente, puede usar la estructura de datos de la pila para seguir los nodos usted mismo; Esto evitará la recursividad e iterará sobre el árbol de forma iterativa.
Pilas en Java
Antes de explicar la versión iterativa de la búsqueda en profundidad, miraré la estructura de datos de la pila. Comenzamos con el concepto general de la pila, y luego hablamos de dos interfaces Java que definen los métodos de la pila: Stack y Deque.
Una pila es una estructura de datos tipo lista: es una colección que mantiene el orden de los elementos. La principal diferencia entre la pila y la lista es que la primera incluye menos métodos. Por convención, la pila proporciona métodos:
- empujar, agregando un elemento a la parte superior de la pila;
- pop, que realiza la eliminación y devuelve el valor del elemento superior de la pila;
- echar un vistazo, devolviendo el elemento superior de la pila sin cambiar la pila en sí;
- isEmpty, que indica si la pila está vacía.
Como pop siempre devuelve el elemento superior, la pila también se llama LIFO, que significa "último en entrar, primero en salir". Una alternativa a la pila es una cola que devuelve elementos en el mismo orden en que se agregaron, es decir, "primero en entrar, primero en salir" o FIFO.
A primera vista, no está claro por qué las pilas y las colas son útiles: no proporcionan ninguna característica especial que no se pueda obtener de las listas; de hecho, tienen aún menos oportunidades. Entonces, ¿por qué no aplicar listas siempre? Hay dos razones para justificar las pilas y las colas.
1. Si se limita a un pequeño conjunto de métodos (es decir, una pequeña API), su código será más legible y menos propenso a errores. Por ejemplo, cuando usa una lista para representar una pila, puede eliminar accidentalmente un elemento en el orden incorrecto. Con la API de pila, tal error es literalmente imposible. Y la mejor manera de evitar errores es hacerlos imposibles.
2. Si la estructura de datos proporciona una API pequeña, entonces es más fácil de implementar de manera eficiente. Por ejemplo, una manera simple de implementar una pila es usar una sola lista. Empujando un elemento en la pila, lo agregamos a la parte superior de la lista; haciendo estallar un elemento, lo eliminamos desde el principio. Para una lista vinculada, agregar y eliminar desde el principio es una operación de tiempo constante, por lo que esta implementación es efectiva. Por el contrario, las API grandes son más difíciles de implementar de manera eficiente.
Hay tres formas de implementar la pila en Java.
1. Aplicar ArrayList o LinkedList. Al usar ArrayList, debe recordar agregar y eliminar del final para que estas operaciones se realicen en tiempo constante. Evite agregar elementos al lugar incorrecto o eliminarlos en el orden incorrecto.
2. Java tiene una clase de pila que proporciona un conjunto estándar de métodos de pila. Pero esta clase es una parte antigua de Java: es incompatible con el Java Collections Framework, que apareció más tarde.
3. Probablemente, la mejor opción es utilizar una de las implementaciones de la interfaz Deque, por ejemplo ArrayDeque.
Deque se forma a partir de una cola de doble extremo, que significa "cola de dos vías". En Java, la interfaz Deque proporciona métodos push, pop, peek e isEmpty, por lo que puede usarse como una pila. Contiene otros métodos, cuya información está disponible en
thinkdast.com/deque , pero por ahora no los utilizaremos.
Búsqueda de profundidad iterativa
La siguiente es una versión iterativa de DFS que usa ArrayDeque para representar una pila de objetos de tipo Nodo:
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); } } }
El parámetro raíz es la raíz del árbol que queremos omitir, por lo que comenzamos creando una pila y agregando este parámetro.
El ciclo continúa hasta que la pila esté vacía. Cada pase empuja a Nodo fuera de la pila. Si se recibe un TextNode, se imprime su contenido. Luego, los vértices secundarios se agregan a la pila. Para procesar descendientes en el orden correcto, debe empujarlos a la pila en el orden inverso; esto se realiza copiando los vértices secundarios en una ArrayList, reorganizando los elementos en su lugar y luego iterando la ArrayList invertida.
Una de las ventajas de la versión en profundidad de la búsqueda en profundidad es que es más fácil de implementar como Iterator en Java; cómo hacerlo se describe en el próximo capítulo.
Pero primero, una nota final sobre la interfaz de Deque: además de ArrayDeque, Java proporciona otra implementación de Deque, nuestro viejo amigo LinkedList. Este último implementa ambas interfaces: List y Deque. La interfaz resultante depende de su uso. Por ejemplo, al asignar un LinkedList a una variable Deque:
Deqeue<Node> deque = new LinkedList<Node>();
Puede aplicar métodos desde la interfaz Deque, pero no todos los métodos desde la interfaz Lista. Al asignarlo a la Lista variable:
List<Node> deque = new LinkedList<Node>();
puede usar los métodos de Lista, pero no todos los métodos de Deque. Y asignándolos de la siguiente manera:
LinkedList<Node> deque = new LinkedList<Node>();
Todos los métodos pueden ser utilizados. Pero al combinar métodos de diferentes interfaces, el código será menos legible y más propenso a errores.
»Se puede encontrar más información sobre el libro en
el sitio web del editor»
Contenidos»
Extracto20% de descuento en cupones para fermentadores de
Java -
Java