Optimizar un codigo

[Arcana]

Hola, buenas noches, tengo este codigo, que lo que hace es abrir un archivo .txt sacar todas las palabras, quitar puntuaciones y solo contar de separadores lo que es .,();
Ahora tomar cada palabra, ordenarla alfabeticamente, y checar cuantas veces aparece en el arreglo, despues añadir las veces que aparece esa palabra.
entonces por ejemplo si tenemos http://pagina.unam.mx/cyp
la primera palabra seria
http://pagina 1
unam 1
mx/cpy 1

La primera es la palabra y la segunda las veces que aparece, pero cuando hablamos de mas de 100 000 palabras en el .txt el codigo se torna muy lento y se tarda aprox 5 min en arrojar resultados, alguien me podria ayudar a optimizarlo?

Código:

void Diccionario(char *szNombre, char szPalabras[][TAMTOKEN], int iEstadisticas[], int &iNumElementos)
{
	//char szNombre[50];
	//printf("Dame el nombre del archivo");
	//scanf_s("%s", szNombre, 49);
	FILE *libro;
	fopen_s(&libro, szNombre, "r");
	char palabra[TAMTOKEN];
	char *palabra1;
	char szPalabras1[NUMPALABRAS][TAMTOKEN];
	int estad[NUMPALABRAS];
	char *next = NULL;
	int i, j, k, conta = 0;
	int numpala;
	int mayor[NUMPALABRAS];
	char aux[100];
	if (libro == NULL)
	{
		printf("No se pudo abrir el archivo");
	}
	else
	{
		i = 0;

		while (!feof(libro))
		{
			fscanf_s(libro, "%s", palabra, 49);
			_strlwr_s(palabra);
			palabra1 = strtok_s(palabra, " ;,.)(", &next);
			while (palabra1 != NULL)
			{
				//printf("%s\n", palabra1);
				strcpy_s(szPalabras1[i], palabra1);
				palabra1 = strtok_s(NULL, " ;,.)(", &next);
				i++;
			}
			//strcpy_s(diccionario[i], palabra1);
			
			//printf("%s\n", diccionario[i]);
			//i++;

		}
		numpala = i;

		// ORDENAR CADENAS
		for (i = 0; i < numpala -1 ; i++)
		{
			k = i;
			strcpy_s(aux, szPalabras1[i]);
			for (j = i + 1; j < numpala; j++)
			{
				if (strcmp(szPalabras1[j], aux) < 0)
				{
					k = j;
					strcpy_s(aux, szPalabras1[j]);
					//permite hacer una copia auxiliar de la cadena szPalabras[j];
				}
			}
			strcpy_s(szPalabras1[k], szPalabras1[i]);
			strcpy_s(szPalabras1[i], aux);
		}

		for (i = 0; i < numpala; i++)
		{
			//printf("%s\n", diccionario[i]);

		}

		}
		//ordenamos por estadisticas.
		for (i = 0; i < numpala; i++)
		{
			estad[i] = 0;
			for (j = 0; j < numpala; j++)
			{
				if (strcmp(szPalabras1[i], szPalabras1[j]) == 0)
				{
					estad[i]++;
				}

			}

		}
		i = 0;
		while (i < numpala)
		{
			if (estad[i] != 1)
			{
				//printf("La palabra %s se repite %i veces\n", diccionario[i], esta[i]);
			}
			else
			{
				//printf("La palabra %s solo se encuentra una vez\n", diccionario[i]);
			}

			i = i + estad[i];
		}
	iNumElementos = 0;
		for (i = 0; i < numpala; i++)
		{
			if (strcmp(szPalabras1[i], szPalabras1[i + 1]) != 0)
			{
				iNumElementos++;
			}
		}
		//printf("%i\n", iNumElementos);
		
		i = 0;

		while (i < numpala)
		{
			mayor[i] = 0;
			if (estad[i] != 1)
			{
				for (j = i; j < i + estad[i]; j++)
				{

					if (estad[j] >= mayor[i])
					{
						mayor[i] = estad[j];
					}
					else
					{
						mayor[i] = mayor[i];
					}
				}
				
			}
			else
			{
				mayor[i] = estad[i];
				
			}
			//imprimimos diccionario
			//printf("%s %i\n", szPalabras[i], mayor[i]);
			strcpy_s(szPalabras[conta], szPalabras1[i]);
			iEstadisticas[conta] = mayor[i];
			conta++;
			i = i + estad[i];
			
		}
	
	fclose(libro);

}

[eferion]

Yo usaría un puntero doble para almacenar las palabras... así a la hora de ordenarlas en vez de tener que copiar las palabras infinidad de veces (hasta 100! veces en el peor de los casos) simplemente tendrías que copiar punteros. Otra posibilidad estaría en usar un algoritmo de ordenamiento más óptimo (quizás incluso usando varios hilos para ordenar).

