Apakah ada tujuan khusus untuk daftar heterogen?

13

Berasal dari latar belakang C # dan Java, saya terbiasa dengan daftar saya yang homogen, dan itu masuk akal bagi saya. Ketika saya mulai mengambil Lisp, saya perhatikan bahwa daftar itu bisa heterogen. Ketika saya mulai mencari-cari dengan dynamickata kunci dalam C #, saya perhatikan bahwa, pada C # 4.0, ada juga daftar yang heterogen:

List<dynamic> heterogeneousList

Pertanyaan saya, apa gunanya? Sepertinya daftar yang heterogen akan memiliki lebih banyak overhead saat melakukan pemrosesan dan bahwa jika Anda perlu menyimpan berbagai jenis di satu tempat Anda mungkin memerlukan struktur data yang berbeda. Apakah kenaifan saya merawat wajahnya yang jelek atau apakah benar-benar ada saatnya berguna untuk memiliki daftar yang heterogen?

Jetti
sumber
1
Apakah maksud Anda ... Saya perhatikan bahwa daftar itu bisa heterogen ...?
Insinyur Dunia
Bagaimana List<dynamic>perbedaan (untuk pertanyaan Anda) dari sekadar melakukan List<object>?
Peter K.
@ WorldEngineer ya, saya lakukan. Saya telah memperbarui posting saya. Terima kasih!
Jetti
@PeterK. Saya kira untuk penggunaan sehari-hari, tidak ada perbedaan. Namun, tidak semua jenis dalam C # berasal dari System.Object sehingga akan ada kasus tepi di mana ada perbedaan.
Jetti

Jawaban:

16

Makalah Sangat Diketik Koleksi Heterogen oleh Oleg Kiselyov, Ralf Lämmel, dan Keean Schupke tidak hanya berisi implementasi daftar heterogen di Haskell, tetapi juga contoh memotivasi kapan, mengapa dan bagaimana Anda akan menggunakan HLists. Secara khusus, mereka menggunakannya untuk akses basis data yang diperiksa jenis kompilasi-waktu aman. (Pikirkan LINQ, pada kenyataannya, kertas yang mereka rujuk adalah kertas Haskell oleh Erik Meijer et al yang mengarah ke LINQ.)

Mengutip dari paragraf pengantar dari makalah HLists:

Berikut adalah daftar contoh umum terbuka yang membutuhkan koleksi heterogen:

  • Tabel simbol yang seharusnya menyimpan entri dari berbagai jenis berbeda-beda. Ini adalah peta hingga, di mana tipe hasil tergantung pada nilai argumen.
  • Elemen XML diketik secara heterogen. Faktanya, elemen XML adalah kumpulan bersarang yang dibatasi oleh ekspresi reguler dan properti 1-ambiguitas.
  • Setiap baris yang dikembalikan oleh kueri SQL adalah peta heterogen dari nama kolom ke sel. Hasil kueri adalah aliran homogen baris heterogen.
  • Menambahkan sistem objek canggih ke bahasa fungsional membutuhkan koleksi heterogen dari jenis yang menggabungkan catatan extensible dengan subtyping dan antarmuka enumerasi.

Perhatikan bahwa contoh yang Anda berikan dalam pertanyaan Anda benar-benar bukan daftar yang heterogen dalam arti bahwa kata tersebut umum digunakan. Mereka lemah diketik atau untyped daftar. Faktanya, mereka sebenarnya adalah daftar yang homogen , karena semua elemen memiliki tipe yang sama: objectatau dynamic. Anda kemudian dipaksa untuk melakukan gips atau instanceoftes yang tidak dicentang atau sesuatu seperti itu, agar benar-benar dapat bekerja secara bermakna dengan elemen-elemen, yang membuat mereka diketik dengan lemah.

Jörg W Mittag
sumber
Terima kasih atas tautan dan tanggapan Anda. Anda membuat poin yang baik bahwa daftar tersebut benar-benar tidak heterogen tetapi diketik dengan lemah. Saya tak sabar untuk membaca makalah itu (mungkin besok, mendapat saya tengah semester :))
Jetti
5

Singkatnya, kontainer yang heterogen memperdagangkan kinerja runtime untuk fleksibilitas. Jika Anda ingin memiliki "daftar barang" tanpa memperhatikan jenis barang tertentu, heterogenitas adalah jalan yang harus ditempuh. Lisps secara karakteristik diketik secara dinamis, dan sebagian besar semuanya merupakan daftar nilai kotak, jadi kinerja hit yang lebih kecil diharapkan. Di dunia Lisp, produktivitas programmer dianggap lebih penting daripada kinerja runtime.

Dalam bahasa yang diketik secara dinamis, wadah yang homogen sebenarnya memiliki sedikit overhead dibandingkan dengan yang heterogen, karena semua elemen yang ditambahkan harus diperiksa jenisnya.

