VPF::Возведение в степень Fork/Join Framework'ом

Pawl

Дата 2.7.2012, 12:15 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Уважаемые форумчане,
Исследую возможности Fork-Join фрэймворка. Написал программку возведения в степень числа.

Код


import java.util.concurrent.*;

public class ForkJoinPow extends RecursiveTask<Double> {
    private Double x;
    private int y;
    
    public ForkJoinPow(Double x, int y) {
        this.x = x;
        this.y = y;
    }
    
    public Double compute() {
        System.out.println(Thread.currentThread().getName() + " pow is: " + y);            
        if (y > 0) {
            ForkJoinPow pow = new ForkJoinPow(x, y - 1);            
            pow.fork();                
            return pow.join() * x;                        
        }

        return 1d;            
    }
    
    public static void main(String[] args) {     
     ForkJoinPow task = new ForkJoinPow(2d, 100);
        ForkJoinPool pool = new ForkJoinPool();
        System.out.println(pool.invoke(task));
        System.out.println(pool.getPoolSize());
        System.out.println(pool.getParallelism());
    }
}

и вот какой вопрос у меня возник: этой строкой

Код


System.out.println(Thread.currentThread().getName() + " pow is: " + y);

я определяю в частности, какой поток сейчас производит вычисление. Так вот, вычисления производят у меня всего 2 потока, хотя пул создается по умолчанию на 3 потока (т. к. на компе 3 проца), и методы

Код


        System.out.println(pool.getPoolSize());
        System.out.println(pool.getParallelism());

возвращают 3.
Более того, если написать, к примеру,

Код


ForkJoinPool pool = new ForkJoinPool(10);

все равно количество работающих потоков получается меньшим, чем размер пула. Был бы благодарен, если кто-нибудь объяснит мне, в чем тут дело, и насколько корректно я тут вообще реализовал Fork/Join framework.
Спасибо!

--------------------

В действительности всё совсем не так, как на самом деле

jk1

Дата 2.7.2012, 13:07 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 1168
Регистрация: 17.10.2008
Где: Санкт-Петербург

Репутация: 40
Всего: 75

Имхо проблема в декомпозиции. Надо бы делить работу пополам и правильно мержить:

Код


public class ForkJoinPow extends RecursiveTask<Double> {
    private Double x;
    private int y;

    public ForkJoinPow(Double x, int y) {
        this.x = x;
        this.y = y;
    }

    public Double compute() {
        System.out.println(Thread.currentThread().getName() + " pow is: " + y);
        if (y > 1) {
            ForkJoinPow pow1 = new ForkJoinPow(x, y / 2);
            pow1.fork();
            ForkJoinPow pow2 = new ForkJoinPow(x, y - y / 2);
            return pow2.compute() * pow1.join();
        } else {
            return x * y;
        }
    }


    public static void main(String[] args) {
        ForkJoinPow task = new ForkJoinPow(2d, 100);
        ForkJoinPool pool = new ForkJoinPool(5);
        System.out.println(pool.invoke(task));
        System.out.println(pool.getPoolSize());
        System.out.println(pool.getParallelism());
    }
}

Писал в браузере, так что мог не учесть какой-нибудь +- 1 или граничный случай. Но в целом идея должна быть понятна

--------------------

Opinions are like assholes — everybody has one

Pawl

Дата 2.7.2012, 13:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Цитата(jk1 @ 2.7.2012, 13:07

)

Но в целом идея должна быть понятна

Идея понятна, подобный способ я, собственно, в начале и применял, но меня смущает то, что в этом случае появляются "лишние" шаги рекурсии. Например, при у = 10 получается такой вывод:

Код


ForkJoinPool-1-worker-1 pow is: 10
ForkJoinPool-1-worker-1 pow is: 5
ForkJoinPool-1-worker-2 pow is: 5
ForkJoinPool-1-worker-1 pow is: 3
ForkJoinPool-1-worker-2 pow is: 3
ForkJoinPool-1-worker-1 pow is: 2
ForkJoinPool-1-worker-3 pow is: 2
ForkJoinPool-1-worker-1 pow is: 1
ForkJoinPool-1-worker-2 pow is: 2
ForkJoinPool-1-worker-1 pow is: 1
ForkJoinPool-1-worker-3 pow is: 1
ForkJoinPool-1-worker-1 pow is: 1
ForkJoinPool-1-worker-2 pow is: 1
ForkJoinPool-1-worker-3 pow is: 1
ForkJoinPool-1-worker-2 pow is: 1
ForkJoinPool-1-worker-3 pow is: 2
ForkJoinPool-1-worker-1 pow is: 1
ForkJoinPool-1-worker-3 pow is: 1
ForkJoinPool-1-worker-2 pow is: 1
1024.0
3
3

