Apa manfaat dan kelemahan yang melekat pada penggunaan kelas untuk merangkum algoritma numerik?

13

Banyak algoritma yang digunakan dalam komputasi ilmiah memiliki struktur inheren yang berbeda dari algoritma yang umumnya dianggap dalam bentuk rekayasa perangkat lunak yang kurang intensif matematika. Secara khusus, algoritma matematika individu cenderung sangat kompleks, sering melibatkan ratusan atau ribuan baris kode, namun demikian tidak melibatkan keadaan (yaitu tidak bertindak pada struktur data yang kompleks) dan sering dapat dididihkan - dalam hal programatis interface - ke satu fungsi yang bekerja pada array (atau dua).

Ini menunjukkan bahwa suatu fungsi, dan bukan kelas, adalah antarmuka alami untuk sebagian besar algoritma yang ditemukan dalam komputasi ilmiah. Namun argumen ini menawarkan sedikit wawasan tentang bagaimana implementasi algoritma multi-bagian yang kompleks harus ditangani.

Sementara pendekatan tradisional adalah hanya memiliki satu fungsi yang memanggil sejumlah fungsi lainnya, melewati argumen yang relevan di sepanjang jalan, OOP menawarkan pendekatan yang berbeda, di mana algoritma dapat diringkas sebagai kelas. Untuk kejelasan, dengan merangkum suatu algoritma dalam suatu kelas, maksud saya membuat kelas di mana input algoritma dimasukkan ke dalam konstruktor kelas, dan kemudian metode publik dipanggil untuk benar-benar memanggil algoritma. Implementasi multigrid seperti itu di C ++ psuedocode mungkin terlihat seperti:

class multigrid {
    private:
        x_, b_
        [grid structure]

        restrict(...)
        interpolate(...)
        relax(...)
    public:
        multigrid(x,b) : x_(x), b_(b) { }
        run()
}

multigrid::run() {
     [call restrict, interpolate, relax, etc.]
}

Pertanyaan saya kemudian adalah sebagai berikut: apa manfaat dan kelemahan dari praktik semacam ini dibandingkan dengan pendekatan yang lebih tradisional tanpa kelas? Apakah ada masalah perpanjangan atau perawatan? Untuk lebih jelasnya, saya tidak bermaksud untuk meminta pendapat, tetapi lebih untuk memahami efek hilir (yaitu yang mungkin tidak muncul sampai basis kode menjadi cukup besar) untuk mengadopsi praktik pengkodean semacam itu.

Ben
sumber
2
Itu selalu pertanda buruk ketika nama kelas Anda adalah kata sifat dan bukan kata benda.
David Ketcheson
3
Kelas bisa berfungsi sebagai namespace stateless untuk mengatur fungsi untuk mengelola kompleksitas, tetapi ada cara lain untuk mengelola kompleksitas dalam bahasa yang menyediakan kelas. (Namespace dalam C ++ dan modul dalam Python datang ke pikiran.)
Geoff Oxberry
@ GeoffOxberry Saya tidak dapat berbicara apakah ini adalah penggunaan yang baik atau buruk - itulah sebabnya saya bertanya pada awalnya - tetapi kelas, tidak seperti ruang nama atau modul, juga dapat mengelola "keadaan sementara", misalnya hierarki kisi dalam multigrid, yang dibuang setelah penyelesaian algoritma.
Ben

Jawaban:

13

