Haruskah "Set" memiliki metode Get?

Mari kita buat kelas C # ini (akan hampir sama di Jawa)

public class MyClass {
   public string A {get; set;}
   public string B {get; set;}

   public override bool Equals(object obj) {
        var item = obj as MyClass;

        if (item == null || this.A == null || item.A == null)
        {
            return false;
        }
        return this.A.equals(item.A);
   }

   public override int GetHashCode() {
        return A != null ? A.GetHashCode() : 0;
   }
}

Seperti yang Anda lihat, persamaan dua contoh hanya MyClassbergantung pada A. Jadi bisa ada dua contoh yang sama, tetapi memegang informasi yang berbeda di Bproperti mereka .

Di perpustakaan koleksi standar banyak bahasa (termasuk C # dan Java, tentu saja) ada Set( HashSetdalam C #), yang koleksi, yang dapat menampung paling banyak satu item dari setiap set instance yang sama.

Seseorang dapat menambahkan item, menghapus item dan memeriksa apakah set berisi item. Tetapi mengapa tidak mungkin untuk mendapatkan item tertentu dari set?

HashSet<MyClass> mset = new HashSet<MyClass>();
mset.Add(new MyClass {A = "Hello", B = "Bye"});

//I can do this
if (mset.Contains(new MyClass {A = "Hello", B = "See you"})) {
    //something
}

//But I cannot do this, because Get does not exist!!!
MyClass item = mset.Get(new MyClass {A = "Hello", B = "See you"});
Console.WriteLine(item.B); //should print Bye

Satu-satunya cara untuk mengambil item saya adalah dengan mengulang seluruh koleksi dan memeriksa semua item untuk kesetaraan. Namun, ini membutuhkan O(n)waktu, bukan O(1)!

Saya belum menemukan bahasa yang mendukung dapatkan dari set sejauh ini. Semua bahasa "umum" yang saya tahu (Java, C #, Python, Scala, Haskell ...) tampaknya dirancang dengan cara yang sama: Anda dapat menambahkan item, tetapi Anda tidak dapat mengambilnya. Adakah alasan bagus mengapa semua bahasa ini tidak mendukung sesuatu yang mudah dan jelas bermanfaat? Mereka tidak mungkin salah, kan? Apakah ada bahasa yang mendukungnya? Mungkin mengambil kembali item tertentu dari set adalah salah, tetapi mengapa?

Ada beberapa pertanyaan terkait SO:

/programming/7283338/getting-an-element-from-a-set

/programming/7760364/how-to-retrieve-actual-item-from-hashsett

Masalahnya di sini adalah tidak HashSetkekurangan Getmetode, melainkan karena kode Anda tidak masuk akal dari sudut pandang HashSetjenisnya.

Itu Getmetode adalah efektif, "mendapatkan saya nilai ini, silakan", dimana NET framework rakyat bijaksana akan menjawab, "eh? Anda sudah memiliki nilai yang <confused face />".

Jika Anda ingin menyimpan item dan kemudian mengambilnya berdasarkan pencocokan nilai yang sedikit berbeda, kemudian gunakan Dictionary<String, MyClass>yang dapat Anda lakukan:

var mset = new Dictionary<String, MyClass>();
mset.Add("Hello", new MyClass {A = "Hello", B = "Bye"});

var item = mset["Hello"];
Console.WriteLine(item.B); // will print Bye

Informasi kebocoran kesetaraan dari kelas yang dienkapsulasi. Jika saya ingin mengubah set properti yang terlibat Equals, saya harus mengubah kode di luar MyClass...

Ya, tapi itu karena MyClassmengamuk dengan prinsip least astonishment (POLA). Dengan fungsionalitas kesetaraan yang dienkapsulasi, sangat masuk akal untuk menganggap bahwa kode berikut ini valid:

HashSet<MyClass> mset = new HashSet<MyClass>();
mset.Add(new MyClass {A = "Hello", B = "Bye"});

if (mset.Contains(new MyClass {A = "Hello", B = "See you"})) 
{
    // this code is unreachable.
}

Untuk mencegah hal ini, MyClassperlu didokumentasikan dengan jelas bentuk kesetaraan yang aneh. Setelah melakukan itu, itu tidak lagi dienkapsulasi dan mengubah cara kerja kesetaraan akan melanggar prinsip terbuka / tertutup. Ergo, itu tidak boleh berubah dan karena itu Dictionary<String, MyClass>merupakan solusi yang baik untuk persyaratan aneh ini.

Anda sudah memiliki item yang "dalam" set - Anda menyerahkannya sebagai kunci.

"Tapi itu bukan contoh yang saya sebut Tambahkan dengan" - Ya, tetapi Anda secara khusus mengklaim bahwa mereka sama.

A Setjuga merupakan kasus khusus dari a Map| Dictionary, dengan void sebagai tipe nilai (yah metode yang tidak berguna tidak didefinisikan, tetapi itu tidak masalah).

Struktur data yang Anda cari adalah Dictionary<X, MyClass>tempat Xentah bagaimana mengeluarkan As dari MyClasses.

Tipe C # Kamus bagus dalam hal ini, karena memungkinkan Anda untuk memasok IEqualityComparer untuk kunci.

Untuk contoh yang diberikan, saya akan memiliki yang berikut:

public class MyClass {
   public string A {get; set;}
   public string B {get; set;}
}

public class MyClassEquivalentAs : IEqualityComparer<MyClass>{
   public override bool Equals(MyClass left, MyClass right) {
        if (Object.ReferenceEquals(left, null) && Object.ReferenceEquals(right, null))
        {
            return true;
        }
        else if (Object.ReferenceEquals(left, null) || Object.ReferenceEquals(right, null))
        {
            return false;
        }
        return left.A == right.A;
   }

   public override int GetHashCode(MyClass obj) {
        return obj?.A != null ? obj.A.GetHashCode() : 0;
   }
}

Dengan demikian digunakan:

var mset = new Dictionary<MyClass, MyClass>(new MyClassEquivalentAs());
var bye = new MyClass {A = "Hello", B = "Bye"};
var seeyou = new MyClass {A = "Hello", B = "See you"};
mset.Add(bye);

if (mset.Contains(seeyou)) {
    //something
}

MyClass item = mset[seeyou];
Console.WriteLine(item.B); // prints Bye

Masalah Anda adalah bahwa Anda memiliki dua konsep kesetaraan yang kontradiktif:

• kesetaraan aktual, di mana semua bidang sama
• mengatur kesetaraan keanggotaan, di mana hanya A yang sama

Jika Anda akan menggunakan relasi kesetaraan yang sebenarnya di set Anda, masalah mengambil item tertentu dari set tidak muncul - untuk memeriksa apakah suatu objek ada di set, Anda sudah memiliki objek itu. Oleh karena itu tidak perlu untuk mengambil contoh tertentu dari set, dengan asumsi Anda menggunakan hubungan kesetaraan yang benar.

Kita juga bisa berargumen bahwa suatu himpunan adalah tipe data abstrak yang didefinisikan murni oleh S contains xatau x is-element-of Srelasi ("fungsi karakteristik"). Jika Anda ingin operasi lain, Anda sebenarnya tidak mencari satu set.

Apa yang terjadi cukup sering - tetapi apa yang bukan merupakan himpunan - adalah bahwa kita mengelompokkan semua objek ke dalam kelas kesetaraan yang berbeda . Objek di setiap kelas atau subset tersebut hanya setara, tidak sama. Kami dapat mewakili setiap kelas ekivalensi melalui anggota subset mana pun, dan kemudian diinginkan untuk mengambil elemen yang mewakili. Ini akan menjadi pemetaan dari kelas ekivalensi ke elemen perwakilan.

Dalam C #, sebuah kamus dapat menggunakan hubungan kesetaraan eksplisit, saya pikir. Kalau tidak, hubungan seperti itu dapat diimplementasikan dengan menulis kelas pembungkus cepat. Kodesemu:

// The type you actually want to store
class MyClass { ... }

// A equivalence class of MyClass objects,
// with regards to a particular equivalence relation.
// This relation is implemented in EquivalenceClass.Equals()
class EquivalenceClass {
  public MyClass instance { get; }
  public override bool Equals(object o) { ... } // compare instance.A
  public override int GetHashCode() { ... } // hash instance.A
  public static EquivalenceClass of(MyClass o) { return new EquivalenceClass { instance = o }; }
}

// The set-like object mapping equivalence classes
// to a particular representing element.
class EquivalenceHashSet {
  private Dictionary<EquivalenceClass, MyClass> dict = ...;
  public void Add(MyClass o) { dict.Add(EquivalenceClass.of(o), o)}
  public bool Contains(MyClass o) { return dict.Contains(EquivalenceClass.of(o)); }
  public MyClass Get(MyClass o) { return dict.Get(EquivalenceClass.of(o)); }
}

Tetapi mengapa tidak mungkin untuk mendapatkan item tertentu dari set?

Karena bukan itu gunanya set.

Biarkan saya ulangi contohnya.

"Saya memiliki HashSet yang saya inginkan untuk menyimpan objek MyClass dan saya ingin bisa mendapatkannya dengan menggunakan properti A yang sama dengan properti objek A".

Jika ganti "HashSet" dengan "Collection", "objek" dengan "Values" dan "property A" dengan "Key", kalimatnya menjadi:

"Saya memiliki Koleksi yang ingin saya simpan Nilai MyClass dan saya ingin bisa mendapatkannya dengan menggunakan Kunci yang sama dengan Kunci objek".

Yang dijelaskan adalah Kamus. Pertanyaan aktual yang diajukan adalah "Mengapa saya tidak bisa memperlakukan HashSet sebagai Kamus?"

Jawabannya adalah mereka tidak digunakan untuk hal yang sama. Alasan untuk menggunakan set adalah untuk menjamin keunikan konten individu itu, jika tidak, Anda bisa menggunakan Daftar atau array. Perilaku yang dijelaskan dalam pertanyaan adalah untuk apa Kamus. Semua desainer bahasa tidak mengacau. Mereka tidak menyediakan metode get karena jika Anda memiliki objek dan itu dalam set, mereka setara, yang berarti Anda akan "mendapatkan" objek yang setara. Berargumen bahwa HashSet harus diimplementasikan sedemikian rupa sehingga Anda bisa "mendapatkan" objek yang tidak setara yang Anda tetapkan sama adalah tidak starter ketika bahasa menyediakan struktur data lain yang memungkinkan Anda untuk melakukan itu.

Catatan tentang OOP dan komentar / jawaban kesetaraan. Tidak apa-apa jika kunci pemetaan menjadi properti / anggota dari nilai yang disimpan dalam Kamus. Sebagai contoh: memiliki Guid sebagai kunci dan juga properti yang digunakan untuk metode yang sama adalah sangat masuk akal. Apa yang tidak masuk akal adalah memiliki nilai yang berbeda untuk properti lainnya. Saya menemukan bahwa jika saya menuju ke arah itu, saya mungkin perlu memikirkan kembali struktur kelas saya.

Begitu Anda menimpa sama dengan Anda lebih baik menimpa kode hash. Segera setelah Anda melakukan ini, "contoh" Anda seharusnya tidak pernah mengubah keadaan internal lagi.

Jika Anda tidak menimpa sama dan hashcode, identitas objek VM digunakan untuk menentukan kesetaraan. Jika Anda meletakkan objek ini ke dalam Set Anda dapat menemukannya lagi.

Mengubah nilai suatu objek yang digunakan untuk menentukan kesetaraan akan menyebabkan ketidaklacakan objek ini dalam struktur berbasis hash.

Jadi Setter pada A berbahaya.

Sekarang Anda tidak memiliki B yang tidak berpartisipasi dalam kesetaraan. Masalahnya di sini secara teknis tidak semantik. Karena secara teknis mengubah B adalah netral terhadap fakta kesetaraan. Semantik B harus seperti bendera "versi".

Intinya adalah:

Jika Anda memiliki dua objek yang sama dengan A tetapi tidak B Anda memiliki asumsi bahwa salah satu objek ini lebih baru daripada yang lain. Jika B tidak memiliki informasi versi, asumsi ini disembunyikan dalam algoritme Anda KAPAN Anda memutuskan untuk "menimpa / memperbarui" objek ini dalam Set. Lokasi kode sumber ini di mana hal ini terjadi mungkin tidak jelas sehingga pengembang akan mengalami kesulitan untuk mengidentifikasi hubungan antara objek X dan objek Y yang berbeda dari X di B.

Jika B memiliki informasi versi, Anda mengekspos asumsi yang sebelumnya hanya secara implisit diturunkan dari kode. Sekarang Anda bisa melihat, objek Y itu adalah versi X. yang lebih baru

Pikirkan tentang diri Anda: Identitas Anda tetap sepanjang hidup Anda, mungkin beberapa properti berubah (misalnya warna rambut Anda ;-)). Tentu Anda dapat berasumsi bahwa jika Anda memiliki dua foto, satu dengan rambut cokelat satu dengan rambut abu-abu, Anda mungkin lebih muda di foto dengan rambut cokelat. Tapi mungkin Anda sudah mewarnai rambut Anda? Masalahnya adalah: ANDA mungkin tahu bahwa Anda mewarnai rambut Anda. Mungkin orang lain? Untuk memasukkan ini ke dalam konteks yang valid, Anda harus memperkenalkan usia properti (versi). Maka Anda, Anda secara semantik eksplisit dan tidak beragama.

Untuk menghindari operasi tersembunyi "mengganti yang lama dengan objek baru" suatu Set seharusnya tidak memiliki Metode-get. Jika Anda menginginkan perilaku seperti ini, Anda harus membuatnya eksplisit dengan menghapus objek lama dan menambahkan objek baru.

BTW: Apa artinya jika Anda memasukkan objek yang sama dengan objek yang ingin Anda dapatkan? Itu tidak masuk akal. Jagalah semantik Anda dan jangan lakukan ini meskipun secara teknis tidak ada yang akan menghalangi Anda.

Khususnya di Jawa, HashSetpada awalnya diimplementasikan menggunakan HashMappula, dan hanya mengabaikan nilai. Jadi desain awal tidak mengantisipasi keuntungan apa pun dalam menyediakan metode get to HashSet. Jika Anda ingin menyimpan dan mengambil nilai kanonik di antara berbagai objek yang sama, maka Anda hanya menggunakan HashMapdiri Anda sendiri.

Saya belum memperbarui informasi implementasi seperti itu, jadi saya tidak bisa mengatakan apakah alasan ini masih berlaku sepenuhnya di Jawa, apalagi di C # dll. Tetapi bahkan jika HashSet diterapkan kembali untuk menggunakan memori lebih sedikit daripada HashMap, dalam hal apapun itu akan menjadi perubahan besar untuk menambahkan metode baru ke Setantarmuka. Jadi itu cukup banyak rasa sakit untuk mendapatkan yang tidak semua orang lihat layak untuk dimiliki.

Ada bahasa utama yang himpunannya memiliki properti yang Anda inginkan.

Dalam C ++, std::setadalah set yang dipesan. Ini memiliki .findmetode yang mencari elemen berdasarkan operator pemesanan <atau bool(T,T)fungsi biner yang Anda berikan. Anda dapat menggunakan find untuk mengimplementasikan operasi get yang Anda inginkan.

Bahkan, jika bool(T,T)fungsi yang Anda berikan memiliki bendera khusus di atasnya (is_transparent ), Anda bisa mengirimkan objek dari tipe yang berbeda yang fungsinya terlalu banyak. Itu berarti Anda tidak harus memasukkan data "dummy" ke dalam kolom kedua, cukup pastikan operasi pemesanan yang Anda gunakan dapat memesan antara tipe pencarian dan tipe yang diatur.

Ini memungkinkan efisien:

std::set< std::string, my_string_compare > strings;
strings.find( 7 );

dimana my_string_compare mengerti bagaimana cara memesan bilangan bulat dan string tanpa terlebih dahulu mengubah bilangan bulat menjadi string (dengan biaya potensial).

Untuk unordered_set(kumpulan hash C ++), tidak ada flag transparan yang setara (belum). Anda harus lulus dalam Tsebuahunordered_set<T>.find metode. Itu dapat ditambahkan, tetapi hash membutuhkan ==dan hasher, tidak seperti set memerintahkan yang hanya membutuhkan pemesanan.

Pola umum adalah bahwa wadah akan melakukan pencarian, kemudian memberi Anda "iterator" untuk elemen itu di dalam wadah. Pada titik mana Anda bisa mendapatkan elemen dalam set, atau menghapusnya, dll.

Singkatnya, tidak semua kontainer standar bahasa memiliki kekurangan yang Anda gambarkan. Wadah berbasis iterator pustaka standar C ++ tidak, dan setidaknya beberapa wadah sudah ada sebelum bahasa lain yang Anda deskripsikan, dan kemampuan untuk mendapatkan bahkan lebih efisien daripada bagaimana Anda menggambarkan telah ditambahkan. Tidak ada yang salah dengan desain Anda, atau menginginkan operasi itu; desainer Set yang Anda gunakan sama sekali tidak menyediakan antarmuka itu.

Wadah standar C ++ tempat dirancang untuk membungkus dengan bersih operasi tingkat rendah dari kode C linting tangan yang setara, yang dirancang agar sesuai dengan cara Anda dapat menulisnya secara efisien dalam perakitan. Iteratornya adalah abstraksi dari pointer C-style. Bahasa yang Anda sebutkan semuanya telah pindah dari pointer sebagai konsep, sehingga mereka tidak menggunakan abstraksi iterator.

Ada kemungkinan bahwa fakta bahwa C ++ tidak memiliki cacat ini adalah kecelakaan desain. Jalur iterator-centric berarti bahwa untuk berinteraksi dengan item dalam wadah asosiatif Anda pertama kali mendapatkan iterator ke elemen, lalu Anda menggunakan iterator untuk berbicara tentang entri dalam wadah.

Biayanya adalah bahwa ada aturan pembatalan iterasi yang harus Anda lacak, dan beberapa operasi memerlukan 2 langkah alih-alih satu (yang membuat ribut kode klien). Keuntungannya adalah abstraksi yang kuat memungkinkan penggunaan yang lebih maju daripada yang dimiliki oleh para perancang API semula.