使用线程池计算Java阶乘

Question

我已经成功地使用了两个线程来计算阶乘，而没有使用线程池。我有两个阶乘类，它们分别命名为Factorial1和Factorial2，并且都继承自Thread类。假设我要计算的是!160000，那么在Factorial1的run()方法中，我使用for循环从i=2到i=80000进行乘法操作；在Factorial2的run()方法中，我使用for循环从i=80001到i=160000进行乘法操作。之后，我将这两个值返回并在主方法中将它们相乘。当我比较执行时间时，用两个线程来计算阶乘明显更快（只需要5000毫秒），即使使用了两个线程也优于不使用线程的计算时间（需要15000毫秒）。

现在我想编写更加清晰和高效的代码，因为我看到了线程在阶乘计算中的效率。但是，当我使用线程池来计算阶乘时，与非线程计算相比，并行计算总是需要更多的时间（近16000毫秒）。我的代码片段如下：

for(int i=2; i<= Calculate; i++)
{
    myPool.execute(new Multiplication(result, i));
}

在Multiplication类中的run()方法：

public void run() 
{
        s1.Mltply(s2); // s1 and s2 are instances of my Number class
                       // their fields holds BigInteger values
}

Number类中的Mltply()方法：

public void Multiply(int number)
{
    area.lock(); // result is going wrong without lock
    Number temp = new Number(number);
    value = value.multiply(temp.value); // value is a BigInteger
    area.unlock();       
}

在我看来，这个锁可能会破坏线程使用的所有优势，因为它似乎只是在做乘法，没有其他任何操作。但如果没有它，我甚至不能计算出真正的结果。比如说我想计算!10，那么thread1就要计算10*9*8*7*6，而thread2则要计算5*4*3*2*1。这是我想要的方式吗？使用线程池是否可行？当然，执行时间必须少于普通计算...

非常感谢您提供的所有帮助和建议。

编辑：- 我自己解决问题的方法 -

public class MyMultiplication implements Runnable 
{
    public static BigInteger subResult1;
    public static BigInteger subResult2;
    int thread1StopsAt;
    int thread2StopsAt;
    long threadId;
    static boolean idIsSet=false;

    public MyMultiplication(BigInteger n1, int n2)  // First Thread
    {
        MyMultiplication.subResult1 = n1;
        this.thread1StopsAt = n2/2;

        thread2StopsAt = n2;

    }
    public MyMultiplication(int n2,BigInteger n1)   // Second Thread
    {
        MyMultiplication.subResult2 = n1;
        this.thread2StopsAt = n2;

        thread1StopsAt = n2/2;
    }
    @Override
    public void run() 
    {
        if(idIsSet==false)
        {
            threadId = Thread.currentThread().getId(); 
            idIsSet=true;            
        }
        if(Thread.currentThread().getId() == threadId)
        {
            for(int i=2; i<=thread1StopsAt; i++)
            {
                subResult1 = subResult1.multiply(BigInteger.valueOf(i));
            }
        }
        else
        {
            for(int i=thread1StopsAt+1; i<= thread2StopsAt; i++)
            {
                subResult2 = subResult2.multiply(BigInteger.valueOf(i));
            }
        }            
    }   
}
public class JavaApplication3 
{
    public static void main(String[] args) throws InterruptedException 
    {
        int calculate=160000;
        long start = System.nanoTime(); 
        BigInteger num = BigInteger.valueOf(1);
        for (int i = 2; i <= calculate; i++) 
        {
          num = num.multiply(BigInteger.valueOf(i));
        }
        long end = System.nanoTime();
        double time = (end-start)/1000000.0;
        System.out.println("Without threads: \t" + 
        String.format("%.2f",time) + " miliseconds");    
        System.out.println("without threads Result: " + num);

        BigInteger num1 = BigInteger.valueOf(1);
        BigInteger num2 = BigInteger.valueOf(1);
        ExecutorService myPool = Executors.newFixedThreadPool(2);
        start = System.nanoTime();

            myPool.execute(new MyMultiplication(num1,calculate));  
            Thread.sleep(100);
            myPool.execute(new MyMultiplication(calculate,num2));

        myPool.shutdown();
        while(!myPool.isTerminated())   {}  // waiting threads to end
        end = System.nanoTime();
        time = (end-start)/1000000.0;
        System.out.println("With threads: \t" +String.format("%.2f",time) 
        + " miliseconds");    
        BigInteger result = 

        MyMultiplication.subResult1.
        multiply(MyMultiplication.subResult2);
        System.out.println("With threads Result: " + result);
        System.out.println(MyMultiplication.subResult1);
        System.out.println(MyMultiplication.subResult2);
    }   
}

输入: !160000 没有使用线程的执行时间: 15000 毫秒 使用 2 个线程的执行时间: 4500 毫秒

感谢您的想法和建议。

- İbrahim Akar

---

您省略了太多细节：[mcve] - assylias

这行代码的作用是什么：Number temp = new Number(number); 我看不到temp被使用过。 - Jhonny007

除非你正在计算一个相当大的数字的阶乘，比如10,000，否则你不会从多线程中看到持续的改进。线程管理的开销将压倒任何拆分计算的优势，而且你无法对迭代次数为10,000进行微基准测试，因为需要JIT预热时间。简而言之，对于这样一个小问题，你不需要也不想要多线程。 - Jim Garrison

@Jhonny007 我在multiply()函数中使用temp。 - İbrahim Akar

