Pola untuk algoritme yang menampilkan penjelasan tentang bagaimana hal itu sampai ke solusi saat diperlukan

14

Skenario berikut terjadi pada saya beberapa kali.

Saya memprogram algoritma yang memecahkan masalah tertentu. Ini berfungsi dengan baik dan menemukan solusi yang benar. Sekarang, saya ingin memiliki opsi untuk memberi tahu algoritma "tulis penjelasan lengkap tentang bagaimana Anda mendapatkan solusi". Tujuan saya adalah untuk dapat menggunakan algoritma dalam demonstrasi online, kelas tutorial, dll. Saya masih ingin memiliki opsi untuk menjalankan algoritma secara real time, tanpa penjelasan. Apa pola desain yang baik untuk digunakan?

CONTOH: Misalkan saya menerapkan metode ini untuk menemukan pembagi umum terbesar . Metode yang diterapkan saat ini mengembalikan jawaban yang benar, tetapi tanpa penjelasan. Saya ingin memiliki opsi untuk metode untuk menjelaskan tindakannya, seperti:

Initially, a=6 and b=4. The number of 2-factors, d, is initialized to 0.
a and b are both even, so we divide them by 2 and increment d by 1.
Now, a=3 and b=2.
a is odd but b is even, so we divide b by 2.
Now, a=3 and b=1.
a and b are both odd, so we replace a by (a-b)/2 = 1.
Now, a=1 and b=1.
a=b, so the GCD is a*2^d = 2.

Output harus dikembalikan sehingga dapat dengan mudah ditampilkan baik di konsol maupun di aplikasi berbasis web.

Apa pola yang baik untuk memberikan penjelasan saat dibutuhkan, sementara tidak mengganggu kinerja algoritma waktu nyata ketika penjelasan tidak diperlukan?

design-patterns algorithms Erel Segal-Halevi
sumber

Jawaban:

50

"Pola" yang Anda cari disebut "logging", cukup buat pernyataan logging sama jelasnya dengan yang Anda butuhkan. Dengan menggunakan kerangka logging yang layak Anda harus dapat menghidupkan dan mematikannya pada waktu berjalan, memberikan tingkat verbositas yang berbeda, atau menyesuaikan output untuk tujuan yang berbeda (seperti web vs konsol).

Jika ini memiliki dampak kinerja yang nyata (bahkan jika logging dimatikan) mungkin akan tergantung pada bahasa, kerangka kerja dan jumlah pernyataan logging yang Anda butuhkan dalam kasus tertentu. Dalam bahasa yang dikompilasi, jika ini benar-benar menjadi masalah, Anda bisa memberikan sakelar kompiler untuk membuat "varian logging" dan "varian non-logging" dari kode Anda. Namun, saya sangat merekomendasikan untuk tidak mengoptimalkan "berjaga-jaga", tanpa mengukur terlebih dahulu.

Doc Brown
sumber
2
Meskipun mereka bukan sesuatu yang Anda nyalakan dan matikan seperti pencatatan, rasanya seperti komentar dan kode yang mendokumentasikan sendiri setidaknya harus mendapatkan penyebutan terhormat dalam pertanyaan tentang "algoritma yang menjelaskan sendiri".
candied_orange
9
@CandiedOrange pertanyaan khusus meminta "penjelasan" dengan nilai run-time nyata yang disertakan di dalamnya. Komentar tidak akan banyak membantu dalam kasus itu.
dimakamkan
@metacubed oh ayolah. Saya tidak mengatakan itu adalah alternatif untuk penebangan. Lihatlah judul pertanyaan dan pikirkan tentang lalu lintas yang datang ke sini.
candied_orange
4
@CandiedOrange: Saya pikir judul pertanyaan itu menyesatkan, Anda benar itu bisa ditafsirkan seperti itu, tetapi bukan itu yang diminta OP. Tapi saya biarkan saya memperbaiki itu, saya akan mengedit judulnya.
Doc Brown
1
Perhatikan bahwa sesuatu seperti treelog dirancang khusus untuk menghasilkan output yang menjelaskan perhitungan kompleks dengan menghasilkan catatan lengkap panggilan fungsi.
Boris the Spider
7

Pola yang baik adalah Pengamat. https://en.wikipedia.org/wiki/Observer_pattern

Dalam algoritme Anda, pada setiap titik di mana Anda ingin menampilkan sesuatu, Anda memberi tahu beberapa pengamat. Mereka kemudian memutuskan apa yang harus dilakukan, apakah akan menampilkan teks Anda di konsol, atau mengirimkannya ke mesin HTML / Apache dll.

Tergantung pada bahasa pemrograman Anda, mungkin ada berbagai cara untuk membuatnya cepat. Misalnya, di Jawa (perlakukan sebagai pseudocode, untuk singkatnya; menjadikannya "benar", dengan getter, setter, diserahkan kepada pembaca):

interface AlgoLogObserver {
   public void observe(String message);
}

class AlgorithmXyz {   
   AlgoLogObserver observer = null;
   void runCalculation() {   
       if (observer!=null) { oberserver.observe("Hello"); }
       ...
   }   
}

