Matching Patrones de consulta con cadenas previamente almacenadas -- ++ campo con beginner campo con time-limit-exceeded camp codereview Relacionados El problema

Matching query patterns with previously stored strings


8
vote

problema

Español

Descripción del programa

El objetivo de este programa es obtener un número, que es el número de líneas de insumos (le llamamos a ese número N) que el programa recibirá. Luego, las siguientes n líneas constarán de dos partes, primero un carácter que es 't' o 'm'. La siguiente parte será una cadena que sea un poco diferente para 'T' y 'M'. Si el char es 't', entonces la cadena consistirá en los siguientes caracteres: '-', '+' y '0'. Si el primer carácter en la línea de entrada es 'M', la siguiente cadena puede consistir en los siguientes caracteres: '-', '+', '0' y '?'.

Cuando la línea comienza con una 't', entonces se almacenará la cadena. Lo almacano en una matriz y las entradas estarán numeradas de 1 a la cantidad de entradas.

Cuando la línea comienza con una 'M', entonces la cadena se comparará con la lista de cadenas que se almacenan para averiguar cuál de ellos coincida con ellos.

El programa saldrá luego después de que cada línea de entrada comenzó con 'M' El número asociado con la cadena almacenada con la que se basa la cadena probada. Si hay más que cada uno comparta la mejor coincidencia, entonces generará el que tiene el número más alto asociado con él.

El programa verifique si las cadenas coinciden de derecha a izquierda.

Si una cadena después de un 'm' contiene el carácter '?' Puede ser cualquier carácter ('-', '+' y '0').

La forma en que construyo el programa fue haciendo una matriz para las cadenas almacenadas, luego haciendo una función que pueda obtener una "puntuación de coincidencia" al intentar ver cuál de las cadenas almacenadas coinciden mejor con la cadena que se está probando. Si la puntuación de coincidencia es igual a la longitud de la cadena probada, entonces es la mejor coincidencia posible.

El programa no le importa hacer coincidir más, los caracteres en la cadena probada, por lo que si intentamos que intentamos coincidir "0 ++ - 0" en "++ 0 ++ - 0" le daría a OS una coincidencia. Puntuación de 6, lo que significa que sería el mejor partido posible.

Ejecución del programa

  #include <iostream>  //For strcpy: #include <stdio.h> #include <string.h> using namespace std;  //Gets match score for checking which match is the best of all. The highest match value is the best. int getMatchScore(string matchCheck, string matchTarget) {     //Declares integers for length of matchCheck and matchTarget, and also for matchScore.     int lenCheck=matchCheck.length(), lenTarget=matchTarget.length(),matchScore=0;     //Declares int checkCounter and targetCounter, that has values lenCheck-1 and lenTarget-1 respectively used in while loop condition.     int checkCounter=lenCheck-1, targetCounter=lenTarget-1;      //If the length of the matchTarget is less than the length of matchCheck return 0.     if(lenCheck>lenTarget){         return 0;     }      //Declares char arrays for check and target so they can be compared.     char matchCheckArr[50], matchTargetArr[50];      //These two lines copy the strings for check and target into their respective char arrays.     strcpy(matchCheckArr, matchCheck.c_str());     strcpy(matchTargetArr, matchTarget.c_str());      //While there are still elements in matchCheckArr:     while(checkCounter>=0){          //If matchCheckArr and matchTargetArr are the same (starting from the right going left) increment matchScore.         if(matchCheckArr[checkCounter]=='?'){             matchScore++;         }          else if(matchCheckArr[checkCounter]==matchTargetArr[targetCounter]){             matchScore++;         }          //Decrement checkCounter and TargetCounter to move one spot to the left in the matchCheckArr and matchTargetArr arrays.         checkCounter--;         targetCounter--;     }     return matchScore; }  int main() {     //Declares numInput for getting the number of inputs. Also declares targetCounter to hold the amount of data in targets array. tempLen to hold strInputHolders length.     int numInput, targetCounter=0, tempLen;      //Gets numInput from user.     cin >> numInput;      //Declares targets, that holds the data for checking against. Declares strInputHolder to hold string input when it needs to be checked against targets array.     string targets[numInput], strInputHolder;      //Declares inputHolder, that holds the char inputs temporarily.     char inputHolder;      //For loop for testing each line of input.     for(int i=0; i<numInput; i++){         //Takes the char that is in line of input and puts it in inputHolder.         cin >> inputHolder;          //Checks what char inputHolder is, if 'T' then do if statement if not ('M') do else statement.         if(inputHolder=='T'){              //Takes the string that follows the char in an input line and puts it in the targets array at the targetCounter position.             cin >> targets[targetCounter];              //Increments targetCounter so that the next input that goes to targets is placed in the right position.             targetCounter++;         }          //Check comment at if statement.         else{              //Declares two ints, matchScoreHolder which is set to 0 because we will need to check if the current match score is bigger then matchScoreHolder.             //Also declares targetPosition, which will hold the value of which target the match string matches best with.             int matchScoreHolder=0, targetPosition;              //Gets the string that follows the char in an input line and puts it in strInputHolder.             cin >> strInputHolder;              //Sets tempLen to the length of strInputHolder this will be temporary as strInputHolder will change for each input.             tempLen=strInputHolder.length();              //For loop that checks each target string against the current match string.             for(int x=0; x<targetCounter; x++){                  /*Sets currentMatchScore to the number of chars that the current match string and the target string at the targetCounter-1-x position has in                 common (they have a char in common when they share the same char in the same position from right to left).*/                 int currentMatchScore=getMatchScore(strInputHolder, targets[targetCounter-1-x]);                  //Checks if currentMatchScore is greater then matchScoreHolder this is why we set matchScoreHolder to 0 to begin with.                 if(currentMatchScore>matchScoreHolder){                      //Sets targetPosition to targetCounter-x, because we want the targetPosition to be the most accurate first of all, and then highest.                     targetPosition=targetCounter-x;                      //Sets matchScoreHolder to currentMatchScore since matchScoreHolder should hold the value of the highest match score.                     matchScoreHolder=currentMatchScore;                 }                  //If matchScoreHolder is as high as it can possibly be for the current match string execute if statement.                 if (matchScoreHolder==tempLen){                      //Sets targetPosition to the correct value.                     targetPosition=targetCounter-x;                      //Jumps out of loop, because we have found the highest possible match score and there is no reason to check the others.                     goto matchOutput;                 }             }              //For goto matchOutput in last if statement in the last for loop in main (just above).             matchOutput:              //Outputs targetPosition and goes to a new line.             cout << targetPosition << " ";         }     } }   

