SoloCodigo

CLR: .Net / Mono / Boo / Otros CLR => C# => Mensaje iniciado por: JuanK en Domingo 5 de Noviembre de 2006, 16:46

Título: Performance
Publicado por: JuanK en Domingo 5 de Noviembre de 2006, 16:46

Saludos,

quisiera recibir opiniones y sugerencias para optimizar el rendimiento de esta funcion porque me esta costando mucho trabajo y no se que mas hacerle.

La funcion ObtenerTablaHuffman recibe como parámetro el primer nodo de un árbol binario donde los únicos nodos que me interesan son las hojas, esta función invoca a la función  ProcesarNodo la cual se encarga de recorrer el árbol de manera recursiva e ir elaborando un mapa para llegar a cada una de las hojas, cuando tiene completo el mapa para llegar a una de las hojas guarda esa información en el objeto  tablaHuffman.

El problema desde luego esta en la funcion recursiva, he hecho pruebas usando arrays en vez de listas pero los resultados, si bien han existido, son casi despreciables, y estoy necesitando optimizar esta rutina de alguna manera.

Recibo sugerencias y/o correcciones.

Gracias.

<!--xc1--></div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td>XCODE </td></tr><tr><td id='XCODE'><!--exc1-->
        /// <summary>
        /// Obtiene una tabla con el color y el mapa a seguir en el arbol binario
        /// para hallar dicho color
        /// </summary>
        /// <param name="nodoPadre">Nodo padre del arbol huffman</param>
        /// <returns>Un array que representa la tabla creada</returns>
        public NumeroColorHuff[] ObtenerTablaHuffman(NodoHuffman nodoPadre)
        {
            List<NumeroColorHuff> tablaHuffman = new List<NumeroColorHuff>(nodoPadre.frecuencia);
            NodoHuffman nodoAux = nodoPadre;
            CodificadorJKI<T>.CompNumColorHuff_NumColorHuff_Color comparador = new CodificadorJKI<T>.CompNumColorHuff_NumColorHuff_Color();
            List<byte> listaBytes = new List<byte>(32);

            ProcesarNodo(nodoAux, tablaHuffman, listaBytes);

            NumeroColorHuff[] tabla = tablaHuffman.ToArray();
            Array.Sort(tabla, comparador);
            return tabla;
        }

        /// <summary>
        /// Procesa un nodo y sus hijos, determina si agrega u nuevo nodo a la tabla y lleva un registo de la
        /// ruta seguida hasta llegar a un nodo que debe ser ingresado en la tabla
        /// </summary>
        /// <param name="nodo">Nodo padre del arbol huffman</param>
        /// <param name="tablaHuffman">Tabla donde se dejaran los nodos validos hallados</param>
        /// <param name="listaBytes">Lista de bytes que sirve de mapa para determinar la ruta hasta llegar a los diferentes nodos hoja.</param>
        private void ProcesarNodo(NodoHuffman nodo, List<NumeroColorHuff> tablaHuffman, List<byte> listaBytes)
        {
            if (nodo.color != null)
                tablaHuffman.Add(new NumeroColorHuff(
                                         (T)nodo.color,
                                         listaBytes)
                                         );
            else
            {
                if (nodo.derecha != null)
                {
                    listaBytes.Add(1);
                    ProcesarNodo(nodo.derecha, tablaHuffman, listaBytes);
                }

                if (nodo.izquierda != null)
                {
                    listaBytes.Add(0);
                    ProcesarNodo(nodo.izquierda, tablaHuffman, listaBytes);
                }
            }

            if (listaBytes.Count > 0)
                listaBytes.RemoveAt(listaBytes.Count - 1);
        }
    }<!--xc2--></td></tr></table><div class='postcolor'><!--exc2-->

