Najlepsze praktyki zastępowania to: Równe: i mieszające

Jak poprawnie przesłonić isEqual:cel C? „Złap” wydaje się polegać na tym, że jeśli dwa obiekty są równe (jak określa isEqual:metoda), muszą mieć tę samą wartość skrótu.

Introspekcja odcinek kakao Fundamentals Przewodnik ma przykład, w jaki sposób zastąpić isEqual:, kopiowane następująco, dla klasy o nazwie MyWidget:

- (BOOL)isEqual:(id)other {
    if (other == self)
        return YES;
    if (!other || ![other isKindOfClass:[self class]])
        return NO;
    return [self isEqualToWidget:other];
}

- (BOOL)isEqualToWidget:(MyWidget *)aWidget {
    if (self == aWidget)
        return YES;
    if (![(id)[self name] isEqual:[aWidget name]])
        return NO;
    if (![[self data] isEqualToData:[aWidget data]])
        return NO;
    return YES;
}

Sprawdza równość wskaźnika, następnie równość klas, a na koniec porównuje obiekty isEqualToWidget:, które tylko sprawdzają właściwości namei data. W tym przykładzie nie pokazano, jak zastąpić hash.

Załóżmy, że istnieją inne właściwości, które nie wpływają na równość, powiedzmy age. Nie powinien hashmetoda być przesłonięte tak, że tylko namei datawpływać na hash? A jeśli tak, to jak byś to zrobił? Po prostu dodaj skróty namei data? Na przykład:

- (NSUInteger)hash {
    NSUInteger hash = 0;
    hash += [[self name] hash];
    hash += [[self data] hash];
    return hash;
}

Czy to wystarczy? Czy istnieje lepsza technika? Co jeśli masz prymitywy int? Konwertuj je, aby NSNumberuzyskać skrót? Lub struktury takie jak NSRect?

( Brain fart : Oryginalnie napisałem je „bitowe LUB” razem z nimi |=. Znacząco dodaj.)

Zacząć od

 NSUInteger prime = 31;
 NSUInteger result = 1;

Następnie dla każdego prymitywnego robicie

 result = prime * result + var

Dla obiektów używasz 0 dla zera, a poza tym ich hashcode.

 result = prime * result + [var hash];

Dla wartości logicznych używasz dwóch różnych wartości

 result = prime * result + ((var)?1231:1237);

Wyjaśnienie i przypisanie

To nie jest praca tcurdta, a komentarze prosiły o więcej wyjaśnień, więc uważam, że zmiana atrybucji jest uczciwa.

Algorytm ten został spopularyzowany w książce „Skuteczna Java”, a odpowiedni rozdział można obecnie znaleźć w Internecie tutaj . Ta książka spopularyzowała algorytm, który jest teraz domyślny w wielu aplikacjach Java (w tym w Eclipse). Wywodziło się to jednak od jeszcze starszej implementacji, którą w różny sposób przypisuje się Danowi Bernsteinowi lub Chrisowi Torek. Ten starszy algorytm pierwotnie krążył w sieci Usenet i pewne przypisanie jest trudne. Na przykład w tym kodzie Apache jest kilka interesujących komentarzy (szukaj ich nazw), które odwołują się do oryginalnego źródła.

Podsumowując, jest to bardzo stary, prosty algorytm mieszający. Nie jest najbardziej wydajny i nie udowodniono nawet matematycznie, że jest „dobrym” algorytmem. Ale to jest proste i wiele osób używało go od dawna z dobrymi wynikami, więc ma wiele historycznego wsparcia.

Po prostu wybieram Objective-C, więc nie mogę mówić konkretnie w tym języku, ale w innych językach, których używam, jeśli dwa wystąpienia są „równe”, muszą zwrócić ten sam skrót - w przeciwnym razie będziesz mieć wszystko rodzaje problemów podczas próby użycia ich jako kluczy w tablicy mieszającej (lub dowolnej kolekcji typu słownikowego).

Z drugiej strony, jeśli 2 instancje nie są równe, mogą mieć lub nie mieć tego samego skrótu - najlepiej, jeśli nie. Jest to różnica między wyszukiwaniem O (1) w tabeli skrótów a wyszukiwaniem O (N) - jeśli wszystkie twoje skróty się zderzą, może się okazać, że wyszukiwanie w tabeli nie jest lepsze niż przeszukiwanie listy.

