Czy „Set” powinien mieć metodę Get?

22

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

Vojta
źródło
12
C ++ std::setobsługuje pobieranie obiektów, więc nie wszystkie „powszechne” języki są takie, jak opisano.
Przywróć Monikę
17
Jeśli twierdzisz (i kodujesz), że „równość dwóch wystąpień MyClass zależy tylko od A”, to innym wystąpieniem, które ma tę samą wartość A i różne B skutecznie, jest „to konkretne wystąpienie”, ponieważ sam określiłeś, że są one równe i różnice w B nie mają znaczenia; kontener może „zwrócić” drugą instancję, ponieważ jest równa.
Peteris,
7
Prawdziwa historia: w Javie wiele Set<E>implementacji jest tylko Map<E,Boolean>w środku.
corsiKa
10
przemawiając do osoby A : „Cześć, czy możesz przyprowadzić tutaj osobę A”
Brad Thomas
7
To łamie zwrotność ( a == bzawsze prawda) w przypadku this.A == null. if (item == null || this.A == null || item.A == null)Test jest „przesadzone” i sprawdza się dużo, być może w celu stworzenia sztucznie „wysokiej jakości” kod. Widzę tego rodzaju „sprawdzanie” i nadmierną poprawność w Code Review.
usr

Odpowiedzi:

66

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.

David Arno
źródło
2
@vojta, W takim przypadku użyj, Dictionary<MyClass, MyClass>ponieważ pobierze wartość na podstawie używanego klucza MyClass.Equals.
David Arno,
8
Chciałbym użyć Dictionary<MyClass, MyClass>dostarczonego z odpowiednim IEqualityComparer<MyClass>i wyciągnąć relację równoważności z MyClassDlaczego MyClasstrzeba wiedzieć o tej relacji w jej instancjach?
Caleth
16
@vojta i komentarz tam: „ meh. Problemem jest zastąpienie implementacji równości tak, aby nierówne obiekty były„ równe ”. Zapytanie o metodę, która mówi„ przynieś mi identyczny obiekt do tego obiektu ”, a następnie spodziewaj się, że zwrócony nieidentyczny obiekt wydaje się szalony i łatwy do spowodowania problemów konserwacyjnych ”jest na miejscu. To jest często problem z SO: poważnie błędne odpowiedzi są doceniane przez ludzi, którzy nie przemyśleli implikacji ich pragnienia szybkiej naprawy złamanego kodu ...
David Arno
6
@DavidArno: jest to jednak nieuniknione tak długo, jak długo używamy języków, które odróżniają równość i tożsamość ;-) Jeśli chcesz kanonizować obiekty, które są równe, ale nie są identyczne, potrzebujesz metody, która mówi: „nie daj mi identyczności sprzeciwić się temu obiektowi ”, ale„ przynieś mi obiekt kanoniczny równy temu obiektowi ”. Każdy, kto uważa, że ​​HashSet.Get w tych językach koniecznie oznaczałoby „zdobądź identyczny obiekt”, jest już poważnie w błędzie.
Steve Jessop
4
Ta odpowiedź ma wiele ogólnych stwierdzeń, takich jak ...reasonable to assume.... Wszystko to może być prawdą w 99% przypadków, ale nadal może przydać się możliwość odzyskania przedmiotu z zestawu. Kod świata rzeczywistego nie zawsze musi być zgodny z zasadami POLA itp. Na przykład, jeśli deduplikujesz ciągi bez rozróżniania wielkości liter, możesz chcieć uzyskać element „master”. Dictionary<string, string>jest obejściem, ale kosztuje perf.
usr
24

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
Caleth
źródło
Istnieje wiele sytuacji, w których dla kodu, który ma obiekt pasujący do klucza, może być korzystne zastąpienie go odniesieniem do obiektu używanego jako klucz. Na przykład, jeśli wiadomo, że wiele ciągów pasuje do ciągu w kolekcji z haszowaniem, zastąpienie odwołań do wszystkich tych ciągów odwołaniami do tego w kolekcji może być wygraną wydajności.
supercat,
@supercat dzisiaj osiąga się to dzięki Dictionary<String, String>.
MikeFHay,
@MikeFHay: Tak, ale wydaje się trochę nieeleganckie, aby przechowywać dwa odwołania do łańcucha.
supercat
2
@ superupat Jeśli masz na myśli identyczny ciąg, to tylko internowanie łańcucha. Użyj wbudowanych elementów. Jeśli masz na myśli jakąś reprezentację „kanoniczną” (taką, której nie można osiągnąć za pomocą prostych technik zmiany wielkości liter itp.), Brzmi to tak, jakbyś potrzebował indeksu (w tym sensie DB używa tego terminu). Nie widzę problemu z przechowywaniem każdej „formy niekanonicznej” jako klucza, który jest odwzorowywany na formę kanoniczną. (Myślę, że dotyczy to równie dobrze, jeśli forma „kanoniczna” nie jest struną). Jeśli nie o tym mówisz, to zupełnie mnie straciłeś.
jpmc26
1
Niestandardowe Compareri Dictionary<MyClass, MyClass>jest pragmatycznym rozwiązaniem. W Javie to samo można osiągnąć za pomocą niestandardowego TreeSetlub TreeMapplus Comparator.
Markus Kull,
19

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)); }
}
amon
źródło
„pobierz konkretną instancję z zestawu”. Myślę, że przekazałoby to, co masz na myśli bardziej bezpośrednio, jeśli zmienisz „instancję” na „członka”. Drobna sugestia. =) +1
jpmc26
7

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.

Stary Gruby Ned
źródło
6

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.

oopexpert
źródło
7
„Gdy tylko zastąpienie jest równe, lepiej zastąp kod skrótu. Gdy tylko to zrobisz,„ instancja ”nie powinna już nigdy zmieniać stanu wewnętrznego.” To oświadczenie jest warte +100, właśnie tam.
David Arno,
+1 za wskazanie niebezpieczeństw związanych z równością i hashcode w zależności od stanu zmienności
Hulk
3

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.

Steve Jessop
źródło
Cóż, w Javie można zapewnić defaultimplementację, aby zrobić to w sposób niezniszczalny. To po prostu nie wydaje się bardzo przydatna zmiana.
Hulk
@Hulk: Mogę się mylić, ale myślę, że każda domyślna implementacja byłaby niesamowicie nieefektywna, ponieważ, jak pytający pyta: „Jedynym sposobem na odzyskanie mojego przedmiotu jest iteracja po całej kolekcji i sprawdzenie wszystkich elementów pod kątem równości”. Tak dobrze, że możesz to zrobić w sposób zgodny z poprzednimi wersjami, ale dodanie gotcha, że ​​wynikowa funkcja get gwarantuje działanie tylko w O(n)porównaniach, nawet jeśli funkcja skrótu daje dobrą dystrybucję. Wówczas implementacje Settego typu zastępują domyślną implementację interfejsu, w tym HashSet, mogą dać lepszą gwarancję.
Steve Jessop
Zgoda - nie sądzę, że byłby to dobry pomysł. Istnieją jednak pierwszeństwa dla tego rodzaju zachowania - List.get (indeks wewnętrzny) lub - aby wybrać domyślną implementację dodaną ostatnio List.sort . Interfejs zapewnia gwarancje maksymalnej złożoności, ale niektóre implementacje mogą działać znacznie lepiej niż inne.
Hulk
2

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.

Jak
źródło