Programa Java WordIdder -- java campo con time-limit-exceeded campo con edit-distance camp codereview Relacionados El problema

Java WordLadder Program


7
vote

problema

Español

Escribí un programa que calcula el número mínimo de peldaños de una "escalera de palabras" entre una palabra inicial y una palabra final. La función minlinks() toma en 3 argumentos: una lista que actúa como un diccionario, una palabra inicial y una palabra final. Devuelve un int[] de dos valores; El primero es el número mínimo de enlaces en la palabra Ladder, el segundo es el número de rutas con dicho número de enlaces.

Ejemplo de una escalera de palabras:

palabras = [lluvia, ruina, ganancia, sonrisa, grano, principal, dolor, par, cubo, correo] de = navegar a = ruip

Devoluciones: [6, 2]

Hay dos enlaces de longitud seis y no hay enlaces más cortos.

Correo de vela Ruina de lluvia principal RuiP
Pail de vela dolor lluvia ruina ruip

según lo escrito, el programa funciona. Sin embargo, como alguien nuevo en la codificación en Java, apreciaría a otros comentarios sobre el estilo de codificación. Además, incluyí un caso de prueba en el método principal que se ejecuta en aproximadamente 4 segundos en mi computadora, que es demasiado lento. ¿Hay alguna manera de optimizar este programa para que funcione más rápido?

  import java.util.*; public class WordLinksMin {      // Helper method, returns true if two words are one letter away from each other.     public boolean isStep(String from, String s) {         if (from.length() != s.length()) {             return false;         }         int differences = 0;         for (int charIndex = 0; charIndex < from.length(); charIndex++) {             if (from.charAt(charIndex) != s.charAt(charIndex)) {                 differences++;             }             if(differences > 1) break;         }         return (differences == 1);     }      // given an array of words (our "dictionary"), the starting word and the ending word. find the minimum number of links between start and end using the given dictionary.     // function returns int[] array {min number of links, number of paths with min number of links}     public int[] minLinks(String[] words, String start, String end) {         int firstFindSize = 0;         int[] result = new int[2];         // Convert String[] into a HashSet.         List < String > myWordList = new ArrayList < String > (Arrays.asList(words));         Set < ArrayDeque < String >> allStacks = new HashSet < ArrayDeque < String >> ();         if (myWordList.size() == 0) return result;         // We will implement BFS with a stack of queues         ArrayDeque < ArrayDeque < String >> wordQueue = new ArrayDeque < ArrayDeque < String >> (); //one queue of stacks to track nodes visited         // initialize the parent node, which is a stack containing starting word.         ArrayDeque < String > startStack = new ArrayDeque < String > ();         startStack.push(start);         wordQueue.add(startStack);         // we act differently in while loop based on whether we have already found a path from start to end         boolean firstFind = true;          while (!wordQueue.isEmpty()) {              ArrayDeque < String > currentStack = wordQueue.pop();              String currentWord = currentStack.peek();             if (isStep(currentWord, end) && currentStack.size() >= 2 && firstFind) { //no direct link                 currentStack.push(end);                 allStacks.add(currentStack);                 firstFind = false; //after finding first stack, we know the stack size we must look for, for any other path of the same length.                 firstFindSize = currentStack.size();                 //System.out.println((firstFindSize));                 //System.out.println("before ff");                 //System.out.println(currentStack);              } else if (isStep(currentWord, end) && currentStack.size() == firstFindSize - 1 && !firstFind) {                 currentStack.push(end);                 //System.out.println("not ff");                 //System.out.println(currentStack);                 allStacks.add(currentStack);             }              if (firstFind) {                 for (String word: myWordList) {                     if (isStep(currentWord, word) && !currentStack.contains(word)) {                         ArrayDeque < String > wordStack = new ArrayDeque < String > (currentStack);                         wordStack.push(word);                         wordQueue.add(wordStack);                     }                 }             }         }          result[1] = allStacks.size();         result[0] = firstFindSize;         System.out.printf("%d %d", result[0], result[1]);         return result;     }      public static void main(String[] args) {         WordLinksMin a = new WordLinksMin();         String[] b = {                 "abcde", "abcda", "abcdb", "abcdc", "abcdd", "abcdf", "abcdg", "abcdh", "abcdi", "abcdj", "abcdk", "obcda", "obcdb", "obcdc", "obcdd", "obcdf", "obcdg", "obcdh", "obcdi", "obcdj", "obcdk", "obcdm", "obadm", "obbdm", "obddm", "obedm", "obfdm", "obgdm", "obhdm", "obidm", "objdm", "obkdm", "okadm", "okbdm", "okddm", "okedm", "okfdm", "okgdm", "okhdm", "okidm", "okjdm", "okkdm", "okodm", "okokm"          };         long startTime = System.nanoTime();         System.out.println(a.minLinks(b, "abode","okoko"));         long endTime = System.nanoTime();         long duration = (endTime - startTime);         System.out.println(duration);         //      for (List<String> list : a.listOfPaths){         //          for (String s : list) {         //              System.out.print(s+" ");         //          }         //          System.out.println();         //      }     } }   
Original en ingles

I wrote a program that calculates the minimum number of rungs of a "word ladder" between a starting word and an ending word. The function minlinks() takes in 3 arguments: a list which acts as a dictionary, a starting word, and an ending word. It returns an int[] of two values; the first is minimum number of links in the word ladder, the second is the number of paths with said number of links.

Example of a word ladder:

words = [rain, ruin, gain, grin, grit, main, pain, pair, pail, mail] from = sail to = ruip

Returns: [6, 2]

There are two links of length six and no shorter links.

sail mail main rain ruin ruip
sail pail pain rain ruin ruip

As written, the program works. However, as someone new to coding in Java, I would appreciate others commenting on the coding style. Also, I included a test case in the main method which runs in about 4 seconds on my computer, which is too slow. Is there any way to optimize this program to make it run faster?

import java.util.*; public class WordLinksMin {      // Helper method, returns true if two words are one letter away from each other.     public boolean isStep(String from, String s) {         if (from.length() != s.length()) {             return false;         }         int differences = 0;         for (int charIndex = 0; charIndex < from.length(); charIndex++) {             if (from.charAt(charIndex) != s.charAt(charIndex)) {                 differences++;             }             if(differences > 1) break;         }         return (differences == 1);     }      // given an array of words (our "dictionary"), the starting word and the ending word. find the minimum number of links between start and end using the given dictionary.     // function returns int[] array {min number of links, number of paths with min number of links}     public int[] minLinks(String[] words, String start, String end) {         int firstFindSize = 0;         int[] result = new int[2];         // Convert String[] into a HashSet.         List < String > myWordList = new ArrayList < String > (Arrays.asList(words));         Set < ArrayDeque < String >> allStacks = new HashSet < ArrayDeque < String >> ();         if (myWordList.size() == 0) return result;         // We will implement BFS with a stack of queues         ArrayDeque < ArrayDeque < String >> wordQueue = new ArrayDeque < ArrayDeque < String >> (); //one queue of stacks to track nodes visited         // initialize the parent node, which is a stack containing starting word.         ArrayDeque < String > startStack = new ArrayDeque < String > ();         startStack.push(start);         wordQueue.add(startStack);         // we act differently in while loop based on whether we have already found a path from start to end         boolean firstFind = true;          while (!wordQueue.isEmpty()) {              ArrayDeque < String > currentStack = wordQueue.pop();              String currentWord = currentStack.peek();             if (isStep(currentWord, end) && currentStack.size() >= 2 && firstFind) { //no direct link                 currentStack.push(end);                 allStacks.add(currentStack);                 firstFind = false; //after finding first stack, we know the stack size we must look for, for any other path of the same length.                 firstFindSize = currentStack.size();                 //System.out.println((firstFindSize));                 //System.out.println("before ff");                 //System.out.println(currentStack);              } else if (isStep(currentWord, end) && currentStack.size() == firstFindSize - 1 && !firstFind) {                 currentStack.push(end);                 //System.out.println("not ff");                 //System.out.println(currentStack);                 allStacks.add(currentStack);             }              if (firstFind) {                 for (String word: myWordList) {                     if (isStep(currentWord, word) && !currentStack.contains(word)) {                         ArrayDeque < String > wordStack = new ArrayDeque < String > (currentStack);                         wordStack.push(word);                         wordQueue.add(wordStack);                     }                 }             }         }          result[1] = allStacks.size();         result[0] = firstFindSize;         System.out.printf("%d %d", result[0], result[1]);         return result;     }      public static void main(String[] args) {         WordLinksMin a = new WordLinksMin();         String[] b = {                 "abcde", "abcda", "abcdb", "abcdc", "abcdd", "abcdf", "abcdg", "abcdh", "abcdi", "abcdj", "abcdk", "obcda", "obcdb", "obcdc", "obcdd", "obcdf", "obcdg", "obcdh", "obcdi", "obcdj", "obcdk", "obcdm", "obadm", "obbdm", "obddm", "obedm", "obfdm", "obgdm", "obhdm", "obidm", "objdm", "obkdm", "okadm", "okbdm", "okddm", "okedm", "okfdm", "okgdm", "okhdm", "okidm", "okjdm", "okkdm", "okodm", "okokm"          };         long startTime = System.nanoTime();         System.out.println(a.minLinks(b, "abode","okoko"));         long endTime = System.nanoTime();         long duration = (endTime - startTime);         System.out.println(duration);         //      for (List<String> list : a.listOfPaths){         //          for (String s : list) {         //              System.out.print(s+" ");         //          }         //          System.out.println();         //      }     } } 
        

Lista de respuestas

2
 
vote
vote
La mejor respuesta
 
  1. sobre el algoritmo en sí. No entiendo completamente el algoritmo que está utilizando ahora, pero se ve bastante extraño (¡un BFS con una pila de colas?) Y, como ha dicho, es ineficiente. Así que vamos a rediseñarlo:

    • Comencemos con una declaración de problema clara en términos de gráficos: dado un gráfico donde cada nodo corresponde a una palabra y hay un borde bidireccional entre dos nodos IFF, las palabras difieren en una carta exactamente, encuentre la ruta más corta entre dos nodos y el número de caminos más cortos.

    • Antes de ejecutar la primera búsqueda de amplias, vamos a construir la gráfica explícitamente y olvídenos de las palabras. Podemos hacer simplemente revisar cada pares de palabras como lo hace ahora.

    • Ahora vamos a ejecutar un BFS en este gráfico y obtener la longitud del camino más corto.

    • ¿Cómo encontrar el número de tales caminos? Tenemos la siguiente fórmula: f(v) = sum f(u) for all u such that dist[u] = dist[v] - 1 y f(start) = 1 . Podemos calcularlo de manera eficiente utilizando la memorización.

    • La complejidad del tiempo es O(len * N ^ 2) , donde 9988776655544333 es la longitud de las palabras y 9988776655544334 es su número. Debe ser muy rápido para un diccionario tan pequeño si se implementa correctamente.

  2. El método minLinks parece demasiado grande para mí. Teniendo en cuenta un nuevo algoritmo descrito en 1., lo haría de esta manera:

    • Crear tres métodos separados: uno para construir el gráfico, otro para ejecutar la primera búsqueda de amplias y la última para contar el número de ruta más corta.

    • Podemos ir aún más lejos y crear una clase de gráfico separada para que esta clase tenga que construir solo un gráfico apropiado. Definitivamente es bueno para la reutilización del código y tiene un buen sentido desde el punto de vista de diseño: una nueva búsqueda de gráficos y amplitud es una noción muy general y casi no tiene nada que ver con las palabras.

Resumen: ambos 1. y 2. Exprese la misma idea (desde diferentes puntos de vista): podemos representar este problema como un problema de gráfico utilizando conceptos de gráficos y algoritmos estándar y separarlos de las palabras para lograr un mejor rendimiento y un mejor diseño .

 
  1. About the algorithm itself. I do not fully understand the algorithm you are using now, but it looks pretty strange(a bfs with a stack of queues?) and, as you have said, it is inefficient. So let's redesign it:

    • Let's start with a clear problem statement in terms of graphs: given a graph where each node corresponds to a word and there is a bidirectional edge between two nodes iff the words differ in exactly one letter, find the shortest path between two nodes and the number of shortest paths.

    • Before running the breadth-first search, let's build the graph explicitly and forget about the words. We can do by simply checking each pairs of words as you do it now.

    • Now let's run a BFS on this graph and get the length of the shortest path.

    • How to find the number of such paths? We have the following formula: f(v) = sum f(u) for all u such that dist[u] = dist[v] - 1 and f(start) = 1. We can compute it efficiently using memoization.

    • The time complexity is O(len * N ^ 2), where len is the length of the words and N is their number. It should be very fast for such a small dictionary if implemented properly.

  2. The minLinks method seems too big to me. Taking into account a new algorithm described in 1., I'd do it this way:

    • Create three separate methods: one for building the graph, another one for running the breadth-first search and the last one for counting the number of shortest path.

    • We can go even further and create a separate graph class so that this class has to only build an appropriate graph. It is definitely good for code reuse and makes a good sense from the design point of view: a graph and breadth-first search is a very general notion and it has almost nothing to do with words.

Summary: both 1. and 2. express the same idea(from different point of views): we can represent this problem as a graph problem using standard graph concepts and algorithms and separate it from words to achieve better performance and better design.

 
 
 
 

Relacionados problema

5  Comparando dos algoritmos de coincidencia de cadena aproximada en Java  ( Comparing two approximate string matching algorithms in java ) 
Descripción del problema Dado un texto $ t [0..n) $, un patrón $ P [0..M) $, y un no negativo INTEGER $ K $, informe todas las posiciones $ J en [...

3  Dalerau Levenshtein Implementación en Kotlin  ( Damerau levenshtein implementation in kotlin ) 
Esta es una implementación de la distancia Damerau-Levenshtein en Kotlin, que creé como un ejercicio, pero también podría ser útil, si demuestra ser correcto....

2  Comparando largas listas de cadenas para la coincidencia más cercana  ( Comparing long lists of strings for the closest match ) 
¿Qué es lo más rápido (la calidad es importante, pero una forma poco menos importante) de comparar dos cadenas? Estoy buscando la forma más eficiente de com...

3  Iterar en gran cantidad de palabras en Python  ( Iterate over large amount of words in python ) 
Escribí un programa que debe revisar un diccionario que contiene unos 50000 diccionarios. En esos diccionarios, una de las teclas tiene una lista de palabras ...

3  Entidades coincidentes en SQL Server para reemplazar el guión iterativo de Python  ( Matching entities in sql server to replace iterative python script ) 
Tengo una base de datos SQL (MS SQL Server) de ~ 22 millones de empresas (llamado target_db en mi código). Por ejemplo: +-----------------------+--------...

2  Nombre-deduplicando clase  ( Name deduplicating class ) 
Recientemente, hice una pregunta sobre la programación SE sobre Métodos públicos vs privados para pruebas de la unidad , que generaron muchas respuestas inte...

25  Algoritmo para transformar una palabra a otra a través de palabras válidas  ( Algorithm to transform one word to another through valid words ) 
He estado practicando retroceso y quería saber cómo puedo mejorar mi código. Por ejemplo, no quiero usarlo global. Además, no estoy seguro de si mi código fun...

2  Una secuencia de errores  ( A sequence of mistakes ) 
Esta pregunta es parte de una serie que resuelve la Rosalind desafíos. Para la pregunta anterior en esta serie, consulte el código genético . El repositor...

2  Escriba un programa de corrección de tipográficos con algoritmo de distancia Levenshtein  ( Write a typo correction program with levenshtein distance algorithm ) 
Estoy construyendo un programa de corrección de tipografía. Esta es la función, que calcula la distancia Levenshtein entre dos palabras (una palabra de diccio...

2  Editar distancia entre 2 cuerdas  ( Edit distance between 2 strings ) 
He escrito un programa que calcula el "costo" de transformar una cadena en otra. Me gustaría que lo revises. public class EditDistance { public static...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos