Papan anjal untuk berfungsi melebihi primitif rekursif? Pelaksanaan untuk fungsi Ackermann Peter

Apabila meneroka teknik papan anjal, saya pada mulanya menggunakannya dalam situasi yang lebih mudah, dengan hanya satu ulangan – mungkin subset yang betul bagi fungsi rekursif primitif. Walau bagaimanapun, keperluan timbul untuk melakukan pengiraan yang sangat panjang di tempat kerja. Idea pertama saya ialah fungsi sibuk memerang, tetapi, sebagai tambahan kepada kerumitan pengiraan yang tinggi, saya tidak begitu biasa. Saya kemudian memilih fungsi yang lebih dikenali: fungsi Ackermann-Peter.

Fungsi Ackermann-Peter

Ini ialah fungsi yang mudah difahami yang mengambil dua hujah integer sebagai input:

<code class="language-java">int ackermannPeter(int m, int n) {
    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ackermannPeter(m - 1, 1);
    }
    return ackermannPeter(m - 1, ackermannPeter(m, n - 1));
}</code>

Untuk butiran lanjut, lihat halaman Wikipedia atau WolframAlpha.

Menggunakan Fungsi

Apabila menguji ackermannPeter(3, 3), keputusan dikira dengan betul. Walau bagaimanapun, apabila melaksanakan ackermannPeter(4, 3), letupan tindanan berlaku. Kedalaman panggilan rekursif ke fungsi Ackermann-Peter adalah sangat besar; hanya menukar hujah pertama daripada 3 kepada 4 menjadikan output, iaitu 61, menjadi $2^{2^{65536}} - 3$.

Mengatasi Had Tindanan

Masalahnya terletak pada pengulangan sengit fungsi Ackermann-Peter, yang cepat meletihkan timbunan. Penyelesaiannya adalah dengan menggunakan sambungan untuk mengelak daripada membebankan tindanan, melaksanakan idea papan anjal.

Satu langkah di atas trampolin memerlukan tiga tingkah laku:

• Nyatakan sama ada pengiraan telah tamat.
• Kembalikan nilai yang dikira.
• Lakukan satu langkah dan dapatkan kesinambungan seterusnya.

Untuk kes kami (pulangan integer):

<code class="language-java">interface Continuation {
    boolean finished();
    int value();
    Continuation step();

    static Continuation found(int v) { /* ... */ }
    static Continuation goon(Supplier<Continuation> nextStep) { /* ... */ }
}</code>

Trampolin itu sendiri:

<code class="language-java">static int compute(Continuation c) {
    while (!c.finished()) {
        c = c.step();
    }
    return c.value();
}</code>

Memohon pada fungsi Ackermann-Peter: fungsi terbahagi kepada tiga kes: kes asas, rekursi mudah dan rekursi berganda. Papan anjal harus mengawal hasil rekursi kedua. Untuk melakukan ini, hujah kedua menjadi Continuation. Jika n sudah selesai, proses diteruskan seperti biasa; jika tidak, satu langkah diambil dalam kesinambungan, menjana yang baharu.

<code class="language-java">private static Continuation ackermannPeter(int m, Continuation c) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeter(m, next));
        });
    }
    int n = c.value();
    if (m == 0) {
        return Continuation.found(n + 1);
    } else if (n == 0) {
        return Continuation.goon(() -> ackermannPeter(m - 1, Continuation.found(1)));
    }
    return Continuation.goon(() ->
        ackermannPeter(m - 1,
            Continuation.goon(() -> ackermannPeter(m, Continuation.found(n - 1)
        )))
    );
}</code>

Menambah Memoisasi

Menghafal meningkatkan prestasi. Dua situasi: 1) hasilnya sudah dalam ingatan; 2) langkah seterusnya membolehkan anda membuat kesimpulan hasil semasa. Memoisasi digunakan selepas menyelesaikan kesinambungan hujah kedua. Pelaksanaan dengan memoisasi menggunakan kekunci HashMap dan long (menggabungkan m dan n) dibentangkan, menunjukkan pengurangan ketara dalam bilangan panggilan rekursif. Versi akhir mengalih keluar kebergantungan memori global, memberikan HashMap sebagai hujah.

Atas ialah kandungan terperinci Papan anjal untuk berfungsi melebihi primitif rekursif? Pelaksanaan untuk fungsi Ackermann Peter. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!