Setelah melakukan perangkat lunak numerik selama 15 tahun, saya dapat dengan jelas menyatakan sebagai berikut:

  • Enkapsulasi itu penting. Anda tidak ingin membagikan pointer ke data (seperti yang Anda sarankan) karena mengekspos skema penyimpanan data. Jika Anda mengekspos skema penyimpanan, Anda tidak akan pernah bisa mengubahnya lagi karena Anda akan mengakses data di seluruh program. Satu-satunya cara untuk menghindari hal ini adalah dengan merangkum data ke dalam variabel anggota pribadi kelas dan membiarkan hanya fungsi anggota yang bertindak di dalamnya. Jika saya membaca pertanyaan Anda, Anda berpikir tentang fungsi yang menghitung nilai eigen dari sebuah matriks sebagai stateless, mengambil pointer ke entri matriks sebagai argumen dan mengembalikan nilai eigen dengan cara tertentu. Saya pikir ini adalah cara yang salah untuk memikirkannya. Dalam pandangan saya, fungsi ini harus menjadi fungsi anggota "const" dari suatu kelas - bukan karena ia mengubah matriks, tetapi karena ia adalah yang beroperasi dengan data.

  • Sebagian besar bahasa pemrograman OO memungkinkan Anda memiliki fungsi anggota pribadi. Ini adalah cara Anda untuk memecah satu algoritma besar menjadi lebih kecil. Sebagai contoh, berbagai fungsi pembantu yang Anda butuhkan untuk perhitungan nilai eigen masih beroperasi pada matriks, dan dengan demikian akan secara alami menjadi fungsi anggota pribadi dari kelas matriks.

  • Dibandingkan dengan banyak sistem perangkat lunak lain, mungkin benar bahwa hierarki kelas sering kurang penting daripada, katakanlah, dalam antarmuka pengguna grafis. Tentu saja ada tempat-tempat dalam perangkat lunak numerik di mana mereka menonjol - Jed menguraikan satu dalam jawaban lain untuk utas ini, yaitu banyak cara seseorang dapat mewakili matriks (atau, lebih umum, operator linear pada ruang vektor dimensi terbatas). PETSc melakukan ini dengan sangat konsisten, dengan fungsi-fungsi virtual untuk semua operasi yang bekerja pada matriks (mereka tidak menyebutnya "fungsi virtual", tapi memang begitu). Ada area lain dalam kode elemen hingga tipikal di mana seseorang menggunakan prinsip desain perangkat lunak OO ini. Yang muncul di pikiran adalah banyak jenis rumus quadrature dan banyak jenis elemen hingga, yang semuanya secara alami direpresentasikan sebagai satu antarmuka / banyak implementasi. Deskripsi hukum materi juga akan termasuk dalam kelompok ini. Tapi itu mungkin benar bahwa itu tentang hal itu dan bahwa sisa kode elemen hingga tidak menggunakan warisan sebanyak yang dapat digunakan, misalnya, dalam GUI.

Dari hanya tiga poin ini, harus jelas bahwa pemrograman berorientasi objek paling pasti berlaku untuk kode numerik juga, dan itu akan bodoh untuk mengabaikan banyak manfaat dari gaya ini. Mungkin benar bahwa BLAS / LAPACK tidak menggunakan paradigma ini (dan bahwa antarmuka yang biasa diekspos oleh MATLAB juga tidak) tetapi saya berani menebak bahwa setiap perangkat lunak numerik yang berhasil ditulis dalam 10 tahun terakhir, pada kenyataannya, Berorientasi pada objek.

Wolfgang Bangerth
sumber
16

Enkapsulasi dan penyembunyian data sangat penting bagi perpustakaan yang dapat diperluas dalam komputasi ilmiah. Pertimbangkan matriks dan pemecah linier sebagai dua contoh. Seorang pengguna hanya perlu tahu bahwa seorang operator adalah linier, tetapi mungkin memiliki struktur internal seperti sparsity, kernel, representasi hirarkis, produk tensor, atau komplemen Schur. Dalam semua kasus, metode Krylov tidak tergantung pada rincian operator, mereka hanya bergantung pada tindakanMatMult fungsi (dan mungkin adjoin). Demikian pula, pengguna antarmuka pemecah linear (mis. Pemecah nonlinier) hanya peduli bahwa masalah linier dipecahkan, dan seharusnya tidak perlu atau ingin menentukan algoritma yang digunakan. Memang, menentukan hal-hal seperti itu akan menghambat kemampuan pemecah nonlinier (atau antarmuka luar lainnya).

