3

我有一个返回一组点的方法,我确信这个方法的 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;
    }

ForkPoints.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;
    }
}
4

2 回答 2

1

这里的主要问题是您试图拆分 3D 对象,但仅在一个方向上拆分。即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;
    }
}

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

于 2014-03-31T08:38:30.173 回答
1

您正在尝试将任务分成几部分,但您忘记了您的数据是 3D 的:对所有三个坐标应用相同的约束将解决方案限制为沿“主对角线”的立方体链,而使所有其他空间未处理。这就是为什么你只得到 54 分(一倍)而不是 125:它是 27 + 27(两倍三立方),覆盖立方体 ((0,0,0)..(2,2,2)) 和 ( (2,2,2)..(5,5,5)) 与点 (2,2,2) 相同。

您可以通过多种方式解决问题。最简单的可能是将工作空间分成两半,最好在最长的边缘处,直到零件的点数足够低。

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

    private static final long serialVersionUID = -5450450150370659468L;

    private double minX;
    private double minY;
    private double minZ;
    private double maxX;
    private double maxY;
    private double maxZ;

    // max number of points allowed for a task
    static final double PTS_THRESHOLD = 25;

    // cube case
    public ForkPoints(double minValue, double maxValue) {
        this.minX   =   minValue;
        this.minY   =   minValue;
        this.minZ   =   minValue;
        this.maxX   =   maxValue;
        this.maxY   =   maxValue;
        this.maxZ   =   maxValue;
    }

    // rectangular cuboid case
    public ForkPoints(double minx, double maxx, double miny, double maxy, double minz, double maxz) {
        this.minX   =   minx;
        this.minY   =   miny;
        this.minZ   =   minz;
        this.maxX   =   maxx;
        this.maxY   =   maxy;
        this.maxZ   =   maxz;
    }

    @Override
    protected Set<Point3D> compute() {
        double dx = maxX - minX + 1;  // no of points
        double dy = maxY - minY + 1;  // in every
        double dz = maxZ - minZ + 1;  // direction

        if (dx*dy*dz <= PTS_THRESHOLD) {  // no of points to make
            return computeValue();    // cuboid small enough
        } else {
            bool splitx = (dx >= dy) && (dx >= dz);  // choose axis
            bool splity = !splitx && (dy >= dz);     // for split

            ForkPoints left;
            ForkPoints right;

            if (splitx) {
                double midx = Math.floor( (minx + maxx)/2);
                left    =   new ForkPoints(minx,   midx, miny, maxy, minz, maxz);
                right   =   new ForkPoints(midx+1, maxx, miny, maxy, minz, maxz);
            } else if (splity) {
                double midy = Math.floor( (miny + maxy)/2);
                left    =   new ForkPoints(minx, maxx, miny,   midy, minz, maxz);
                right   =   new ForkPoints(minx, maxx, midy+1, maxy, minz, maxz);
            } else {
                double midz = Math.floor( (minz + maxz)/2);
                left    =   new ForkPoints(minx, maxx, miny, maxy, minz,   midz);
                right   =   new ForkPoints(minx, maxx, miny, maxy, midz+1, maxz);
            }
            left.fork();
            Set<Point3D> rightPoints    =   right.compute();
            Set<Point3D> leftPoints     =   left.join();
            leftPoints.addAll(rightPoints);
            return leftPoints;
        }
    }

    private Set<Point3D> computeValue() {
        Set<Point3D> points =   new LinkedHashSet<>();

        for (double z = minZ; z < maxZ + 0.01; z += 1)
        for (double y = minY; y < maxY + 0.01; y += 1)
        for (double x = minX; x < maxX + 0.01; x += 1)
        {
            Point3D ppoint = new Point3D(); 

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

            points.add(ppoint);
        }

        return points;
    }
}
于 2014-04-06T21:22:43.470 回答