Apakah ada paradigma untuk menyusun fungsi “pembaruan tambahan” dalam gaya aliran data murni?

Saya tidak tahu terminologi yang benar untuk mengajukan pertanyaan ini, jadi saya akan menggambarkannya dengan banyak kata, bersabarlah.

Latar belakang , jadi kita ada di halaman yang sama: Program sering mengandung cache - waktu / memori tradeoff. Kesalahan programmer yang umum adalah lupa memperbarui nilai yang di-cache setelah mengubah salah satu sumber / preseden hulu. Tetapi paradigma dataflow atau pemrograman FRP kebal terhadap kesalahan tersebut. Jika kita memiliki sejumlah fungsi murni, dan menghubungkannya bersama-sama dalam grafik dependensi terarah, maka node dapat memiliki nilai output di-cache dan digunakan kembali sampai salah satu input fungsi berubah. Arsitektur sistem ini dijelaskan dalam makalah Caching Di Lingkungan Berbasis Dataflow dan dalam bahasa imperatif lebih atau kurang analog dengan memoisasi.

Masalah : Ketika salah satu input ke fungsi berubah, kita masih harus menjalankan fungsi secara keseluruhan, membuang output yang di-cache dan menghitung ulang dari awal. Dalam banyak kasus, ini sepertinya sia-sia bagi saya. Pertimbangkan contoh sederhana yang menghasilkan daftar "5 teratas apa pun". Data input adalah daftar apa pun yang tidak disortir. Ini dilewatkan sebagai input ke fungsi yang menampilkan daftar yang diurutkan. Yang pada gilirannya adalah input ke fungsi yang mengambil 5 item pertama saja. Dalam pseudocode:

input = [5, 20, 7, 2, 4, 9, 6, 13, 1, 45]
intermediate = sort(input)
final_output = substring(intermediate, 0, 5)

Kompleksitas fungsi sortir adalah O (N log N). Tetapi perhatikan bahwa aliran ini digunakan dalam aplikasi di mana input hanya berubah sedikit demi sedikit, dengan menambahkan 1 elemen. Daripada menyortir ulang dari awal setiap kali, akan lebih cepat, bahkan O (N), untuk menggunakan fungsi yang memperbarui daftar diurutkan dalam cache lama dengan memasukkan elemen baru di posisi yang benar. Ini hanya satu contoh - banyak fungsi "dari awal" memiliki mitra "pembaruan tambahan" seperti itu. Juga, mungkin elemen yang baru ditambahkan bahkan tidak akan muncul di final_output karena setelah posisi ke-5.

Intuisi saya menyarankan untuk menambahkan fungsi "incremental update" seperti apa saja ke sistem aliran data, berdampingan dengan fungsi "dari awal" yang ada. Tentu saja, menghitung ulang semuanya dari awal harus selalu memberikan hasil yang sama dengan sekelompok pembaruan bertahap. Sistem harus memiliki sifat bahwa jika masing-masing pasangan FromScratch-Incremental primitif individu selalu memberikan hasil yang sama, maka fungsi komposit yang lebih besar yang dibangun dari mereka juga harus secara otomatis memberikan hasil yang sama.

Pertanyaan : Apakah mungkin untuk memiliki sistem / arsitektur / paradigma / meta-algoritma yang dapat mendukung fungsi FromScratch dan rekan-rekan tambahan mereka, bekerja sama untuk efisiensi, dan disusun menjadi aliran besar? Jika tidak, mengapa? Jika seseorang telah meneliti paradigma ini dan menerbitkannya, apa sebutannya, dan bisakah saya mendapatkan ringkasan singkat tentang cara kerjanya?

Bidang ini telah ditemukan berulang kali, dan menggunakan banyak nama, seperti:

• Algoritma online .
• Algoritma streaming, streaming kueri, kueri berkelanjutan.
• Struktur data dinamis.
• Perhitungan penyesuaian diri (sesuai Andrej).

(Dan mungkin lebih.) Itu tidak sama, tetapi terkait.

Mengutip Cai et al (1): Ada dua cara inti untuk mengimplementasikan algoritma online secara umum (yaitu tanpa referensi ke masalah algoritmik tertentu):

• Incrementalisation statis. Pendekatan statis menganalisis suatu program pada waktu kompilasi dan menghasilkan versi tambahan yang secara efisien memperbarui output dari program asli sesuai dengan perubahan input. Pendekatan statis memiliki potensi untuk menjadi lebih efisien daripada pendekatan dinamis, karena tidak diperlukan pembukuan saat runtime. Juga, versi inkremental yang dikomputasi seringkali dapat dioptimalkan menggunakan teknik kompiler standar seperti pelipatan konstan atau inlining. Ini adalah pendekatan yang diselidiki dalam (1).

• Inkrementalisasi dinamis. Pendekatan dinamis membuat grafik dependensi dinamis saat program berjalan dan menyebarkan perubahan di sepanjang grafik ini. Pendekatan yang paling banyak diketahui adalah perhitungan penyesuaian diri Acar. Gagasan utamanya sederhana: program dijalankan pada input asli dalam lingkungan runtime yang disempurnakan yang melacak ketergantungan antara nilai-nilai dalam grafik ketergantungan dinamis; hasil antara di-cache. (Seperti yang Anda bayangkan, ini cenderung menggunakan banyak memori, dan banyak penelitian dalam bidang ini adalah tentang cara membatasi penggunaan memori.) Kemudian, perubahan pada propagasi input melalui grafik dependensi dari input yang diubah ke hasil, memperbarui perantara dan hasil akhir; pemrosesan ini seringkali lebih efisien daripada perhitungan ulang. Namun, membuat grafik ketergantungan dinamis membebankan overhead faktor konstan yang besar selama runtime, mulai dari 2 hingga 30 dalam percobaan yang dilaporkan.

Selain itu, seseorang selalu dapat mencoba dan muncul 'dengan tangan' dengan versi online dari algoritma yang diberikan. Ini bisa sulit.

^{(1) Y. Cai, PG Giarrusso, T. Rendel, K. Ostermann, Teori Perubahan untuk Bahasa Tingkat Tinggi: Menambah λ-Calculi dengan Diferensiasi Statis .}

Anda mungkin mencari pemrograman adaptif . Lihat juga tesis PhD Umut Acar . Saya tidak up-to-date dengan bidang pekerjaan ini tetapi harus membantu Anda, Anda dapat mengejar referensi.