Java ExecutorService для решения рекурсивной серии Фибоначчи - PullRequest
Новая
       7

Java ExecutorService для решения рекурсивной серии Фибоначчи

1 голос
/ 02 июля 2011

Мне нужно узнать число, основанное на некотором индексе в Серии Фибоначчи, рекурсивно используя потоки, и я попробовал следующий код, но программа никогда не заканчивается.Пожалуйста, дайте мне знать, если я что-то упустил.

Код : 

  import java.math.BigInteger;
  import java.util.concurrent.*;

  public class MultiThreadedFib {

    private ExecutorService executorService;

    public MultiThreadedFib(final int numberOfThreads) {
      executorService = Executors.newFixedThreadPool(numberOfThreads);
    }

    public BigInteger getFibNumberAtIndex(final int index) 
      throws InterruptedException, ExecutionException {

      Future<BigInteger> indexMinusOne = executorService.submit(
        new Callable<BigInteger>() {
          public BigInteger call() 
          throws InterruptedException, ExecutionException {
            return getNumber(index - 1);
          }
      });

      Future<BigInteger> indexMinusTwo = executorService.submit(
        new Callable<BigInteger>() {
          public BigInteger call() 
          throws InterruptedException, ExecutionException {
            return getNumber(index - 2);
          }
      });

      return indexMinusOne.get().add(indexMinusTwo.get());
    }

    public BigInteger getNumber(final int index) 
    throws InterruptedException, ExecutionException {
      if (index == 0 || index == 1)
        return BigInteger.valueOf(index);

      return getFibNumberAtIndex(index - 1).add(getFibNumberAtIndex(index - 2));
    }
  }

Исправлено (Спасибо fiver )

Вместо вызова getNumber (int) из метода вызова я обращаюсь к алгоритму динамического программирования, который вычисляет число по этому индексу.

Код для этого: 

public class DynamicFib implements IFib {

private Map<Integer, BigInteger> memoize = new HashMap<Integer, BigInteger>();

public DynamicFib() {
  memoize.put(0, BigInteger.ZERO);
  memoize.put(1, BigInteger.ONE);
}

public BigInteger getFibNumberAtIndex(final int index) {

  if (!memoize.containsKey(index))
    memoize.put(index, getFibNumberAtIndex(index - 1).add(getFibNumberAtIndex(index - 2)));

  return memoize.get(index);
  }
}

Ответы [ 3 ]

1 голос
/ 02 июля 2011

То, что вы делаете, заменяет простую рекурсию рекурсией через потоки / задачи.

Пока вы не дойдете до случаев fib (0) и fib (1), каждая задача отправляет еще две задачи, а затем ожидает их завершения. Пока он ожидает, он все еще использует поток. Так как пул потоков ограничен, вы скоро доберетесь до точки, где вызовы submit block ... и все вычисления блокируются.

В дополнение к этому у вас есть ошибка в indexMinusTwo, из-за которой вычисления дают неправильный ответ.

Но все же рекурсивная многопоточная процедура занимает гораздо больше времени, чем запомненная рекурсивная не многопоточная ... какой-нибудь совет по улучшению производительности?

Даже если предположить, что вы "исправили" вышеуказанную проблему (например, с помощью неограниченного пула потоков), не может быть , что вы сможете создать многопоточную версию Фибоначчи, которая работает лучше, чем однопоточная версия, которая использует памятку. Вычисление просто не подходит для распараллеливания.

1 голос
/ 02 июля 2011

Эта рекурсия очень быстро переполняет стек.Это потому, что вы вычисляете более низкие числа Фибоначчи снова и снова - экспоненциально много раз.

Один из эффективных способов избежать этого - использовать запомненную рекурсию (подход динамического программирования)

В основномиспользуйте статический массив для хранения уже вычисленных чисел Фибоначчи и всякий раз, когда он вам нужен, извлекайте его из массива, если он уже вычислен.Если нет, то вычислите его и сохраните в массиве.Таким образом, каждое число будет вычислено только один раз.

(Конечно, вы можете использовать другую структуру данных вместо массива, т.е. хеш-таблицу)

0 голосов
/ 02 июля 2011

Потоки работают лучше всего, когда у вас есть независимые задачи для выполнения. Ряд Фибоначчи по определению не имеет степеней параллелизма. Каждый f (n) зависит от двух предыдущих значений. Таким образом, невозможно вычислить f (n) быстрее, используя несколько потоков, чем используя один (если у вас неэффективный алгоритм)

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

Самый быстрый / простой способ вычисления чисел Фибоначчи - использовать цикл в одном потоке. Вам не нужно использовать recusrion или запоминать значения.

...