Обойти неизвестной глубины дерево параллельно

[Palych]

проблема в том чтобы количество потоков можно было переконфигурить на лету.

А зачем? Чтобы не перегружать удалённую систему?

[valchkou]

проблема в том чтобы количество потоков можно было переконфигурить на лету.

А зачем? Чтобы не перегружать удалённую систему?

да, как удаленную так и локальную.

[Ann4Ann]

я сейчас очень похожую задачу пишу, только у меня не дерево, а граф, так что стейт сложнее. вначале один-в-один как у автора написала, но очень уж оно не сбалансровано все. в итоге по времени и по перформансу мне легче вышло вначале сделать легкий траверс графа (в лоб) собирая инфу для heavy lifting в какой-то мнее.. execution plan. а потом этот план уже параллельно запустить. так получилось больше контроля за балансом нагрузки на потоки. по времени выигрыш ~ в 4 раза в моем случае. но, понятно, что не всегда можно легкий траверс сделать, там как раз дьявол в деталях.

[valchkou]

автор еще ничего не написал,
если я пойду первым путем то работа будет распределяться и распараллеливаться через
ArrayBlockingQueue<Node> queue;

с одной стороны я буду доставать и добавлять в эту очередь ноды
queue.put(node);

с другой же будет фиксированное количество потоков читающих из очереди
Node n = queue.take();
process(n)

что то типа этого

Code: Select all

package com.valchkou;

import javax.annotation.PostConstruct;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class TaskPubSub {

    private int queueSize = 100;
    private int workerSize = 4;

    private ArrayBlockingQueue<Task> queue;
    private ExecutorService taskExecutor;

    public TaskPubSub () {
        queue = new ArrayBlockingQueue<Task>(queueSize);
        taskExecutor = Executors.newFixedThreadPool(workerSize);
        subscribe();
    }


    /**
     * Submit Task for processing or block if queue is full.
     */
    public void submit(Task t) {
    	queue.put(t);
    }


    /**
     * initialize working threads to process the queued items
    */
    private void subscribe() {
        for (int i=0; i< workerSize; i++) {
            taskExecutor.submit(() -> {
                 while (true) {
                         Task t = queue.take();
                          process(t);
                 }
            });
        }
    }

}

[ALV00]

я сейчас очень похожую задачу пишу, только у меня не дерево, а граф, так что стейт сложнее. вначале один-в-один как у автора написала, но очень уж оно не сбалансровано все. в итоге по времени и по перформансу мне легче вышло вначале сделать легкий траверс графа (в лоб) собирая инфу для heavy lifting в какой-то мнее.. execution plan.

Интересно, как этот план запоминается? Тоже дерево?

[Palych]

я сейчас очень похожую задачу пишу, только у меня не дерево, а граф, так что стейт сложнее. вначале один-в-один как у автора написала, но очень уж оно не сбалансровано все. в итоге по времени и по перформансу мне легче вышло вначале сделать легкий траверс графа (в лоб) собирая инфу для heavy lifting в какой-то мнее.. execution plan.

Интересно, как этот план запоминается? Тоже дерево?

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

[ALV00]

я сейчас очень похожую задачу пишу, только у меня не дерево, а граф, так что стейт сложнее. вначале один-в-один как у автора написала, но очень уж оно не сбалансровано все. в итоге по времени и по перформансу мне легче вышло вначале сделать легкий траверс графа (в лоб) собирая инфу для heavy lifting в какой-то мнее.. execution plan.

Интересно, как этот план запоминается? Тоже дерево?

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

Что-то не осилил. Как из дерева получился список? В базах данных план выполнения это дерево.

[Palych]

я сейчас очень похожую задачу пишу, только у меня не дерево, а граф, так что стейт сложнее. вначале один-в-один как у автора написала, но очень уж оно не сбалансровано все. в итоге по времени и по перформансу мне легче вышло вначале сделать легкий траверс графа (в лоб) собирая инфу для heavy lifting в какой-то мнее.. execution plan.

Интересно, как этот план запоминается? Тоже дерево?

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

Что-то не осилил. Как из дерева получился список? В базах данных план выполнения это дерево.

Допустим дерево - это файлы в под-директориях. Нужно каждый переименовать.
Тогда построение плана: нахождение каждого файла и отправка его во очередь на переименование.

[DropAndDrag]

странно ... вроде бы написал здесь, а ничего нет

[Boriskin]

Напоминает задачу определения порядка компиляции множественных проектов с зависимостями друг на друга.

[Ann4Ann]

я сейчас очень похожую задачу пишу, только у меня не дерево, а граф, так что стейт сложнее. вначале один-в-один как у автора написала, но очень уж оно не сбалансровано все. в итоге по времени и по перформансу мне легче вышло вначале сделать легкий траверс графа (в лоб) собирая инфу для heavy lifting в какой-то мнее.. execution plan.

Интересно, как этот план запоминается? Тоже дерево?

ну в итоге thread-am `отдается PriorityBlockingQueque. объекты в ней, правда, могут быть композитами. т.е. если развернуть, то таки дерево. priority помогает выполнение/ресурсы сбалансировать - в зависимости от точки входа в граф, даже для одного стейта графа планы разные собираются, не только по балансу, но и по объёму работ/данных/требуемых ресурсов (собс-но из за этой фичи и все затевалось).
получился приятный сайд-эффект : сейчас я уже этот план в базе сохранять могу (одна таблица), выяснилось, что очень удобно народу взять конкретный стейт. при этом новый траверс на живом графе уже может выдать другой план для той же точки входа.

[АццкоМото]

Это... прочитал только пару ответов, но... Это же обычный BFS - breadth first search. Ну а дальше - например, RxJava-й прикручиваем observeOn(workerThreadPool) ну и как только очередь пуста - onComplete() и типа обход завершен. Несколько строк же