Tiempo de ejecucion menor

[Farookh_Bulsara]

hola ,tengo unas dudas
hay un concurso de programacion en el que pretendo participar ,el lenguaje sera Java
el problema o mas bien mi duda radica en que en ese concurso ,lo que mas califican es el tiempo de ejecucion
osea por decir el programa funciona como se desea , pero lo que mas valor tiene en el puntaje es cuanto es su tiempo de ejecucion
por decir:
int var=0;
var=var+1 ;

o


var++;


como sabemos la segunda opcion es mejor ,es mas rapida
tambien al hacer el tipico problema de factorial es mejor hacer con un fro (o while ,cualquier estrucutra de control que se desee) que hacer con un metodo recursivo
en fin, mi pregunta es la siguiente:
cuales son los factores o que debo tomar en cuenta al momento de programar y que el tiempo de ejcucion sea menor? ;donde consigo las tecnicas que debo seguir? ,(como di en los ejemplos)

[GreenEyed]

como sabemos la segunda opcion es mejor ,es mas rapida

¿Ah si? Yo sinceramente lo dudo ya que cualquier compilador minimamente inteligente acaba con el mismo codigo en ambos casos. Lo unico que haces es escribir menos.

En cuanto a consejos generales sobre optimización... son muy dificiles de dar ya que hay muchos aspectos diferentes y al ser Java un lenguaje de nivel bastante alto (con varias capas de abstracción, me refiero) es dificil hacer predicciones.

Pero asi por encima, normalmente el código más "simple/previsible" suele ser el más eficiente, puesto que el compilador es capaz de optimizarlo más facilmente. Las llamadas a métodos són más costosas que insertar código, por ejemplo y luego depende mucho del programa y lo que haya que realizar. Y en Java hay muchas cosas a tener en cuenta, empezando por el Garbage Collector que es "dificil de predecir".

Para poder ser capaz de predecir esas cosas, habria que estudiarse la especificacion de la JVM que se va a utilizar, ya que puede variar, y jugar con el codigo resultante en bytecode de diferentes aproximaciones.

Habia un apartado antes en el web de sun sobre rendimiento, pero no se si sigue por ahi. Para la mayoria de casos es un tema relativamente irrelevante, y por eso no hay mucha literatura.

Suerte!

[Farookh_Bulsara]

sinceramente lo dudo ya que cualquier compilador minimamente inteligente acaba con el mismo codigo en ambos casos. Lo unico que haces es escribir menos.

estas seguro? ,hacer count++ es menos costoso que hacer count=count+1, lo lei en varios libros ,incluso en el de Deitel (programando en C/c++) dice eso,
tambien dice que hacer metodos recursivos es mas costoso que hacer procesos utilizando estructuras de control(for ,while,etc)
es por eso que quisiera saber que otras tecnicas hay que tomar en cuenta

[GreenEyed]

En lo de los métodos recursivos estoy totalmente de acuerdo, ya he dicho que llamar a metodos es mas costoso que escribir el codigo directo, y la recursividad es un claro ejemplo. Eso si, hace poco lei un articulo que decia que con los nuevos compiladores, a veces no estaba tan claro ya que al tener el codigo en una sola funcion, los compiladores nuevos podian hacer optimizaciones que el programador por si solo no puede hacer en tiempo de compilacion.

En todo caso, el ejemplo de count++ y count=count+1 es simplemente una cuestion del compilador. Cuando el compilador lee las dos sentencias, lo transformara en exactamente el mismo codigo bytecode y por eso el rendimiento ha de ser el mismo. Y si no lo hace así, el compilador es una chapuza para tirar , cosa que el de Java no es.

En Java y con compiladores tan sofisticados, es bastante complicado hacer predicciones.

S!

[Farookh_Bulsara]

que otros aspectos hay que tomar en cuenta para lo que quiero?

[locoporelrojo]

Iniciado por Farookh_Bulsara

estas seguro? ,hacer count++ es menos costoso que hacer count=count+1, lo lei en varios libros ,incluso en el de Deitel (programando en C/c++) dice eso,
tambien dice que hacer metodos recursivos es mas costoso que hacer procesos utilizando estructuras de control(for ,while,etc)
es por eso que quisiera saber que otras tecnicas hay que tomar en cuenta

Si es más costoso hacer métodos recursivos, porq estos almacenan los valores q retorna el método temporalmente en la memoria, haciendo que esta se cope mucho más y más veloz q haciendo un ciclo común.

En cuanto al tiempo, hacer un método recursivo resulta mucho más eficiente, ya q este no haría las n comparaciones q hace un ciclo común (en algunos casos, en otros si es inevitable q los haga) sino q cada llamado evalua un camino a seguir, algo asi como un arbol, y si sabes algo de complejidad de algoritmos, sabras q es más eficiente una complejidad de orden log(n) q una de n.

[Farookh_Bulsara]

osea hacer un metodo recursivo es mas costos en espacio ,pero mas rapido en tiempo?
que otras tecnicas existen para reducior el tiempo ? o que aspectos se deben tomar en cuenta?

