Это не хороший способ сделать последовательность Фибоначчи: -)
Ваш первый поток запускает два других, каждый из которых запускает два других и так далее.Поэтому, когда n > 16, вы можете получить очень большое количество потоков (в тысячах) (a) .
Если ваш процессор не имеет way moreчем мои ядра, вы будете тратить свое время на запуск тысяч потоков для такой задачи, связанной с процессором.Для задач, связанных только с процессором, лучше иметь столько потоков, сколько имеется физических механизмов исполнения (ядер или процессоров).Очевидно, что это меняется, когда вы не ограничены только процессором.
Если вам нужен эффективный рекурсивный (не поточный) калькулятор Фибоначчи, вы должны использовать что-то вроде (псевдокод):
def fib(n, n ranges from 1 to infinity):
if n is 1 or 2:
return 1
return fib(n-1) + fib(n-2)
Фибоначчи даже не очень хорош для непоточной рекурсии, так как проблема не очень быстро уменьшается.Под этим я подразумеваю, что при расчете fib(1000) будет использовано 1000 кадров стека.Сравните это с рекурсивным поиском двоичного дерева, где требуется только десять кадров стека.Это связано с тем, что первое удаляет только 1/1000 пространства поиска для каждого кадра стека, а второе - половину оставшегося пространства поиска.
Лучший способ сделать Фибоначчи с помощью итерации:
def fib(n, n ranges from 1 to infinity):
if n is 1 or 2:
return 1
last2 = 1, last1 = 1
for i ranges from 3 to n:
last0 = last2 + last1
last2 = last1
last1 = last0
return last0
Конечно, если вам нужен быстрый быстрый генератор Фибоначчи , вы пишете программу, которая генерирует все те, которые вы можете сохранить (например, в длинном значении), и записывает структуру Cсодержать их.Затем включите этот вывод в вашу C-программу, и ваши «вычисления» во время выполнения сдувают любой другой метод из воды.Это ваш стандартный метод оптимизации «обмен пространства на время»:
long fib (size_t n) {
static long fibs[] = {0, 1, 1, 2, 3, 5, 8, 13, ...};
if (n > sizeof(fibs) / sizeof(*fibs))
return -1;
return fibs[n];
}
Эти рекомендации применимы к большинству ситуаций, когда пространство поиска сокращается не так быстро (не только по Фибоначчи).
(a) Первоначально я думал, что это будет 2 16 , но, как показывает следующая программа (и благодаря Nemo за то, что я выпрямился), этоне так уж и плохо - я не принял во внимание сокращающую природу порожденных потоков при приближении к fib(0):
#include <stdio.h>
static count = 0;
static void fib(int n) {
if (n <= 2) return;
count++; fib(n-1);
count++; fib(n-2);
}
int main (int argc, char *argv[]) {
fib (atoi (argv[1]));
printf ("%d\n", count);
return 0;
}
Это эквивалентно коду, который вы имеете, но он просто увеличивает счетчикдля каждой порожденной нити, а не на самом деле порождая их.Количество потоков для различных входных значений:
N Threads
--- ---------
1 0
2 0
3 2
4 4
5 8
6 14
:
14
15 1,218
16 1,972
:
20 13,528
:
26 242,784
:
32 4,356,616
Теперь обратите внимание, что хотя я сказал, что это не как плохо, я не говорил, что это хорошо :-)Даже две тысячи потоков - это достаточная нагрузка на систему, каждый из которых имеет свои собственные структуры ядра и стеки.И вы можете видеть, что, хотя увеличение начинается с малого, оно быстро ускоряется до такой степени, что становится неуправляемым.И это не то, что число 32 и велико - это всего лишь смайлик, превышающий два миллиона.
Таким образом, итоговая черта остается неизменной: используйте рекурсию там, где это имеет смысл (где вы можете уменьшитьсравнительно быстро ищите пространство, чтобы не исчерпать пространство стека), и используйте threds там, где это имеет смысл (когда вы не заканчиваете тем, что запускаете так много, что перегружаете ресурсы операционной системы).