@JimGarrison，我之前提到过，我在没有使用线程的情况下计算了160000（用时15000毫秒），而使用两个线程则只需5000毫秒。因此，我认为160000比10000要大得多，而对于这样一个小进程来说，10秒并不是一个“短”的时间。我想知道如何通过线程池实现相同的目标，无论如何还是谢谢您。 - İbrahim Akar

Answer 1

线程必须独立运行才能快速运行。许多依赖项，例如锁定、代码的同步部分或某些系统调用会导致休眠线程等待访问某些资源。

在您的情况下，您应该尽量减少线程在锁内的时间。也许我错了，但是似乎您为每个数字创建一个线程。因此，对于1000！，您会生成1000个线程。它们都试图获取area上的锁，并且无法计算任何内容，因为一个线程已成为锁定状态，所有其他线程必须等待直到锁定再次解除。因此，线程仅按顺序运行，这与您的非线程示例一样快，只是需要额外的时间进行锁定和解锁、线程管理等等。哦，由于CPU的上下文切换，情况变得更糟。

您第一次尝试将阶乘分为两个线程是更好的方法。每个线程可以计算自己的结果，只有当它们完成后，线程才需要相互通信。因此，它们大部分时间是独立的。

现在你需要将这个解决方案推广。为了减少CPU上下文切换，你只需要与CPU核心数量相同的线程（可能稍微少一些，因为你的操作系统）。每个线程获得一组数字并计算它们的乘积。计算完成后，它锁定总体结果并将自己的结果添加到其中。

这应该可以提高你的问题性能。

---

更新：您要求额外的建议：

您说您有两个类 Factorial1 和 Factorial2。可能它们已经在代码中硬编码了它们的范围。您只需要一个将范围作为构造函数参数传入的类。这个类实现 Runnable 接口，因此它有一个 run 方法，该方法将范围内的所有值相乘。

在您的 main 方法中，您可以这样做：

int n = 160_000;
int threads = 2;
ExecutorService executor = Executors.newFixedThreadPool(threads);
for (int i = 0; i < threads; i++) {
    int start = i * (n/threads) + 1;
    int end = (i + 1) * (n/threads) + 1;
    executor.execute(new Factorial(start, end));
}
executor.shutdown();
executor.awaitTermination(1, TimeUnit.DAYS);

现在你已经计算出了每个线程的结果，但还没有整体结果。这可以通过一个BigInteger来解决，它对Factorial类可见（就像同一主类中的static BigInteger reuslt;一样），也需要一个锁。在Factorial的run方法中，您可以通过锁定锁并计算结果来计算整体结果：

Main.lock.lock();
Main.result = Main.result.multiply(value);
Main.lock.unlock();

---

对于未来的一些额外建议：这并不是真正的干净代码，因为 Factorial 需要知道主类的信息，所以它对其有依赖性。但是，ExecutorService 返回一个 Future<T> 对象，该对象可用于接收线程的结果。使用此 Future 对象，您无需使用锁。但是，这需要一些额外的工作，所以现在只需尝试将其运行起来即可 ;-)

- Obenland

---

谢谢您的建议。但是您有关于如何在线程池中模仿我的第一个成功方法的建议吗？ - İbrahim Akar

Answer 2

您可以通过将160000分成不相交的块来同时计算！160000，而无需使用锁，就像您所解释的将其分成2..80000和80001..160000一样。

但是您也可以使用Java Stream API实现此目的：

IntStream.rangeClosed(1, 160000).parallel()
    .mapToObj(val -> BigInteger.valueOf(val))
    .reduce(BigInteger.ONE, BigInteger::multiply);

它可以完全完成您尝试做的事情。它将整个范围分成块，建立线程池并计算部分结果。然后将这些部分结果合并为一个结果。

那么，为什么要自己去做呢？只是为了练习清晰的编码吗？

在我的真实四核机器上，使用并行流比在for循环中计算慢8倍。

- Harmlezz

---

我只是想知道是否可以使用线程池获得相同的结果和良好的执行时间。我对线程池还不熟悉，但我认为这可以通过它来完成，只是不知道如何操作。在run()方法中创建两个相同的阶乘类，只是使用不同的for循环，这不是清晰的代码。 - İbrahim Akar

Answer 3

除了我之前提供的Java Stream API解决方案，这里还有另一种解决方案，它使用了一个自管理的线程池，正如您所要求的：

public static final int CHUNK_SIZE = 10000;

public static BigInteger fac(int max) {
    ExecutorService executor = newCachedThreadPool();
    try {
        return rangeClosed(0, (max - 1) / CHUNK_SIZE)
                .mapToObj(val -> executor.submit(() -> prod(leftBound(val), rightBound(val, max))))
                .map(future -> valueOf(future))
                .reduce(BigInteger.ONE, BigInteger::multiply);
    } finally {
        executor.shutdown();
    }
}

private static int leftBound(int chunkNo) {
    return chunkNo * CHUNK_SIZE + 1;
}

private static int rightBound(int chunkNo, int max) {
    return Math.min((chunkNo + 1) * CHUNK_SIZE, max);
}

private static BigInteger valueOf(Future<BigInteger> future) {
    try {
        return future.get();
    } catch (Exception e) {
        throw new RuntimeException(e);
    }
}

private static BigInteger prod(int min, int max) {
    BigInteger res = BigInteger.valueOf(min);
    for (int val = min + 1; val <= max; val++) {
        res = res.multiply(BigInteger.valueOf(val));
    }
    return res;
}

- Harmlezz