Czy „Set” powinien mieć metodę Get?

Miejmy tę klasę C # (w Javie byłoby prawie tak samo)

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;
   }
}

Jak widać, równość dwóch przypadków MyClasszależy Atylko od. Mogą więc istnieć dwa przypadki, które są równe, ale zawierają inną informację w swojej Bwłaściwości.

W standardowej bibliotece wielu języków (w tym oczywiście C # i Java) znajduje się Set( HashSetw C #) kolekcja, która może pomieścić maksymalnie jeden element z każdego zestawu równych instancji.

Można dodawać elementy, usuwać elementy i sprawdzać, czy zestaw zawiera element. Ale dlaczego nie można zdobyć określonego przedmiotu z zestawu?

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

Jedynym sposobem na odzyskanie mojego przedmiotu jest iteracja całej kolekcji i sprawdzenie, czy wszystkie elementy są równe. To jednak wymaga O(n)czasu zamiast O(1)!

Do tej pory nie znalazłem żadnego języka, który obsługuje pobieranie z zestawu. Wszystkie „popularne” języki, które znam (Java, C #, Python, Scala, Haskell ...) wydają się być zaprojektowane w ten sam sposób: możesz dodawać elementy, ale nie możesz ich odzyskać. Czy jest jakiś dobry powód, dla którego wszystkie te języki nie obsługują czegoś tak łatwego i oczywiście przydatnego? Nie mogą się wszyscy mylić, prawda? Czy są jakieś języki, które to obsługują? Może wycofywanie określonego elementu z zestawu jest złe, ale dlaczego?

Istnieje kilka powiązanych pytań SO:

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

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

Problem nie polega na tym, że nie HashSetma Getmetody, to, że twój kod nie ma sensu z punktu widzenia HashSettypu.

Że Getmetoda ta jest skutecznie „daj mi tę wartość, proszę”, do którego ludowa NET byłoby sensownie odpowiedzieć, „co? Masz już tę wartość <confused face />”.

Jeśli chcesz przechowywać elementy, a następnie odzyskać je na podstawie dopasowania innej nieco innej wartości, użyj następujących opcji Dictionary<String, MyClass>:

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

Informacja o równości wycieka z enkapsulowanej klasy. Gdybym chciał zmienić zestaw właściwości zaangażowanych Equals, musiałbym zmienić kod poza MyClass...

No tak, ale to dlatego, że MyClassdziała amok z zasadą najmniejszego zdziwienia (POLA). Po zamknięciu tej funkcji równości można całkowicie założyć, że następujący kod jest prawidłowy:

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.
}

Aby temu zapobiec, MyClassnależy jasno udokumentować jego dziwną formę równości. Po wykonaniu tej czynności nie jest już zamknięty, a zmiana sposobu działania tej równości złamałaby zasadę otwartego / zamkniętego. Ergo, nie powinno się to zmieniać i dlatego Dictionary<String, MyClass>jest dobrym rozwiązaniem dla tego dziwnego wymagania.

Masz już element „w” zestawie - przekazałeś go jako klucz.

„Ale to nie jest przypadek, który nazwałem Add with” - Tak, ale konkretnie twierdziłeś, że były one równe.

A Setjest także specjalnym przypadkiem Map| Dictionary, z void jako typem wartości (cóż, bezużyteczne metody nie są zdefiniowane, ale to nie ma znaczenia).

Struktura danych, której szukasz, jest miejscem, w Dictionary<X, MyClass>którym Xjakoś wydobywa się As z MyClasses.

Słownik typu C # jest pod tym względem fajny, ponieważ pozwala dostarczyć IEqualityComparer dla kluczy.

W podanym przykładzie miałbym następujące:

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;
   }
}

Używany w ten sposób:

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

Twoim problemem jest to, że masz dwie sprzeczne koncepcje równości:

• faktyczna równość, w której wszystkie pola są równe
• ustawić równość członkostwa, gdzie tylko A jest równe

Jeśli użyjesz rzeczywistej relacji równości w swoim zestawie, nie pojawia się problem pobierania określonego elementu ze zbioru - aby sprawdzić, czy obiekt znajduje się w zestawie, już go masz. Dlatego nigdy nie jest konieczne pobieranie konkretnej instancji ze zbioru, zakładając, że używasz prawidłowej relacji równości.

Możemy również argumentować, że zbiór jest abstrakcyjnym typem danych, który jest zdefiniowany wyłącznie przez relację S contains xlub x is-element-of S(„funkcja charakterystyczna”). Jeśli chcesz innych operacji, tak naprawdę nie szukasz zestawu.