[locoporelrojo]

Iniciado por Farookh_Bulsara

osea hacer un metodo recursivo es mas costos en espacio ,pero mas rapido en tiempo?

Asi es, un método recursivo es más optimo en cuanto al tiempo de ejecución que un bucle, pero en cuanto al costo de memoria es mucho mejor manejar estos ultimos.

[GreenEyed]

Iniciado por locoporelrojo

Asi es, un método recursivo es más optimo en cuanto al tiempo de ejecución que un bucle

No estoy de acuerdo. El coste de llamar a un metodo y recuperar lo que devuelve es mucho mayor que hacer una comparación o dos extra, cosa que un calculo simple de complejidad no tiene en cuenta.

Para muestra, un botón:

Código:

static int factorial(int n)
  {
    if (n <= 1)
    {
      return 1;
    }
    else
    {
      return n * factorial(n - 1);
    }
  }

Código:

static int factorial_2(int n)
  {
    if (n <= 1)
    {
      return 1;
    }
    else
    {
      int fact = n;
      for (int i = n - 1; i > 1; i--)
      {
        fact *= i;
      }
      return fact;
    }
  }

El segundo método(bucle) se ejecuta, en mi maquina, más del doble de rápido que el primero(recursión).

Aparte de que con la recursión, con n mayor que 12000 y pico empieza a saltarme StackOverflowError, y con el bucle puedo seguir hasta que los int se me salgan de rango.

Así que como regla general... yo no diría que la recursión es más rápida. Para mi siempre ha sido: recursion -> claro, limpio y limitado; bucle -> más complejo, más rápido y menos limitado.

S!

[locoporelrojo]

Y, puede q tengas razón GreenEyed; en la segunda respuesta que le doy a Farookh_Bulsara cometo un error al no escribir que un método recursivo no siempre es el más optimo en cuanto a velocidad de respuesta, como si lo hice en la primera respuesta que le dí, pero lo que si escribí es que un método recursivo consume mucha más memoría que un bucle, y esto es debido a que debe almacenar valores temporales en la memoria.

[Farookh_Bulsara]

como se sabe que metodo es mas recursivo y cual ocupa mas memoria?

pero lo que si escribí es que un método recursivo consume mucha más memoría que un bucle, y esto es debido a que debe almacenar valores temporales en la memoria.

entonces por eso sale este mensaje:
StackOverflowError
osea ya no hay campo en la memoria?

[pyanqn]

Bueno, para determinar si usas un metodo recursivo o iterativo, debes de evaluar su tiempo de ejecución primero. Como muestran los ejemplos dados por GreenEyed, los dos algoritmos tinen el mismo orden de ejecución O(n). La diferencia entre ellos es tan solo una constante. Ahora depende de ti, lograr que esa constante sea lo mas pequeña posible para que tu algoritmo sea mas eficiente. El overhead del algoritmo recursivo es alto, recuerda que en cada llamada a un metodo, se generan en la pila un nuevo registro de activación, aquí, el costo es muy alto!!

Yo te aconsejaria uses recursividad solo cuando esta tenga un impacto significativo. es decir ciertos algoritmos se comportan de forma optima para entradas pequeñas o medias, pero luego escalan a ordenes intolerables! ese es otro punto a tener en cuenta. Para que no te ocurra que tu algoritmo sea optimo, como suele ocurrir con algoritmos de ordenamiento, en los cuales, la ventaja se ve en grandes entradas de datos, pero para pequeñas, su comportamiento no significativamente menor al de uno algoritmo lineal.

Saludos

[GreenEyed]

StackOverflowError no significa que ya no tengas memoria. Significa que te has quedado sin espacio en la pila de llamadas. Imagina que cada vez que un metodo llama a un metodo pones un ladrillo y que solo se quita cuando el metodo acaba. Si llegas al "techo" da un StackOverflow, y los metodos recursivos son todo llamar a un metodo que se llama a si mismo que se llama a si mismo que se llama... asi que es facil que den estos errores.

S!

[Farookh_Bulsara]

como puedo saber cuando un metodo es mejor en cuanto a tiempo o a cuanto recursos? hay alguna de saber eso ,usando alguna metrica?

[pyanqn]

Iniciado por Farookh_Bulsara

como puedo saber cuando un metodo es mejor en cuanto a tiempo o a cuanto recursos? hay alguna de saber eso ,usando alguna metrica?

Así como Orden de ejecución O() existen otras metricas para el calculo de uso de recursos, claro que esto es mas dificil de calcular porque dependel codigo generado por tu compilador y la maquina subyacente, yo te diria, solo presta atencion al Orden de ejecucion O(), este te dira cuando usar recursion y cuando no.

[Farookh_Bulsara]

solo presta atencion al Orden de ejecucion O(), este te dira cuando usar recursion y cuando no.

que es O() ? es un algoritmo para calcular el tiempo de ejecucion? donde consigo info sobre eso?
ahora cual es mejor un proceso recursivo o un bucle? me confundieron

