Witam,
w jaki sposób najefektywniej mogę usunąć duplikaty z DUŻEJ listy typu <MójObiekt>, sprawdzając duble pod kątem konkretnych pól?
np. MójObiekt posiada pola: id, a, b, c, d, e, f
Posiadam listę z np 500 000 el. i chciałbym z niej usunąć elementy o tych samych wartościach A, C, F.
W jaki sposób mogę tego dokonać w najkrótszym czasie?
Pozdrawiam
Możesz spróbować tego:
http://stackoverflow.com/questions/30366669/most-efficient-way-to-remove-duplicates-from-a-list
To się pewnie wiąże z przesłonięciem takich metod jak equals, getHashCode, czy operator==. Ale chyba nie ma innej drogi.
Mógłbyś też zwracać unikalne hashe dla konkretnych elementów. I wtedy albo dictionary, gdzie kluczem jest hash - bardzo szybko wtedy nie pozwolisz na dodanie duplikatu, albo po prostu będziesz porównywał po hashu.
Tylko, jeśli zapisujesz tą listę do pliku, czy do bazy, to musisz pamiętać, żeby nie zapisywać hasha, tylko tworzyć go zawsze po wczytaniu listy. Chyba, że zrobisz własny mechanizm dla hashy i on się nigdy nie zmieni.
W jaki sposób mogę zwracać unikalne hashe biorąc pod uwagę to że pozostałe parametry mogą być różne?
Możesz przeciążyć GetHashCode tak, aby brała tylko interesujące Cie wartości pod uwagę.
A co jest źródłem danych w tej liście?
Dane wyciągane są z bazy.
To może zamiast je usuwać z listy, po prostu nie pobieraj tych zbędnych?
Ale ja je potrzebuje tylko po jednej sztuce
Jeśli potrzebujesz jednej sztuki, to po co Ci lista?
Sprecyzuj co chcesz osiągnąć.
Nie zrozumieliśmy się :)
Mam listę typu MojaKlasa która posiada np. 500 000 elementów
Klasa posiada pola A, B, C, D
100 000 elementów z tej listy ma taką samą wartość B,C,D, ale różną wartość A, dlatego distinct sobie z tym nie poradzi, chce odfiltrować te duplikaty i zostawić tylko jeden obiekt z tych 100 000.
Powiedzmy, że pozostałe elementy też mają taką zależność więc w wyniku końcowym nadal mieć listę typu MojaKlasa która zwróci wg opisanego przykładu 5 obiektów.
Aktualnie próbuję zaimplementować IEqualityComparer jednak nie wiem jak obsłużyć GetHashCode w przypadku jeśli pole może być nullem (long?) oraz jeśli jest obiektem który może być np. tablicą.
Odnośnie tego jak liczyć hasha na podstawie już istniejących hashy z naszych pól, to właśnie się natknął na to na stackoverflow:
http://stackoverflow.com/questions/263400/what-is-the-best-algorithm-for-an-overridden-system-object-gethashcode/263416#263416
@drakoo, a ja Ci mówię, żeby zamiast pobierać z bazy 500 tys elementów pobrał tylko 400 tys (czy ile Ci tam trzeba).
Niestety odsianie po stronie bazy odpada, poza tym zapytanie które by odsiewało takie duble trwało by znacznie dłużej niż zrobienie tego po stronie c#.
Zaimplementowałem taką metode:
public int GetDataHashCode(MyClass obj)
{
long idLoc = obj.IdLoc.HasValue ? obj.IdLoc.Value : 0;
long idMet = obj.IdMet.HasValue ? obj.IdMet.Value : 0;
long ser = obj.SerHasValue ? obj.Ser.Value : 0;
int valueHash = 0;
if (obj.Value != null)
valueHash = obj.Value.GetHashCode();
else
valueHash = valueHash.GetHashCode();
return (idLoc.GetHashCode() + idMet.GetHashCode() + ser.GetHashCode() + valueHash + obj.IdDataType.GetHashCode() + obj.Time.GetHashCode()).GetHashCode();
}
Póki co kręcę się foreachem po danych wyznaczam hashcode i wkładam do słownika. Przetworzenie w taki sposób 750 000 elementów zajmuje około 0,2 sekundy!
Nie zapomnij tylko po tym jak hashe się zgodzą porównywać obiektów czy rzeczywiście są takie same pole po polu, bo mówią delikatnie przy takiej implementacji możesz mieć sporo kolizji.
Skad wniosek, ze odsianie po stronie bazy zajmie sluzej niz jakims foreachem?
neves napisał(a):
Nie zapomnij tylko po tym jak hashe się zgodzą porównywać obiektów czy rzeczywiście są takie same pole po polu, bo mówią delikatnie przy takiej implementacji możesz mieć sporo kolizji.
Sam hash nie zapewni mi że na pewno są takie same?
Czyli co lepiej zaimplementować IEqualityComparer który zawiera gethash oraz equals, problem w tym że nie wiem jak w Equals porównywać typ Object
Hash Ci jednoznacznie zidentyfikuje obiekt, jeśli go tak napiszesz. Jeśli np. Twoja metoda GetHashCode będzie wyglądała tak:
return a + b + c + d;
To na pewno nie będziesz miał unikalnych haszy.
Jeśli używasz w jakiś sposób domyślnej metody, musisz uważać na to, co pisze MS:
Two objects that are equal return hash codes that are equal. However, the reverse is not true: equal hash codes do not imply object equality, because different (unequal) objects can have identical hash codes. Furthermore, the .NET Framework does not guarantee the default implementation of the GetHashCode method, and the value this method returns may differ between .NET Framework versions and platforms, such as 32-bit and 64-bit platforms. For these reasons, do not use the default implementation of this method as a unique object identifier for hashing purposes
(https://msdn.microsoft.com/pl-pl/library/system.object.gethashcode(v=vs.110).aspx)
W prawdzie nie spotkałem się z tym, żeby różne obiekty dały ten sam hash code, ale to jest możliwe. Chociaż jestem ciekawy, czy ktoś wie, jaka jest szansa na to?
Juhas napisał(a):
Chociaż jestem ciekawy, czy ktoś wie, jaka jest szansa na to?
Policz sobie na podstawie wielkości zbioru obiektów oraz wielkości zbioru możliwych wartości zwracanych z GetHashCode (czyli int.MaxValue).
Takie filtrowanie powinno się odbyć na etapie wyciągania danych z bazy.
neves napisał(a):
Nie zapomnij tylko po tym jak hashe się zgodzą porównywać obiektów czy rzeczywiście są takie same pole po polu, bo mówią delikatnie przy takiej implementacji możesz mieć sporo kolizji.
Czyli w końcu jak mam się do tego odnieść?
class Comparer : IEqualityComparer<MyClass>
{
public bool Equals(MyClass x, MyClass y)
{
int xValue = x.Value.GetHashCode();
int yValue = y.Value.GetHashCode();
return x.IdLoc == y.IdLoc && x.IdMet == y.IdMet && x.Ser == y.Ser &&
x.IdDataType == y.IdDataType && x.Time == y.Time && xValue == yValue;
}
public int GetHashCode(MyClass obj)
{
long idLoc = obj.IdLoc.HasValue ? obj.IdLoc.Value : 0;
long idMet = obj.IdMet.HasValue ? obj.IdMet.Value : 0;
long ser = obj.Ser.HasValue ? obj.Ser.Value : 0;
int valueHash = 0;
if (obj.Value != null)
valueHash = obj.Value.GetHashCode();
else
valueHash = valueHash.GetHashCode();
return (idLoc.GetHashCode() + idMet.GetHashCode() + ser.GetHashCode() + valueHash + obj.IdDataType.GetHashCode() + obj.Time.GetHashCode()).GetHashCode();
}
}
W ten sposób lepiej?
Lepiej, nie jest to najbardziej optymalny sposób (sposób liczenia hasha, i używania hashy w bezpośrednim porównywaniu), no ale jeśli nie zrobiłeś błędu w metodzie porównującej (czego nie da się stwierdzić bez wiedzy jak wygląda obiekt i co decyduje o jego unikalności od innych), to powinno śmigać :).
Mam problem z: valueHash = obj.Value.GetHashCode();
Value to zmienna typu Object w ktorej mam tablice bajtów byte[7] z takimi samymi wartościami, jednak za każdym razem jest dla niej generowany inny hashcode, jak mogę sobie z tym poradzić?
Tablica jest typem referencyjnym, więc domyślnie zarówno GetHashCode jaki i Equals porównuje referencje, musisz zrobić to samo co dla obiektu, czyli napisać własną implementację aby porównywać zawartość, tak jak tutaj chociażby:
http://stackoverflow.com/questions/7244699/gethashcode-on-byte-array