java - 卡在递归 Fork/Join 上

Question

我有一个返回一组点的方法，我确信这个方法的 for 循环部分可以拆分为一个 RecursiveTask，它为每个线程返回一组点。

我尝试了很多次，但都失败了。那里有 Java 天才吗？

我现有的方法:

private Set<Point3D> getCordinatesAroundCenterPoint(Point3D point, int width) {
    Set<Point3D> points         =   new LinkedHashSet<>();

    double maxValue             =   width;
    double minValue             =   maxValue * -1;

    double minX                 =   point.getX() + minValue;
    double maxX                 =   point.getX() + maxValue;
    double minY                 =   point.getY() + minValue;
    double maxY                 =   point.getY() + maxValue;
    double minZ                 =   point.getY() + minValue;
    double maxZ                 =   point.getZ() + maxValue;
    double x                    =   point.getX();
    double y                    =   point.getY();
    double z                    =   point.getZ();

    double numberOfPoints       =   Math.pow((double) (maxValue * 2) + 1, Double.parseDouble("3"));     

    for (int i = 1; i <= numberOfPoints; i++) {
        if (x > maxX) {
            x = minX;
            y++;
        }

        if (y > maxY) {
            y = minY;
            z++;
        }

        if (z > maxZ) {
            z = minZ;
        }

        Point3D ppoint =    new Point3D();

        ppoint.setX(x);
        ppoint.setY(y);
        ppoint.setZ(z);

        points.add(ppoint);
        x++;
    }

    return points;
}

更新#1:

这是我将其拆分为递归任务的尝试，它似乎在范围为 1(应等于 27 点)-1、0、+1、= 3 点、3 立方 = 27 时工作正常。任何范围失败的更大数字，例如范围 2 应该返回 125 点。 -2、-1、0、+1、+2 = 5 点，5 的立方 = 125。

主要.java:

public static void main(String[] args) {

        System.out.println("Enter system extent: ");

        BufferedReader bufferedReader   =   new BufferedReader(new InputStreamReader(System.in));

        try {
            String string                   =   bufferedReader.readLine();
            LinkedHashSet<Point3D> set      =   getStarSystemCordinatesAroundCenterSystem(Integer.parseInt(string));
            System.out.println(set.size() + " systems generated.");
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private static LinkedHashSet<Point3D> getStarSystemCordinatesAroundCenterSystem(int extent) {
        ForkJoinPool pool           =   new ForkJoinPool();

        double maxValue             =   extent;
        double minValue             =   maxValue * -1;

        ForkPoints task =   new ForkPoints(minValue, maxValue);

        LinkedHashSet<Point3D> linkedHashSet = (LinkedHashSet<Point3D>) pool.invoke(task);

        return linkedHashSet;
    }

叉点.java:

public class ForkPoints extends RecursiveTask<Set<Point3D>> {

    private static final long serialVersionUID = -5450450150370659468L;

    private double minValue;
    private double maxValue;

    static final double SEQUENTIAL_THRESHHOLD = 2;

    public ForkPoints(double minValue, double maxValue) {
        this.minValue   =   minValue;
        this.maxValue   =   maxValue;
    }

    @Override
    protected Set<Point3D> compute() {
        if (maxValue - minValue <= SEQUENTIAL_THRESHHOLD) {
            return computeValue(minValue, maxValue);
        } else {
            double midValue             =   minValue + SEQUENTIAL_THRESHHOLD;
            ForkPoints left             =   new ForkPoints(minValue, midValue);
            ForkPoints right            =   new ForkPoints(midValue, maxValue);
            left.fork();
            Set<Point3D> rightPoints    =   right.compute();
            Set<Point3D> leftPoints     =   left.join();
            leftPoints.addAll(rightPoints);
            return leftPoints;
        }
    }

    private Set<Point3D> computeValue(double minv, double maxv) {

        //Assume starting point of 0,0,0
        double minX                 =   0 + minv;
        double maxX                 =   0 + maxv;
        double minY                 =   0 + minv;
        double maxY                 =   0 + maxv;
        double minZ                 =   0 + minv;
        double maxZ                 =   0 + maxv;
        double x                    =   minv;
        double y                    =   minv;
        double z                    =   minv;

        Set<Point3D> points         =   new LinkedHashSet<>();

        boolean notFinished = true;

        while (notFinished) {
            if (x > maxX) {
                x = minX;
                y++;
            }

            if (y > maxY) {
                y = minY;
                z++;
            }

            if (z > maxZ) {
                z = minZ;
            }

            Point3D ppoint = new Point3D(); 

            ppoint.setX(x);
            ppoint.setY(y);
            ppoint.setZ(z);

            points.add(ppoint);
            if (x == maxX && y == maxY && z == maxZ) {
                notFinished = false;
            }
            x++;
        }

        return points;
    }
}

Answer 1

这里的主要问题是您正在尝试拆分 3D 对象，但只在一个方向上拆分。 IE。 ForkPoints.compute() 实际上不应产生 2 个，而是至少 8 个子任务，以防它无法自行执行计算。

下面是它的外观示例 - 代码的最小更改:

public class ForkPoints extends RecursiveTask<Set<Point3D>> {

    private static final long serialVersionUID = -5450450150370659468L;

    private final Point3D origin;
    private final double radius;

    static final double SEQUENTIAL_THRESHHOLD = 5;

    public ForkPoints(final Point3D origin, final double radius) {
        this.origin = origin;
        this.radius = radius;
    }

    @Override
    protected Set<Point3D> compute() {
        if (radius <= SEQUENTIAL_THRESHHOLD) {
            return computeValue();
        } else {
            final ForkPoints subCubes[] = new ForkPoints[8];
            final double newRadius = radius / 2;

            Point3D newOrigin = new Point3D();
            newOrigin.setX(origin.getX() + newRadius);
            newOrigin.setY(origin.getY() + newRadius);
            newOrigin.setZ(origin.getZ() + newRadius);
            subCubes[0] = new ForkPoints(newOrigin, newRadius);
            subCubes[0].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() + newRadius);
            newOrigin.setY(origin.getY() + newRadius);
            newOrigin.setZ(origin.getZ() - newRadius);
            subCubes[1]   = new ForkPoints(newOrigin, newRadius);
            subCubes[1].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() + newRadius);
            newOrigin.setY(origin.getY() - newRadius);
            newOrigin.setZ(origin.getZ() + newRadius);
            subCubes[2]   = new ForkPoints(newOrigin, newRadius);
            subCubes[2].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() + newRadius);
            newOrigin.setY(origin.getY() - newRadius);
            newOrigin.setZ(origin.getZ() - newRadius);
            subCubes[3]   = new ForkPoints(newOrigin, newRadius);
            subCubes[3].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() - newRadius);
            newOrigin.setY(origin.getY() + newRadius);
            newOrigin.setZ(origin.getZ() + newRadius);
            subCubes[4]   = new ForkPoints(newOrigin, newRadius);
            subCubes[4].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() - newRadius);
            newOrigin.setY(origin.getY() + newRadius);
            newOrigin.setZ(origin.getZ() - newRadius);
            subCubes[5]   = new ForkPoints(newOrigin, newRadius);
            subCubes[5].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() - newRadius);
            newOrigin.setY(origin.getY() - newRadius);
            newOrigin.setZ(origin.getZ() + newRadius);
            subCubes[6]   = new ForkPoints(newOrigin, newRadius);
            subCubes[6].fork();

            newOrigin = new Point3D();
            newOrigin.setX(origin.getX() - newRadius);
            newOrigin.setY(origin.getY() - newRadius);
            newOrigin.setZ(origin.getZ() - newRadius);
            subCubes[7]   = new ForkPoints(newOrigin, newRadius);
            subCubes[7].fork();

            final Set<Point3D> results = new LinkedHashSet<Point3D>();
            for(final ForkPoints singleSubCube : subCubes) {
                results.addAll(singleSubCube.join());
            }

            return results;
        }
    }

    private Set<Point3D> computeValue() {
        double minX                 =   origin.getX() - radius;
        double maxX                 =   origin.getX() + radius;
        double minY                 =   origin.getY() - radius;
        double maxY                 =   origin.getY() + radius;
        double maxZ                 =   origin.getZ() + radius;
        double x                    =   minX;
        double y                    =   minY;
        double z                    =   origin.getZ() - radius;

        Set<Point3D> points         =   new LinkedHashSet<>();

        boolean notFinished = true;

        while (notFinished) {
            if (x > maxX) {
                x = minX;
                y++;
            }

            if (y > maxY) {
                y = minY;
                z++;
            }

            if (z > maxZ) {
                break;
            }

            Point3D ppoint = new Point3D(); 

            ppoint.setX(x);
            ppoint.setY(y);
            ppoint.setZ(z);

            points.add(ppoint);
            x++;
        }

        return points;
    }
}

但请注意，使用此代码还有很多工作要做。例如 - 两个对相邻空间执行计算的子任务都生成位于相互 Pane 上的点；当前代码通过 Set.addAll(..) 调用的 Point3D.equals(..) 排除了这些重复项。在现实生活中，算法甚至不应该生成它们，因为这些重复的点在整个生成的点中占很大一部分，尤其是对于 SEQUENTIAL_THRESHHOLD 的低值。