Załóżmy, że chcemy obliczyć pewne liczby Fibonacciego, modulo 997.

Dla n=500 w C++ możemy uruchomić

#include <iostream>
#include <array>

std::array<int, 2> fib(unsigned n) {
    if (!n)
        return {1, 1};
    auto x = fib(n - 1);
    return {(x[0] + x[1]) % 997, (x[0] + 2 * x[1]) % 997};
}

int main() {
    std::cout << fib(500)[0];
}

Iw Pythonie

def fib(n):
    if n==1:
        return (1, 2)
    x=fib(n-1)
    return ((x[0]+x[1]) % 997, (x[0]+2*x[1]) % 997)

if __name__=='__main__':
    print(fib(500)[0])

Obaj znajdą odpowiedź 996 bez problemów. Bierzemy modulo, aby utrzymać rozsądny rozmiar wyjścia i używamy par, aby uniknąć rozgałęzienia wykładniczego.

W przypadku n=5000 kod C++ wyprowadza 783, ale Python będzie narzekał

RecursionError: maximum recursion depth exceeded in comparison

Jeśli dodamy kilka linijek

import sys

def fib(n):
    if n==1:
        return (1, 2)
    x=fib(n-1)
    return ((x[0]+x[1]) % 997, (x[0]+2*x[1]) % 997)

if __name__=='__main__':
    sys.setrecursionlimit(5000)
    print(fib(5000)[0])

Wtedy również Python udzieli właściwej odpowiedzi.

Dla n=50000 C++ znajduje odpowiedź 151 w ciągu milisekund, podczas gdy Python ulega awarii (przynajmniej na moim komputerze).

Dlaczego wywołania rekurencyjne są tak dużo tańsze w C++? Czy możemy w jakiś sposób zmodyfikować kompilator Pythona, aby był bardziej podatny na rekurencję?

Oczywiście jednym z rozwiązań jest zastąpienie rekurencji iteracją. W przypadku liczb Fibonacciego jest to łatwe. Jednak spowoduje to zamianę warunków początkowych i końcowych, a ten drugi jest trudny w przypadku wielu problemów (np. przycinanie alfa-beta). Tak więc generalnie będzie to wymagało dużo ciężkiej pracy ze strony programisty.

79
jtallk 15 czerwiec 2021, 18:03

4 odpowiedzi

Najlepsza odpowiedź

Rozwiązaniem jest trampolina: funkcja rekurencyjna, zamiast wywoływać inną funkcję, zwraca funkcję, która wykonuje to wywołanie z odpowiednimi argumentami. Jest pętla o jeden poziom wyżej, która wywołuje wszystkie te funkcje w pętli, aż do uzyskania końcowego wyniku. Chyba nie wyjaśniam tego zbyt dobrze; możesz znaleźć zasoby online, które wykonują lepszą pracę.

Chodzi o to, że przekształca to rekurencję w iterację. Nie sądzę, że jest to szybsze, może nawet wolniej, ale głębokość rekurencji pozostaje niska.

Implementacja mogłaby wyglądać jak poniżej. Podzieliłem parę x na a i b dla jasności. Następnie przekonwertowałem funkcję rekurencyjną na wersję, która śledzi a i b jako argumenty, czyniąc ją rekurencyjną.

def fib_acc(n, a, b):
    if n == 1:
        return (a, b)
    return lambda: fib_acc(n - 1, (a+b) % 997, (a+2*b) % 997)

def fib(n):
    x = fib_acc(n, 1, 2)
    while callable(x):
        x = x()
    return x

if __name__=='__main__':
    print(fib(50000)[0])
26
Roel Schroeven 16 czerwiec 2021, 09:28

Problem polega na tym, że Python ma wewnętrzne ograniczenie liczby wywołań funkcji rekurencyjnych.

Ten limit można skonfigurować, jak pokazano w odpowiedzi Quentina Coumesa. Jednak zbyt głęboki łańcuch funkcji spowoduje przepełnienie stosu. To podstawowe ograniczenie¹ dotyczy zarówno C++, jak i Pythona. To ograniczenie dotyczy również wszystkich wywołań funkcji, nie tylko rekurencyjnych.

Ogólnie: nie należy pisać algorytmów², które mają wzrost głębokości rekurencji z liniową złożonością lub gorzej. Rekurencja rosnąca logarytmicznie jest zazwyczaj w porządku. Funkcje rekurencyjne ogona są trywialne do przepisania jako iteracji. Inne rekursje można przekształcić w iterację przy użyciu zewnętrznych struktur danych (zwykle stosu dynamicznego).

Powiązana zasada jest taka, że ​​nie powinieneś mieć dużych obiektów z automatycznym przechowywaniem. Jest to specyficzne dla C++, ponieważ Python nie ma koncepcji automatycznego przechowywania.


¹ Podstawowym ograniczeniem jest rozmiar stosu wykonania. Domyślny rozmiar różni się w zależności od systemu, a różne wywołania funkcji zużywają różne ilości pamięci, więc limit nie jest określony jako liczba wywołań, ale zamiast tego w bajtach. To też jest konfigurowalne w niektórych systemach. Zazwyczaj nie polecam dotykania tego limitu ze względu na problemy z przenoszeniem.

