Trampolin, contoh di Jawa

Mari kita tulis atur cara mudah untuk menambah nombor daripada n kepada 0. Tetapi daripada menggunakan pendekatan berulang, mengapa tidak mencuba pendekatan rekursif?

Kami memanggil program ini sum. Kami tahu sum(0) == 0, jadi ini adalah kes asas kami. Bagaimanakah kita sampai ke kes asas? sum(n) == n sum(n-1), sehingga akhirnya mencapai sum(0). Kod Java adalah seperti berikut:

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

Masalah rekursi?

Rekursi mempunyai kelemahan yang wujud apabila kes asas berada jauh daripada nilai input... Dalam kebanyakan bahasa, panggilan fungsi menggunakan tindanan program untuk menyimpan maklumat panggilan fungsi, jadi rekursi yang sangat besar boleh menyebabkan limpahan tindanan.

Tetapi, adakah cara untuk mengelakkan perkara ini? Sebenarnya ada. Ini adalah strategi lama yang dipanggil trampolin.

Springboard

Idea asas strategi papan anjal ialah sebahagian daripada program mengembalikan "nilai" atau "sambungan". Apakah kesinambungan? Fungsi yang akan meneruskan pemprosesan.

Ia kira-kira seperti berikut:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

Apakah kesinambungan

sum?

Mari kita model sum program sebagai: Daripada hanya mengulangi, gunakan sambungan. Satu cara ialah menggunakan acc sebagai objek yang dilalui melalui sambungan. Jadi apabila sum_trampoline(0, acc) dicapai, kami kembali acc. Bagaimana untuk meneruskan?

Mari kita pergi dari sum_trampoline(n, acc) ke sum_trampoline(n-1, acc n). Input pertama ialah sum_trampoline(n, 0).

Jadi, kodnya adalah seperti berikut:

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

Gunakan jenis untuk menerangkan papan anjal

Papan anjal perlu kira-kira dalam bentuk berikut:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

Tetapi ini memberikan banyak kebebasan pengekodan dan tidak begitu intuitif untuk dunia Java. Kita boleh menyemak sama ada ia adalah kesinambungan dengan bertanya objek. Bagaimana jika kita bertanya "Adakah nilai ditemui?" Perkara lain ialah memandangkan Java tidak mempunyai jumlah-jenis, return trampolim sebenarnya akan mengembalikan jenis trampolim dan bukannya mengembalikan nilai. Kita boleh kembali ke trampolim.value().

Akhir sekali, perkara utama ialah bootstrap papan anjal. Untuk melakukan ini, kita boleh menggunakan fungsi untuk menukar input kepada nilai pulangan pogo yang sesuai. Input dan hasil boleh digeneralisasikan untuk kegunaan yang lebih baik:

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

TrampolineStep<R>Bagaimana pula dengan antara muka?

Ia mentakrifkan tiga kaedah:

• gotValue: Bertanya sama ada nilai telah ditemui
• value: Mengembalikan nilai yang ditemui
• runNextStep: Mengembalikan nilai atau kesinambungan

Ia pada asasnya mempunyai dua keadaan:

• Nilai ditemui
• Ia adalah kesinambungan

Oleh itu, kita boleh menggunakan kaedah statik untuk memulakannya. Untuk kes di mana nilai telah ditemui, nilai perlu diluluskan:

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

Untuk kes sambungan, anda perlu lulus cara mendapatkan item sambungan seterusnya:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

sum_trampolineBagaimana ini akan dicapai?

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

Panggilan ekor Fibonacci

Pelaksanaan klasik Fibonacci mengikut definisi rekursif:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

Terdapat juga versi berulang yang mengembangkan definisi Fibonacci bukan secara rekursif, tetapi ke hadapan: bermula dari 0 dan 1 sehingga nilai yang sepadan dicapai:

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

Terdapat versi hadapan pelaksanaan ini, menggunakan "rekursi panggilan ekor":

static <X> TrampolineStep<X> valueFound(X value) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return true;
        }

        @Override
        public X value() {
            return value;
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return this;
        }
    };
}

Di sini saya memisahkan antara muka input, yang menyediakan nombor yang akan digunakan dalam panggilan ekor rekursif Fibonacci. Semasa ia bergerak ke hadapan, kita mulakan dengan pemetaan fib[0] => 0, fib[1] => 1 dan menavigasi dari indeks 0 sehingga kita mencapai indeks n.

Fibonacci: Dari Panggilan Ekor ke Papan anjal

Contoh

fib_tc menggambarkan papan anjal Fibonacci dengan baik:

static <X> TrampolineStep<X> goonStep(Supplier<TrampolineStep<X>> x) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return false;
        }

        @Override
        public X value() {
            throw new RuntimeException("dont call this");
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return x.get();
        }
    };
}

Sila ambil perhatian bahawa ini hanyalah rangka dan memerlukan pelaksanaan lengkap antara muka TrampolineStep dan pelaksanaan lengkap fungsi trampoline untuk menyusun dan menjalankan. Selain itu, IN perlu digantikan dengan jenis input tertentu.

Atas ialah kandungan terperinci Trampolin, contoh di Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!