Tuenti Contest

M

markov #91 Jun '11

#90 no tengo ni idea de PHP, pero eso que pones de 'memory_get_peak_usage() 700MB' , quiere decir que en ejecución tu programa necesita 700MB de RAM?
si es así, no se si los de tuenti tendrán algún límite prefijado de RAM para cada proceso en ejecución.

S2

1 respuesta

tracker086 #92 Jun '11

He hecho lo de pasarlo a 2 listas en memoria, y tarda unos 3 minutos en copiarlo todo a memoria.

Luego a la hora de resolverlo, va bastante mas rapido....en plan de calcular 2- 3 duraciones por segundo. Asiq voy a echarle un test con 2 cojones a ver si lo pasa mientras me veo una serie xD

El mio se queda en unos 70 megas de ram...tambien es verdad q una parte es en recursiva, pero no estoy hoy con la mente fina para sacarlo de otra forma xd

LOc0 #93 Jun '11

#91

Y memory_get_peak_usage() te devuelve bastante menos memoria de la que chupa realmente xD. Pero ya te digo que el array en memoria no ocupa ni 30MB y está definido globalmente. Otra cosa es PHP y su implementación de funciones recursivas no-tail-asquerosas que a saber ese mega array en qué monstruo se convierte. Intenté primero a sacar las cosas de disco directamente en cada llamada recursiva y era lentísimo. Luego probé a meter todo el fichero en una cadena a pelo y aunque chupaba mucha menos memoria, seguía siendo muy lento a la hora de buscar y sacar las cosas del megachorizo.

Salu2

tracker086 #94 Jun '11

Vale segun lo tengo, me tarda en cargar el primer numero del Test, unos 6 minutos xDDDDD No esta mal xD

1 respuesta

LOc0 #95 Jun '11

#94 ¿Qué número del test es?

salu2

1 respuesta

tracker086 #96 Jun '11

#95 el 4 xDD con C# xD

Hoy estoy en uno de esos dias q no me siento inspirao, y he debido hacer una basura monumental xD. En pasarlo a una lista, tarda unos 2 minutos y medio. Luego en calcular el primer numero solo ha tardado unos 4 mas. Ahora he dicho, a lo loco!! y le lanzao el test, mientras veo una serie xD y a ver q pasa xD. Realmente no me apetece nada ponerme a optimizarlo mas xD.

Por cierto, lo del map, exactamente que es? q no lo he usado nunca.

LOc0 #97 Jun '11

Me refería a qué número del test has probado. A mi con el 3 me tarda 13 segundos en un Core2Duo E8400.

http://en.wikipedia.org/wiki/Mmap

Salu2

1 respuesta

tracker086 #98 Jun '11

#97 he probado el 999566 que es el primero que me pone en el test_challenge.exe xD

Gracias ahora lo leo

LOc0 #99 Jun '11

$time echo "999566" | php tasks_mem.php
999566 849

real 0m3.667s
user 0m3.313s
sys 0m0.350s

En C y usando varios threads se podría mejorar bastante...

Salu2

EDITO:

versión_c_guarra

#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define FICHERO "tasks.in"
#define MAX_BUFFER 4192

typedef struct tarea{
	int d, tot_dep;
	int *dep;
}TAREA;

TAREA *tasks;
int tot_tasks;

int dura(int);
void load_in_file();

int dura(int t)
{
	int dur=tasks[t].d, i,j, max=0, d;
	
if(tasks[t].tot_dep > 1)
{
	for(i=0; i<tasks[t].tot_dep; i++)
		if((d=dura(tasks[t].dep[i])) > max)
			max=d;
			
	dur+=max;
}
else if(tasks[t].tot_dep)
	dur+=dura(tasks[t].dep[0]);

return dur;
}

void load_in_file()
{
	FILE *fp=fopen(FICHERO,"r");
	
if((fp=fopen(FICHERO,"r")))
{
	char buffer[MAX_BUFFER], aux[MAX_BUFFER];
	int tot,i,fin,j,h,k,l;
	
	fgets(buffer, MAX_BUFFER, fp);
	fgets(buffer, MAX_BUFFER, fp);
	buffer[strlen(buffer)-1]=0;
	tot_tasks=atoi(buffer);

	fgets(buffer, MAX_BUFFER, fp);
	fgets(buffer, MAX_BUFFER, fp);
	
	tasks=malloc(tot_tasks*sizeof(TAREA));
	
	for(i=0; i<tot_tasks; i++)
	{
		fgets(buffer, MAX_BUFFER, fp);
		buffer[strlen(buffer)-1]=0;
	
		j=0;
		while(buffer[j])
		{
			h=0;
			while(buffer[j] && buffer[j]!=',')
				aux[h++]=buffer[j++];
			
			aux[h]=0;
			
			tasks[i].d=atoi(aux);
			tasks[i].tot_dep=0;
			j++;
		}
	}
			
	fgets(buffer, MAX_BUFFER, fp);
	fgets(buffer, MAX_BUFFER, fp);
	
	while(fgets(buffer, MAX_BUFFER, fp))
	{
		buffer[strlen(buffer)-1]=0;
		
		h=0;
		j=0;
		while(buffer[j] && buffer[j]!=',')
			aux[h++]=buffer[j++];
		
		aux[h]=0;
		
		k=atoi(aux);
		
		l=0;
		j=0;
		while(buffer[j])
		{
			if(buffer[j++]==',')
				l++;
		}
		
		tasks[k].tot_dep=l;
		
		if(tasks[k].tot_dep)
		{
			j=0;
			while(buffer[j] && buffer[j++]!=',');
		
			tasks[k].dep=malloc(tasks[k].tot_dep*sizeof(int));
			l=0;
			
			while(buffer[j])
			{
				h=0;
				while(buffer[j] && buffer[j]!=',')
					aux[h++]=buffer[j++];
				
				aux[h]=0;
				
				tasks[k].dep[l]=atoi(aux);
				j++;
				
				l++;
			}
		}

	}

	fclose(fp);
}
}
	

