разделяй и властвуй в реальной жизни
Идея разделяй и властвуй, как следует из названияразделяй и властвуй.就像古代的王想治理好天下，单单靠他一个人是不够的，还需要大臣的辅助，把天下划分为一块块区域，分派的下面的人负责，然后下面的人又分派给他们的属下负责，层层传递。
Разделяй и властвуй имеет множество приложений в алгоритмах, подобных MapReduce для больших данных,алгоритм слияния, алгоритм быстрой сортировки и т. д.
Платформа параллельных вычислений под названием Fork/Join также предоставляется в JUC для обработки ситуации «разделяй и властвуй», которая аналогична автономной версии.MapReduce.
Fork/Join
Разделяй и властвуй разделен на два этапа,Первый этап разбивает задачу, разбивает задачу на маленькие задачи до тех пор, пока маленькие задачи нельзя будет просто вычислить и вернуть.
На втором этапе результаты объединяются, а результаты каждой небольшой задачи объединяются и возвращаются для получения конечного результата.. а такжеForkдекомпозировать задачи,Joinявляется объединенным результатом.
Фреймворк Fork/Join в основном состоит из двух частей:ForkJoinPool、ForkJoinTask.
ForkJoinPool
Задача управления состоит в том, чтобы разделить и завоевать пул потоков. Это упоминалось в предыдущей статьеThreadPoolExecutorПул потоков, общим моментом является реализация шаблона потребитель-производитель, но есть и некоторые отличия.ThreadPoolExecutoПул потоков R имеет только одну очередь задач, иForkJoinPoolЕсть несколько очередей задач. пройти черезForkJoinPoolизinvokeилиsubmitилиexecuteПри отправке задачи она будет распределяться по разным очередям задач в соответствии с определенными правилами, а также в двухстороннюю очередь очереди задач.
выполняться асинхронно, результат не возвращается вызвать синхронизацию, есть возвращаемый результат (будет блокироваться) submit является асинхронным, с возвращаемым результатом (будущее)
Почему дека? потому чтоForkJoinPoolЕсть механизм,Когда очередь задач, соответствующая потреблению рабочим потоком, простаивает, она переходит в хвост других занятых очередей задач для выполнения задач кражи (хороший партнер).. Затем занятая очередь задач по-прежнему выводит задачу в соответствующий рабочий поток для использования. Таким образом, два конца находятся в упорядоченном порядке, и не будет конкуренции за задачи.
ForkJoinTask
Это задача разделяй и властвуй, что эквивалентно тому, что мы используем в будние дни.Runnable. Это абстрактный класс, основной методforkа такжеjoin.forkметод используется для асинхронного выполнения подзадачи,joinМетод блокирует текущий поток и ожидает возврата подзадачи.
ForkJoinTaskЕсть два подкласса, которыеRecursiveActionа такжеRecursiveTask. Эти два подкласса также являются абстрактными классами, и оба рекурсивно выполняют задачи «разделяй и властвуй». Каждый подкласс имеет абстрактные методыcomputeРазница в том,RecursiveActionне возвращаемое значение иRecursiveTaskИмеет возвращаемое значение.
Простое приложение
Классический случай рекурсивной реализации идеи «разделяй и властвуй» — это последовательность Фибоначчи.
Последовательность Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, … Формула: F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n>=3, n∈N*)
public static void main(String[] args) {
ForkJoinPool forkJoinPool = new ForkJoinPool(4); // 最大并发数4
Fibonacci fibonacci = new Fibonacci(20);
long startTime = System.currentTimeMillis();
Integer result = forkJoinPool.invoke(fibonacci);
long endTime = System.currentTimeMillis();
System.out.println("Fork/join sum: " + result + " in " + (endTime - startTime) + " ms.");
}
//以下为官方API文档示例
static class Fibonacci extends RecursiveTask<Integer> {
final int n;
Fibonacci(int n) {
this.n = n;
}
@Override
protected Integer compute() {
if (n <= 1) {
return n;
}
Fibonacci f1 = new Fibonacci(n - 1);
f1.fork();
Fibonacci f2 = new Fibonacci(n - 2);
return f2.compute() + f1.join();
}
}
Конечно, вы можете сделать и то, и другоеfork, обратите внимание, что обе задачиforkслучае необходимо соблюдатьf1.fork()，f2.fork()， f2.join()，f1.join()Такой порядок, иначе будут проблемы с производительностью. В официальной документации JDK есть инструкции, и те, кому это интересно, могут их изучить.
Я рекомендую использовать метод invokeAll
Fibonacci f1 = new Fibonacci(n - 1);
Fibonacci f2 = new Fibonacci(n - 2);
invokeAll(f1,f2);
return f2.join() + f1.join();
Method invokeAll (available in multiple versions) performs the most common form of parallel invocation: forking a set of tasks and joining them all.
Официальный документ API написан так, поэтому обычно используетсяinvokeAllДостаточно. invokeAll передаст первую входящую задачу текущему потоку для выполнения, а все остальные задачи будут разветвлены и добавлены в рабочую очередь, что означает, что текущий поток также используется для выполнения задачи. Ниже приведеныinvokeAllисходный код
public static void invokeAll(ForkJoinTask<?>... tasks) {
Throwable ex = null;
int last = tasks.length - 1;
for (int i = last; i >= 0; --i) {
ForkJoinTask<?> t = tasks[i];
if (t == null) {
if (ex == null)
ex = new NullPointerException();
}
else if (i != 0) //除了第一个都fork
t.fork();
else if (t.doInvoke() < NORMAL && ex == null) //留一个自己执行
ex = t.getException();
}
for (int i = 1; i <= last; ++i) {
ForkJoinTask<?> t = tasks[i];
if (t != null) {
if (ex != null)
t.cancel(false);
else if (t.doJoin() < NORMAL)
ex = t.getException();
}
}
if (ex != null)
rethrow(ex);
}
Эпилог
Fork/JoinЭто фреймворк, использующий идею «разделяй и властвуй», и многие сцены в будние дни могут использовать идею «разделяй и властвуй». ядро фреймворкаForkJoinPool, из-за особенностей очереди задач и кражи он может лучше использовать ресурсы.
Наконец, я желаю вам всем счастливой пятницы!
Если есть ошибки, поправьте меня! Личный публичный аккаунт: стратегия прокачки да
Есть соответствующие дополнительные материалы для интервью, ожидающие сбора