En cualquier caso ningún programador sabe localizar correctamente cuellos de botella. Quizás en un algoritmo simple sí, pero en tareas más complejas ya te digo yo que eso no funciona. Yo en tu lugar mostraría marcas de tiempo para saber cuánto tarda en ejecutarse cada parte del algoritmo. Así sabrás a ciencia cierta dónde se consume la mayor parte del tiempo y te podrás centrar en intentar optimizar esa sección.

Piensa que lo mismo destinas 2 horas (o más) a revisar una parte del algoritmo que, sin optimizar, consume 2 segundos del total de 300 que dices que tarda actualmente...

Eso sí, la prueba con las marcas de tiempo ejecútala en modo release con todas las optimizaciones posibles... los resultados en modo debug no son nada fiables

[Arcana]

Ok, muchas gracias, intente compilarlo en modo Release, pero me manda excepcion no controlada, stack overflow, estoy en visual studio 2015, sabra por que es?

[eferion]

El modo release es para hacer pruebas de rendimiento, no pruebas de funcionamiento.

Deberías plantearte trocear tu código en funciones más simples. Eso puede ayudar a encontrar el error.

[aguml]

Haces cosas muy poco eficientes. Por ejemplo usas la variable i para contar el número de palabras y luego asignas el resultado a otra variable la cual su función es almacenar el número de palabras ¿por qué no usar esa variable para contar las palabras? Así te ahorras asignaciones, que no es que se vaya a notar mucho pero es absurdo hacer lo que haces.
Luego el método de ordenación de burbuja es poco eficiente y si encima usas funciones de cadenas la cosa empeora pero si encima usas más funciones y asignaciones de las necesarias ya no hablemos. Prueba con esta modificacion:

Código PHP:

  // ORDENAR CADENAS
        for (i = 0; i < numpala -1 ; i++)
        {
            for (j = i + 1; j < numpala; j++)
            {
                if (strcmp(szPalabras1[j], szPalabras1[i]) < 0)
                {
                    strcpy_s(aux, szPalabras1[j]);
                    strcpy_s(szPalabras1[j], szPalabras1[i]);
                    strcpy_s(szPalabras[i], aux);
                }
            }
        }  
   

Prueba lo y veras que mejora los tiempos simplemente por haber eliminado varias copias innecesarias. Si además usas punteros para ordenar en vez de estar copiando cadenas la cosa mejora mucho más y si cambias el método de ordenación ya sería la leche jajaja.
La parte con la que obtienes las palabras podría quedar asi para trabajar con punteros:

Código C:

char **szPalabras1;
...
...
...
      szPalabras1 = (char**) malloc(sizeof(char*) * NUMPALABRAS);
      i = 0;
      while (!feof(libro))
        {
            fscanf_s(libro, "%s", palabra, 49);
            _strlwr_s(palabra);
            palabra1 = strtok_s(palabra, " ;,.)(", &next);
            while (palabra1 != NULL)
            {
                szPalabras1[i] = palabra1;
                palabra1 = strtok_s(NULL, " ;,.)(", &next);
                i++;
            }
        }
 

Con eso en vez de tener un array de cadenas tendrías un array de punteros a cadenas con lo que no necesitas la función strcpy para intercambiarlos y puedes hacerlo con el operador de asignación.

Código PHP:

  // ORDENAR CADENAS
      char *aux;
        for (i = 0; i < numpala -1 ; i++)
        {
            for (j = i + 1; j < numpala; j++)
            {
                if (strcmp(szPalabras1[j], szPalabras1[i]) < 0)
                {
                    aux = szPalabras1[j];
                    szPalabras1[j] = szPalabras1[i];
                    szPalabras[i] = aux;
                }
            }
        }  
   

Lo único que al final te tienes que asegurar de liberar la memoria.

Código C:

free(szPalabras1);
 

[Arcana]

Muchas gracias!!
Modifique un poco mi codigo y aumento mas la velocidad, pero necesito aun mas velocidad, ya he intentado con punteros como me dices, pero no me funciona, tal vez hago algo mal, el codigo queda asi:
Este es el codigo que funciona Normal.

Código:

