Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: AlbertoBSD en 30 Noviembre 2018, 18:38 pm


Título: Primero en Entrar, primero en salir FIFO, Cola o Fila
Publicado por: AlbertoBSD en 30 Noviembre 2018, 18:38 pm
No es lo mas eficiente, hay muchas cosas se podrian mejorar, en especifico la forma en la que se organizan  el arreglo de elementos actuales en la Fila,  sin embargo funciono para el proposito.

Yo se que la mayoría de estas estructuras ya están implementadas. Pero no se puede decir que eres programador si no sabes implementarlas por tu cuenta.

(https://i.imgur.com/vE0c5nr.png)

Código
  1. /*
  2.  El tipo de dato se puede cambiar dependiendo de la implementación que se le quiera dar, también se tendrían que cambiar los tipos de datos devueltos por las funciones
  3.  En este caso yo quería un arreglo de apuntadores char* por lo cual el contenedor es char**
  4.  */
  5.  
  6.  
  7. typedef struct str_queue	{
  8. 	char **queue;
  9. 	int len;
  10. 	int max;
  11. }Queue;	
  12.  
  13. Queue *create_queue()	{
  14. 	Queue *r = malloc(sizeof(struct str_queue));
  15. 	r->len = 0;
  16. 	r->max = 2;
  17. 	r->queue = malloc(sizeof(char*)*r->max);
  18. 	return r;
  19. }
  20.  
  21. void free_queue(Queue *q)	{
  22. 	if(q)	{
  23. 		if(q->queue)
  24. 			free(q->queue);
  25. 		free(q);
  26. 	}
  27. }
  28.  
  29. void en_queue(Queue *q, char *ptr)	{
  30. 	if((q->len+1) == q->max)	{
  31. 		q->max *= 2;
  32. 		q->queue = realloc(q->queue,q->max*sizeof(char*));	
  33. 	}
  34. 	if(q->queue != NULL)	{
  35. 		q->queue[q->len] = ptr;
  36. 		q->len++;
  37. 	}
  38. }
  39.  
  40. char * de_queue(Queue *q)	{
  41. 	char *r = NULL;
  42. 	int i = 0;
  43. 	if(q->len >= 1)	{
  44. 		r = q->queue[0];
  45. 		q->len--;
  46. 		while(i < q->len)	{
  47. 			q->queue[i] = q->queue[i+1];
  48. 			i++;
  49. 		}
  50. 		q->queue[i] = NULL;
  51. 	}
  52. 	return r;
  53. }

Yo en su momento lo utilize para un post, donde realizaba una versión iterativa y necesitaba almacenar en una Cola el listado de los directorios que aun faltaba por recorrer:

problema de memoria con readdir (Solucionado) (https://foro.elhacker.net/programacion_cc/problema_de_memoria_con_readdir_solucionado-t490167.0.html)

Ejemplo de uso:

Código
  1. int main()	{
  2. 	char *cadenas[10] = { "Cadena_0","Cadena_1","Cadena_2","Cadena_3","Cadena_4","Cadena_5","Cadena_6","Cadena_7","Cadena_8","Cadena_9"};
  3. 	char *actual;
  4. 	int index1,index2,i =0;
  5. 	srand(time(NULL));
  6. 	Queue *q = create_queue();
  7. 	while(i < 10)	{
  8. 		index1 = rand() % 10;
  9. 		index2 = rand() % 10;
  10. 		printf("Agregando a la fila: %s\n",cadenas[index1]);
  11. 		en_queue(q,cadenas[index1]);
  12. 		printf("Agregando a la fila: %s\n",cadenas[index2]);
  13. 		en_queue(q,cadenas[index2]);
  14. 		printf("Saliendo de la fila %s\n",de_queue(q));
  15. 		i++;
  16. 	}
  17. 	free_queue(q);
  18. }
  19.  

Como es randon la salida es variada, pero podemos observar el funcionamiento:



Código:
Agregando a la fila: Cadena_5
Agregando a la fila: Cadena_5
Saliendo de la fila Cadena_5
Agregando a la fila: Cadena_8
Agregando a la fila: Cadena_2
Saliendo de la fila Cadena_5
Agregando a la fila: Cadena_5
Agregando a la fila: Cadena_7
Saliendo de la fila Cadena_8
Agregando a la fila: Cadena_8
Agregando a la fila: Cadena_7
Saliendo de la fila Cadena_2
Agregando a la fila: Cadena_9
Agregando a la fila: Cadena_2
Saliendo de la fila Cadena_5
Agregando a la fila: Cadena_1
Agregando a la fila: Cadena_3
Saliendo de la fila Cadena_7
Agregando a la fila: Cadena_8
Agregando a la fila: Cadena_5
Saliendo de la fila Cadena_8
Agregando a la fila: Cadena_0
Agregando a la fila: Cadena_3
Saliendo de la fila Cadena_7
Agregando a la fila: Cadena_4
Agregando a la fila: Cadena_0
Saliendo de la fila Cadena_9
Agregando a la fila: Cadena_7
Agregando a la fila: Cadena_1
Saliendo de la fila Cadena_2


Funcion actualizada de de_queue

Código
  1. char * de_queue(Queue *q)	{
  2. 	char *r = NULL;
  3. 	int i = 0;
  4. 	if(q->len >= 1)	{
  5. 		r = q->queue[0];
  6. 		q->len--;
  7. 		while(i < q->len)	{
  8. 			q->queue[i] = q->queue[i+1];
  9. 			i++;
  10. 		}
  11. 		q->queue[i] = NULL;
  12. 	}
  13. 	return r;
  14. }
  15.  

Título: Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
Publicado por: do-while en 1 Diciembre 2018, 16:56 pm
Solo un detalle, en de_queue estás usando memcpy para mover el contenido de un vector sobre sí mismo. Cuando usas memcpy sobre dos buferes que se superponen (como en este caso) el comportamiento queda indefinido (puede que a veces funcione y otras no o puede depender del compilador...). Lo correcto en estos casos es utilizar memmove, que utiliza un bufer auxiliar y así evitar que la información del vector se pueda "machacar".

¡Saludos!

Título: Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
Publicado por: CalgaryCorpus en 1 Diciembre 2018, 17:04 pm
Por qué free_queue dice que devuelve int y no devuelve valor alguno?

Título: Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
Publicado por: AlbertoBSD en 1 Diciembre 2018, 20:02 pm
Cita de: do-while en  1 Diciembre 2018, 16:56 pm
Solo un detalle, en de_queue estás usando memcpy para mover el contenido de un vector sobre sí mismo. Cuando usas memcpy sobre dos buferes que se superponen (como en este caso) el comportamiento queda indefinido (puede que a veces funcione y otras no o puede depender del compilador...). Lo correcto en estos casos es utilizar memmove, que utiliza un bufer auxiliar y así evitar que la información del vector se pueda "machacar".

¡Saludos!

Si me imagine que si la implementación empieza de alravez puede pasar eso, lo voy editar como mentas o en su defecto con una versión iterativa con while moviendo los elementos del buffer.

Código
  1. char * de_queue(Queue *q)	{
  2. 	char *r = NULL;
  3. 	int i = 0;
  4. 	if(q->len >= 1)	{
  5. 		r = q->queue[0];
  6. 		q->len--;
  7. 		while(i < q->len)	{
  8. 			q->queue[i] = q->queue[i+1];
  9. 			i++;
  10. 		}
  11. 		q->queue[i] = NULL;
  12. 	}
  13. 	return r;
  14. }
  15.  

Cita de: CalgaryCorpus en  1 Diciembre 2018, 17:04 pm
Por qué free_queue dice que devuelve int y no devuelve valor alguno?

Por mala practica de programación, viejo habito de declarar las funciones como int, cuando no he definido si van a retornar valor o no.

En un momento corrijo el código.

Saludos!

Título: Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
Publicado por: CalgaryCorpus en 1 Diciembre 2018, 22:41 pm
O bien no estas compilando el codigo, o estas ignorando los warnings que se presentan y si no hay warnings, sugiero cambiar de compilador.

Linea 16, el prototipo de la funcion en_queue dice retornar int, pero la definicion, linea 34 establece void en el tipo de retorno.,

Título: Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
Publicado por: AlbertoBSD en 1 Diciembre 2018, 23:07 pm
Gracias, si no lo compile, solo lo edite y se me olvido editar el prototipo.

Saludos

Título: Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
Publicado por: CalgaryCorpus en 1 Diciembre 2018, 23:38 pm
Te estas ganando innecesariamente un problema al poner los prototipos al lado de la implementacion. No tienen ningun uso alli, deberian estar al lado del main que usa las funciones o un en un header file aparte.

Por otro lado, estar pidiendo memoria y copiando el contenido de la cola todas las veces que insertas, y andar moviendo todos los elementos cada vez que borras parece ineficiente, especialmente a medida que la cola se use mas y mas,

Sugiero usar un buffer circular: No mueves los contenidos al borrar, y solo pides memoria al agregar si ya no queda espacio en el buffer, pero si lo hay solo se copia el contenido en algun lugar disponible. Solo es necesario pedir memoria y mover si el buffer esta lleno,

Por esa ultima razon, parece mejor pedir memoria en potencias de 2, o en algo mayor que 1 cada vez, para darle la oportunidad a la cola que o bien desocupe algunos espacios para las siguientes inserciones o bien haya algun espacio antes de pedir otra vez.

Título: Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
Publicado por: AlbertoBSD en 1 Diciembre 2018, 23:49 pm
Por lo mismo lo dije:

Cita de: AlbertoBSD en 30 Noviembre 2018, 18:38 pm
No es lo mas eficiente, hay muchas cosas se podrian mejorar, en especifico la forma en la que se organizan  el arreglo de elementos actuales en la Fila,  sin embargo funciono para el proposito.

Si claramente se puede manejar de mejor manera, me gusta lo de pedir memoria en potencias de 2, y lo del buffer Circular.

Pidiendo memoria de 2 en 2, requiere cambios en la estructura, en la funcion de crear para inicializar con 2 espacios disponibles y en la funcion en_queue

Código
  1. typedef struct str_queue	{
  2. 	char **queue;
  3. 	int len;
  4. 	int max;
  5. }Queue;
  6.  
  7. Queue *create_queue()	{
  8. 	Queue *r = malloc(sizeof(struct str_queue));
  9. 	r->len = 0;
  10. 	r->max = 2;
  11. 	r->queue = malloc(sizeof(char*)*r->max);
  12. 	return r;
  13. }
  14.  
  15. void en_queue(Queue *q, char *ptr)	{
  16. 	if((q->len+1) == q->max)	{
  17. 		q->max *= 2;
  18. 		printf("Tamanio actual %i\n",q->max);
  19. 		q->queue = realloc(q->queue,q->max*sizeof(char*));	
  20. 	}
  21. 	if(q->queue != NULL)	{
  22. 		q->queue[q->len] = ptr;
  23. 		q->len++;
  24. 	}
  25. }
  26.  

Saludos!

Título: Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
Publicado por: AlbertoBSD en 2 Diciembre 2018, 22:50 pm
En teoría quedo esta versión, utilizando un buffer semi circular y creciendo la memoria en potencias de 2.

Tiene muchos printf para depuración, y mostrar el funcionamiento.

Código
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. #include<time.h>
  5.  
  6. typedef struct str_queue	{
  7. 	char **queue;
  8. 	int len;
  9. 	/*
  10. 		Las siguientes variales son para hacer mas eficiente la asignacion de memoria
  11. 		len_max indica el numero de espacios len_maximos reservados actualmente, este siempre esta en potencias de 2
  12. 		offset indica cuantos espacios vacios hay al principio del arreglo, con el fin de no tener que reacomodar el arreglo con cada de-queue
  13. 		offset_max indica la cantidad cada cuantos movimientos se va a reorganizar la memoria.
  14. 	*/
  15. 	int len_max;
  16. 	int offset;
  17. 	int offset_max;
  18. }Queue;	
  19.  
  20. Queue *create_queue()	{
  21. 	Queue *q = malloc(sizeof(struct str_queue));
  22. 	q->len = 0;
  23. 	q->offset = 0;
  24. 	q->len_max = 2;
  25. 	q->offset_max = 1;
  26. 	q->queue = malloc(sizeof(char*)*q->len_max);
  27. 	return q;
  28. }
  29.  
  30. void free_queue(Queue *q)	{
  31. 	if(q)	{
  32. 		if(q->queue)
  33. 			free(q->queue);
  34. 		free(q);
  35. 	}
  36. }
  37.  
  38. void en_queue(Queue *q, char *ptr)	{
  39. 	char **temp;
  40. 	int i;
  41. 	//printf("%i == %i ?\n",q->len,q->len_max);
  42. 	if( q->len == q->len_max)	{
  43. 		q->len_max *= 2;
  44. 		//printf("%p -> ",q->queue);
  45. 		temp = q->queue;
  46. 		q->queue = realloc(temp,q->len_max*sizeof(char*));
  47. 		//printf("%p\n",q->queue);
  48.  
  49. 		if(q->queue == NULL)	{
  50. 			fprintf(stderr,"error realloc\n");
  51. 		}
  52. 		else	{
  53. 			printf("Tamanio actual %i\n",q->len_max);
  54. 		}
  55. 	}
  56. 	if(q->queue != NULL)	{
  57. 		printf("q->queue[%i] <- %p\n",q->len,ptr);
  58. 		q->queue[q->len] = ptr;
  59. 		q->len++;
  60. 	}
  61. }
  62.  
  63. char * de_queue(Queue *q)	{
  64. 	char *r = NULL;
  65. 	int i,j;
  66. 	if((q->len - q->offset) >= 1)	{
  67. 		r = q->queue[q->offset];
  68. 		printf("q->queue[%i] : %p -> out\n",q->offset,q->queue[q->offset]);
  69. 		q->queue[q->offset] = NULL;
  70. 		q->offset++;
  71. 		if(q->offset == q->offset_max)	{
  72. 			//printf("%i == %i\n",q->offset,q->offset_max);
  73. 			i = q->offset;
  74. 			j = 0;
  75. 			//printf("i:%i  j:%i\n",i,j);
  76. 			while(i < q->len)	{
  77. 				//printf("i:%i < q->len:%i\n",i,q->len);
  78. 				printf("q->queue[%i]: %p  <- q->queue[%i]: %p\n",j,q->queue[j],i,q->queue[i]);
  79. 				q->queue[j] = q->queue[i];
  80. 				q->queue[i] = NULL;
  81. 				j++;
  82. 				i++;
  83. 			}
  84. 			//printf("%i:q->len %i -= q->offset %i\n",(q->len-q->offset),q->len,q->offset);
  85. 			q->len -= q->offset;
  86. 			q->offset = 0;
  87. 			q->offset_max *=2;
  88. 		}
  89. 	}
  90. 	//printf("r: %p, %s\n",r,r);
  91. 	return r;
  92. }
  93.  
  94. int main()	{
  95. 	char *cadenas[10] = { "Cadena_0","Cadena_1","Cadena_2","Cadena_3","Cadena_4","Cadena_5","Cadena_6","Cadena_7","Cadena_8","Cadena_9"};
  96. 	char *actual;
  97. 	int index1,index2,i =0;
  98. 	srand(time(NULL));
  99. 	Queue *q = create_queue();
  100. 	while(i < 1000)	{
  101. 		index1 = rand() % 10;
  102. 		index2 = rand() % 10;
  103. 		//printf("Agregando a la fila: %p %s\n",cadenas[index1],cadenas[index1]);
  104. 		en_queue(q,cadenas[index1]);
  105. 		//printf("Agregando a la fila: %p %s\n",cadenas[index2],cadenas[index2]);
  106. 		en_queue(q,cadenas[index2]);
  107. 		de_queue(q);
  108. 		//printf("Saliendo de la fila %s\n",de_queue(q));
  109. 		i++;
  110. 	}
  111. 	free_queue(q);
  112. }
  113.  

Salidos!

Título: Re: Primero en Entrar, primero en salir FIFO, Cola o Fila
Publicado por: CalgaryCorpus en 3 Diciembre 2018, 00:01 am
Si haces el buffer circular, simplificaras el codigo, pues no necesitaras hacer copias en de_queue como lo haces ahora.


Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines