Foros del Web » Programación para mayores de 30 ;) » C/C++ »

Busqueda Binaria con palabras

Estas en el tema de Busqueda Binaria con palabras en el foro de C/C++ en Foros del Web. Hola, que tal! Trato de hacer un programa dividido por funciones, tengo un diccionario con la frecuencia en la que aparecen las palabras, y en ...
  #1 (permalink)  
Antiguo 21/11/2016, 20:53
 
Fecha de Ingreso: mayo-2010
Mensajes: 185
Antigüedad: 7 años, 4 meses
Puntos: 2
Busqueda Binaria con palabras

Hola, que tal! Trato de hacer un programa dividido por funciones, tengo un diccionario con la frecuencia en la que aparecen las palabras, y en otro arreglo tengo otras cuantas palabras, necesito checar si las palabras del arreglo szPalabrasSugeridas aparecen en el arreglo szPalabras, si aparece agregar esa palabra y su estadistica a szListaFinal, lo intento hacer por busqueda binaria por que seran mas de 50 000 palabras las que se comparen, pero al momento de compilar el programa se queda parpadeando y no me marca ningun error, alguna sugerencia? Les dejo mi codigo.

Codigo que imprime las palabras
Código:
		//Con esa lista de palabras y el diccionario, recupera las sugerencias
		ListaCandidatas(szPalabrasSugeridas, iNumSugeridas, szPalabras, iEstadisticas, iNumElementos,
			szListaFinal, iPeso, iNumLista);

		//Mostrar las opciones candidatas, por orden de peso(frecuencia)
		printf("Las candidatas son \n");
		for (int j = 0; j < iNumLista; j++)
			printf("%s %i\n", szListaFinal[j], iPeso[j]);
Codigo de la funcion que genera las palabras y las compara
Código:
void	ListaCandidatas(
	char	szPalabrasSugeridas[][TAMTOKEN],	
	int		iNumSugeridas,						
	char	szPalabras[][TAMTOKEN],				
	int		iEstadisticas[],					
	int		iNumElementos,						
	char	szListaFinal[][TAMTOKEN],			
	int		iPeso[],							
	int &	iNumLista)							
{

	 int inf, sup, mitad,i;

	 
	 iNumLista = 0;
	 for (i = 0; i < iNumSugeridas; i++)
	 {
		 inf = 0;
		 sup = iNumElementos;
		 char bandera = 'F';
		 while (inf <= sup)
		 {
			 mitad = (inf + sup) / 2;
			 if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) == 0)
			 {
				 strcpy_s(szListaFinal[i], szPalabras[mitad]);
				 iPeso[i] = iEstadisticas[mitad];
				 iNumLista++;
				 bandera = 'V';
				 break;
			 }
			 if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) > 0)
			 {
				 sup = mitad;
				 mitad = (inf + sup) / 2;
			 }
			 if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) < 0)
			 {
				 inf = mitad;
				 mitad = (inf + sup) / 2;
			 }
		 }
	 }
}
  #2 (permalink)  
Antiguo 22/11/2016, 05:00
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 2 años, 11 meses
Puntos: 204
Respuesta: Busqueda Binaria con palabras

A riesgo de pecar de adivino, si en el bucle

Código C:
Ver original
  1. while (inf <= sup)

Acaba resultando que sup==mitad y el código que se ejecuta a continuación es:

Código C:
Ver original
  1. if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) > 0) {
  2.   sup = mitad; // (1)
  3.   mitad = (inf + sup) / 2; //(2)
  4. }

O si resulta que inf==miad y el código que se ejecuta a continuación es:

Código C:
Ver original
  1. if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) < 0) {
  2.   inf = mitad;
  3.   mitad = (inf + sup) / 2;
  4. }

El programa entrará en bucle.

La explicación es la siguiente (me centro en el primer caso ambos casos son idénticos):

Se produce que sup==mitad, luego:
  • el valor de sup no se verá modificado en (1)
  • Como no ha cambiado el valor de sup ni tampoco el de inf, el valor de mitad en (2) tampoco cambiará
  • Como el valor de mitad no cambia, en la siguiente iteración volverás a comprobar las dos mismas palabras que en la iteración anterior.
  • Repite los pasos anteriores cuantas veces quieras hasta que te aburras.
Yo modificaría ese código para que sea capaz de detectar que una palabra no existe. Quizás algo así:

Código C:
Ver original
  1. if (strcmp(szPalabras[mitad], szPalabrasSugeridas[i]) > 0) {  
  2.   if( sup == mitad ) break;
  3.  
  4.   sup = mitad;
  5.   mitad = (inf + sup) / 2;
  6. }

Y lo mismo para el límite inferior.

Por cierto, si tanto te preocupa el rendimiento como para no hacer una búsqueda lineal... ¿Por qué fuerzas hasta 3 comparaciones de la cadena en cada iteración? ¿No sería más adecuado entonces hacer una única comparación de cadenas y almacenar el resultado para comparar éste en cada uno de los if?
__________________
La ayuda se paga con esfuerzo o con dinero. Si no estás dispuesto a esforzarte y quieres que te hagan los deberes pide presupuesto, al menos así ahorrarás tiempo.

Etiquetas: busqueda, int, palabras
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 00:17.