² Wyjątkiem od tej reguły są pewne języki funkcjonalne, które gwarantują eliminację rekurencji ogonowej – takie jak Haskell – gdzie reguła ta może być złagodzona w przypadku rekurencji, których wyeliminowanie jest gwarantowane. Python nie jest takim językiem, a funkcja, o której mowa, nie jest tail-recursive. Chociaż kompilatory C++ mogą wykonywać eliminację jako optymalizację, nie jest to gwarantowane i zwykle nie są zoptymalizowane w kompilacjach debugowania. W związku z tym wyjątek generalnie nie dotyczy również C++.

Zastrzeżenie: Oto moja hipoteza; Właściwie nie znam ich uzasadnienia: limit Pythona jest prawdopodobnie funkcją, która wykrywa potencjalnie nieskończone rekurencje, zapobiegając prawdopodobnie niebezpiecznym awariom przepełnienia stosu i zastępując bardziej kontrolowany RecursionError.

Dlaczego wywołania rekurencyjne są tak dużo tańsze w C++?

C++ jest językiem skompilowanym. Python jest interpretowany. (Prawie) wszystko jest tańsze w C++, z wyjątkiem tłumaczenia z kodu źródłowego na program wykonywalny.

51
Toby Speight 18 czerwiec 2021, 07:30

Możesz zwiększyć limit rekurencji za pomocą:

import sys

sys.setrecursionlimit(new_limit)

Pamiętaj jednak, że ten limit istnieje z jakiegoś powodu i że czysty Python nie jest zoptymalizowany pod kątem rekurencji (i ogólnie zadań wymagających dużej mocy obliczeniowej).

7
qcoumes 15 czerwiec 2021, 15:23

W przypadku plików wykonywalnych systemu Windows rozmiar stosu jest określony w nagłówku pliku wykonywalnego. W przypadku wersji Pythona 3.7 x64 dla systemu Windows ten rozmiar to 0x1E8480 lub dokładnie 2 000 000 bajtów.

Ta wersja ulega awarii z

Process finished with exit code -1073741571 (0xC00000FD)

I jeśli poszukamy tego stwierdzamy, że jest to przepełnienie stosu.

To, co możemy zobaczyć na (natywnym) stosie z natywnym debuggerem, takim jak WinDbg (włącz debugowanie procesów potomnych) to

[...]
fa 000000e9`6da1b680 00007fff`fb698a6e     python37!PyArg_UnpackStack+0x371
fb 000000e9`6da1b740 00007fff`fb68b841     python37!PyEval_EvalFrameDefault+0x73e
fc 000000e9`6da1b980 00007fff`fb698a6e     python37!PyArg_UnpackStack+0x371
fd 000000e9`6da1ba40 00007fff`fb68b841     python37!PyEval_EvalFrameDefault+0x73e
fe 000000e9`6da1bc80 00007fff`fb698a6e     python37!PyArg_UnpackStack+0x371
ff 000000e9`6da1bd40 00007fff`fb68b841     python37!PyEval_EvalFrameDefault+0x73e

2:011> ? 000000e9`6da1bd40 - 000000e9`6da1ba40 
Evaluate expression: 768 = 00000000`00000300

Tak więc Python użyje 2 ramek stosu na wywołanie metody i istnieje ogromna różnica 768 bajtów w pozycjach stosu.

Jeśli zmodyfikujesz tę wartość w EXE (zrób kopię zapasową) za pomocą edytora szesnastkowego, powiedzmy 256 MB

Python.exe edited in 010 Editor

Możesz uruchomić następujący kod

[...]
if __name__=='__main__':
    sys.setrecursionlimit(60000)
    print(fib(50000)[0])

I da odpowiedź 151.


W C++ możemy też wymusić Stack Overflow, np. przekazując 500 000 jako parametr. Podczas debugowania otrzymujemy

0:000> .exr -1
ExceptionAddress: 00961015 (RecursionCpp!fib+0x00000015)
ExceptionCode: c00000fd (Stack overflow)
[...]
0:000> k
[...]
fc 00604f90 00961045     RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7] 
fd 00604fb0 00961045     RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7] 
fe 00604fd0 00961045     RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7] 
ff 00604ff0 00961045     RecursionCpp!fib+0x45 [C:\...\RecursionCpp.cpp @ 7] 

0:000> ? 00604ff0 - 00604fd0
Evaluate expression: 32 = 00000020

Co stanowi tylko 1 ramkę stosu na wywołanie metody i tylko 32 bajty różnicy na stosie. W porównaniu do Pythona, C++ może wykonać 768/32 = 24x więcej rekurencji dla tego samego rozmiaru stosu.

Mój kompilator Microsoftu utworzył plik wykonywalny z domyślnym rozmiarem stosu 1 MB (wersja wydania, 32-bitowa):

010 Editor for C++ executable

Wersja 64-bitowa ma 64-bitową różnicę stosu (również wersja wydania).


Narzędzia użyte:

7
Thomas Weller 17 czerwiec 2021, 18:55