Często zdarza się - ale nie jest to zbiór - grupujemy wszystkie obiekty w odrębne klasy równoważności . Obiekty w każdej takiej klasie lub podzbiorze są tylko równoważne, a nie równe. Możemy reprezentować każdą klasę równoważności za pośrednictwem dowolnego elementu tego podzbioru, a następnie pożądane jest pobranie tego elementu reprezentującego. Byłoby to odwzorowanie z klasy równoważności na reprezentatywny element.

Myślę, że w języku C # słownik może używać jawnej relacji równości. W przeciwnym razie relacja taka może zostać zaimplementowana przez napisanie klasy szybkiego opakowania. Pseudo kod:

// 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)); }
}

Ale dlaczego nie można zdobyć określonego przedmiotu z zestawu?

Ponieważ nie po to są zestawy.

Pozwól, że powtórzę przykład.

„Mam zestaw HashSet, w którym chcę przechowywać obiekty MyClass i chcę je uzyskać za pomocą właściwości A, która jest równa właściwości A obiektu”.

Jeśli zamienisz „HashSet” na „Collection”, „objects” na „Values” i „property A” na „Key”, zdanie to:

„Mam kolekcję, w której chcę przechowywać wartości MyClass i chcę je uzyskać za pomocą klucza równego kluczowi obiektu”.

Opisywany jest Słownik. Zadawane pytanie brzmi: „Dlaczego nie mogę traktować HashSet jako słownika?”

Odpowiedź jest taka, że ​​nie są one używane do tego samego. Powodem korzystania z zestawu jest zagwarantowanie wyjątkowości jego indywidualnych treści, w przeciwnym razie możesz po prostu użyć listy lub tablicy. Zachowanie opisane w pytaniu jest tym, do czego służy Słownik. Wszyscy projektanci języków nie spieprzyli. Nie zapewniają metody get, ponieważ jeśli masz obiekt i znajduje się on w zestawie, są one równoważne, co oznacza, że ​​„otrzymujesz” równoważny obiekt. Argument, że HashSet powinien być zaimplementowany w taki sposób, aby można było „uzyskać” nie równoważne obiekty, które zdefiniowałeś jako równe, nie jest początkowy, gdy języki zapewniają inne struktury danych, które to umożliwiają.

Uwaga na temat OOP i komentarzy / odpowiedzi na temat równości. Można mieć klucz odwzorowania jako właściwość / element przechowywanej wartości w słowniku. Na przykład: posiadanie Guid jako klucza oraz właściwości używanej w metodzie równości jest całkowicie uzasadnione. Nieuzasadnione jest posiadanie różnych wartości dla pozostałych właściwości. Uważam, że jeśli zmierzam w tym kierunku, prawdopodobnie muszę przemyśleć moją strukturę klas.

Gdy tylko zastąpienie będzie równe, lepiej zastąp kod skrótu. Jak tylko to zrobisz, twoja „instancja” nie powinna już nigdy zmieniać stanu wewnętrznego.

Jeśli nie zastąpisz wartości równej, a hashcode do określenia równości zostanie użyta tożsamość obiektu VM. Jeśli umieścisz ten obiekt w zestawie, będziesz mógł go znaleźć ponownie.

Zmiana wartości obiektu służącego do ustalenia równości doprowadzi do niewykrywalności tego obiektu w strukturach opartych na haszowaniu.

Więc Setter na A jest niebezpieczny.

Teraz nie masz B, który nie uczestniczy w równości. Problem tutaj nie jest semantyczny technicznie. Ponieważ technicznie zmiana B jest neutralna dla faktu równości. Semantycznie B musi być czymś w rodzaju flagi „wersji”.

Chodzi o to:

Jeśli masz dwa obiekty, które są równe A, ale nie B, masz założenie, że jeden z tych obiektów jest nowszy od drugiego. Jeśli B nie ma informacji o wersji, założenie to jest ukryte w algorytmie, GDY zdecydujesz się „zastąpić / zaktualizować” ten obiekt w zestawie. Lokalizacja kodu źródłowego, w której to się dzieje, może nie być oczywista, więc deweloperowi trudno będzie zidentyfikować relację między obiektem X a obiektem Y, która różni się od X w B.

Jeśli B ma informacje o wersji, ujawniasz założenie, że poprzednio można było je domyślnie wyprowadzić z kodu. Teraz możesz zobaczyć, że obiekt Y jest nowszą wersją X.

Pomyśl o sobie: Twoja tożsamość pozostaje przez całe życie, może niektóre właściwości się zmieniają (np. Kolor włosów ;-)). Pewnie możesz założyć, że jeśli masz dwa zdjęcia, jedno z brązowymi włosami i jedno z siwymi włosami, możesz być młodszy na zdjęciu z brązowymi włosami. Ale może farbujesz włosy? Problem w tym, że możesz wiedzieć, że farbujesz włosy. Czy inni mogą? Aby umieścić to w prawidłowym kontekście, musisz wprowadzić wiek nieruchomości (wersja). Jesteś więc semantycznie wyraźny i niedwuznaczny.

Aby uniknąć ukrytej operacji „zamiany starego na nowy obiekt”, Zestaw nie powinien mieć metody get-get. Jeśli chcesz takiego zachowania, musisz wyrazić je jawnie, usuwając stary obiekt i dodając nowy obiekt.

BTW: Co to powinno znaczyć, jeśli przekazujesz obiekt równy obiektowi, który chcesz uzyskać? To nie ma sensu. Utrzymuj swoją semantykę w czystości i nie rób tego, chociaż technicznie nikt ci nie przeszkodzi.

W szczególności w Javie HashSetzostał początkowo zaimplementowany za pomocą i HashMaptak, po prostu ignorując wartość. Tak więc początkowy projekt nie przewidywał żadnej korzyści w zapewnieniu metody get HashSet. Jeśli chcesz przechowywać i odzyskiwać wartość kanoniczną wśród różnych obiektów, które są równe, po prostu użyj HashMapsiebie.

Nie śledziłem na bieżąco takich szczegółów implementacyjnych, więc nie mogę powiedzieć, czy to rozumowanie nadal obowiązuje w całości w Javie, nie mówiąc już o C # itp. Ale nawet jeśli HashSetzostałyby zaimplementowane w celu zużywania mniejszej ilości pamięci niż HashMapw każdym razie byłoby przełomową zmianą, aby dodać nową metodę do Setinterfejsu. Jest to więc dość bolesne dla zysku, którego nie wszyscy uważają za warte posiadania.

Istnieje jeden główny język, którego zestaw ma właściwość, którą chcesz.

W C ++ std::setjest zestawem uporządkowanym. Ma .findmetodę polegającą na wyszukiwaniu elementu na podstawie podanego operatora zamawiania <lub bool(T,T)funkcji binarnej . Możesz użyć find, aby zaimplementować żądaną operację get.

W rzeczywistości, jeśli podana bool(T,T)funkcja ma określoną flagę ( is_transparent), możesz przekazać obiekty innego typu, dla których funkcja ma przeciążenia. Oznacza to, że nie musisz umieszczać „fałszywego” danych w drugim polu danych, po prostu upewnij się, że operacja porządkowania, której używasz, może zamówić między typami wyszukiwania i zawartymi w zestawie.

Pozwala to na efektywne:

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

gdzie my_string_comparerozumie, jak zamówić liczby całkowite i ciągi bez uprzedniej konwersji liczby całkowitej na ciąg (za potencjalnym kosztem).

W przypadku unordered_set(zestawu skrótów C ++) nie ma jeszcze równoważnej przezroczystej flagi (jeszcze). Należy przekazać w Tdo unordered_set<T>.findmetody. Można go dodać, ale hashe wymagają ==i hashera, w przeciwieństwie do zestawów uporządkowanych, które wymagają tylko uporządkowania.

Ogólny wzorzec jest taki, że kontener przeprowadzi wyszukiwanie, a następnie da ci „iterator” do tego elementu w kontenerze. W którym momencie możesz pobrać element z zestawu lub go usunąć itp.

Krótko mówiąc, nie wszystkie standardowe pojemniki we wszystkich językach mają wady, które opisujesz. Kontenery oparte na iteratorze biblioteki standardowej C ++ nie istnieją, a przynajmniej niektóre z nich istniały przed którymkolwiek z innych języków, które opisałeś, a możliwość dodania jeszcze wydajniej niż opisujesz. Nie ma nic złego w twoim projekcie lub chęci takiej operacji; projektanci zestawów, których używasz, po prostu nie udostępnili tego interfejsu.

Standardowe kontenery C ++ zostały zaprojektowane do czystego pakowania operacji niskiego poziomu równoważnego ręcznie zwijanego kodu C, który został zaprojektowany tak, aby pasował do tego, jak można go efektywnie napisać w asemblerze. Jej iteratory są abstrakcją wskaźników w stylu C. Wymienione języki odeszły od wskaźników jako koncepcji, więc nie używają abstrakcji iteratora.

Możliwe, że fakt, że C ++ nie ma tej wady, jest przypadkiem przy projektowaniu. Ścieżka zorientowana na iteratory oznacza, że ​​aby wejść w interakcję z przedmiotem w kontenerze asocjacyjnym, najpierw dostajesz iterator do elementu, a następnie używasz tego iteratora, aby mówić o wejściu do kontenera.

Koszt polega na tym, że istnieją reguły unieważniania iteracji, które należy śledzić, a niektóre operacje wymagają 2 kroków zamiast jednego (co powoduje, że kod klienta jest głośniejszy). Zaletą jest to, że solidna abstrakcja pozwala na bardziej zaawansowane wykorzystanie niż te, które pierwotnie mieli na myśli projektanci API.