Así que el código funciona, pero es una forma de despacio. Debe poder tomar 50000 líneas de entrada y terminar con la salida en 2 segundos. Realmente no sé cómo mejorar esto.

Entrada / salida de muestra:

   (input) 8  (input) T 0--+0++-  (input) M ?+0++- (output) 1  (input) M ?0++- (output) 1  (input) T ---0++0  (input) M ?+0 (output) 2  (input) T 0+  (input) M +0?+- (output) 1  (input) T +- 1  

La "(Entrada)" y "(SALIDA)" son para mostrar cuál de los anteriores se ingresa y salida, no están separados de la entrada y salida real.

Original en ingles

Program description

The goal of this program is to get a number, which is the number of lines of inputs (lets call that number N) that the program will receive. Then the following N lines will consist of two parts, first a char which is either 'T' or 'M'. The next part will be a string that is a little different for 'T' and 'M'. If the char is 'T' then the string will consist of the following chars: '-', '+' and '0'. If the first char in the input line is 'M' then the following string can consist of the following chars: '-', '+', '0' and '?'.

When the line starts with a 'T', then the string will be stored. I store it in an array and the entries will be numbered from 1 to the number of entries.

When the line starts with an 'M', then the string will be compared to the list of strings that are stored to find out which of them that it matches best with.

The program will then output after each input line starting with 'M' the number associated with the stored string that the tested string matches best with. If there are more that each share the best match then it will output the one with the highest number associated with it.

The program check if the strings match from right to left.

If a string after an 'M' contains the char '?' it can be any char ('-', '+' and '0').

The way I build the program was by making an array for the stored strings, then making a function that can get a "match score" when trying to see which of the stored strings match best with the string being tested. If the match score is equal to the length of the tested string then it is the best possible match.

The program does not care about matching more then the chars in the tested string, so if we tried tried matching "0++--0" to "++0++--0" it would give os a match score of 6 which means it would be the best possible match.

Program execution

