Uso de hilos y recursión en Java para calcular números de Fibonacci

Question

Soy relativamente nuevo en el mundo de Java y tengo un problema que no entiendo.

tengo una clase (para obtener la fila de Fibonacci):

class Fib { 
    public static int f(int x){ 
     if (x < 2) 
      return 1;  
     else 
      return f(x-1)+ f(x-2);  
    } 
} 

La tarea ahora es comenzar f (x-1) y f (x-2) cada uno en un hilo separado. Una vez con la implementación de la clase Thread y la otra con la implementación de Runnable. Como probablemente sepa, es un ejercicio de mi prof.

Sé cómo iniciar un subproceso en Java y sé cómo funciona todo esto en Thread teóricamente, pero no puedo encontrar una solución para iniciar Threads por separado en esta función recursiva.

¿Qué se debe hacer en la función de ejecución?

Probablemente

public void run(){ 
//int foo=start f(this.x-1) 
    //int bar=start f(this.x-2) 
    //return foo+bar? 
} 

Y cómo puede pegar I x en función de mi ejecutable? ¿Se ha pasado x al objeto en la creación?

Class Fib ...{ 
    int x; 
    public ... run ... 
    public ... f(x).... 

} 

en el método principal

(new Fib(x)).start(); 

o estoy en un camino totalmente equivocado?

Answer 1

Para que esto funcione, necesita 1) una forma de pasar el número al nuevo hilo, 2) iniciar el hilo, 3) esperar a que termine el hilo, y 4) una forma de obtener el resultado de regreso del hilo.

Puede pasar el número a través del constructor. Puede tener un miembro de datos públicos llamado "respuesta" para contener el resultado del cálculo. El inicio del hilo se puede hacer con el método start(), y el método join() espera a que se complete el hilo.

El siguiente ejemplo lo demuestra. Ese debería ser un buen punto de partida; desde aquí puede abstraer algo del desorden para obtener una API mejor si así lo desea.

public class Fib extends Thread 
{ 
    private int x; 
    public int answer; 

    public Fib(int x) { 
     this.x = x; 
    } 

    public void run() { 
     if(x <= 2) 
      answer = 1; 
     else { 
      try { 
       Fib f1 = new Fib(x-1); 
       Fib f2 = new Fib(x-2); 
       f1.start(); 
       f2.start(); 
       f1.join(); 
       f2.join(); 
       answer = f1.answer + f2.answer; 
      } 
      catch(InterruptedException ex) { } 
     } 
    } 

    public static void main(String[] args) 
     throws Exception 
    { 
     try { 
      Fib f = new Fib(Integer.parseInt(args[0])); 
      f.start(); 
      f.join(); 
      System.out.println(f.answer); 
     } 
     catch(Exception e) { 
      System.out.println("usage: java Fib NUMBER"); 
     } 
    } 
} 

Answer 2

usted tiene la idea correcta acerca de cómo iniciar las discusiones en la función fib, y acerca de pasar x al objeto a través del constructor; también necesitarás tener una forma de obtener el resultado del cálculo del objeto al final; estoy seguro de que puedes resolverlo ;-) El procedimiento de inicio del hilo que usas en fib es exactamente de la misma manera siempre inicia un hilo, como (new Fib(x-1)).start(), aunque es posible que desee guardar el hilo en una variable porque lo necesitará para obtener el resultado del cálculo más adelante.

Answer 3

El uso de hilos generalmente está destinado a mejorar el rendimiento. Sin embargo, cada hilo agrega una sobrecarga y si la tarea realizada es pequeña, puede haber mucho más por encima del trabajo real realizado. Además, la mayoría de las PC solo pueden manejar alrededor de 1000 subprocesos y se bloquearán si tiene más de 10 mil subprocesos.

En su caso, fib (20) generará 6765 hilos, fib (30) crea 832K, fib (40) crea hilos 102M, fib (50) crea más de 12 billones. Espero que puedan ver que esto no es escalable.

Sin embargo, usando un enfoque diferente puede calcular fib (1000000) en menos de un minuto.

import java.math.BigInteger; 

/* 
250000th fib # is: 36356117010939561826426 .... 10243516470957309231046875 
Time to compute: 3.466557 seconds. 
1000000th fib # is: 1953282128707757731632 .... 93411568996526838242546875 
Time to compute: 58.1 seconds. 
*/ 
public class Main { 
    public static void main(String... args) { 
     int place = args.length > 0 ? Integer.parseInt(args[0]) : 250 * 1000; 
     long start = System.nanoTime(); 
     BigInteger fibNumber = fib(place); 
     long time = System.nanoTime() - start; 

     System.out.println(place + "th fib # is: " + fibNumber); 
     System.out.printf("Time to compute: %5.1f seconds.%n", time/1.0e9); 
    } 

    private static BigInteger fib(int place) { 
     BigInteger a = new BigInteger("0"); 
     BigInteger b = new BigInteger("1"); 
     while (place-- > 1) { 
      BigInteger t = b; 
      b = a.add(b); 
      a = t; 
     } 
     return b; 
    } 
} 

Answer 4

Así que con la ayuda de todo lo que he logrado hacer lo mismo con la aplicación ejecutable en lugar de utilizar la clase Thread.

¿Pueden todos echar un vistazo y decirme si esa es la forma de hacerlo si la tarea es implementar ejecutable. El código en sí funciona.

public class Fib implements Runnable 
{ 
private int x; 
public int answer; 

public Fib(int x) { 
    this.x = x; 
} 

public void run() { 
    if(x < 2) 
     answer = 1; 
    else { 
     try { 
      Fib f1= new Fib(x-1); 
      Fib f2= new Fib(x-2); 
      Thread threadf1=new Thread(f1); 
      Thread threadf2=new Thread(f2); 
      threadf1.start(); 
      threadf2.start(); 
      threadf1.join(); 
      threadf2.join(); 

      answer = f1.answer + f2.answer; 

     } 
     catch(InterruptedException ex) { } 
    } 
} 

public static void main(String[] args) 

{ 
    try { 

      for (int i=0;i<19;i++){ 
       Fib f= new Fib(i); 
       Thread threadf= new Thread(f); 
       threadf.start(); 
       threadf.join(); 

       System.out.println("Ergebnis:"+f.answer); 

      } 
     } 

    catch(Exception e) { 
     System.out.println("usage: java Fib NUMBER"); 
    } 
    } 
}