int main()
{	
	int i,j;
	char c, aux[MAX_BUFFER];
	
load_in_file();

FILE *fp=fopen("/dev/stdin", "r");

while((c=fgetc(fp))!=EOF)
{
	aux[0]=c;
	i=1;
	while((c=fgetc(fp))!=EOF && c!=',')
		aux[i++]=c;
	
	aux[i]=0;
	
	printf("\n\n%d %d\n\n", atoi(aux), dura(atoi(aux)));
}

fclose(fp);

return 0;
}

$ulimit -s 32768
$time echo "999566" | ./tasks

999566 849

real 0m0.380s
user 0m0.363s
sys 0m0.013s

No da casi tiempo a verlo, pero chupará unos 25 MB de RAM (el tamaño máximo de la pila he tenido que subirlo a 32M, eso sí).

¡Ayyynns! El viejo C no me ha defraudado xD

2 respuestas

tracker086 #100 Jun '11

#99 Jajaja, vamos que si hay un premio al algoritmo que mas tarde, me lo llevo de calle jaja

tracker086 #101 Jun '11

#99 Joder, vaya tiempos jaja. A mi solo pasarlo lo que viene siendo del fichero a una lista de strings de C#, me tarda ya 2minutos y pico xD.

no es mas que un bucle hasta q llega a #Task Durations y luego otro bucle leyendo lineas y añadiendo cada linea a la lista xd

Lo mas facil sería decir que C# no tiene nada q ver a C y por eso va tan lento, pero se que la culpa no será de C# sino mía xDD.

Mi codigo del problema 4

class Program
    {
        static void Main(string[] args)
        {

        Lector lector = new Lector();

        string input = Console.ReadLine();
        string[] datos = input.Split(',');

        foreach (string n in datos)
            Console.WriteLine(lector.DuracionTotal(n));
        Console.Read();
    }
}

class Lector
{
    List<string> duraciones;
    List<string> dependencias;
    string url = "in";

    public Lector()
    {
        LeerDuracion();
        LeerDependencias();
    }

    private int Duracion(string tarea)
    {
        string[] numeros = duraciones[Convert.ToInt32(tarea)].Split(',');
        return Convert.ToInt32(numeros[1]);
    }

    private List<string> Dependencias(string tarea)
    {
        string[] aux;
        List<string> resultado = new List<string>();
        foreach (string i in dependencias)
        {
            if (i != null)
            {
                aux = i.Split(',');
                if (aux[0] == tarea)
                {
                    for (int j = 1; j < aux.Length; j++)
                        resultado.Add(aux[j]);
                    break;
                }
            }
        }
        return resultado;
    }

    public int DuracionTotal(string tarea)
    {
        List<string> dependencias;
        dependencias = Dependencias(tarea);


        int max = 0;
        foreach (string n in dependencias)
        {
            int aux = DuracionTotal(n);
            if (aux > max)
                max = aux;
        }

        return Duracion(tarea) + max;
    }

    private void LeerDuracion()
    {
        duraciones = new List<string>();
        using (StreamReader reader = new StreamReader(url))
        {
            string linea = reader.ReadLine();
            while (linea != "#Task duration")
            {
                linea = reader.ReadLine();
            }

            while (linea != String.Empty)
            {
                linea = reader.ReadLine();
                duraciones.Add(linea);
            }
        }
    }

    private void LeerDependencias()
    {
        dependencias = new List<string>();
        using (StreamReader reader = new StreamReader(url))
        {
            string linea = reader.ReadLine();
            while (linea != "#Task dependencies")
            {
                linea = reader.ReadLine();
            }

            while (linea != null)
            {
                linea = reader.ReadLine();
                dependencias.Add(linea);
            }
        }
    }
}

Gollumiko #102 Jun '11

¿A alguno se os queda atascado al intentar enviar una solución?

