Использование потоков и рекурсии в Java для вычисления чисел Фибоначчи

Question

Я относительно новичок в мире Java, и у меня есть проблема, которую я не понимаю.

У меня есть класс (чтобы получить строку Фибоначчи):

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

Теперь задача состоит в том, чтобы запустить f (x-1) и f (x-2) каждый в отдельном потоке. Один раз с реализацией класса Thread, а другой с реализацией Runnable. Как вы, наверное, знаете, это упражнение от моего профессора.

Я знаю, как запустить поток в Java, и я знаю, как теоретически работает весь этот поток, но я не могу найти решение для запуска отдельных потоков в этой рекурсивной функции.

Что нужно сделать в функции запуска?

Возможно

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

А как я могу вставить x в мою выполняемую функцию? Передается ли x в объект при создании?

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

}

в основном методе

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

Или я на неверном пути?

Answer 1

Чтобы это работало, вам нужно 1) способ передать число в новый поток, 2) запустить поток, 3) дождаться окончания потока и 4) способ вернуть результат из потока.

Вы можете передать число через конструктор. У вас может быть открытый элемент данных с именем «answer», который будет содержать результат вычисления. Запуск потока можно выполнить с помощью метода start(), а метод join() ожидает завершения потока.

Следующий пример демонстрирует это. Это должно быть хорошей отправной точкой; отсюда вы можете абстрагироваться от некоторой путаницы, чтобы получить лучший API по желанию.

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

Использование потоков обычно предназначено для повышения производительности. Однако каждый поток добавляет накладные расходы, и если выполняемая задача невелика, накладных расходов может быть гораздо больше, чем фактически выполненной работы. Кроме того, большинство компьютеров могут обрабатывать только около 1000 потоков и зависают, если у вас более 10 тысяч потоков.

В вашем случае, fib (20) создаст 6765 потоков, fib (30) создаст 832K, fib (40) создаст 102M потоков, fib (50) создаст более 12 триллионов. Я надеюсь, вы видите, что это не масштабируется.

Однако, используя другой подход, вы можете вычислить fib (1000000) менее чем за одну минуту.

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 3

У вас есть правильное представление о запуске потоков в функции fib и о передаче x объекту через конструктор; у вас также должен быть способ получить результат вычисления из объекта в конце - я уверен, что вы можете понять это ;-) Процедура запуска потока, которую вы используете в fib, это просто Точно так же вы всегда запускаете поток, например (new Fib(x-1)).start(), хотя вам может потребоваться сохранить поток в переменной, потому что он понадобится вам, чтобы получить результат вычисления позже.

Answer 4

Так что с помощью всех вас мне удалось сделать то же самое с реализацией runnable вместо использования класса Thread.

Можете ли вы все взглянуть и сказать мне, если это так, как это сделать, если задача заключается в реализации работоспособного. Сам код работает.

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");
    }
  }
}