0

我读过类似的问题，其中问题是同步方法的使用（如 Math.random() ）或者工作太少而无法证明开销是合理的，但我认为这里不是这种情况。

我的处理器有 4 个物理/8 个逻辑内核。一次预热后，我在 11x11 矩阵上使用 n=1;2;3;4;8 测试以下代码；

ExecutorService pool = Executors.newFixedThreadPool(n);
long startTime = System.currentTimeMillis();
double result = pool.submit(new Solver(pool, matrix)).get();
System.out.println(result);
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println(elapsedTime);

执行分别需要：

1 ~ 15500 2 ~ 13500 - 14000 3 ~ 14300 - 15500 4 ~ 14500 - 19000 8 ~ 19000 - 23000

所以我用 2 得到一点提升，用 3 几乎没有提升，有时几乎没有提升，但有时用 4 极度减速，用 8 完全减速；

这是代码：

import java.util.ArrayList;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;
import java.util.concurrent.ThreadPoolExecutor;

public class Solver implements Callable<Double> {

    private ExecutorService pool;
    private double[][] matrix;


    public Solver(ExecutorService pool, double[][] matrix){
        this.pool = pool;
        this.matrix = matrix;
    }

    public double determinant(double[][] matrix) {
        if (matrix.length == 1)
            return (matrix[0][0]);

        double coefficient;
        double sum = 0;
        int threadsCount = ((ThreadPoolExecutor) pool).getMaximumPoolSize();
        ArrayList<Double> coefficients = new ArrayList<Double>();
        ArrayList<Future<Double>> delayedDeterminants = new ArrayList<Future<Double>>();

        for (int k = 0; k < matrix.length; k++) {
            double[][] smaller = new double[matrix.length - 1][matrix.length - 1];
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 0; j < matrix.length; j++) {
                    if (j < k)
                        smaller[i - 1][j] = matrix[i][j];
                    else if (j > k)
                        smaller[i - 1][j - 1] = matrix[i][j];
                }
            }
            coefficient = ((k % 2 == 0) ? 1 : -1) * matrix[0][k];
            if (((ThreadPoolExecutor) pool).getActiveCount() < threadsCount
                    && matrix.length > 5) {
                coefficients.add(coefficient);
                delayedDeterminants.add(pool.submit(new Solver(pool, smaller)));
            } else
                sum += coefficient * (determinant(smaller));
        }

        try {
            for (int i = 0; i < coefficients.size(); i++)
                sum += coefficients.get(i) * delayedDeterminants.get(i).get();
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }

        return (sum);
    }

    @Override
    public Double call() throws Exception {
        return determinant(matrix);
    }

}
4

1 回答 1

4

处理这种分治算法的一般方法是在单个线程中下降到某个级别，直到有足够的独立任务，然后将所有这些任务调度到 ExecutorService 上，让更多级别的递归在同一个任务中执行. 例如，下一层您有 121 个子矩阵来计算其行列式，因此向 ExecutorService 提交 121 个任务。或者再上一层以获得 12,100 个子问题并提交所有这些子问题。

轮询ExecutorService的活动任务计数可能不是最好的主意。创建一个newFixedThreadPool(4)或任意数量的要测试的线程，并让ExecutorService管理任务执行。如果您要完成的是工作窃取，那么我强烈建议您花一些时间熟悉 Fork/Join 框架，该框架会自动管理工作窃取。它旨在完全处理您的任务。

另一件事，与问题没有直接关系：您绝对应该重新设计代码，以便只有一个二维数组用于所有计算。一维阵列会更好。

于 2013-05-27T14:16:16.650 回答