Estimados,
Subí un tree.zip actualizado con los siguientes cambios:
*tree_delete
*fclose en tree_read
*tree_generator.m: genera árboles binarios balanceados y degenerados en el formato definido. SÓLO funciona con tamaños potencia de dos (ej. 2^h-1). Cambiando una variable se elige un tipo u otro.
*t1.tree ... t5.tree: árboles chicos de ejemplo
Hola. Estuve probando con los árboles de ejemplo y funcionan todos salvo el t5.tree. Me podrían confirmar si el formato es correcto? Al parecer falta el -1 al final. Pero más allá de eso, todos los nodos a partir del 10 tienen como padre al nodo 0, inclusive el nodo raíz. Cuando corro el algoritmo, al pasarle el nodo raíz a la función de búsqueda, como este no tiene hijos termina inmediatamente. A alguien le funciona? Gracias!
no lo probe aun, pero tiene pinta que falta el -1 si.
Otro comentario, en el nuevo tree.c tuve que comentar el primer include y cambiar "surt()" por "printf()" ... para que compilara.
salute!
matias
Ahora reviso los dos problemas. Voy a hacer un archivo de test así no tenemos esos problemas.
El problema de los árboles es con el generado o con el t5.tree nomás?
Abrazo.
El problema lo tuve solo con el t5.tree. No probé el generador de árboles grandes todavía.
Corregí todo. El t5.tree lo borré, se ve que era un remanente de algo viejo.
Saqué la dependencia de la función surt(). Ahora debería andar todo bien.
Cualquier cosa me avisan.
Estuve tratando de usar el generador de árboles grandes, pero no le encontré la vuelta. Quería saber si la idea es correrlo en Matlab, por ejemplo con: "> file_tree=gen_tree(32,0)" y luego escribir el resultado a un archivo, algo como: "> csvwrite('test_32.tree', file_tree');".
Si hago lo anterior después no puedo levantar correctamente los árboles desde C, es decir, los levanto pero tengo el mismo problema que tenía con el árbol t5.tree que solo se visita el nodo raíz.
En caso de que alguien lo logre o se dé cuenta de qué estoy haciendo mal le agradezco que me avise.
Saludos!
a mi me pasaba lo mismo pero si uso la opción de que sea balanceado y no degenerado me andaba bien.
%%
%genera ?rbol balanceado
type=0;
%genera ?rbol degenerado
%type=1;
lo que hice fue cambiar el hmax para generar arboles con distinto numero de niveles. En particular probé con hmax de 3 a 8 y me funciono ok.
salute
matias
Dos comentarios:
1.- El archivo que hay que usar es el tree_generator.m es un script que hace cosas y llama al gen_tree(), ya hace el guardado y todo. Deja un t.tree en el directorio donde estés.
2.- El caso del árbol degenerado tenía un bug en el número de nodos, ponía más de los que tenía que haber y quedaban vacíos.
Ahora los dos casos están probados, el bug salió porque había hecho dos programas, uno para cada caso. Luego me di cuenta que eran casi iguales y los junté y ahi la embarré. El caso degenerado es más eficiente para reventar el stack porque es el árbol que tiene más profundidad para un número dado de nodos.
Igual les pido disculpas, las cosas hay que probarlas mejor. Por eso es importante hacer testing, eso lo vamos a ver en la última clase, espero.
Un abrazo.
OK. Confirmo que todo funciona ahora. Gracias. No había visto el tree_generator.m, disculpas.
Probé con árboles grandes y veo siempre una diferencia de desempeño a favor de la implementación recursiva. Me gustaría generar un ejemplo donde la implementación iterativa funciona y la recursiva no, pero no pude lograrlo. En particular cuando supero el tamaño 2^18 ambas implementaciones dan segmentation fault. Pensé que podía venir por el lado del uso de int y pasé todo a long, pero no tuvo ningún impacto, siguen sin funcionar. Voy a probar un poco más, pero no sé si me dará el tiempo, quiero terminar el informe.
Saludos!
Martín,
La idea de hacerlo grande era medir la eficiencia más o menos. En general no es mejor una que la otra. Para que el stack reviente, conviene forzarlo. El caso recursivo lo exige porque la dirección de retorno va al stack, pero también porque los argumentos de la función y las variables locales también. Hay un caso, que les voy a subir, donde se puede hacer explotar haciendo que la función recursiva tenga bastantes variables locales.
De todas formas, como les dije al principio, no se cuelguen demasiado. La idea de esta práctica era entender como hacer algoritmos utilizando estructuras de datos más complejas, no importa la eficiencia ni nada.
Hagan el informe y ya está. Después en la puesta en común discutimos estos temas.
Saludos,
Juan
Buenas, bajé el archivo tree.zip desde el wiki, pero sigue teniendo el archivo t5.tree y el #include "graf_utils.h" por mas que esa biblioteca no está incluida en el .zip
Comento porque capaz el nuevo tree.zip esta en algun otro lado de la página y le estoy errando en eso.
Saludos
Disculpas,
El zip se crea automáticamente, y en vez de pasar por encima el viejo le hacía append. Ya se fue el t5.tree y se corrigió el #include sobrante.
Gracias.
Perfecto, esta tarde lo pruebo.
Gracias y saludos