带有线程池的Java阶乘计算

Question

我实现了在没有池的情况下使用两个线程计算阶乘。我有两个名为 Factorial1、Factorial2 和扩展 Thread 类的阶乘类。让我们考虑一下我要计算 !160000 的值。在 Factorial1 的 run() 方法中，我在 for 循环中从 i=2 乘以 i=80000，在 Factorial2 中从 i=80001 到 160000。之后，我返回两个值并在 main 方法中将它们相乘。当我比较执行时间时，即使有两个线程，它也比非线程计算的时间(15000 毫秒)要好得多(5000 毫秒)。

现在我想编写干净更好的代码，因为我看到了线程在阶乘计算中的效率，但是当我使用线程池计算阶乘值时，并行计算总是比非线程计算花费更多的时间(几乎16000)。我的代码片段如下所示:

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

乘法类中的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，那么线程 1 计算 10*9*8*7*6，线程 2 计算 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 毫秒

感谢您的想法和建议。

Answer 1

您可以在不使用锁的情况下同时计算 !160000，方法是将 160000 拆分为不连续的垃圾，正如您通过将其拆分为 2..80000 和 80001..160000 所解释的那样。

但是您可以通过使用 Java Stream API 来实现:

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

它完全按照您的意愿行事。它将整个范围拆分成垃圾，建立线程池并计算部分结果。之后它将部分结果合并为一个结果。

那么你为什么要费心自己做呢？只是练习干净的编码？

在我真正的 4 核机器上，for 循环中的计算比使用并行流花费的时间长 8 倍。