Antarmuka bagus. Tergantung pada implementasi yang buruk. Apakah Anda mencapai ini menggunakan kelas C ++, objek C, kacamata types Haskell, atau fitur bahasa lainnya tidak penting. Kemampuan, kekokohan, dan ekstensibilitas antarmuka adalah hal yang penting dalam perpustakaan ilmiah.

Jed Brown
sumber
8

Kelas harus digunakan hanya jika struktur kodenya hirarkis. Karena Anda menyebutkan Algoritma, struktur alami mereka adalah bagan alur, bukan hierarki objek.

Dalam kasus OpenFOAM, bagian algoritmik diimplementasikan dalam istilah operator generik (div, grad, curl, dll.) Yang pada dasarnya adalah fungsi abstrak yang beroperasi pada berbagai jenis tensor, menggunakan berbagai jenis skema numerik. Bagian kode ini pada dasarnya dibangun dari banyak algoritma generik yang beroperasi di kelas. Ini memungkinkan klien untuk menulis sesuatu seperti:

solve(ddt(U) + div(phi, U)  == rho*g + ...);

Hierarki seperti model transportasi, model turbulensi, skema diferensiasi, skema gradien, kondisi batas, dll diimplementasikan dalam hal kelas C ++ (sekali lagi, generik pada jumlah tensor).

Saya telah memperhatikan struktur yang sama di perpustakaan CGAL, di mana berbagai algoritma dikemas bersama sebagai kelompok objek fungsi yang dibundel dengan informasi geometri untuk membentuk Kernel Geometris (kelas), tetapi ini sekali lagi dilakukan untuk memisahkan operasi dari geometri (penghapusan titik dari wajah, dari tipe data titik).

Struktur hierarki ==> kelas

Prosedural, diagram alur ==> algoritma

tmaric
sumber
5

Sekalipun ini adalah pertanyaan lama, saya pikir patut disebutkan solusi khusus Julia . Apa yang dilakukan bahasa ini adalah "OOP tanpa kelas": konstruksi utama adalah tipe, yaitu objek data komposit yang mirip dengan structs di C, di mana relasi pewarisan didefinisikan. Tipe tidak memiliki "fungsi anggota", tetapi masing-masing fungsi memiliki tipe tanda tangan dan menerima subtipe. Misalnya, Anda bisa memiliki abstrak Matrixjenis dan subtipe DenseMatrix, SparseMatrixdan memiliki metode generik do_something(a::Matrix, b::Matrix)dengan spesialisasi do_something(a::SparseMatrix, b::SparseMatrix). Pengiriman ganda digunakan untuk memilih versi yang paling tepat untuk dipanggil.

Pendekatan ini lebih kuat daripada OOP berbasis kelas, yang setara pada pengiriman berdasarkan warisan pada argumen pertama saja, jika Anda mengadopsi konvensi bahwa "metode adalah fungsi dengan thissebagai parameter pertama" (umum misalnya dalam Python). Beberapa bentuk pengiriman ganda dapat ditiru dalam, katakanlah, C ++, tetapi dengan contortions yang besar .

Perbedaan utama adalah bahwa metode bukan milik kelas, tetapi mereka ada sebagai entitas yang terpisah dan pewarisan dapat terjadi pada semua parameter.

Beberapa referensi:

http://docs.julialang.org/en/release-0.4/manual/methods/

http://assoc.tumblr.com/post/71454527084/cool-things-you-can-do-in-julia

https://thenewphalls.wordpress.com/2014/03/06/understanding-object-oriented-programming-in-julia-inheritance-part-2/

Federico Poloni
sumber
1

Dua keuntungan dari pendekatan OO adalah:

  • βαcalculate_alpha()αcalculate_beta()calculate_alpha()α

  • calculate_f()f(x,y,z). Jika Anda kemudian memutuskan untuk mengulang perhitungan untuk nilai lain dariz, Anda dapat memanggil set_z()danzparameter ditandai secara internal sebagai 'kotor', sehingga ketika Anda menelepon calculate_f()lagi, hanya bagian dari perhitungan yang tergantungz redone.

ptomato
sumber