Intuisi Anda tentang memilih struktur data yang lebih baik tepat sasaran. Secara umum, semakin banyak kontrak yang dapat Anda tempatkan pada kode Anda, semakin banyak Anda tahu tentang cara kerjanya, dan semakin dapat diandalkan, dipelihara, & c. menjadi. Namun, kadang-kadang Anda benar-benar menginginkan wadah yang heterogen, dan Anda harus diizinkan memilikinya jika Anda membutuhkannya.

Jon Purdy
sumber
1
"Namun, kadang-kadang kamu benar-benar menginginkan wadah yang heterogen, dan kamu seharusnya diizinkan untuk memilikinya jika kamu membutuhkannya." - Kenapa begitu? Itu pertanyaan saya. Mengapa Anda hanya perlu campur aduk sekelompok data ke dalam daftar acak?
Jetti
@ Jetti: Katakanlah Anda memiliki daftar pengaturan berbagai jenis yang dimasukkan oleh pengguna. Anda bisa membuat antarmuka IUserSettingdan mengimplementasikannya beberapa kali lipat, atau membuat generik UserSetting<T>, tetapi salah satu masalah dengan pengetikan statis adalah Anda mendefinisikan antarmuka sebelum Anda tahu persis bagaimana itu akan digunakan. Hal-hal yang Anda lakukan dengan pengaturan integer mungkin sangat berbeda dari hal-hal yang Anda lakukan dengan pengaturan string, jadi operasi apa yang masuk akal untuk dimasukkan ke dalam antarmuka umum? Sampai Anda tahu pasti, lebih baik menggunakan pengetikan dinamis, dan membuatnya konkret nanti.
Jon Purdy
Lihat di situlah saya mengalami masalah. Bagi saya, itu sepertinya desain yang buruk, membuat sesuatu sebelum Anda tahu apa yang akan dilakukan / digunakan. Juga, dalam hal ini Anda bisa membuat Antarmuka dengan nilai pengembalian objek. Melakukan hal yang sama dengan daftar heterogen tetapi lebih jelas dan lebih mudah diperbaiki setelah Anda tahu dengan pasti apa jenis yang digunakan dalam antarmuka.
Jetti
@Jetti: Namun, pada dasarnya itu adalah masalah yang sama — kelas dasar universal seharusnya tidak ada karena, apa pun operasi yang didefinisikannya, akan ada jenis operasi yang tidak masuk akal. Tetapi jika C # membuatnya lebih mudah untuk menggunakan objectdaripada dynamic, maka tentu saja, gunakan yang pertama.
Jon Purdy
1
@ Jetti: Ini tentang polimorfisme. Daftar ini berisi sejumlah objek "heterogen" meskipun mereka mungkin subkelas dari superclass tunggal. Dari sudut pandang Java, Anda bisa mendapatkan definisi kelas (atau antarmuka) dengan benar. Untuk bahasa lain (LISP, Python, dll.) Tidak ada manfaatnya untuk mendapatkan semua deklarasi dengan benar, karena tidak ada perbedaan implementasi praktis.
S.Lott
2

Dalam bahasa fungsional (seperti lisp), Anda menggunakan pencocokan pola untuk menentukan apa yang terjadi pada elemen tertentu dalam daftar. Setara dalam C # akan menjadi rantai if ... else jika pernyataan yang memeriksa jenis elemen dan melakukan operasi berdasarkan itu. Tidak perlu dikatakan, pencocokan pola fungsional lebih efisien daripada pengecekan tipe runtime.

Menggunakan polimorfisme akan lebih cocok dengan pencocokan pola. Artinya, memiliki objek daftar cocok dengan antarmuka tertentu dan memanggil fungsi pada antarmuka itu untuk setiap objek. Alternatif lain adalah menyediakan serangkaian metode kelebihan beban yang menggunakan jenis objek tertentu sebagai parameter. Metode default mengambil Objek sebagai parameternya.

public class ListVisitor
{
  public void DoSomething(IEnumerable<dynamic> list)
  {
    foreach(dynamic obj in list)
    {
       DoSomething(obj);
    }
  }

  public void DoSomething(SomeClass obj)
  {
    //do something with SomeClass
  }

  public void DoSomething(AnotherClass obj)
  {
    //do something with AnotherClass
  }

  public void DoSomething(Object obj)
  {
    //do something with everything els
  }
}

Pendekatan ini memberikan perkiraan untuk pencocokan pola Lisp. Pola pengunjung (seperti yang diterapkan di sini, adalah contoh yang bagus dari penggunaan untuk daftar heterogen). Contoh lain akan untuk pengiriman pesan di mana, ada pendengar untuk pesan tertentu dalam antrian prioritas dan menggunakan rantai tanggung jawab, pengirim melewati pesan dan penangan pertama yang cocok dengan pesan menanganinya.