Jeśli chodzi o najlepsze praktyki, skrót powinien zwracać losowy rozkład wartości dla danych wejściowych. Oznacza to, że na przykład jeśli masz wartość podwójną, ale większość twoich wartości ma tendencję do klastrowania między 0 a 100, musisz upewnić się, że skróty zwracane przez te wartości są równomiernie rozmieszczone w całym zakresie możliwych wartości skrótu . To znacznie poprawi Twoją wydajność.

Istnieje wiele algorytmów mieszających, w tym kilka wymienionych tutaj. Staram się unikać tworzenia nowych algorytmów mieszania, ponieważ może to mieć duży wpływ na wydajność, więc użycie istniejących metod mieszania i wykonanie kombinacji bitowej, tak jak w przykładzie, jest dobrym sposobem na uniknięcie tego.

Zwykły XOR ponad wartościami mieszania właściwości krytycznych wystarcza na 99% czasu.

Na przykład:

- (NSUInteger)hash
{
    return [self.name hash] ^ [self.data hash];
}

Rozwiązanie znalezione na stronie http://nshipster.com/equality/ przez Mattta Thompsona (który również odniósł się do tego pytania w swoim poście!)

Uważam, że ten wątek jest niezwykle pomocny, dostarczając wszystko, czego potrzebowałem, aby uzyskać moje metody isEqual:i hashmetody zaimplementowane za jednym razem. Podczas testowania zmiennych instancji obiektu w isEqual:przykładowym kodzie użyto:

if (![(id)[self name] isEqual:[aWidget name]])
    return NO;

To wielokrotnie nie powiodło się ( tj. Zwróciło NO ) bez i błąd, gdy wiedziałem, że obiekty były identyczne w moim testowaniu jednostkowym. Powodem było to, że jedna ze NSStringzmiennych instancji była zerowa, więc powyższa instrukcja brzmiała:

if (![nil isEqual: nil])
    return NO;

a ponieważ zero zareaguje na każdą metodę, jest to całkowicie legalne, ale

[nil isEqual: nil]

Zwraca nil , która jest NIE , więc, gdy zarówno obiekt i jeden testowany był zerowy przedmiotu byłyby uważane jest równe ( tj , isEqual:powróci NO ).

Ta prosta poprawka polegała na zmianie instrukcji if na:

if ([self name] != [aWidget name] && ![(id)[self name] isEqual:[aWidget name]])
    return NO;

W ten sposób, jeśli ich adresy są takie same, pomija wywołanie metody bez względu na to, czy oba są zerowe, czy oba wskazują na ten sam obiekt, ale jeśli albo nie jest zerowy, albo wskazują inne obiekty, wówczas komparator jest odpowiednio wywoływany.

Mam nadzieję, że zaoszczędzi to komuś drapanie w głowie.

Funkcja skrótu powinna utworzyć częściowo unikalną wartość, która prawdopodobnie nie zderzy się ani nie dopasuje wartości skrótu innego obiektu.

Oto pełna funkcja skrótu, którą można dostosować do zmiennych instancji klas. Używa NSUInteger zamiast int dla kompatybilności z aplikacjami 64 / 32bit.

Jeśli wynik zmienia się na 0 dla różnych obiektów, istnieje ryzyko kolizji skrótów. Kolizje skrótów mogą powodować nieoczekiwane zachowanie programu podczas pracy z niektórymi klasami kolekcji zależnymi od funkcji skrótu. Przed użyciem sprawdź działanie funkcji skrótu.

-(NSUInteger)hash {
    NSUInteger result = 1;
    NSUInteger prime = 31;
    NSUInteger yesPrime = 1231;
    NSUInteger noPrime = 1237;

    // Add any object that already has a hash function (NSString)
    result = prime * result + [self.myObject hash];

    // Add primitive variables (int)
    result = prime * result + self.primitiveVariable; 

    // Boolean values (BOOL)
    result = prime * result + (self.isSelected?yesPrime:noPrime);

    return result;
}

Prostym, ale nieefektywnym sposobem jest zwrócenie tej samej -hashwartości dla każdej instancji. W przeciwnym razie tak, musisz wdrożyć hash oparty tylko na obiektach, które wpływają na równość. Jest to trudne, jeśli używasz lekkich porównań w -isEqual:(np. Porównania ciągów znaków bez rozróżniania wielkości liter). W przypadku liczb całkowitych możesz ogólnie użyć samej liczby wewnętrznej, chyba że będziesz porównywał z numerami NSNumbers.

Nie używaj | =, jednak będzie nasycone. Zamiast tego użyj ^ =.

