Pensando en animar un poco esta sección propongo un reto en el que podrán participar TODOS LOS QUE SEPAN C o C++.
Imaginen que tengo una matriz de 3x3 y necesito rellenarla de números enteros positivos comprendidos entre 0 y 3*3-1. Los números deben estar dispersos por la matriz, colocados de forma aleatoria. En la matriz no puede repetirse ningún número.
La matriz realmente será de 1000x1000. El que tenga el tiempo de ejecución más bajo GANA, simple no?
Los códigos por MP para no dar ideas. Aquí las preguntas.
Yo no participo, pero tengo mi código que mostraré cuando este reto acabe. También postearé los 3 códigos más rápidos ;).
FECHA LÍMITE: Viernes 31 de mayo de 2013.
Reglas
- Cada código será ejecutado 3 veces y se hará la media entre los tiempos.
- Los números deben estar colocados de modo aleatorio.
- No puede repetirse un número en la matriz.
- Los lenguajes aceptados son C y C++, no es válido combinarlos con ASM de ningún modo.
- Los códigos deben ser multiplataforma. (IMPORTANTE)
EDITO:
Debéis usar dos #define por todo el código para que cambiando los valores de estos pueda crear matrices de 3x3 o 4x4 para poder corregir más rápido, por favor, hacedlo así.
También debéis poner un for que recorra y muestre la matriz, cuando tome los tiempos comentaré y compilaré esa parte, así que tranquilos.
Suerte a tod@s!
Sa1uDoS
1000x1000x4 = 4000000 bytes = 3'8 GB :-\ No tiene sentido tener una matriz así cargada en RAM/paginación. Estaría bien que hubiese que hacer algo con esa matriz y así poder optimizar para evitar generarla o similar...
¿A que te refieres con dispersos? ¿Qué clase de test aplicas sobre ellos para saber si cumplen tu 'dispersión'? ¿Acaso no sería válido ponerlos en orden? Ya que colocándolos de forma aleatoria eso podría ocurrir :P
(EDIT) Ah, me olvidaba: ¿Como medirás la velocidad? ¿Compilador? ¿Parámetros de compilación? ¿Lo decidimos nosotros?
Me encantan los retos :P Saludos ;D
3'8 MB si no fallan mis cuentas (básicamente tengo unos 256MB de RAM y me funciona el código ;) )
No ricemos el rizo, simplemente no pueden estar todos en orden, ese es el punto, debes usar la función rand().
De verdad quieres sacar la probabilidad que hay de que 1 millón de números salgan en orden? Diría que es matemáticamente imposible :P.
La velocidad la mediré con el comando time de UNIX. Quiero el código así que compilaré todos igual gcc code.c -o code.
Sa1uDoS
Interesante, pero necesitaras ver la matriz no?
o no es necesario, porque al mostrarla gasta mucho tiempo.
$4!u2
Cierto, se me olvidó decirlo, poned un for que muestre la matriz para comprobar que cumple con los requisitos, cuando tome el tiempo esa parte del código la comento y compilo para que no se ejecute.
Y por favor haced un
#define MAX_X 1000
#define MAX_Y 1000
que se use por todo el código para que cambiando esos dos valores yo vea que todo está correcto. Así puedo hacer una matriz de 4x4 y ver que no se repitan valores por ejemplo ;).
Por ejemplo for(i=0;i<MAX_X;i++) en vez de poner for(i=0;i<1000;i++)
Ahora edito el post principal. Gracias STANHMAL.
Sa1uDoS
No tienes permitido ver los links.
Registrarse o Entrar a mi cuenta
3'8 MB si no fallan mis cuentas (básicamente tengo unos 256MB de RAM y me funciona el código ;) )
Vaya vergüenza xD No sé ya ni dividir jajaja
¿Entonces estamos forzados a usar rand()? ¿No podemos implementar nuestro PRNG? :-[ Se podría hacer muchísimo más rápido utilizando el PRNG SIMD2 de Intel que genera 4 valores aleatorios por llamada pero para ello debes habilitar la compilación optimizada...
Al principio para que todos tengáis las mismas oportunidades todos serán compilados del mismo modo.
En próximos retos cada uno enviará como quiere compilar...
Suerte a tod@s!
Sa1uDoS
Wooha interesante! haber si es posible hacerlo, nunca he trabajado con una matriz tan grande xD
Por ahora se me ocurre una idea para lo de no repetir tales numeros en tan inmensa matriz :P
ya que hacer una busqueda cada que vayas a meter alguno seria solo una perdida de tiempo(DEMASIADO y absurdo) xD
s00rk espero tu código. Quiero ver que se te ocurrió.
Sa1uDoS
Una consulta podemos hacer uso de Threads? hago pruebas y despues de 500 o mas se me hace que tarda demasiado >___<!!
El tuyo cuando tiempo tarda ? ;$ xD
Debe ser multiplataforma, y los threads, no lo son. No creo que el resultado variase mucho.
500 segundos? El mio tarda entre 0.700s y 0.900s en llenar la matriz(SIN MOSTRAR NADA). Pero mostrando con printf la matriz entera tarda sobre 16-17s.
Sa1uDoS
Señores! Anímense a participar! La fecha límite es el Viernes día 31 de Mayo :).
Espero sus códigos. Venga que no es difícil.
Sa1uDoS
Solo participó s00rk, dejo su código para que juzguen!
No lo declaro ganador porque no funciona correctamente, además de ser bastante poco eficaz.
s00rk me gustaría que pudieras explicar como funciona tu código ;).
Posteo su código y, de paso, el mío.
s00rk:
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_X 10
#define MAX_Y MAX_X
int main()
{
int total = (MAX_X*MAX_Y), nuevonum, x , y, pag = 0, partir = 0, vpartir = total, jx = 0, jy = 0, valor;
int *numeros = (int*) malloc(total*sizeof(int));
int **matriz;
matriz = (int **) malloc(total*sizeof(int*));
for(x = 2; x < total; x++)
if((total%x) == 0 && vpartir > (total/x))
{
partir = x;
vpartir = (total/x);
}
valor = total/partir;
srand (time(NULL));
matriz[jx] = (int*) malloc(total*sizeof(int));
for(x = 0; x < partir; x++)
{
for(y = 0; y < (total/partir); y++)
{
do{
nuevonum = rand() % valor;
if(pag != 0)
nuevonum = rand() % ((valor + (valor*pag)) - valor) + valor;
}while(numeros[nuevonum] == -1);
matriz[jx][jy++] = nuevonum;
numeros[nuevonum] = -1;
if(jy == MAX_Y)
{
jx++;
jy = 0;
matriz[jx] = (int*) malloc(total*sizeof(int));
}
}
pag++;
}
free(matriz);
int i,j;
for(i=0;i<MAX_X;i++)
{
for(j=0;j<MAX_Y;j++)
{
printf("%i\t", matriz[i][j]);
}
putchar('\n');
}
return 0;
}
mr.blood:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAX_X 1000
#define MAX_Y 1000
int main()
{
srand(time(NULL));
int matriz[MAX_X][MAX_Y], x, y;
register int i, j, k;
memset(matriz, -1, sizeof(int)*(MAX_X*MAX_Y));
for(i=0;i<(MAX_X*MAX_Y);)
{
x=rand()%MAX_X;
y=rand()%MAX_Y;
for(k=-1;k<=1;k++)
{
for(j=-1;j<=1;j++)
{
if(matriz[x+k][y+j]==-1 && (x+k>=0 && x+k<MAX_X) && (y+j>=0 && y+j<MAX_Y))
{
matriz[x+k][y+j]=i;
i++;
}
}
}
}
//~ for(i=0;i<MAX_X;i++)
//~ {
//~ putchar('\n');
//~ for(j=0;j<MAX_Y;j++)
//~ printf("%i\t", matriz[i][j]);
//~ }
return 0;
}
Sa1uDoS