Sisi lain memberitahu semua orang yang mendaftar untuk pesan (misalnya pola Agregator Acara yang biasa digunakan untuk kopling longgar ViewModels dalam pola MVVM). Saya menggunakan konstruksi berikut

IDictionary<Type, List<Object>>

Satu-satunya cara untuk menambahkan ke kamus adalah fungsi

Register<T>(Action<T> handler)

(dan objek tersebut sebenarnya adalah WeakReference ke yang diteruskan dalam handler). Jadi di sini saya HARUS menggunakan Daftar <Object> karena pada waktu kompilasi, saya tidak tahu apa tipe yang akan ditutup. Namun pada Runtime saya dapat memastikan bahwa itu adalah Jenis yang merupakan kunci untuk kamus. Ketika saya ingin memecat acara yang saya sebut

Send<T>(T message)

dan sekali lagi saya menyelesaikan daftar. Tidak ada keuntungan menggunakan Daftar <dynamic> karena saya harus tetap menggunakannya. Jadi seperti yang Anda lihat ada manfaat untuk kedua pendekatan. Jika Anda akan secara dinamis mengirimkan objek menggunakan Metode overloading, dinamis adalah cara untuk melakukannya. Jika Anda dipaksa untuk membuang apa pun, mungkin juga menggunakan Object.

Michael Brown
sumber
Dengan pencocokan pola, kasing (biasanya - setidaknya dalam ML dan Haskell) disetel oleh deklarasi tipe data yang cocok. Daftar yang mengandung tipe-tipe demikian juga tidak beragam.
Saya tidak yakin tentang ML dan Haskell tetapi Erlang dapat menandingi apa pun yang berarti, jika Anda sampai di sini karena tidak ada pertandingan lain yang terpenuhi, lakukan ini.
Michael Brown
@MikeBrown - Ini bagus tapi tidak mencakup MENGAPA seseorang akan menggunakan daftar heterogen dan tidak akan selalu bekerja dengan List <dynamic>
Jetti
4
Dalam C #, kelebihan beban diselesaikan pada waktu kompilasi . Jadi, kode contoh Anda akan selalu memanggil DoSomething(Object)(setidaknya saat menggunakan objectdalam foreachloop; dynamicadalah hal yang sama sekali berbeda).
Heinzi
@Heinzi, kau benar ... Aku mengantuk hari ini: P diperbaiki
Michael Brown
0

Anda benar bahwa heterogenitas membawa overhead runtime, tetapi yang lebih penting itu melemahkan jaminan waktu kompilasi yang disediakan oleh typechecker. Meski begitu, ada beberapa masalah di mana alternatifnya bahkan lebih mahal.

Dalam pengalaman saya, berurusan dengan byte mentah melalui file, soket jaringan, dll, Anda sering mengalami masalah seperti itu.

Untuk memberikan contoh nyata, pertimbangkan sistem perhitungan terdistribusi menggunakan futures . Seorang pekerja pada sebuah simpul individu dapat menelurkan pekerjaan dari jenis serial apapun, menghasilkan masa depan dari jenis itu. Di belakang layar, sistem mengirimkan pekerjaan ke rekan, dan kemudian menyimpan catatan yang menghubungkan unit kerja itu dengan masa depan tertentu yang harus diisi begitu jawaban untuk pekerjaan itu kembali.

Di mana catatan ini bisa disimpan? Secara intuitif, yang Anda inginkan adalah sesuatu seperti Dictionary<WorkId, Future<TValue>>, tetapi ini membatasi Anda untuk mengelola hanya satu jenis masa depan di seluruh sistem. Jenis yang lebih cocok adalah Dictionary<WorkId, Future<dynamic>>, karena pekerja dapat memilih jenis yang sesuai ketika memaksa masa depan.

Catatan : Contoh ini berasal dari dunia Haskell tempat kami tidak memiliki subtyping. Saya tidak akan terkejut jika ada solusi yang lebih idiomatis untuk contoh khusus ini dalam C #, tapi mudah-mudahan masih ilustratif.

Adam
sumber
0

ISTR yang Lisp tidak memiliki struktur data selain daftar, jadi jika Anda memerlukan segala jenis objek data agregat, itu harus menjadi daftar yang heterogen. Seperti yang telah ditunjukkan orang lain, mereka juga berguna untuk membuat serialisasi data untuk transmisi atau penyimpanan. Salah satu fitur yang bagus adalah bahwa mereka juga bersifat terbuka, sehingga Anda dapat menggunakannya dalam suatu sistem berdasarkan analogi pipa-dan-filter dan memiliki langkah-langkah pemrosesan yang berurutan menambah atau memperbaiki data tanpa memerlukan objek data tetap atau topologi alur kerja .

TMN
sumber