#include <iostream>  //For strcpy: #include <stdio.h> #include <string.h> using namespace std;  //Gets match score for checking which match is the best of all. The highest match value is the best. int getMatchScore(string matchCheck, string matchTarget) {     //Declares integers for length of matchCheck and matchTarget, and also for matchScore.     int lenCheck=matchCheck.length(), lenTarget=matchTarget.length(),matchScore=0;     //Declares int checkCounter and targetCounter, that has values lenCheck-1 and lenTarget-1 respectively used in while loop condition.     int checkCounter=lenCheck-1, targetCounter=lenTarget-1;      //If the length of the matchTarget is less than the length of matchCheck return 0.     if(lenCheck>lenTarget){         return 0;     }      //Declares char arrays for check and target so they can be compared.     char matchCheckArr[50], matchTargetArr[50];      //These two lines copy the strings for check and target into their respective char arrays.     strcpy(matchCheckArr, matchCheck.c_str());     strcpy(matchTargetArr, matchTarget.c_str());      //While there are still elements in matchCheckArr:     while(checkCounter>=0){          //If matchCheckArr and matchTargetArr are the same (starting from the right going left) increment matchScore.         if(matchCheckArr[checkCounter]=='?'){             matchScore++;         }          else if(matchCheckArr[checkCounter]==matchTargetArr[targetCounter]){             matchScore++;         }          //Decrement checkCounter and TargetCounter to move one spot to the left in the matchCheckArr and matchTargetArr arrays.         checkCounter--;         targetCounter--;     }     return matchScore; }  int main() {     //Declares numInput for getting the number of inputs. Also declares targetCounter to hold the amount of data in targets array. tempLen to hold strInputHolders length.     int numInput, targetCounter=0, tempLen;      //Gets numInput from user.     cin >> numInput;      //Declares targets, that holds the data for checking against. Declares strInputHolder to hold string input when it needs to be checked against targets array.     string targets[numInput], strInputHolder;      //Declares inputHolder, that holds the char inputs temporarily.     char inputHolder;      //For loop for testing each line of input.     for(int i=0; i<numInput; i++){         //Takes the char that is in line of input and puts it in inputHolder.         cin >> inputHolder;          //Checks what char inputHolder is, if 'T' then do if statement if not ('M') do else statement.         if(inputHolder=='T'){              //Takes the string that follows the char in an input line and puts it in the targets array at the targetCounter position.             cin >> targets[targetCounter];              //Increments targetCounter so that the next input that goes to targets is placed in the right position.             targetCounter++;         }          //Check comment at if statement.         else{              //Declares two ints, matchScoreHolder which is set to 0 because we will need to check if the current match score is bigger then matchScoreHolder.             //Also declares targetPosition, which will hold the value of which target the match string matches best with.             int matchScoreHolder=0, targetPosition;              //Gets the string that follows the char in an input line and puts it in strInputHolder.             cin >> strInputHolder;              //Sets tempLen to the length of strInputHolder this will be temporary as strInputHolder will change for each input.             tempLen=strInputHolder.length();              //For loop that checks each target string against the current match string.             for(int x=0; x<targetCounter; x++){                  /*Sets currentMatchScore to the number of chars that the current match string and the target string at the targetCounter-1-x position has in                 common (they have a char in common when they share the same char in the same position from right to left).*/                 int currentMatchScore=getMatchScore(strInputHolder, targets[targetCounter-1-x]);                  //Checks if currentMatchScore is greater then matchScoreHolder this is why we set matchScoreHolder to 0 to begin with.                 if(currentMatchScore>matchScoreHolder){                      //Sets targetPosition to targetCounter-x, because we want the targetPosition to be the most accurate first of all, and then highest.                     targetPosition=targetCounter-x;                      //Sets matchScoreHolder to currentMatchScore since matchScoreHolder should hold the value of the highest match score.                     matchScoreHolder=currentMatchScore;                 }                  //If matchScoreHolder is as high as it can possibly be for the current match string execute if statement.                 if (matchScoreHolder==tempLen){                      //Sets targetPosition to the correct value.                     targetPosition=targetCounter-x;                      //Jumps out of loop, because we have found the highest possible match score and there is no reason to check the others.                     goto matchOutput;                 }             }              //For goto matchOutput in last if statement in the last for loop in main (just above).             matchOutput:              //Outputs targetPosition and goes to a new line.             cout << targetPosition << "\n";         }     } } 

So the code works, but it is way to slow. It needs to be able to take 50000 lines of input and be finished with outputting in 2 seconds. I don't really know how to improve on this.

Sample input/output:

 (input) 8  (input) T 0--+0++-  (input) M ?+0++- (output) 1  (input) M ?0++- (output) 1  (input) T ---0++0  (input) M ?+0 (output) 2  (input) T 0+  (input) M +0?+- (output) 1  (input) T +- 

The "(input)" and "(output)" are for showing which of the above are input and output, they are not apart of the actual input and output.

        
       
       

Lista de respuestas

3
 
vote

Una cosa que noté con su código existente. Esto:

  char matchCheckArr[50], matchTargetArr[50];  //These two lines copy the strings for check and target into their respective char arrays. strcpy(matchCheckArr, matchCheck.c_str()); strcpy(matchTargetArr, matchTarget.c_str());   

es redundante y un desperdicio de recursos, ya que solo está revisando cada char y matchCheck y MatchTarget, se puede acceder a cada indexación.

En una nota lateral, goto1 es una de las peores estructuras de programación jamás creadas. No hay nada que pueda hacer con goto que no se puede lograr con estructuras más razonables. En su caso, se dividirá una declaración simple 99887766555443333 saldrá del bucle y ejecute la primera línea después del bucle.

 

