Как написать многопоточную версию рекурсивного алгоритма Фибоначчи в Python

Question

Я пытаюсь лучше понять распараллеливание в Python. У меня проблемы с реализацией распараллеленного алгоритма Фибоначчи.

Я читал документы по многопроцессорности и многопоточности, но мне не повезло.

# TODO Figure out how threads work
# TODO Do a Fibonacci counter

import concurrent.futures


def fib(pos, _tpe):
    """Return the Fibonacci number at position."""
    if pos < 2:
        return pos

    x = fib(pos - 1, None)
    y = fib(pos - 2, None)

    return x + y


def fibp(pos, tpe):
    """Return the Fibonacci number at position."""
    if pos < 2:
        return pos

    x = tpe.submit(fib, (pos - 1), tpe).result()
    y = tpe.submit(fib, (pos - 2), tpe).result()

    return x + y


if __name__ == '__main__':
    import sys

    with concurrent.futures.ThreadPoolExecutor() as cftpe:
        fun = fibp if len(sys.argv) is 3 else fib
        position = int(sys.argv[1])
        print(fun(position, cftpe))
        print(fun.__name__)

Вывод командной строки:

$ time python test_fib_parallel.py 35
9227465
fib

real    0m3.778s
user    0m3.746s
sys     0m0.017s

$ time python test_fib_parallel.py 35 dummy-var
9227465
fibp

real    0m3.776s
user    0m3.749s
sys     0m0.018s

Я думал, что время должно значительно отличаться, но это не так.

---

ОБНОВЛЕНИЕ

Хорошо, так что советы помогли, и я заставил его работать (намного быстрее, чем оригинальная версия). Игнорируя код игрушки в оригинальном посте, я помещаю фрагмент фактической проблемы, которую я пытался решить, которая заключалась в том, чтобы вырастить дерево решений (для домашней работы). Это была проблема с процессором. Это было решено с использованием ProcessPoolExecutor и Manager.

def induce_tree(data, splitter, out=stdout, print_bool=True):
    """Greedily induce a decision tree from the given training data."""

    from multiprocessing import Manager
    from concurrent.futures import ProcessPoolExecutor

    output_root = Node(depth=1)
    input_root = Node(depth=1, data=data)
    proxy_stack = Manager().list([(input_root, output_root)])
    pool_exec = ProcessPoolExecutor()

    while proxy_stack:
        # while proxy_stack:
        #   pass proxy stack to function
        # return data tree
        current = proxy_stack.pop()
        if current[0] is not ():
            pool_exec.submit(grow_tree, proxy_stack, current, splitter)

    finish_output_tree(input_root, output_root)

    return output_root

---

ОБНОВЛЕНИЕ СНОВА

Это все еще глючит, потому что я неправильно управляю splitter между процессами. Я собираюсь попробовать что-то еще.

---

ПОСЛЕДНИЕ ОБНОВЛЕНИЯ

Я пытался распараллелить на слишком высоком уровне в моем коде. Мне пришлось сверлить до той части моего сплиттера, где было узкое место. Параллельная версия примерно в два раза быстрее. (Ошибка высока, потому что это просто тестовый образец без достаточного количества данных, чтобы на самом деле обучить хорошее дерево.)

Код в итоге выглядел так

inputs = [(data, idx, depth) for idx in range(data.shape[1] - 1)]

if self._splittable(data, depth):
      with ProcessPoolExecutor() as executor:
          for output in executor.map(_best_split_help, inputs):
          # ... ...

Последовательная

$ time python main.py data/spambase/spam50.data
Test Fold: 1, Error: 0.166667
Test Fold: 2, Error: 0.583333
Test Fold: 3, Error: 0.583333
Test Fold: 4, Error: 0.230769
Average training error: 0.391026

real    0m29.178s
user    0m28.924s
sys     0m0.106s

PARALLEL

$ time python main.py data/spambase/spam50.data
Test Fold: 1, Error: 0.166667
Test Fold: 2, Error: 0.583333
Test Fold: 3, Error: 0.583333
Test Fold: 4, Error: 0.384615
Average training error: 0.429487

real    0m14.419s
user    0m50.748s
sys     0m1.396s