Java простой рекурсивный алгоритм, сделайте его параллельным - PullRequest
Новая
       56

Java простой рекурсивный алгоритм, сделайте его параллельным

0 голосов
/ 18 января 2020

У меня есть простой рекурсивный алгоритм, который генерирует все перестановки строки и подсчитывает число перестановок, которое проходит несколько условий. Я хотел бы сделать его более эффективным при параллельном программировании, но я не могу использовать его с 'forkJoinPool' (я не уверен, но это невозможно сделать способом разделяй и властвуй). Поэтому у меня была идея запустить все вычисления (проверка условий и счетчик приращений) в разделенных потоках, но это не лучше, чем алгоритм секвенции. 

Thread thread = new Thread(() -> {
    compute(elements);
});
thread.start();

Код выше, похоже, не работает лучше. 

package com.company;

public class Main {
    public static void main(String[] args) {
        long start = System.nanoTime();
        call();
        long end = System.nanoTime();
        System.out.println((end - start) / 1000000);
    }

    private static void call() {
        char[] elements = "1234567890+/".toCharArray();
        Permutation p = new Permutation();
        p.printAllRecursive(elements.length, elements);
        System.out.println(p.counter);
    }
}


class Permutation {
    Integer counter = 0;

    public void printAllRecursive(int n, char[] elements) {
        if (n == 1) {
            // running compute() in parallel
            Thread thread = new Thread(() -> {
                compute(elements);
            });
            thread.start();
        } else {
            for (int i = 0; i < n - 1; i++) {
                printAllRecursive(n - 1, elements);
                if (n % 2 == 0) {
                    swap(elements, i, n - 1);
                } else {
                    swap(elements, 0, n - 1);
                }
            }
            printAllRecursive(n - 1, elements);
        }
    }

    private void swap(char[] elements, int a, int b) {
        char tmp = elements[a];
        elements[a] = elements[b];
        elements[b] = tmp;
    }

    private void compute(char[] elements) {
        String string = new String(elements);
        int index1 = string.indexOf('/');
        int index2 = string.indexOf('+');
        if (index1 > 0 && index2 > 0 && index1 < 11 && index2 < 11) {
            if (index1 > index2) {
                if (index1 - index2 != 1) {
                    counter++;
                }
            }
        }
    }
}

Метод compute (elements) занимает много времени, как я могу сделать его более эффективным с многопоточностью? Заранее спасибо

1 Ответ

1 голос
/ 18 января 2020

Когда вы вызываете printAllRecursive(), вы создаете дополнительный поток для вызова compute(), а затем вызываете printAllRecursive() и снова создаете новый поток. Дополнительный поток не поможет вам. Похоже, ваш алгоритм неверен .

Посмотрите на правильный код для вычисления перестановок: 

public class Main {
    public static void main(String[] args) {
        long start = System.nanoTime();
        call();
        long end = System.nanoTime();
        System.out.println("time: " + (end - start) / 1000000);
    }

    private static void call() {
        char[] elements = "ABCD".toCharArray();
        int n = elements.length;
        Permutation p = new Permutation();
        p.printAllRecursive(elements, 0 , n-1);
        System.out.println("number of permutations: " + p.counter);
    }

}

class Permutation {
    Integer counter = 0;

    public void printAllRecursive(char[] elements, int l, int r) {
        if (l == r) {
            counter++;
            //System.out.println(String.valueOf(elements));
        } else {
            for (int i = l; i <= r; i++) {
                swap(elements, l, i);
                printAllRecursive(elements, l+1, r);
                swap(elements, l, i);
            }
        }
    }

    private void swap(char[] elements, int a, int b) {
        char tmp = elements[a];
        elements[a] = elements[b];
        elements[b] = tmp;
    }
}

Вы можете увидеть иллюстрацию этого алгоритма, чтобы лучше понять его, например, здесь

PS Как я уже говорил, ваша проблема не в многопоточности, но в любом случае я опишу, почему вы не можете просто добавить следующий код: 

Thread thread = new Thread(() -> {
    compute(elements);
});
thread.start();

Первое, что вы должны понять, это то, что Вы не можете изменить одну область памяти разными потоками. В вашем примере кода вы модифицируете поле counter и массив elements из разных потоков. Почему вы не можете изменить одну переменную из разных потоков? Например, поток1 хочет записать в ваш массив последовательность '777777777', и во время этого процесса записи поток2 хочет прочитать значения из массива. Итак, thread2 может читать значения '777456789', потому что thread1 все еще записывает данные в массив и еще не завершил sh. Таким образом, мы можем изменить Integer на потокобезопасный AtomicInteger и добавить synchronized к сигнатуре swap метода.

...