т. е. всего 19 шагов, в то время, как минимально необходимое - 11 (от 10 до 0 вкл.).

--------------------

В действительности всё совсем не так, как на самом деле

jk1

Дата 2.7.2012, 14:00 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 1168
Регистрация: 17.10.2008
Где: Санкт-Петербург

Репутация: 40
Всего: 75

Цитата

т. е. всего 19 шагов, в то время, как минимально необходимое - 11 (от 10 до 0 вкл.).

Тут будет 10 считающих шагов, а остальные делают декомпозицию и вычислений не производят.
Вот этот код

Код


 public Double compute() {
        if (y > 1) {
            System.out.println(Thread.currentThread().getName() + " decomposing, pow is: " + y);
            ForkJoinPow pow1 = new ForkJoinPow(x, y / 2);
            pow1.fork();
            ForkJoinPow pow2 = new ForkJoinPow(x, y - y / 2);
            return pow2.compute() * pow1.join();
        } else {
            System.out.println(Thread.currentThread().getName() + " computing, pow is: " + y);
            return x * y;
        }
    }

показывает, какие шаги что делают.

Вообще говоря это логично, Fork/Join - это всегда дерево задач, а не линейная последовательность, как в вашем первом посте.

--------------------

Opinions are like assholes — everybody has one

Pawl

Дата 2.7.2012, 14:21 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Ок, будем разбираться. Кстати, ИМХО, писать

Код


return x * y;

ненужно. Ведь в ветке else y все-равно будет = 1, так что достаточно написать

Код


return x;

и еще я в самом начале compute() дописал

Код


     if (y == 0) {
         return 1d;
     }

чтобы корректно получить число в степени 0.

--------------------

В действительности всё совсем не так, как на самом деле

jk1

Дата 2.7.2012, 14:44 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 1168
Регистрация: 17.10.2008
Где: Санкт-Петербург

Репутация: 40
Всего: 75

Цитата

Ок, будем разбираться. Кстати, ИМХО, писать
код Java

return x * y;

ненужно. Ведь в ветке else y все-равно будет = 1, так что достаточно написать

Как уже писал выше - это черновик для иллюстрации концептуальных вещей. Так-то Вы конечно правы

--------------------

Opinions are like assholes — everybody has one

Pawl

Дата 2.7.2012, 14:58 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Спасибо!
Вообще, наверное, данный фреймворк не очень подходит для вычисления степени. Ветвления тут явно лишние. Может быть Вы знаете более подходящие и наглядные примеры?

Это сообщение отредактировал(а) Pawl - 2.7.2012, 15:10

--------------------

В действительности всё совсем не так, как на самом деле

jk1

Дата 2.7.2012, 15:32 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 1168
Регистрация: 17.10.2008
Где: Санкт-Петербург

Репутация: 40
Всего: 75

Я когда-то писал merge sort сначала на потоках с ручной синхронизацией, затем - на fork/join, для иллюстрации.
Эта задача разветвляется гораздо лучше. Хорошо должна также пойти обработка любых древовидных структур, например файловых систем.

Важно только понимать, что реальный прирост производительности начинается при достаточной вычислительной емкости подзадач.

--------------------

Opinions are like assholes — everybody has one

Stolzen

Дата 2.7.2012, 15:38 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1041
Регистрация: 17.10.2005

Репутация: 23
Всего: 48

Цитата(Pawl @ 2.7.2012, 15:58

)

Вообще, наверное, данный фреймворк не очень подходит для вычисления степени. Ветвления тут явно лишние. Может быть Вы знаете более подходящие и наглядные примеры?

Может mergesort?

Добавлено через 3 минуты и 22 секунды
Упс, пардон, меня уже опередили с советом про mergesort

--------------------

datatalks.ru - анализ данных, статистика, машинное обучение

Pawl

Дата 2.7.2012, 15:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Цитата(jk1 @ 2.7.2012, 15:32

)

Я когда-то писал merge sort сначала на потоках с ручной синхронизацией, затем - на fork/join, для иллюстрации.

Ок, я тоже попробую - для иллюстрации. smile

Эту тему я закрываю, но если появятся вопросы по применению fork/join в сортировке - открою новую!

Это сообщение отредактировал(а) Pawl - 2.7.2012, 15:47

--------------------

В действительности всё совсем не так, как на самом деле

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »