Apakah antarmuka Daftar abstraksi bocor?

9

Jika saya memiliki variabel yang mengandung Listitu dapat berisi objek dari banyak jenis yang berbeda misalnya ArrayListatau LinkedList. Perbedaan antara a LinkedListdan a ArrayListcukup besar. Perilaku O besar metode sangat berbeda. Misalnya menyortir Listdan kemudian menggunakannya untuk melakukan pencarian biner sangat ok untuk ArrayListtetapi tidak masuk akal dengan a LinkedList.

java object-oriented-design Pagar
sumber
Apa arti "the big O"?
Tulains Córdova
@ user61852 en.wikipedia.org/wiki/Big_O_notation
Paling

Jawaban:

25

Saya tidak akan mengatakannya.

Abstraksi yang bocor adalah yang memaksa Anda untuk berurusan dengan detail implementasi yang seharusnya abstrak. Tetapi kinerja selalu berbeda antara implementasi, jadi jika Anda menghitungnya sebagai bocor, maka tidak ada abstraksi yang tidak bocor.

Jika sesuatu dinyatakan Listtanpa dokumentasi lebih lanjut, harus dipahami bahwa tidak ada jaminan tentang kinerja, dan jika Anda akan melakukan apa pun yang peka terhadap kinerja, Anda harus membuat salinan dan bekerja dengan itu.

Juga, jangan lupa bahwa ada bahkan lebih umum antarmuka yang sering cukup dalam fungsi dan tidak menggoda Anda untuk membuat sebanyak asumsi tentang kinerja: Collection.

Michael Borgwardt
sumber
9
Ada lebih umum antarmuka yang sering cukup dalam fungsi: Iterable.
emory
Perbedaan kinerja antara implementasi yang berbeda diharapkan. Misalnya ada perbedaan antara Vector dan ArrayList, tetapi operasi pada LinkedList sepertinya aneh.
Paling
17

Semua abstraksi non-sepele, sampai taraf tertentu, bocor. Yang mengatakan, saya tidak begitu yakin itu berlaku di sini. :-)

Abstraksi berkaitan dengan perilaku. Kecuali jika perilaku menentukan kinerja tertentu (yang Listtidak dimiliki Java ) itu adalah detail implementasi - yaitu tidak relevan.

Java tidak memungkinkan Anda menentukan kinerja minimum untuk antarmuka di luar dokumentasi, dan saya tidak mengetahui bahasa apa pun yang melakukannya - akan sangat sulit (mustahil?) Bagi kompiler untuk memverifikasi. Saya dapat melihat beberapa opsi jika kinerja menjadi perhatian:

  1. Dokumentasikan di kelas / antarmuka tempat instance akan dimiliki.
  2. Buat antarmuka baru - mis. BinarySearchPerformantList(Yuck!) - yang menentukan persyaratan kinerja berbagai metode.

Opsi 2 mungkin adalah abstraksi yang lebih baik, tetapi dilengkapi dengan overhead tambahan.

vaughandroid
sumber
1
+1. Secara teknis ya, Daftar adalah abstraksi bocor , tapi begitu juga Obyek untuk menyembunyikan kompleksitas yang terkait dengan menggunakan equalsuntuk membandingkan objek.
Neil
2
@Neil Saya pikir ini masih bisa diperdebatkan ... Karena abstraksi tidak menyebutkan kinerja, saya tidak berpikir itu gagal dalam kasus ini (seperti yang saya katakan). Saya akan mengatakan bahwa jika Anda berpikir tentang kinerja Anda memerlukan abstraksi yang berbeda / lebih sempit. Akan mengedit untuk menyebutkan itu.
vaughandroid
Itu tergantung pada apa yang Anda sembunyikan. Apakah kompleksitas dalam penggunaan atau apakah dalam penggunaan memori dan implementasinya? Karena jika ini adalah kelas abstrak, satu atau lebih dari kompleksitas ini disembunyikan dengan satu atau lain cara.
Neil
Aku bermain-main bertahun-tahun kembali menerapkan variasi Opsi 2 menggunakan penanda interface seperti LinearSpacedan LogarithmicTimekemudian menyatakan kelas seperti public class BinarySearch : ISearchStrategy<T>, LogarithmicTime. Kelas lain dapat mengambil parameter seperti public T find<T, S>(IList<T> list, S strategy) where S : ISearchStrategy<T>, LogarithmicTime { }untuk menegakkan batasan kinerja.
Lucas
2
Jika kita membaca artikel Joel Spolsky, saya pikir ini "sedikit banyak, bocor". Lihat kutipan berikut dari artikel: "Jika Anda berurusan dengan administrator sistem di perusahaan Anda dan mereka menghukum Anda dengan menghubungkan Anda ke hub yang kelebihan beban, hanya beberapa paket IP Anda yang akan melewati, dan TCP akan bekerja, tetapi semuanya akan menjadi sangat lambat "Saya pikir ini berlaku
Amish Programmer
4

Di Jawa, ada antarmuka RandomAccess yang didefinisikan sebagai daftar dengan waktu akses acak yang umumnya konstan (O (1) dapatkan, taruh dll). Jika Anda merasa bahwa modul Anda memerlukan daftar dengan karakteristik kinerja, pertimbangkan untuk menggunakan RandomAccessbukan List. Jika Anda tidak merasa perlu untuk melakukan perubahan itu (dan sedikit yang melakukannya), maka mungkin List tidak begitu bocor.

MikeFHay
sumber
1

Anda benar, Daftar adalah abstraksi yang bocor. STL menggunakan ide konsep untuk memodelkan masalah khusus ini. Untuk menggunakan contoh Anda, sebuah ArrayListmodel Iterator Akses Acak sementara LinkedList memodelkan Iterator Teruskan . Konsep yang berbeda memiliki persyaratan kinerja yang berbeda, yang membuatnya sesuai untuk algoritma yang berbeda .

Matthew Finlay
sumber