...
algo = new AlgorithmXyz();
algo.observer = new ConsoleLoggingObserver();  // yes, yes make a 
                                               // setter instead, or use Ruby :-)
algo.runCalculation();

Ini sedikit bertele-tele, tetapi periksa untuk ==null harus secepat mungkin.

(Perhatikan bahwa dalam kasus umum, observermungkin akan menjadiVector observers lebih untuk memungkinkan lebih dari satu pengamat; ini tentu saja mungkin juga dan tidak akan menyebabkan lebih banyak overhead; Anda masih dapat memasukkan optimasi yang Anda tetapkan observers=nullalih-alih memiliki kosongVector .)

Tentu saja, Anda akan menerapkan berbagai jenis pengamat tergantung pada apa yang ingin Anda capai. Anda juga dapat memasukkan statistik waktu dll. Di sana, atau melakukan hal-hal mewah lainnya.

AnoE
sumber
5

Sebagai sedikit perbaikan untuk pembuatan log langsung, buat semacam objek yang memodelkan satu eksekusi algoritma. Tambahkan "langkah" ke objek wadah ini setiap kali kode Anda melakukan sesuatu yang menarik. Di akhir algoritma, catat langkah-langkah yang terakumulasi dari wadah.

Ini memiliki beberapa keunggulan:

  1. Anda dapat mencatat eksekusi penuh sebagai satu entri log, sering kali berguna ketika ada kemungkinan utas lain mencatat hal-hal di antara langkah-langkah algo Anda
  2. Dalam versi Java saya dari kelas ini (disebut hanya "Debug"), saya tidak menambahkan string sebagai entri log, tetapi lambda yang menghasilkan string. Lambda ini hanya dievaluasi JIKA penebangan aktual akan terjadi, yaitu jika objek Debug menemukan bahwa level log-nya saat ini diaktifkan. Dengan cara ini, tidak ada overhead kinerja membangun string log yang tidak perlu.

EDIT: Seperti dikomentari oleh orang lain, lambdas memiliki overhead, jadi Anda harus melakukan benchmark untuk memastikan overhead ini kurang dari evaluasi kode yang tidak diperlukan untuk membangun string log (entri log seringkali bukan literal sederhana, tetapi melibatkan mendapatkan informasi kontekstual dari objek yang berpartisipasi).

Cornel Masson
sumber
2
Ada, tentu saja, overhead menciptakan lambdas ...
Sergio Tulentsev
1
Sergio menjelaskan, tetapi tidak sepenuhnya menjelaskan kebodohan logika Anda. Kinerja overhead membangun string log adalah urutan besarnya lebih rendah daripada kinerja overhead membangun lambda. Anda telah membuat tradeoff yang sangat buruk di sini
Kyeotic
2
@ Tirus: Apakah Anda memiliki tolok ukur yang dapat diandalkan membuktikan hal itu? (Patokan yang Anda tautkan sangat cacat, cf stackoverflow.com/questions/504103/… )
meriton
1
@ Tirus semuanya tergantung pada situasi tertentu. Saya juga bisa memberi Anda, contoh yang dapat diperdebatkan, lebih relevan . Anda dapat melihat bahwa versi String adalah urutan besarnya lebih lambat daripada Runnable. Kasus ini lebih realistis, karena dalam konteks pertanyaan ini Anda akan selalu ingin membangun string Anda secara dinamis. Ini selalu mengharuskan penciptaan objek Stringbuilder, sementara dengan Lambda mereka hanya akan dibuat saat diperlukan (yaitu ketika logging aktif).
jhyot
1
Lambdas memiliki overhead, setuju. Namun, patokan yang dipasang sama sekali tidak relevan dalam konteks ini. Logging algoritma sering melibatkan evaluasi kode lain yang tidak akan dievaluasi seandainya logging dilewati (mengambil informasi kontekstual dari objek yang berpartisipasi, dll.). Evaluasi inilah yang dihindarkan lambda. Tapi Anda benar, jawaban saya di atas memang menganggap bahwa overhead lambda kurang dari overhead ini , sesuatu yang belum saya uji secara konsisten.
Cornel Masson
0

Saya biasanya mencari percabangan, artinya saya mencari jika-pernyataan. Karena ini menunjukkan bahwa saya mengevaluasi nilai, yang akan mengontrol aliran algoritma. Dalam setiap kejadian seperti itu (setiap kondisi) saya kemudian dapat mencatat jalur yang dipilih, dan mengapa itu dipilih.

Jadi pada dasarnya saya akan mencatat nilai entri (keadaan awal), setiap cabang yang dipilih (kondisional) dan nilai-nilai saat memasukkan cabang yang dipilih (keadaan temp).

Richard Tyregrim
sumber
1
ini bahkan tidak berusaha menjawab pertanyaan yang diajukan, tentang tidak melukai kinerja algoritma waktu nyata ketika penjelasan tidak diperlukan
nyamuk
Saya menganggap pertanyaan itu lebih umum dari itu dan saya menjawabnya pada tingkat desain. Tetapi jika itu adalah masalah, tambahkan ke tanda bersyarat bendera untuk mengatur apakah Anda ingin mencetak untuk login atau tidak. Tetapkan bendera ini sebagai parameter saat meluncurkan.
Richard Tyregrim