Memoisasi Faktorial dengan Python

Saat ini saya sedang mengerjakan artikel tentang menghitung sinus dan cosinus menggunakan Taylor Polynomials. Ini membuat banyak penggunaan faktorial jadi saya mulai memikirkan cara-cara untuk menyederhanakan proses.

Artikel ini menjelaskan proyek sederhana menggunakan memoization dengan tabel pencarian untuk menghitung sebelumnya faktorial dan menyimpannya untuk digunakan di masa mendatang.

Banyak algoritme dan proses lain menggunakan nilai-nilai yang berat dan berulang-ulang yang perlu dihitung, seringkali dengan cara yang mahal dalam hal memori dan / atau waktu. Oleh karena itu, masuk akal untuk mengembangkan semacam mekanisme di mana nilai-nilai yang akan atau kemungkinan besar dibutuhkan sering kali dihitung hanya sekali.

Penggunaan faktorial dalam menghitung fungsi trigonometri di atas adalah salah satu contohnya. Dalam artikel mendatang, saya akan memperluas prinsip untuk menghitung dan menyimpan sinus dan cosinus itu sendiri, tetapi tentu saja ada banyak contoh umum lainnya.

Saat mempertimbangkan faktorial, garis besar memoisasi menggunakan tabel pencarian sederhana dan jelas: cukup gunakan daftar bilangan bulat yang indeks tertingginya adalah bilangan tertinggi yang kita inginkan faktorialnya. Oleh karena itu, faktorial dari bilangan tertentu ditetapkan dan diambil menggunakan nomor tersebut sebagai indeks larik.

What Are We Going to Code?

Proyek ini terdiri dari kelas kecil yang menerapkan memoisasi faktorial hingga jumlah maksimum yang ditentukan. Faktorial dihitung __init__dan disimpan dalam daftar. Ada juga metode untuk mendapatkan faktorial individu.

Proyek ini terdiri dari file-file berikut:

• factorialsmemoization.py
• main.py

Mari kita lihat factorialsmemoization.py terlebih dahulu.

The __init__Metode mengambil sebagai argumen jumlah maksimum untuk factorials menghitung dari. Kami kemudian membuat daftar kosong, menyimpan maksimum self.memoized_to, dan menginisialisasi variabel yang dipanggil prevke 1; tujuannya akan menjadi jelas dalam sekejap.

Kami kemudian menambahkan faktorial 0 yang merupakan 1 ke daftar sebelum memasuki perulangan untuk menghitung sisanya. Perhatikan bahwa perulangan ini dimulai dari 1 karena kita telah menetapkan 0. Di dalam perulangan kita mengatur faktorial berikutnya ke sebelumnya dikalikan dengan angka saat ini, maka setel prevke 1 untuk memulai. Kami kemudian menyetel prevke faktorial saat ini.

Akhirnya kita memiliki getmetode yang memeriksa apakah faktorial yang diminta berada di luar rentang, memunculkan pengecualian jika demikian. Jika nvalid, ia mengembalikan nilai yang relevan dari daftar.

Bahwa ini factorialmemoization.py selesai sehingga kita bisa melanjutkan ke main.py .

Setelah mengimpor modul yang dibuat di atas, kita memasuki mainfungsi yang pertama kali membuat turunan FactorialMemoizationkelas dengan nset ke 8. Kami kemudian memasukkan loop untuk mencetak faktorial 0 hingga 10 - Saya sengaja membanjiri rentang untuk menunjukkan penanganan pengecualian.

Jalankan program dengan yang berikut di Terminal…

python3.8 main.py

… Yang akan memberikan hasil sebagai berikut.

Seperti yang Anda lihat, kami mendapatkan faktorial yang benar hingga 8 tetapi kemudian mendapatkan pengecualian dengan 9 yang berada di luar rentang yang dihitung.