Многопоточность и рекурсия вместе - PullRequest
Новая
       24

Многопоточность и рекурсия вместе

6 голосов
/ 01 апреля 2011

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

function(TreeNode curr) 
{
    if (curr.children != null && !curr.children.isEmpty()) 
    {
        for (TreeNode n : curr.children) 
    {
            //do some stuff
            function(n);
        }
    } 
    else 
    {
        //do some other processing
    }
}

Я хочу использовать потоки, чтобы сделать это быстрее.Большую часть времени тратится на прохождение, поэтому я не хочу просто создавать поток для обработки «другой обработки», потому что это не занимает много времени.Я думаю, что хочу разветвлять темы на "делать что-то", но как это будет работать?

Ответы [ 3 ]

12 голосов
/ 01 апреля 2011

Это хороший случай для Fork / Join Framework , который должен быть включен в Java 7. В качестве автономной библиотеки для использования с Java 6 ее можно загрузить здесь .

Примерно так: 

public class TreeTask extends RecursiveAction {
    private final TreeNode node;
    private final int level;

    public TreeTask(TreeNode node, int level) {
        this.node = node;
        this.level = leve;
    }

    public void compute() {
        // It makes sense to switch to single-threaded execution after some threshold
        if (level > THRESHOLD) function(node);

        if (node.children != null && !node.children.isEmpty()) {
            List<TreeTask> subtasks = new ArrayList<TreeTask>(node.children.size());
            for (TreeNode n : node.children) {
                // do some stuff
                subtasks.add(new TreeTask(n, level + 1));
            }
            invokeAll(subtasks); // Invoke and wait for completion
        } else {
            //do some other processing
        }
    }
}

...
ForkJoinPool p = new ForkJoinPool(N_THREADS);
p.invoke(root, 0);

Ключевым моментом структуры fork / join является кража работы - при ожидании завершения потока подзадач выполняется другие задачи. Это позволяет вам написать алгоритм простым способом, избегая при этом проблем с исчерпанием потока, как наивно с ExecutorService.

3 голосов
/ 01 апреля 2011

В блоке кода // do some stuff, где вы работаете с отдельным Узлом, вместо этого вы можете отправить Узлу какой-то вид ExecutorService (в виде Runnable, который будет работать на узле).

Вы можете настроить ExecutorService, который вы используете для поддержки пула определенного количества потоков, что позволяет вам отделить логику "обработки" (наряду с логикой вокруг создания потоков, сколько их создавать и т. Д.) из вашей логики синтаксического анализа дерева.

2 голосов
/ 02 апреля 2011

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

Я бы попросил поток вызывающей стороны выполнить рекурсию, а затем1003 * рабочих, которые обрабатывают листья через пул потоков.Я не рассматриваю InterruptedException в нескольких местах здесь. 

public void processTree(TreeNode top) {
    final LinkedBlockingQueue<Runnable> queue =
        new LinkedBlockingQueue<Runnable>(MAX_NUM_QUEUED);
    // create a pool that starts at 1 threads and grows to MAX_NUM_THREADS
    ExecutorService pool =
        new ThreadPoolExecutor(1, MAX_NUM_THREADS, 0L, TimeUnit.MILLISECONDS, queue,
            new RejectedExecutionHandler() {
                public void rejectedExecution(Runnable r, ThreadPoolExecutor e) {
                    queue.put(r);  // block if we run out of space in the pool
                }
            });
    walkTree(top, pool);
    pool.shutdown();
    // i think this will join with all of the threads
    pool.awaitTermination(WAIT_TILL_CHILDREN_FINISH_MILLIS, TimeUnit.MILLISECONDS);
}
private void walkTree(final TreeNode curr, ExecutorService pool) {
    if (curr.children == null || curr.children.isEmpty()) {
        pool.submit(new Runnable() {
            public void run() {
                processLeaf(curr);
            }
        });
        return;
    }
    for (TreeNode child : curr.children) {
        walkTree(child, pool);
    }
}
private void processLeaf(TreeNode leaf) {
    // ...
}
...