Я хочу построить адаптивное уточнение сетки в 3D.

Основной принцип заключается в следующем:

У меня есть набор ячеек с уникальными идентификаторами ячеек. Я проверяю каждую ячейку, чтобы увидеть, нужно ли ее уточнять.

• Если требуется уточнение, создайте 8 новых дочерних ячеек и добавьте их в список ячеек для проверки уточнения.
• В противном случае это конечный узел, и я добавляю его в свой список конечных узлов.

Я хочу реализовать это с помощью фреймворка ForkJoin и потоков Java 8. Я прочитал эту статью, но не знаю, как применить ее в моем случае.

На данный момент я придумал следующее:

public class ForkJoinAttempt {
    private final double[] cellIds;

    public ForkJoinAttempt(double[] cellIds) {
        this.cellIds = cellIds;
    }

    public void refineGrid() {
        ForkJoinPool pool = ForkJoinPool.commonPool();
        double[] result = pool.invoke(new RefineTask(100));
    }

    private class RefineTask extends RecursiveTask<double[]> {
        final double cellId;

        private RefineTask(double cellId) {
            this.cellId = cellId;
        }

        @Override
        protected double[] compute() {
            return ForkJoinTask.invokeAll(createSubtasks())
                    .stream()
                    .map(ForkJoinTask::join)
                    .reduce(new double[0], new Concat());
        }
    }

    private double[] refineCell(double cellId) {
        double[] result;
        if (checkCell()) {
            result = new double[8];

            for (int i = 0; i < 8; i++) {
                result[i] = Math.random();
            }

        } else {
            result = new double[1];
            result[0] = cellId;
        }

        return result;
    }

    private Collection<RefineTask> createSubtasks() {
        List<RefineTask> dividedTasks = new ArrayList<>();

        for (int i = 0; i < cellIds.length; i++) {
            dividedTasks.add(new RefineTask(cellIds[i]));
        }
        
        return dividedTasks;
    }

    private class Concat implements BinaryOperator<double[]>  {

        @Override
        public double[] apply(double[] a, double[] b) {
            int aLen = a.length;
            int bLen = b.length;

            @SuppressWarnings("unchecked")
            double[] c = (double[]) Array.newInstance(a.getClass().getComponentType(), aLen + bLen);
            System.arraycopy(a, 0, c, 0, aLen);
            System.arraycopy(b, 0, c, aLen, bLen);

            return c;
        }
    }

    public boolean checkCell() {
        return Math.random() < 0.5;
    }
}

... и я застрял здесь.

Пока это мало что дает, потому что я никогда не вызываю функцию refineCell.

У меня также могут быть проблемы с производительностью со всеми теми double[], которые я создаю. И объединение их таким образом может быть не самым эффективным способом сделать это.

Но обо всем по порядку, может ли кто-нибудь помочь мне в реализации форк-соединения в этом случае?

Ожидаемый результат алгоритма — массив идентификаторов конечных ячеек (double[]).

Редактировать 1:

Благодаря комментариям я придумал кое-что, что работает немного лучше.

Некоторые изменения:

• Я перешел от массивов к спискам. Это не очень хорошо для объема памяти, потому что я не могу использовать примитивы Java. Но это сделало имплантацию проще.
• Идентификаторы ячеек теперь длинные, а не двойные.
• Ids are not randomly chosen any more:
  • Root level cells have IDs 1, 2, 3 etc.;
  • Дети 1 имеют идентификаторы 10, 11, 12 и т. д.;
  • Дети 2 лет имеют идентификаторы 20, 21, 22 и т. д.;
  • Вы поняли идею...
• Я уточняю все ячейки, ID которых меньше 100

Это позволяет мне ради этого примера лучше проверить результаты.

Вот новая реализация:

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.concurrent.*;
import java.util.function.BinaryOperator;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class ForkJoinAttempt {
    private static final int THRESHOLD = 2;
    private List<Long> leafCellIds;

    public void refineGrid(List<Long> cellsToProcess) {
        leafCellIds = ForkJoinPool.commonPool().invoke(new RefineTask(cellsToProcess));
    }

    public List<Long> getLeafCellIds() {
        return leafCellIds;
    }

    private class RefineTask extends RecursiveTask<List<Long>> {

        private final CopyOnWriteArrayList<Long> cellsToProcess = new CopyOnWriteArrayList<>();

        private RefineTask(List<Long> cellsToProcess) {
            this.cellsToProcess.addAll(cellsToProcess);
        }

        @Override
        protected List<Long> compute() {
            if (cellsToProcess.size() > THRESHOLD) {
                System.out.println("Fork/Join");
                return ForkJoinTask.invokeAll(createSubTasks())
                        .stream()
                        .map(ForkJoinTask::join)
                        .reduce(new ArrayList<>(), new Concat());
            } else {
                System.out.println("Direct computation");
                
                List<Long> leafCells = new ArrayList<>();

                for (Long cell : cellsToProcess) {
                    Long result = refineCell(cell);
                    if (result != null) {
                        leafCells.add(result);
                    }
                }

                return leafCells;
            }
        }

        private Collection<RefineTask> createSubTasks() {
            List<RefineTask> dividedTasks = new ArrayList<>();

            for (List<Long> list : split(cellsToProcess)) {
                dividedTasks.add(new RefineTask(list));
            }

            return dividedTasks;
        }

        private Long refineCell(Long cellId) {
            if (checkCell(cellId)) {
                for (int i = 0; i < 8; i++) {
                    Long newCell = cellId * 10 + i;
                    cellsToProcess.add(newCell);
                    System.out.println("Adding child " + newCell + " to cell " + cellId);
                }
                return null;
            } else {
                System.out.println("Leaf node " + cellId);
                return cellId;
            }
        }

        private List<List<Long>> split(List<Long> list)
        {
            int[] index = {0, (list.size() + 1)/2, list.size()};

            List<List<Long>> lists = IntStream.rangeClosed(0, 1)
                    .mapToObj(i -> list.subList(index[i], index[i + 1]))
                    .collect(Collectors.toList());

            return lists;
        }


    }



    private class Concat implements BinaryOperator<List<Long>> {
        @Override
        public List<Long> apply(List<Long> listOne, List<Long> listTwo) {
            return Stream.concat(listOne.stream(), listTwo.stream())
                    .collect(Collectors.toList());
        }
    }

    public boolean checkCell(Long cellId) {
        return cellId < 100;
    }
}

И метод тестирования:

    int initialSize = 4;
    List<Long> cellIds = new ArrayList<>(initialSize);
    for (int i = 0; i < initialSize; i++) {
        cellIds.add(Long.valueOf(i + 1));
    }

    ForkJoinAttempt test = new ForkJoinAttempt();
    test.refineGrid(cellIds);
    List<Long> leafCellIds = test.getLeafCellIds();
    System.out.println("Leaf nodes: " + leafCellIds.size());
    for (Long node : leafCellIds) {
        System.out.println(node);
    }

Вывод подтверждает, что он добавляет 8 дочерних элементов к каждой корневой ячейке. Но дальше не идет.

Я знаю почему, но я не знаю, как это решить: это потому, что, несмотря на то, что метод RefineCell добавляет новые ячейки в список ячеек для обработки. Метод createSubTask больше не вызывается, поэтому он не может знать, что я добавил новые ячейки.

Редактировать 2:

Чтобы сформулировать проблему по-другому, я ищу механизм, в котором Queue идентификаторов ячеек обрабатывается некоторыми RecursiveTask, а другие добавляются к Queue параллельно.