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 MyClass
zależy A
tylko od. Mogą więc istnieć dwa przypadki, które są równe, ale zawierają inną informację w swojej B
właściwości.
W standardowej bibliotece wielu języków (w tym oczywiście C # i Java) znajduje się Set
( HashSet
w 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
źródło
std::set
obsługuje pobieranie obiektów, więc nie wszystkie „powszechne” języki są takie, jak opisano.Set<E>
implementacji jest tylkoMap<E,Boolean>
w środku.a == b
zawsze prawda) w przypadkuthis.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.Odpowiedzi:
Problem nie polega na tym, że nie
HashSet
maGet
metody, to, że twój kod nie ma sensu z punktu widzeniaHashSet
typu.Że
Get
metoda 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>
:No tak, ale to dlatego, że
MyClass
dział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:Aby temu zapobiec,
MyClass
należ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 dlategoDictionary<String, MyClass>
jest dobrym rozwiązaniem dla tego dziwnego wymagania.źródło
Dictionary<MyClass, MyClass>
ponieważ pobierze wartość na podstawie używanego kluczaMyClass.Equals
.Dictionary<MyClass, MyClass>
dostarczonego z odpowiednimIEqualityComparer<MyClass>
i wyciągnąć relację równoważności zMyClass
DlaczegoMyClass
trzeba wiedzieć o tej relacji w jej instancjach?...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.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
Set
jest także specjalnym przypadkiemMap
|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órymX
jakoś 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:
Używany w ten sposób:
źródło
Dictionary<String, String>
.Comparer
iDictionary<MyClass, MyClass>
jest pragmatycznym rozwiązaniem. W Javie to samo można osiągnąć za pomocą niestandardowegoTreeSet
lubTreeMap
plusComparator
.Twoim problemem jest to, że masz dwie sprzeczne koncepcje równości:
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 x
lubx 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:
źródło
Ponieważ nie po to są zestawy.
Pozwól, że powtórzę przykład.
Jeśli zamienisz „HashSet” na „Collection”, „objects” na „Values” i „property A” na „Key”, zdanie to:
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.
źródło
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.
źródło
W szczególności w Javie
HashSet
został początkowo zaimplementowany za pomocą iHashMap
tak, po prostu ignorując wartość. Tak więc początkowy projekt nie przewidywał żadnej korzyści w zapewnieniu metody getHashSet
. Jeśli chcesz przechowywać i odzyskiwać wartość kanoniczną wśród różnych obiektów, które są równe, po prostu użyjHashMap
siebie.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
HashSet
zostałyby zaimplementowane w celu zużywania mniejszej ilości pamięci niżHashMap
w każdym razie byłoby przełomową zmianą, aby dodać nową metodę doSet
interfejsu. Jest to więc dość bolesne dla zysku, którego nie wszyscy uważają za warte posiadania.źródło
default
implementację, aby zrobić to w sposób niezniszczalny. To po prostu nie wydaje się bardzo przydatna zmiana.O(n)
porównaniach, nawet jeśli funkcja skrótu daje dobrą dystrybucję. Wówczas implementacjeSet
tego typu zastępują domyślną implementację interfejsu, w tymHashSet
, mogą dać lepszą gwarancję.Istnieje jeden główny język, którego zestaw ma właściwość, którą chcesz.
W C ++
std::set
jest zestawem uporządkowanym. Ma.find
metodę polegającą na wyszukiwaniu elementu na podstawie podanego operatora zamawiania<
lubbool(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:
gdzie
my_string_compare
rozumie, 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ć wT
dounordered_set<T>.find
metody. 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.
źródło