Donar $20 Donar $50 Donar $100 Donar mensualmente
 


Enviar respuesta 
 
Calificación:
  • 0 votos - 0 Media
  • 1
  • 2
  • 3
  • 4
  • 5
Buscar en el tema
Ejercicio de C para mover bien la cabeza
Autor Mensaje
diegomsaiz Sin conexión
Profesor del Modulo A
Always on the Run!!
*****

Ing. Electrónica
Facultad Regional Buenos Aires

Mensajes: 215
Agradecimientos dados: 206
Agradecimientos: 119 en 53 posts
Registro en: Aug 2011
Mensaje: #1
Lightbulb Ejercicio de C para mover bien la cabeza Ejercicios Informática I (Electrónica)
Hola a todos:

Quiero compartirles el enunciado y mi resolución de un ejercicio bastante interesante por varios motivos:
1- Para aprender a pensar y analizar.
2- Para cubrir todos los posibles casos de prueba (los famosos "test cases" que las empresas les tiran por la cabeza), para no dejarse encerrar.
3- Porque a pesar de que una resolución puede parecer correcta, no sólo puede no cubrir todos los casos de prueba, sino que además el sistema podría suspender su ejecución por "timed out" o se les podría colgar el terminal, ya verán por qué:

Enunciado: Un vector dinámico se carga con 'n' enteros ('n' siempre es impar). Todos ellos aparecen repetidos de manera par (dos iguales, cuatro iguales, etcétera), menos sólamente uno de ellos.
¿Cuál es ese elemento "aislado"? Encontrarlo e imprimirlo por pantalla.

Ejemplo: int vector[13] = {1, 7, 1, 3, 3, 48, 48, 99, 99, 99, 99, 0, 0} /* el elemento "aislado" es el 7, porque sólo aparece una vez */



#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main()
{
int n, i, j, aux;

scanf("%d",&n); // ingresar el tamaño del vector dinámico

int *a = malloc(sizeof(int) * n); // reserva de memoria del vector

for(int r = 0; r < n; r++) // ingreso de sus valores
{
scanf("%d",&a[r]);
}

if(n==1)
printf("%d ", *(a+0));

else
{
for(i=0; i<n-1; i++) // ordenamiento ascendente
{
for(j=i+1; j<n; j++)
{
if( *(a+i) > *(a+j) )
{
aux = *(a+i);
*(a+i) = *(a+j);
*(a+j) = aux;
}
}
}

if( *(a+0) < *(a+1) )
printf("%d ", *(a+0));

else if( *(a+(n-2)) < *(a+(n-1)) )
printf("%d ", *(a+(n-1)));

else
{
i=0;
do
{
if( *(a+i) < *(a+(i+1)) )
{
printf("%d", *(a+i));
break;
}
else
i+=2;

}while(i<=n-2);
}
}
return 0;
}



Para que no les salte una suspensión de sistema por "timed out" o se les cuelgue el terminal (dado que un "test case" podría involucrar 176538 enteros), siempre les conviene aplicar la aritmética de punteros más que la notación vectorial; pues como sólo maneja direcciones de memoria y no copia y paso de valores (int, long, etcétera) es mucho más veloz y por ende, más eficiente.

Si algo no se ve claro, por favor me preguntan y me vengo en remís, je!

Alf

"Dos cosas no tienen límite: El universo y la estupidez... Aunque de lo primero, no estoy seguro". (A. Einstein)thumbup3
(Este mensaje fue modificado por última vez en: 05-09-2017 01:29 por diegomsaiz.)
05-09-2017 01:19
Envíale un email Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Desert69 Sin conexión
Presidente del CEIT
Sin estado :( / "Anarquia...
********

Ing. en Sistemas
Facultad Regional Buenos Aires

Mensajes: 2.397
Agradecimientos dados: 203
Agradecimientos: 297 en 186 posts
Registro en: Jun 2008
Mensaje: #2
RE: Ejercicio de C para mover bien la cabeza
¡Aloha!

Che, desconfío un poco, aunque no tengo tanta evidencia por ahora para justificar.

Tenía entendido que la notación vectorial es simplemente una sintaxis "cheta" para hacer aritmética cuando tenés vectores (es decir, hacer a+1 es equivalente a a[1]), pero recién probé dos programitas y el assembly generado por gcc no dio igual igual.

Dejo acá la prueba, después lo analizo mejor.

Los programas son estos: http://mergely.com/asA8btqb
El disassembly es este: http://mergely.com/IZpRl2G7

Probé en un Ubuntu Server de 32 bits con gcc 4.8.2 (gcc <cosa>.c -o <cosa>), y objdump 2.24 (objdump -d cosa).

Igual un poco perdí el foco.

Incluso si hubiera diferencia de performance entre esos casos (que, eso sí, esperaría que cualquier compilador optimice sin dudarlo), incluso en ese caso me parece gede la pérdida de legibilidad que tenés versus una ganancia marginal de performance.

Entiendo que quizá en electrónica esa diferencia de performance sea más importante que en sistemas, por lo general, pero creo que tampoco es tan distinta la canción.

Por tomar tu ejemplo y hacerlo mierda (probablemente sea injusto, lo se - perdón), ganarías muchísima más performance si usaras un algoritmo de ordenamiento como la gente (justo el bubble sort es el peor algoritmo de ordenamiento) que poniéndote a enchastrar tu código con aritmética de punteros.

[Imagen: 1vbelm.jpg]

[Imagen: a2.php]
[Imagen: 971aa6599664453c05cb3e42d58bbc0eo.jpg]
(Este mensaje fue modificado por última vez en: 05-09-2017 10:00 por Desert69.)
05-09-2017 09:52
Visita su sitio web Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
luchovl2 En línea
Secretario General
Dígame, Ingeniero.
*******

Ing. Electrónica
Facultad Regional Buenos Aires

Mensajes: 993
Agradecimientos dados: 19
Agradecimientos: 249 en 226 posts
Registro en: May 2009
Mensaje: #3
RE: Ejercicio de C para mover bien la cabeza
Cita:Dejo acá la prueba, después lo analizo mejor.

Los programas son estos: http://mergely.com/asA8btqb
El disassembly es este: http://mergely.com/IZpRl2G7

En tu ejemplo la dirección del vector se resuelve en tiempo de compilación, mientras que en el de Diego es dinámica. No sé si afectará.
Igualmente coincido con vos. Probablemente el compilador lo optimize a la mierda.
Tal vez en micros chicos (8 bits) sí haya alguna diferencia.

https://stackoverflow.com/questions/2305...s-pointers

Algo que agregaría a la resolución es la verificación de la asignación de memoria.
05-09-2017 15:26
Encuentra todos sus mensajes Agregar agradecimiento Cita este mensaje en tu respuesta
Buscar en el tema
Enviar respuesta 




Usuario(s) navegando en este tema: 1 invitado(s)



    This forum uses Lukasz Tkacz MyBB addons.