java - 如何选择最佳线程数

Question

实际上，我编写了一个 Java 程序来计算斐波那契数列中的特定数字。

现在的问题是我使用的核心数作为所需的线程数。但我观察到，随着输入大小的增加，我通过增加线程数获得了更好的性能。

是否有关于如何将问题划分为多个线程的现有公式/理论？

源代码如下:

import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class Fibonacci {
    private static long[] value;

    public static void main(String args[]) throws InterruptedException {
        int n;
        try {
            n = Integer.parseInt(args[0]);
        } catch (Exception e) {
            throw new RuntimeException(
                    "Please enter in the form java n number ");
        }
        value = new long[n + 1];


        long start = System.nanoTime();
        int nThreads = Runtime.getRuntime().availableProcessors();
        ExecutorService executorService = Executors
                .newFixedThreadPool(nThreads);
        int result;
        try {
            result = fibonacciSum(n, executorService);
        } catch (ExecutionException e) {
            throw new RuntimeException("Thread Interuppted ");
        }
        System.out.print(" MultiThreading = " + result);
        long end = System.nanoTime();
        System.out.println("\t time = " + (end - start) + "ns");
    }


    private static class FibonacciThread implements Runnable {
        int index;
        int result;
        ExecutorService executorService;

        public FibonacciThread(int index) {
            this.index = index;
        }

        public void run() {
            try {
                this.result = fibonacciSum(index, executorService);
            } catch (Exception e) {
                throw new RuntimeException("Thread interupted");
            }
        }
    }

    private static int fibonacciSum(int index, ExecutorService executorService)
            throws InterruptedException, ExecutionException {
        if (index <= 2) {
            return 1;
        } else {

            FibonacciThread fibonacciThread1 = new FibonacciThread(index - 2);
            fibonacciThread1.executorService = executorService;
            Future future = executorService.submit(fibonacciThread1);
            Object object = future.get();
            int resultPart2 = fibonacciSum(index - 1, executorService);
            int result = fibonacciThread1.result + resultPart2;
            // executorService.shutdown();
            return result;
        }
    }

}

Answer 1

如果您还没有意识到这一点，斐波那契数列不是并行化的理想选择。您将获得(越来越)更好的性能:

• 通过使用单线程递归算法，
• 通过使用带有内存的单线程递归算法，以及
• 通过求解递归关系并实现所得公式。

---

基本问题是朴素的斐波那契计算需要指数级的计算步骤。您无法通过多线程对此(在性能方面)产生影响，因为您的处理器数量有限。

即使您确实拥有无限数量的处理器，线程设置/任务创建开销也会超过执行计算步骤的时间。

最后，使用执行程序服务和有界线程池执行斐波那契数列有一个特殊问题。如果线程池太小(或 N 太大)，计算很容易卡住。例如，您编码的方式需要池中的 ~N 个线程来计算 fibonacci(N)，即使它们中的大多数将被阻塞时间。 (理解这一点的最好方法是“手动执行”应用程序，注意每个时间点有多少线程在使用……以及它们在做什么。)

---

因此，您问题的简单答案是(对于这个特定的应用程序)池中至少需要 N 个线程才能完成 Fibonacci(N) 的计算>。 (这不是一般性答案。它是由您已实现的算法的细节强制要求的。)

---

还有很多关于使用线程计算斐波那契数的其他 SO 问题/答案。我建议您也阅读它们。