Tuenti Contest

M

#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

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

#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

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

1 respuesta
LOc0

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

salu2 ;)

1 respuesta
tracker086

#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

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

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

Gracias ahora lo leo

LOc0

$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
2 respuestas
tracker086

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

tracker086

#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
Gollumiko

¿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

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

1 respuesta
LOc0

#103

time echo "10" |./tasks

10 2046061

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

Core 2 Duo E8400 3GHz

Salu2 ;)

M

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

S2

1 respuesta
LOc0

#105
995 me sale a mi

Salu2 ;)

M

ok gracias LOc0

tracker086

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

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

S2

1 respuesta
LOc0

#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

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

#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

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

1 respuesta
tracker086

#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

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

BLZKZ

#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

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 :P

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