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

Я относительно новый в мире 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. Как вы, наверное, знаете, это упражнение от моего профессора.

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

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

Возможно

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();

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

Ответ 1

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

Вы можете передать число через конструктор. У вас может быть открытый элемент данных, называемый "ответ", чтобы содержать результат вычисления. Запуск потока можно выполнить с помощью метода 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");
        }
    }
}

Ответ 2

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

В вашем случае 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;
    }
}

Ответ 3

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

Ответ 4

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

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

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