Описание тега fork-join

Описание тега Вопросы с тегом

Fork-Join означает разделение работы на фрагменты и объединение результатов. Вы можете разделить работу на компоненты и запланировать каждый компонент для пула потоков, объединяя результаты, когда все компоненты будут завершены. Вы можете рекурсивно разбить агрегированную структуру на идентичные задачи и объединить результаты, когда все задачи будут выполнены.

Следуя стратегии "разделяй и властвуй", такие проблемы, как сортировка массива слиянием, разбиваются на (две или более) более мелкие подзадачи. Если эти подзадачи все еще слишком велики для непосредственного решения, они снова рекурсивно разбиваются на еще более мелкие подзадачи. Как только подзадачи станут достаточно мелкими, для их решения можно использовать простой / наивный алгоритм. Частичные решения этих подзадач затем постепенно объединяются в решения исходных более крупных проблем.

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

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

В качестве примера вы можете попробовать Java 1.7, которая поставляется с фреймворком Fork/Join (первоначально называвшимся jsr-166y).