void Diccionario(char *szNombre, static char szPalabras[][TAMTOKEN], static int iEstadisticas[], int &iNumElementos)
{
	FILE *libro;
	fopen_s(&libro, szNombre, "r");
	static char palabra[TAMTOKEN];
	char *palabra1;
	static char szPalabras1[NUMPALABRAS][TAMTOKEN];
static int estad[NUMPALABRAS];
	char *next = NULL;
	int i, j, k;
	int  conta = 0;
	int numpala = 0;
	static int mayor[NUMPALABRAS];
	char aux[100];
	if (libro == NULL)
	{
		printf("No se pudo abrir el archivo");
	}
	else
	{
		i = 0;
	
		while (!feof(libro))
		{
			fscanf_s(libro, "%s", palabra, 49);
			_strlwr_s(palabra);
			palabra1 = strtok_s(palabra, " ;,.)(", &next);
			while (palabra1)
			{
				strcpy_s(szPalabras1[i], palabra1);
				palabra1 = strtok_s(NULL, " ;,.)(", &next);
				i++;
			}

		}
		numpala = i;

		// ORDENAR CADENAS
		int pos;
		for (i = 0; i < numpala;i++)
		{
			pos = i;
			strcpy_s(aux, szPalabras1[i]);
			while ((pos > 0) && (strcmp(aux, szPalabras1[pos - 1]) < 0))
			{
				strcpy_s(szPalabras1[pos], szPalabras1[pos - 1]);
				pos--;
			}
			strcpy_s(szPalabras1[pos], aux);
		}

	}
	iNumElementos = 0;
	//ordenamos por estadisticas.
	for (i = 0; i < numpala; i++)
	{
		estad[i] = 0;
		for (j = 0; j < numpala; j++)
		{
			if (strcmp(szPalabras1[i], szPalabras1[j]) == 0)
			{
				estad[i]++;
			}

		}
		if (strcmp(szPalabras1[i], szPalabras1[i + 1]) != 0)
		{
			iNumElementos++;
		}
	}

	i = 0;

	while (i < numpala)
	{
		strcpy_s(szPalabras[conta], szPalabras1[i]);
		iEstadisticas[conta] = estad[i];
		conta++;
		i = i + estad[i];

	}

	fclose(libro);

}

Este es el codigo con punteros, me imprime los resultados, pero al parecer parece que solo imprime la ultima palabr del archivo o algo asi:

Código:

#include <stdio.h>
#include "stdafx.h"
#include <string.h>
#include<windows.h>
#include "corrector.h"
#include <stdlib.h>


void Diccionario(char *szNombre, static char szPalabras[][TAMTOKEN], static int iEstadisticas[], int &iNumElementos)
{
	FILE *libro;
	fopen_s(&libro, szNombre, "r");
	static char palabra[TAMTOKEN];
	char *palabra1;
	static char **szPalabras1;
static int estad[NUMPALABRAS];
	char *next = NULL;
	int i, j, k;
	int  conta = 0;
	int numpala = 0;
	static int mayor[NUMPALABRAS];
	char *aux;
	if (libro == NULL)
	{
		printf("No se pudo abrir el archivo");
	}
	else
	{
		i = 0;
		szPalabras1 = (char**)malloc(sizeof(char*) * NUMPALABRAS);
		while (!feof(libro))
		{
			fscanf_s(libro, "%s", palabra, 49);
			_strlwr_s(palabra);
			palabra1 = strtok_s(palabra, " ;,.)(", &next);
			while (palabra1)
			{
				szPalabras1[i] = palabra1;
				palabra1 = strtok_s(NULL, " ;,.)(", &next);
				i++;
			}

		}
		numpala = i;

		// ORDENAR CADENAS
		int pos;
		for (i = 0; i < numpala;i++)
		{
			pos = i;
			aux = szPalabras1[i];
			while ((pos > 0) && (strcmp(aux, szPalabras1[pos - 1]) < 0))
			{
				szPalabras1[pos]= szPalabras1[pos - 1];
				pos--;
			}
			szPalabras1[pos] =aux;
		}

	}
	iNumElementos = 0;
	//ordenamos por estadisticas.
	for (i = 0; i < numpala; i++)
	{
		estad[i] = 0;
		for (j = 0; j < numpala; j++)
		{
			if (szPalabras1[i]== szPalabras1[j])
			{
				estad[i]++;
			}

		}
		if (szPalabras1[i] != szPalabras1[i + 1])
		{
			iNumElementos++;
		}
	}

	i = 0;

	while (i < numpala)
	{
		strcpy_s(szPalabras[conta], szPalabras1[i]);
		iEstadisticas[conta] = estad[i];
		conta++;
		i = i + estad[i];

	}

	fclose(libro);
}

[eferion]

Sigues teniendo una función gigantesca. Divídela en unidades más simples. Esto te aporta varias ventajas:

• Al ser unidades más pequeñas el código queda mejor estructura y es sintácticamente más legible (el nombre de la función suele dar idea de su cometido)
• Al ser funciones puedes hacer tests individuales para saber si una función cumple con su cometido o si tiene errores.