2

Напишу сразу, что я новичок и ответ в итоге может находиться не в поле Fork/Join Framework. Пишу программу, в которой требуется пройти по двумерному массиву, состоящему из нулей и единиц и определить количество уникальным образом связанных между собой единиц (связанность по горизонтали-вертикали). Реализовал с помощью рекурсии , однако необходимо данную задачу распараллелить. В ходе размышлений натолкнулся на Fork/Join Framework, но по тем примерам, что я видел не могу понять каким образом можно использовать это в моей задаче.

private static int[][] field = {
        {1, 0, 0, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 0, 1}
};

// Variants of displacement: UP, RIGHT, DOWN, LEFT
private static int[] dy = {-1, 0, 1, 0};
private static int[] dx = {0, 1, 0, -1};

// the sizes of the field are constant, we make them in constants so as not to calculate each time
private static final int MAXY = field.length;
private static final int MAXX = field[field.length - 1].length;

// @param islandName is the name of the island, based on its form
private static StringBuilder islandName;

// use the @param uniqueIslands to get the number of islands with different shapes
private static HashSet<String> uniqueIslands = new HashSet<>();
private static int islandsCount = 0;


public static void main(String[] args){
    long start = System.nanoTime();

    for (int i = 0; i < MAXY; i++) {
        for (int j = 0; j < MAXX; j++) {
            // find the island and begin to describe its shape
            if (field[i][j] == 1){
                islandName = new StringBuilder("I");
                islandsCount++;
                uniqueIslands.add(lookingAround(i, j));
            }
        }
    }

    System.out.println("Islands quantity: " + islandsCount);
    System.out.println("Number of islands of different shapes: " + uniqueIslands.size());


    long finish = System.nanoTime();
    System.out.printf("program execution time %.3f millis", (double)(finish - start)/1_000_000);
}

//recursive method, to determine the shape of the island.
// The basic limitation is the absence of land on neighboring cells.
private static String lookingAround(int y, int x) {
    field[y][x] = 0;

    for (int i = 0; i < 4; i++) {
        int x1 = x + dx[i];
        int y1 = y + dy[i];
        if (y1 < MAXY && y1 >= 0 && x1 < MAXX && x1 >= 0) {
            if (field[y1][x1] == 1) {
                switch (i){
                    case 0:
                        islandName.append("U");
                        break;
                    case 1:
                        islandName.append("R");
                        break;
                    case 2:
                        islandName.append("D");
                        break;
                    case 3:
                        islandName.append("L");
                        break;
                }
                field[y1][x1] = 0;
                lookingAround(y1, x1);
            }
        }
    }
    return islandName.toString();
}

Подскажите, каким образом можно организовать параллельное выполнение данной задачи?

4
  • я бы начал отсюда: dsp.stackexchange.com/questions/16233/… en.wikipedia.org/wiki/Connected-component_labeling
    – etki
    4 мая 2018 в 17:13
  • Параллелить через Fork/Join имеет мало смысла, если только это не одна из многих джоб, которые выполняются у вас в приложении. Если приложение занято только решением этой задачи, то проще взять фиксированный пул тредов и использовать его.
    – etki
    4 мая 2018 в 17:14
  • @etki рекурсивные задачи прекрасно параллелятся именно с помощью Fork/Join. К тому же в Fork/Join есть work stealing, реализовать который самостоятельно на фиксированном пуле потоков не просто. 4 мая 2018 в 17:25
  • @SergeyGornostaev это не рекурсивная задача, и про отсутствующую необходимость work stealing все второе предложение.
    – etki
    4 мая 2018 в 17:32

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Посмотрите другие вопросы с метками или задайте свой вопрос.