Kapan menggunakan DAG (Directed Acyclic Graph) dalam pemrograman?

Saya baru-baru ini menemukan kerangka kerja yang disebut ecto .

Dalam kerangka kerja ini, komponen dasar bernama "plasm" , yang merupakan ecto Directed Acyclic Graph. Dalam ecto, plasm dapat dioperasikan oleh ecto scheduler.

Saya bertanya-tanya apa keuntungan dari mekanisme ini, dan dalam situasi apa lagi kita dapat mengeksploitasi konsep DAG?

Pertanyaan yang bagus

• Kode dapat diwakili oleh DAG yang menggambarkan input dan output dari masing-masing operasi aritmatika yang dilakukan dalam kode; representasi ini memungkinkan kompiler untuk melakukan eliminasi subekspresi umum secara efisien.
• Sebagian besar Sistem Manajemen Kontrol Sumber menerapkan revisi sebagai DAG.
• Beberapa bahasa Pemrograman menjelaskan sistem nilai yang terkait satu sama lain oleh grafik asiklik terarah. Ketika satu nilai berubah, penggantinya dihitung ulang; setiap nilai dievaluasi sebagai fungsi pendahulunya dalam DAG.
• DAG berguna dalam mendeteksi kebuntuan karena mereka menggambarkan ketergantungan antara serangkaian proses dan sumber daya.
• Dalam banyak algoritma acak dalam geometri komputasi, algoritma mempertahankan DAG sejarah yang mewakili fitur dari beberapa konstruksi geometrik yang telah digantikan oleh fitur skala selanjutnya; kueri lokasi titik dapat dijawab, seperti untuk dua struktur data di atas, dengan mengikuti jalur dalam DAG ini.
• Setelah kami memiliki DAG dalam memori, kami dapat menulis algoritma untuk menghitung waktu eksekusi maksimum dari seluruh rangkaian.
• Saat memprogram sistem spreadsheet, grafik dependensi yang menghubungkan satu sel ke sel lain jika sel pertama menyimpan rumus yang menggunakan nilai dalam sel kedua harus berupa grafik asiklik terarah. Siklus ketergantungan tidak diizinkan karena menyebabkan sel yang terlibat dalam siklus tidak memiliki nilai yang terdefinisi dengan baik. Selain itu, membutuhkan dependensi asiklik memungkinkan urutan topologi digunakan untuk menjadwalkan penghitungan ulang nilai sel ketika spreadsheet diubah.
• Menggunakan DAG kita dapat menulis algoritma untuk mengevaluasi perhitungan dalam urutan yang benar.

EDIT:

• Pemesanan evaluasi sel rumus saat menghitung ulang nilai rumus dalam spreadsheet dapat dilakukan menggunakan DAG
• Git menggunakan DAG untuk penyimpanan konten, pointer referensi untuk kepala, representasi model objek, dan protokol jarak jauh.
• DAG digunakan pada penjadwalan Jejak: pendekatan praktis pertama untuk penjadwalan global, penjadwalan jejak mencoba untuk mengoptimalkan jalur aliran kontrol yang paling sering dijalankan.
• Ecto adalah kerangka kerja pemrosesan dan menggunakan DAG untuk memodelkan grafik pemrosesan sehingga grafik melakukan eksekusi sinkron. Plasm di Ecto adalah DAG dan Penjadwal beroperasi di atasnya.
• DAG digunakan pada pipelining perangkat lunak, yang merupakan teknik yang digunakan untuk mengoptimalkan loop, dengan cara yang paralel dengan pipelining perangkat keras.

Sumber Daya yang Baik:

• http://www.biomedcentral.com/1471-2288/8/70
• http://www.ncbi.nlm.nih.gov/pubmed/12453109
• http://www.ericsink.com/vcbe/html/directed_acyclic_graphs.html
• http://xlinux.nist.gov/dads/HTML/directAcycGraph.html

Jawabannya adalah tidak ada hubungannya dengan pemrograman. Ini ada hubungannya dengan pemecahan masalah.

Sama seperti linked-list adalah struktur data yang digunakan untuk kelas masalah tertentu, grafik berguna untuk mewakili hubungan tertentu. Daftar yang ditautkan, pohon, grafik, dan struktur abstrak lainnya hanya memiliki koneksi ke pemrograman karena Anda dapat mengimplementasikannya dalam kode. Mereka ada di tingkat abstraksi yang lebih tinggi. Ini bukan tentang pemrograman, ini tentang menerapkan struktur data dalam solusi masalah.

Jika Anda masih menginginkan hubungan dengan pemrograman, harap pertimbangkan hal-hal berikut:

• DAG (dikenal sebagai Wait-For-Graphs - lebih detail teknis ) berguna dalam mendeteksi kebuntuan karena mereka menggambarkan ketergantungan di antara serangkaian proses dan sumber daya (keduanya adalah node dalam DAG). Kebuntuan akan terjadi ketika sebuah siklus terdeteksi.
• Setelah Anda memiliki DAG dalam memori, Anda dapat menulis algoritme ke:
  • pastikan perhitungan dievaluasi dalam urutan yang benar ( jenis topologi )
  • jika perhitungan dapat dilakukan secara paralel tetapi setiap perhitungan memiliki waktu eksekusi maksimum, Anda dapat menghitung waktu eksekusi maksimum seluruh rangkaian

Orang lain telah menerapkan DAG ke data, tapi saya pikir itu setidaknya berlaku (jika tidak lebih) ke kode. Mahbubur R Aaman menyebutkan ini, jadi sebenarnya ini lebih merupakan tambahan untuk jawabannya daripada jawaban lengkap sendiri.