[pyanqn]

fijate en cualquier libro de algoritmia.
Lo que trato de decirte es que no hay recetas de como enfrentar la resolucion de un problema con algoritmos. El O() (Funcion O; Orden de ejecucion) te puede decir si un algoritmo tiene orden n, n2 (n cuadrado), log n (Logaritmico)... etc...

Bien debes saber que las soluciones que involucran arboles, por lo general tienen una solucion algoritmica, y esta es la mejor! ya que de otra forma puede convertirse en cuadrada.

Y por ultimo no hay mejor ni peor, sino mas o menos adecuado.

[GreenEyed]

Si no recuerdo mal, O() representa la "complejidad" de un algoritmo, pero no dice nada sobre su tiempo de ejecucion ni su consumo de recursos. Puede darte una idea, pero tampoco es para fiarse mucho, en cuanto a tiempo de ejecucion y recursos, ya que no tienen en cuenta la implementacion real de los algoritmos.

S!

[Willie]

* Green tiene razon: O() solo mide la complejidad teoretica del algoritmo. El O() simplemente te da una idea del comportamiento (asintotico) del algoritmo en funcion de la magnitud de los datos procesados (n)
* complejidad algoritmica --> quieres decir logaritmica?

Para saber como se comporta tu programa, tienes que medir varias cosas, como por ejemplo llamada de memoria, llamadas de IO, llamadas al procesador, etc, etc. Esto no necesariatemente facil, y es a lo que se dedican ingenieros de QA (aseguramiento de calidad)

[ec89]

Perdon que levante este post (no se si esta permitido) pero justo estaba buscando info sobre eficiencia. Queria aclarar que no es obvio que utilizar un ciclo es mas eficiente que una funcion recursiva, es mas si la recursion esta bien hecha es imposible que un ciclo sea mas eficiente, con decir que este bien hecha no quiere decir que cumpla con la especificacion, por ejemplo si yo tengo de una recursion "x(int i)" que un caso me retorna: x(i-1)+x(i-1) ; eso es poco eficiente ya que tengo que calcular dos veces "x(i-1)" pero esto es evitable haciendo recursión final.
Por eso todo depende de como sea la recursion.

[HackmanC]

Hola,

Iniciado por ec89

... es mas si la recursion esta bien hecha es imposible que un ciclo sea mas eficiente, ...

¿What?

Ya GreenEyed lo demostró, y pyanqn lo explicó.
(Ahora que después de eso hay varias 'barbaridades').

Un algoritmo que usa recursividad va a ser mucho menos eficiente que un algoritmo secuencial.
Y cualquier algoritmo que usa recursividad es puede reescribir en forma secuencial.

¿Por qué?

• Cuando el compilador genera una llamada a una función (cualquiera que sea), realiza muchas actividades que el programador no 'mira'.
• Cuando el lenguaje está orientado a objetos la llamada a la función es 'inclusive' mucho mas compleja que un lenguaje procedural.
• No importa si lo llama N, N+1, N+1000 veces, cada ciclo consume muchos mas recursos que un ciclo normal 'for', 'while', etc.
• Una vez el código recursivo y secuencial estén bien escritos.

Cuando escribimos una llamada a una función así :

MyObjeto.funcion();

El compilador hace miles de cosas diferentes 'que no miramos'; para saber que 'instancia' de la clase MyObjeto está llamando la función, prepara un area de memoria para almacenar los datos específicos del objeto, revisa si el método no está overloaded, pasa un parámetro 'this' oculto, revisa la sincronización, si el objeto está sincronizado el monitor revisa si fué adquirido o reentrado, etc.

Al final son demasiadas instrucciones invisibles. Cosas que el programador no tiene control porque son parte del compilador.

• Para comprender a profundidad el concepto tendrias que conocer como funciona el compilador de Java, y el bytecode que genera.
• Cada llamada a una función genera una instrucción 'invokevirtual'.

Lee la información de invokevirtual en :
http://java.sun.com/docs/books/jvms/...ons2.doc6.html

Saludos,

Por aparte ...

• Como ejercicio podrías buscar el código fuente de un compilador C++ que esté escrito en C (no un programa escrito en C++ sino el código fuente del compilador), y mira la cantidad de procedimientos que requiere una simple y sencilla llamada a una función.
• Y eso no significa que los lenguajes como C o Pascal, no tengan esta situación, una llamada a una función en C genera muchas instrucciónes en Assembler que consumen muchos ciclos de CPU.

Por qué es importante conocer el bytecode?.
http://www.ibm.com/developerworks/ib...ggar_bytecode/

[Bryan39]

Con esto podran saber el tiempo de ejecucion de un programa
long TInicio = System.currentTimeMillis();//lo ponen al inicio del programa
TFin = System.currentTimeMillis();//y esto lo ponen al final del programa
tiempo = TFin - TInicio;
System.out.println("Tiempo de ejecución en milisegundos: " + tiempo);