Estoy intentando enviar la solución del noveno y despues de poner "Received solution md5sum" y el hash, no hay manera de que avance, he estado esperando durante media hora y nada, he optimizado el código y tampoco.

M

markov #103 Jun '11

habeis probado vuestros algoritmos del problema 4 con numeros bajos? por ejemplo: el 10 ?
probadlo y me contais cuanto tarda

1 respuesta

LOc0 #104 Jun '11

#103

time echo "10" |./tasks

10 2046061

real 0m0.401s
user 0m0.363s
sys 0m0.037s

Core 2 Duo E8400 3GHz

Salu2

M

markov #105 Jun '11

Podéis decirme cuánto da el 999512 en el problema 4?

S2

1 respuesta

LOc0 #106 Jun '11

#105
995 me sale a mi

Salu2

M

markov #107 Jun '11

ok gracias LOc0

tracker086 #108 Jun '11

Alguien sabe segun el codigo que he peusto arriba, si sq he hecho alguna burrada para que me tarde cosa de 6 o 7 minutos en calcular cada numero? XD

1 respuesta

M

markov #109 Jun '11

y para 999721 y 999632 ? joer no me cuadran cosas XD

S2

1 respuesta

LOc0 #110 Jun '11

#109

Si no me he equivocado...

999721 575

999632 718

Compílate algún código de los pegados aquí.

#108

Hay varios "cuellos de botella" en el cuarto. Uno es el propio algoritmo, que es claramente recursivo-no-final (vamos, de la recusividad "petadora" xD) que ahí ya dependes de la "calidad" del lenguaje y en eso C/C++ parten la pana. (Puedes usar un algoritmo iterativo si se te ocurre, pero con muchísima probabilidad tendrás que usar una pila y para "emular" la pila recursiva pues mejor usar la propia recursividad del lenguaje, ¿no?).
Luego está el tema del fichero, pero sobre todo cómo almacenes en memoria éste para poder acceder a él lo más rápido posible. Lo más eficiente es un array que puedas direccionar directamente con el número del task Y para las dependencias lo mismo, otro array de enteros. (Leer de disco cada vez queda completamente descartado). Me he fijado que tú buscas las dependencias de una tarea dada cada vez con un bucle y además usando split para separar los datos. Eso penaliza bastante. Tb es mejor tener el menor número de funciones distintas ya que sus llamadas penalizan. Pero vamos, el lenguaje elegido es fundamental.

Estos de Tuenti me da que han enfocado más el concurso a la escalabilidad que a la algoritmia en sí (id pegando enunciados COMPLETOS si podéis).

Salu2

2 respuestas

Gollumiko #111 Jun '11

No hay manera de enviar el noveno, llevo toda la tarde intentando enviarlo y ya no se hacerlo de una manera más óptima. No se si es problema mío o del servidor de tuenti.

Hay algunos problemas en los que puedes complicarte la vida y su solución es más fácil de lo que en principio parece. En el séptimo perdí un día entero y se puede solucionar googleando un poco.

Por cierto, ¿en qué prueba estáis?

tracker086 #112 Jun '11

#110 Muchas gracias tio! Bueno pues visto lo visto, voy a pasar del 4º, me lo dejare pendiente de revision xD. Y asi almenos pillo el enunciado 5 y lo cuelgo por aqui.

Si alguien tiene el 6 o en adelante que los vaya poniendo q copie pege de la web y ya me encargo yo de organizarlo en 1#

1 respuesta

M

markov #113 Jun '11

#112 ojo, si pasas de un problema luego ya no puedes retomarlo

1 respuesta

tracker086 #114 Jun '11

#113 Ya..si lo tengo hecho y funcionando solo el tema de la lentitud xd. Y prefiero dejarlo sin hacer y continuar con los siguientes.

Si ademas, de lo poco que queda, practicamente ya no voy a poder hacer muchos mas, asiq los ire haciendo poco a poco una vez termine xD.

X cierto, como esta el tema de concursos, en evernote han hecho otro, y ese de premio son 50.000 $ http://www.evernote.com/about/etc/competition.php

Yo a ese no entro xq me pilla en fecha muy mala, y xq ese tiene pinta de ser en plan mucho mas serio, y yo lo que quiero es por ocio y aprendizaje xD

1 respuesta

M

markov #115 Jun '11

#114 los de la UVA-ACM también son interesantes

BLZKZ #116 Jun '11

#110 si tienes un recursivo no final, lo puedes pasar a final y en cuanto lo tengas haces el iterativo del tirón xD

Hay tecnicas para pasar de recursivo a tail recursion

r2d2rigo #117 Jun '11 Inocente

Hice hasta el 6 en C#, pero tuve que dejarlo porque me atasque en el 7 y habia que seguir currando. He publicado el codigo en CodePlex por si alguien quiere echarle un vistazo

http://intmain.codeplex.com/SourceControl/changeset/view/90340

Usuarios habituales

Tags