Itu terjadi kepada saya daripada program komputer penting yang bebas dari loop tak terbatas (terima kasih @AndresF.) Adalah Grafik Acyclic Diarah (DAG). Berarti bahwa kemungkinan jalur eksekusi kode diarahkan (pertama ini, lalu itu), dan asiklik (tidak membentuk loop tak terbatas). Mereka adalah grafik karena jalur melalui kode signifikan jarang jarang sesederhana daftar atau pohon.

Saya bekerja di XSLT selama mungkin 4 tahun. Saya mengalami kesulitan untuk menjelaskan mengapa itu bukan bahasa pemrograman tujuan umum yang baik, tetapi DAG adalah alasannya. Secara khusus, XSLT adalah bahasa yang digerakkan oleh data. Anda mendefinisikan fungsi (ya, dalam arti pemrograman fungsional) tetapi Anda tidak perlu memanggil fungsi-fungsi ini dari kode Anda. Sebaliknya, XSLT mengatur kombinasi pemilihan, dan iterasi melalui, simpul-simpul dari dokumen input XML. Ini memungkinkan struktur data input menentukan fungsi mana yang dipanggil dan dalam urutan apa.

Ini sangat menarik dan sangat keren sampai program Anda menemukan kondisi data yang tidak Anda uji pada pukul 2:30 pagi dan Anda harus bangun dan memperbaikinya. Ketika Anda membiarkan data menentukan DAG, maka definisi DAG menjadi semua kondisi input yang mungkin - yang untuk aplikasi bisnis non-sepele tidak dapat dihitung; mereka tak terbayangkan.

Pada awalnya saya berpikir bahwa pemrograman fungsional mungkin bukan DAG karena urutan eksekusi terkadang tidak jelas, atau bahkan dipikirkan oleh programmer. Tetapi program fungsional mendefinisikan dependensi. Bahkan, sifat deklaratif pemrograman fungsional dapat dianggap sebagai mendefinisikan hanya dependensi (a ^ 2 = b ^ 2 + c ^ 2) tanpa menentukan urutan eksekusi (tidak masalah apakah 'b' atau 'c' dikuadratkan terlebih dahulu , asalkan keduanya dikuadratkan sebelum ditambahkan bersama).

Tetapi sementara pemrograman Fungsional mungkin secara sengaja tidak jelas tentang urutan operasi pada tingkat terperinci, sangat jelas tentang ketergantungan. Ini adalah fitur-fitur yang membuatnya bisa menerima konkurensi. Bagaimanapun, masih ada grafik jalur melalui kode, dan grafik itu masih diarahkan (dependensi harus dievaluasi sebelum tugas tergantung), jadi saya pikir DAG berlaku di sana juga.

Pertanyaan yang bagus - terima kasih telah memposting!

Saat ini DAG diremehkan dalam pemrograman. Secara historis banyak hal yang berkaitan dengan pengembangan dibuat dengan pohon dan hierarki karena memindahkan sesuatu di dalam kotak adalah nyaman bagi otak kita untuk membuat hal-hal rumit lebih mudah untuk dikelola. Tetapi jika Anda melihat acara dan bagaimana mereka bergantung pada acara dan negara lain maka Anda akan mendapatkan DAG karena apa pun dalam hidup kita dan dalam program ini dapat bergantung pada apa pun di masa lalu tetapi tidak di masa depan, sehingga Anda akan mendapatkan "asiklik" yang sempurna hubungan untuk diterapkan pada konsep DAG. Meskipun ini jarang digunakan secara eksplisit dalam pengembangan, mengingat hal ini akan membantu untuk memahami hal-hal yang lebih baik

Saya bertanya-tanya apa manfaat Plasm di Ecto ...

DAG dapat digunakan untuk memodelkan kumpulan tugas secara berurutan dengan batasan bahwa tugas tertentu harus dilakukan sebelum yang lain. Ecto adalah kerangka kerja pemrosesan dan menggunakan DAG untuk memodelkan grafik pemrosesan sehingga grafik melakukan eksekusi sinkron. Plasm di Ecto adalah DAG dan Penjadwal beroperasi di atasnya.

dalam situasi apa lagi kita dapat mengeksploitasi konsep DAG?

• DAWG adalah struktur data yang mewakili satu set string dan memungkinkan untuk operasi kueri yang menguji apakah string yang diberikan milik set dalam waktu sebanding dengan panjangnya.
• Git menggunakan DAG untuk penyimpanan konten, pointer referensi untuk kepala, representasi model objek, dan protokol jarak jauh.

Sebagai contoh dunia nyata, perangkat lunak kami mirip dengan IDE di mana pengguna akhir dapat menentukan serangkaian operasi yang harus dilakukan pada gambar (inspeksi visi mesin). Inspeksi ini dapat memiliki ketergantungan pada inspeksi lain atau mungkin tergantung pada inspeksi tersebut. Karena ini semua dapat dikonfigurasi oleh pengguna akhir, kami tidak dapat membuat optimasi untuk pemrosesan paralel pada waktu desain. Dengan mewakili inspeksi dan dependensi ini sebagai DAG, kami dapat mengoptimalkan paralelisme inspeksi keseluruhan untuk kinerja maksimum pada waktu berjalan.

Sebagai contoh lain, aturan manajemen memori dalam aplikasi Kakao dibuat sehingga semua referensi yang kuat membentuk grafik asiklik terarah, yang dilakukan untuk menjamin tidak adanya kebocoran.

Menambahkan jawaban lain karena belum melihat referensi untuk membangun sistem seperti makeyang menggunakan DAG untuk mengetahui dependensi untuk membangun.

Lebih detail di sini