Ciekawy fakt:, [[NSNumber numberWithInt:0] isEqual:[NSNumber numberWithBool:NO]]ale [[NSNumber numberWithInt:0] hash] != [[NSNumber numberWithBool:NO] hash]. (rdar: // 4538282, otwarte od 05 maja 2006)

Pamiętaj, że wystarczy podać skrót, który jest równy, gdy isEqualjest prawdziwy. Kiedy isEqualjest fałszem, skrót nie musi być nierówny, choć prawdopodobnie tak jest. W związku z tym:

Prosty skrót. Wybierz najbardziej charakterystyczną zmienną członka (lub kilku członków).

Na przykład w przypadku CLPlacemark wystarczy sama nazwa. Tak, są 2 lub 3 znaki CLPlacemark o dokładnie takiej samej nazwie, ale są one rzadkie. Użyj tego skrótu.

@interface CLPlacemark (equal)
- (BOOL)isEqual:(CLPlacemark*)other;
@end

@implementation CLPlacemark (equal)

...

-(NSUInteger) hash
{
    return self.name.hash;
}


@end

Zauważ, że nie zawracam sobie głowy określaniem miasta, kraju itp. Nazwa jest wystarczająca. Być może nazwa i lokalizacja CLL.

Hash powinien być równomiernie rozłożony. Możesz połączyć kilka zmiennych składowych za pomocą znaku karetki ^ (znak xor)

To coś w stylu

hash = self.member1.hash ^ self.member2.hash ^ self.member3.hash

W ten sposób skrót będzie równomiernie rozłożony.

Hash must be O(1), and not O(n)

Co więc robić w tablicy?

Znowu proste. Nie musisz mieszać wszystkich członków tablicy. Wystarczy haszować pierwszy element, ostatni element, liczbę, może jakieś środkowe elementy i to wszystko.

Poczekaj, z pewnością znacznie łatwiejszym sposobem na to jest najpierw przesłonięcie - (NSString )descriptioni przedstawienie ciągu reprezentującego stan obiektu (musisz reprezentować cały stan obiektu w tym ciągu).

Następnie podaj następującą implementację hash:

- (NSUInteger)hash {
    return [[self description] hash];
}

Opiera się to na zasadzie, że „jeśli dwa ciągi znaków są równe (zgodnie z metodą isEqualToString: metoda), muszą mieć tę samą wartość skrótu”.

Źródło: NSString Class Reference

Kontrakty typu equals i hash są dobrze określone i dokładnie zbadane w świecie Java (patrz odpowiedź @ mipardi), ale wszystkie te same uwagi powinny mieć zastosowanie do Celu-C.

Eclipse wykonuje niezawodne zadanie generowania tych metod w Javie, więc oto przykład Eclipse przeniesiony ręcznie do Objective-C:

- (BOOL)isEqual:(id)object {
    if (self == object)
        return true;
    if ([self class] != [object class])
        return false;
    MyWidget *other = (MyWidget *)object;
    if (_name == nil) {
        if (other->_name != nil)
            return false;
    }
    else if (![_name isEqual:other->_name])
        return false;
    if (_data == nil) {
        if (other->_data != nil)
            return false;
    }
    else if (![_data isEqual:other->_data])
        return false;
    return true;
}

- (NSUInteger)hash {
    const NSUInteger prime = 31;
    NSUInteger result = 1;
    result = prime * result + [_name hash];
    result = prime * result + [_data hash];
    return result;
}

A dla podklasy, YourWidgetktóra dodaje właściwość serialNo:

- (BOOL)isEqual:(id)object {
    if (self == object)
        return true;
    if (![super isEqual:object])
        return false;
    if ([self class] != [object class])
        return false;
    YourWidget *other = (YourWidget *)object;
    if (_serialNo == nil) {
        if (other->_serialNo != nil)
            return false;
    }
    else if (![_serialNo isEqual:other->_serialNo])
        return false;
    return true;
}

- (NSUInteger)hash {
    const NSUInteger prime = 31;
    NSUInteger result = [super hash];
    result = prime * result + [_serialNo hash];
    return result;
}

Ta implementacja pozwala uniknąć niektórych pułapek podklas w przykładzie isEqual:od Apple:

• Test klasy Apple other isKindOfClass:[self class]jest asymetryczny dla dwóch różnych podklas MyWidget. Równość musi być symetryczna: a = b wtedy i tylko wtedy, gdy b = a. Można to łatwo naprawić, zmieniając test na other isKindOfClass:[MyWidget class], wówczas wszystkie MyWidgetpodklasy byłyby wzajemnie porównywalne.
• Użycie isKindOfClass:testu podklasy zapobiega zastąpieniu podklas isEqual:za pomocą udoskonalonego testu równości. Wynika to z faktu, że równość musi być przechodnia: jeśli a = b i a = c, to b = c. Jeśli MyWidgetinstancja jest równa dwóm YourWidgetinstancjom, YourWidgetmuszą one być sobie równe, nawet jeśli serialNoróżnią się między sobą.

Drugi problem można rozwiązać, biorąc pod uwagę, że obiekty są równe, jeśli należą do dokładnie tej samej klasy, stąd [self class] != [object class]test tutaj. W przypadku typowych klas aplikacji wydaje się to najlepsze podejście.

Jednak z pewnością istnieją przypadki, w których isKindOfClass:test jest lepszy. Jest to bardziej typowe dla klas frameworku niż klas aplikacji. Na przykład każdy NSStringpowinien się równać z innymi NSStringz tą samą leżącą u podstaw sekwencją znaków, niezależnie od NSString/ NSMutableStringrozróżnienia, a także niezależnie od tego, jakie klasy prywatne w NSStringklastrze klas są zaangażowane.

W takich przypadkach isEqual:powinny mieć dobrze zdefiniowane, dobrze udokumentowane zachowanie i należy wyjaśnić, że podklasy nie mogą tego zastąpić. W Javie ograniczenie „bez wymuszania” można wymusić, oznaczając metody equals i hashcode jako final, ale Cel C nie ma odpowiednika.

To nie odpowiada bezpośrednio na twoje pytanie (w ogóle), ale wcześniej użyłem MurmurHash do generowania skrótów : murmurhash

Chyba powinienem wyjaśnić, dlaczego: szmer jest cholernie szybki ...

Uważam, że ta strona jest pomocnym przewodnikiem w zastępowaniu metod równych i mieszających. Zawiera przyzwoity algorytm obliczania kodów skrótu. Strona jest ukierunkowana na Javę, ale dość łatwo jest ją dostosować do Objective-C / Cocoa.

Jestem newbie zbyt Objective C, ale znalazłem doskonały artykuł na temat równości wobec tożsamości w Objective C tutaj . Z mojego czytania wynika, że ​​możesz zachować domyślną funkcję skrótu (która powinna zapewnić unikalną tożsamość) i wdrożyć metodę isEqual, aby porównać wartości danych.

Quinn się myli, że odniesienie do skrótu szmeru jest tutaj bezużyteczne. Quinn ma rację, że chcesz zrozumieć teorię mieszania. Szmer destyluje wiele z tej teorii do implementacji. Warto zastanowić się, jak zastosować tę implementację w tej konkretnej aplikacji.

Niektóre kluczowe punkty tutaj:

Przykładowa funkcja z tcurdt sugeruje, że „31” jest dobrym mnożnikiem, ponieważ jest liczbą pierwszą. Trzeba pokazać, że bycie najlepszym jest warunkiem koniecznym i wystarczającym. W rzeczywistości 31 (i 7) prawdopodobnie nie są szczególnie dobrymi liczbami pierwszymi, ponieważ 31 == -1% 32. Dziwny mnożnik z około połową ustawionych bitów i połową bitów czystych prawdopodobnie będzie lepszy. (Stała mnożenia wartości skrótu ma tę właściwość).

Ten typ funkcji skrótu byłby prawdopodobnie silniejszy, gdyby po pomnożeniu wartość wyniku była regulowana za pomocą shift i xor. Mnożenie prowadzi do uzyskania wyników wielu interakcji bitowych na górnym końcu rejestru i niskich wyników interakcji na dolnym końcu rejestru. Shift i Xor zwiększają interakcje na dolnym końcu rejestru.

Przydatne byłoby również ustawienie początkowego wyniku na wartość, w której około połowa bitów to zero, a około połowa bitów to jeden.

Przydatne może być zachowanie ostrożności w kolejności łączenia elementów. Prawdopodobnie należy najpierw przetworzyć wartości logiczne i inne elementy, w których wartości nie są silnie rozłożone.

Przydatne może być dodanie kilku dodatkowych etapów szyfrowania bitów na końcu obliczeń.

To, czy skrót szmeru jest naprawdę szybki dla tej aplikacji, jest pytaniem otwartym. Hash szmeru miesza bitów każdego słowa wejściowego. Wiele słów wejściowych może być przetwarzanych równolegle, co pomaga w wielu problemach z przetwarzaniem potokowym.

Łącząc odpowiedź @ tcurdt z odpowiedzią @ oscar-gomez dotyczącą uzyskiwania nazw właściwości , możemy stworzyć łatwe rozwiązanie dla isEqual i hash:

NSArray *PropertyNamesFromObject(id object)
{
    unsigned int propertyCount = 0;
    objc_property_t * properties = class_copyPropertyList([object class], &propertyCount);
    NSMutableArray *propertyNames = [NSMutableArray arrayWithCapacity:propertyCount];

    for (unsigned int i = 0; i < propertyCount; ++i) {
        objc_property_t property = properties[i];
        const char * name = property_getName(property);
        NSString *propertyName = [NSString stringWithUTF8String:name];
        [propertyNames addObject:propertyName];
    }
    free(properties);
    return propertyNames;
}

BOOL IsEqualObjects(id object1, id object2)
{
    if (object1 == object2)
        return YES;
    if (!object1 || ![object2 isKindOfClass:[object1 class]])
        return NO;

    NSArray *propertyNames = PropertyNamesFromObject(object1);
    for (NSString *propertyName in propertyNames) {
        if (([object1 valueForKey:propertyName] != [object2 valueForKey:propertyName])
            && (![[object1 valueForKey:propertyName] isEqual:[object2 valueForKey:propertyName]])) return NO;
    }

    return YES;
}

NSUInteger MagicHash(id object)
{
    NSUInteger prime = 31;
    NSUInteger result = 1;

    NSArray *propertyNames = PropertyNamesFromObject(object);

    for (NSString *propertyName in propertyNames) {
        id value = [object valueForKey:propertyName];
        result = prime * result + [value hash];
    }

    return result;
}

Teraz w swojej klasie niestandardowej możesz łatwo wdrożyć isEqual:i hash:

- (NSUInteger)hash
{
    return MagicHash(self);
}

- (BOOL)isEqual:(id)other
{
    return IsEqualObjects(self, other);
}

Pamiętaj, że jeśli tworzysz obiekt, który można mutować po utworzeniu, wartość skrótu nie może ulec zmianie, jeśli obiekt zostanie wstawiony do kolekcji. W praktyce oznacza to, że wartość skrótu musi zostać ustalona od momentu początkowego utworzenia obiektu. Aby uzyskać więcej informacji, zobacz dokumentację Apple dotyczącą metody -hash protokołu NSObject :

Jeśli zmienny obiekt zostanie dodany do kolekcji, która korzysta z wartości skrótu w celu ustalenia pozycji obiektu w kolekcji, wartość zwrócona przez metodę skrótu obiektu nie może się zmienić, gdy obiekt jest w kolekcji. Dlatego albo metoda mieszania nie może polegać na żadnej z wewnętrznych informacji o stanie obiektu, albo musisz upewnić się, że wewnętrzne informacje o stanie obiektu nie ulegną zmianie, gdy obiekt znajduje się w kolekcji. Tak więc, na przykład, słownik zmiennych można umieścić w tablicy haszującej, ale nie wolno jej zmieniać, gdy jest w niej. (Należy pamiętać, że może być trudno ustalić, czy dany obiekt znajduje się w kolekcji).

Dla mnie to brzmi jak kompletna walka, ponieważ potencjalnie skutecznie sprawia, że ​​wyszukiwanie skrótów jest znacznie mniej wydajne, ale przypuszczam, że lepiej jest zachować ostrożność i postępować zgodnie z tym, co mówi dokumentacja.

Przepraszam, jeśli zaryzykuję sformułowanie kompletnego buminu tutaj, ale ... ... nikt nie zadał sobie trudu, by wspomnieć, że przestrzegając „najlepszych praktyk”, zdecydowanie nie powinieneś określać metody równości, która NIE uwzględniałaby wszystkich danych posiadanych przez obiekt docelowy, np. dane są agregowane do twojego obiektu, w porównaniu z jego powiązaniem, należy wziąć pod uwagę przy wdrażaniu równości. Jeśli nie chcesz brać pod uwagę, powiedz „wiek” w porównaniu, powinieneś napisać komparator i użyć go do wykonania porównań zamiast isEqual :.

Jeśli zdefiniujesz metodę isEqual: arbitralnie wykonującą porównanie równości, poniesiesz ryzyko, że ta metoda zostanie niewłaściwie wykorzystana przez innego programistę, a nawet przez ciebie samego, gdy zapomnisz o „zakręcie” w interpretacji równości.

Ergo, chociaż jest to świetne pytanie dotyczące haszowania, zwykle nie trzeba na nowo definiować metody haszowania, prawdopodobnie zamiast tego należy zdefiniować komparator ad-hoc.