One thing I noticed with your existing code. This:

char matchCheckArr[50], matchTargetArr[50];  //These two lines copy the strings for check and target into their respective char arrays. strcpy(matchCheckArr, matchCheck.c_str()); strcpy(matchTargetArr, matchTarget.c_str()); 

is redundant and a waste of resources, since you're only checking each char and matchCheck and matchTarget can each be accessed by indexing.

On a side note, goto is one of the worst programming structures ever created. There is nothing you can do with goto that can't be achieved with more reasonable structures. In your case a simple break statement will break out of the loop and execute the first line after the loop.

 
 
   
   
0
 
vote

Estoy respondiendo muy cuidadosamente aquí, ya que no quiero decir nada estúpido.

Al intentar obtener el forzamiento bruto para un mejor rendimiento, sugeriría hacer que el programa se basara. Supongamos que tienes un rango de 100 números. El que está buscando fue, digamos, 70.

Entonces, un algoritmo normal necesitaría 70 pasos para encontrar el número correcto. Al crear 2 hilos, uno podría comenzar a 0 y el otro a los 100. Ahora, el segundo hilo solo necesitaría 30 pasos para terminar. Al usar 4 hilos, comenzando a 0 (arriba), 49 (abajo), 50 (arriba), 100 (abajo), solo tomaría 20 pasos para el número de hilo 3.

No estoy seguro de si esto lo ayudará, pero creo que el punto hecho es claro. Esperemos que pueda puertar mi ejemplo mal hecho a su programa.

 

I am answering very carefully here since I don't want to say anything stupid.

When trying to get brute forcing to better performance I would suggest on making the program thread-based. Assume you have a range of 100 numbers. The one you are searching for was, let's say, 70.

Then a normal algorithm would need 70 steps to find the correct number. When creating 2 threads, one could start at 0 and the other at 100. Now the second thread would only need 30 steps to terminate. By using 4 threads, starting at 0 (up), 49 (down), 50 (up), 100 (down), it would only take 20 steps for thread number 3.

I am not sure if this will help you, but I think the point made is clear. Hopefully you can port my poorly-made example to your program.

 
 
   
   

Relacionados problema

6  Implementación eficiente de un desafío de programación dinámica  ( Efficient implementation of a dynamic programming challenge ) 
Escribí el siguiente código para un problema de programación dinámica, pero el juez en línea me da un error de 'límite de tiempo excedido'. ¿Cómo puedo optimi...

2  Imprimiendo todos los números primeros entre dos límites  ( Printing all the prime numbers between two bounds ) 
Sigo recibiendo un límite de tiempo excedido para esta solución a SPOJ PRIME1 . Necesito imprimir todos los números primos dentro de un intervalo dado (con i...

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...

1  Python Bubble Sort  ( Python bubble sort ) 
a = [5, 2, 4, 6, 1, 3] def insert(arr): if len(arr) == 1: return arr # outer loop for i in range(1, len(arr)): # inner loop ...

2  Swift HackerRank faltante Números Challenge  ( Swift hackerrank missing numbers challenge ) 
Estoy intentando resolverlo el desafío de "números faltantes" en Hackerrank donde Me encargo de encontrar elementos que faltan comparando dos matrices. {...

4  Encuentre el número de subcadenas de una cadena numérica mayor que una cadena numérica dada  ( Find the number of substrings of a numerical string greater than a given num str ) 
Pregunta: http://qa.geeksforgeeks.org/9744/vinay-queried-interesting -Problem-optimización Entrada La primera línea contiene n que denota la longitud...

1  Código de rotación izquierdo de Hackerrank usando Java 8  ( Hackerrank left rotation code using java 8 ) 
Intenté resolver este Rotación izquierda problema en Hackerrank. Mi código funciona para la mayoría de los casos de prueba, pero para algunos no, probableme...

6  Valores coincidentes de la tabla HTML para actualizar los valores en Pandas DataFrame  ( Matching values from html table for updating values in pandas dataframe ) 
Esto es más un ejercicio para que me utilice a Pandas y sus cuadros de datos. Para aquellos que no escucharon de él: Panda es un paquete de Python que prop...

3  Código para dividir los regalos por igual  ( Code for dividing gifts equally ) 
Recientemente me encontré con este problema : Es el cumpleaños de Lavanya y varias familias han sido invitadas a la fiesta de cumpleaños. Como es habitu...

1  Caras de cultivo de imágenes en un directorio  ( Cropping faces from images in a directory ) 
Estoy usando el siguiente código para recortar caras de imágenes en un directorio public static void main(String args[]) { solution(new Command() ...




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