Actualmente esta tardando mas 20 segundos en recorrer un árbol que tiene 22.196 hojas aunque el total de nodos es considerablemente mayor y no lo tengo estimado. b:(

Título: Re: Performance
Publicado por: JuanK en Domingo 5 de Noviembre de 2006, 17:13

Ok, ya lo solucione...

Código: Text

1. nodo.color
2.  

La clase color tiene una sobrecarga en los operadores == y != porque en otras partes del código necesito comparar entre colores...

Asi que cambie la pregunta que usaba para saber si estaba en una hoja y en vez de preguntar esto:

Código: Text

1. if (nodo.color != null)
2.  

pregunto esto:

Código: Text

1. if (nodo.derecha == null && nodo.izquierda == null)
2.  

Hice algunos cambios relacionados con eso mismo y ahora el proceso tarda 3 segundos  :lol:


En todo caso sigo recibiendo sugerencias para hacerlo aun mas rápido.  :smartass:

Título: Re: Performance
Publicado por: pabloreda en Domingo 5 de Noviembre de 2006, 18:31

JuanK

Quizas una de las formas mas comunes de perder el tiempo es alojando y desalojando memoria, muchas veces (por no decir todas) es posible estimar cuanto de memoria se va a usar y podes definir la memoria en forma estatica, esto es un horror para muchos puristas del lenguaje, pero generalmente estos puristas jamas en su vida tuvieron que optimizar un codigo.

Es notable como las practicas de "buena" programacion como no usar variables globales y definir clases para cualquier cosa se vuelven contraproducentes cuando tratas de optimizar el codigo.

Yo te recomendaria tratar de programarlo en C pelado (es un dialecto exclusivo :), utilizar PROFUSAMENTE punteros y evitar todo movimiento de memoria, a veces puede ser dificil detectar lo que realmente esta pasando por muchas caracteristicas del lenguaje (late binding, sobrecarga de operadores, garbage colector y esas cosas).

suerte... Pablo

Título: Re: Performance
Publicado por: Eternal Idol en Domingo 5 de Noviembre de 2006, 18:33

JuanK trabaja con C# como si fuera MS-DOS, reserva memoria estatica, te lo recomiendo ya que yo me dedico a optimizar programas que no usa nadie jamas ni sirven para nada.

Título: Re: Performance
Publicado por: JuanK en Domingo 5 de Noviembre de 2006, 18:58

Cita de: "pabloreda"

Quizas una de las formas mas comunes de perder el tiempo es alojando y desalojando memoria, muchas veces (por no decir todas) es posible estimar cuanto de memoria se va a usar y podes definir la memoria en forma estatica, esto es un horror para muchos puristas del lenguaje, pero generalmente estos puristas jamas en su vida tuvieron que optimizar un codigo.

Es notable como las practicas de "buena" programacion como no usar variables globales y definir clases para cualquier cosa se vuelven contraproducentes cuando tratas de optimizar el codigo.

Yo te recomendaria tratar de programarlo en C pelado (es un dialecto exclusivo :), utilizar PROFUSAMENTE puntl detectar lo que realmente esta pasando peros y evitar todo movimiento de memoria, a veces puede ser dificior muchas caracteristicas del lenguaje (late binding, sobrecarga de operadores, garbage colector y esas cosas).

OK,
llegue a pensar en hacerlo en C++/C  pero definitivamente no porque esto es para el reto y ya lo llevo casi en 80% y terminado en C#.

En C# también puedo valerme de diabluras  :devil: para reservar algo de la memoria estáticamente pero no logre adecuar esas diabulras para hacer un uso mas optimo... si la mayoría de problemas los he tenido en la reserva de memoria y en este ultimo caso con lo de la sobrecarga de operadores que desde luego al codificar esta parte del codigo paso desapercibidamente y no fue sino hasta cuando hice un debug paso a paso al 100% de profundidad dentro del código que logre detectarlo y abolir su uso en este segmento.

Como te daras cuanta me fui por la opción de comparación de punteros la cual es completamente mas rápida.

Tengo un proyecto muy importante para iniciar... de hecho en eso ando también por estos días  y el performance puede llegar a ser un asunto demasiado importante , de hecho demasiado delicado, por lo cual estoy pensando seriamente en hacerlo en C++ y si el asunto se me complica tanto como peude ser posible yo no descartaria tener que usar algunas técnicas extremas.

Título: Re: Performance
Publicado por: JuanK en Domingo 5 de Noviembre de 2006, 19:01

Citar

JuanK trabaja con C# como si fuera MS-DOS

No se puede del todo porque no existen en el momento implementaciones del CLR que generen código de 16 bit y que corran en modo real.

Citar

reserva memoria estática, te lo recomiendo ya que yo me dedico a optimizar programas que no usa nadie jamas ni sirven para nada.

Y sino sirven para nada... para que los haces?  :rolleyes:

 :devil:

Título: Re: Performance
Publicado por: Eternal Idol en Domingo 5 de Noviembre de 2006, 19:43

Cita de: "JuanK"

No se puede del todo porque no existen en el momento implementaciones del CLR que generen código de 16 bit y que corran en modo real.

¿Como que no? int variable_estupida[0xFFFFFF]; ya esta, como si fuera MS-DOS ... que fue lo que dije.

Cita de: "JuanK"

Y sino sirven para nada... para que los haces?  :rolleyes:

Podria decirte que para que los boludos pregunten o tambien para que me sigan pagando pero en realidad, cosa que intuyo ya sabias, no hablaba de mi precisamente.

Título: Re: Performance
Publicado por: pabloreda en Domingo 5 de Noviembre de 2006, 20:31

Ok JuanK, cualquier cosa avisa..