How to compare two generic dictionaries

Zilele acestea mi-a fost pusa urmatoarea intrebare:

Intr-un unit test care este cea mai buna modalitate de a compara doua colectii?

Daca va aduceti aminte, in urma cu cateva saptamani am discutat despre CollectionAssert. Aceasta contine o metoda denumita AreEquivalent, care verifica daca doua colectii sunt echivalente. Testul o sa treaca de acest assert daca:

• numarul de elemente este egal
• cele doua colectii contin aceleasi elemente( indiferent de ordinea in care apar)

Doua elemente din colectie sunt egale nu daca puncteaza spre acelasi element ci daca sunt egale prin continut( se apeleaza metoda Equals, pentru a face aceasta verificare). In cazul nostru, metoda AreEquivalent o sa itereze prin intreaga colectie de element KeyValuePair pe care un dictionar le contine.

Dictionary<string,string> collection1=new Dictionary<string, string>();
Dictionary<string, string> collection2 = new Dictionary<string, string>();
...
CollectionAssert.AreEquivalent(collection1,collection2);

In cazul in care avem nevoie in cod sa comparam doua dictionare putem sa face in felul urmator:

collection1
    .OrderBy(i => i)
    .SequenceEqual(collection2.OrderBy(i => i));

Varianta de mai sus este O(n*log(n)). In cazul in care vreti o solutie in O(n), puteti sa incercati o implementare asemanatoare cu aceasta:

public class CollectionComparer<T> : IEqualityComparer<IEnumerable<T>>
    where T : class
{
    public bool Equals(IEnumerable<T> collection1, IEnumerable<T> collection2)
    {
        if ((collection1 == null && collection2!=null)
            || (collection2 == null && collection1!=null))
        {
            return false;
        }

        if (ReferenceEquals(collection1, collection2))
        {
            return true;
        }

        int collection1Count = collection1.Count();
        if (collection1Count != collection2.Count())
        {
            return false;
        }
               
        return collection1Count == 0
            || !AreCollectinDifferent(collection1, collection2);
    }

    private static bool AreCollectinDifferent(IEnumerable<T> collection1, IEnumerable<T> collection2)
    {
        int collection1Count;
        int collection2Count;

        var firstElementCounts = GetElementCounts(collection1, out collection1Count);
        var secondElementCounts = GetElementCounts(collection2, out collection2Count);

        if (collection1Count != collection2Count)
        {
            return true;
        }

        foreach (KeyValuePair<T,int> keyValuePair in firstElementCounts)
        {
            collection1Count = keyValuePair.Value;
            secondElementCounts.TryGetValue(keyValuePair.Key, out collection2Count);

            if (collection1Count != collection2Count)
            {
                return true;
            }
        }

        return false;
    }

    private static Dictionary<T, int> GetElementCounts(IEnumerable<T> enumerable,
                                                        out int nullCount)
    {
        var dictionary = new Dictionary<T, int>();
        nullCount = 0;
        int value;

        foreach (T element in enumerable)
        {
            if (element == null)
            {
                nullCount++;
                continue;
            }

               
            dictionary.TryGetValue(element, out value);
            dictionary[element] = ++value;
        }

        return dictionary;
    }

    public int GetHashCode(IEnumerable<T> enumerable)
    {
        return enumerable
                .OrderBy(x => x)
                .Aggregate(
                    11,
                    (current, val) => current*13 + val.GetHashCode());
    }
}

Enjoy!

Read More

Dictionary - custom key type

In ultimele 2 saptamani am luat la puricat .NET Collections si m-am gandit ca merita sa vorbim astazi putin despre cheile unui dictionar( Dictionary) - map.
In general lucram cu chei care sunt de tip value type.

Dictionary<int, Door> map = new Dictionary<int, Door>();
map.Add(1,door1);
map.Add(2,door2);
...
var door1 = map[1];

In acest caz, cheia o sa fie gasita fara nici o problema. Dar ce se intampla cand cheia noastra este reprezentata de un tip declarat de noi?

Dictionary<DoorKey,Door> map = new Dictionary<DoorKey, Door>();
map.Add(doorKey1, door1);
map.Add(doorKey2, door2);
....
var door1 = map[copyOfDoorKey1];

In momentul cand o sa dorim sa facem retrive la element pe baza de cheie, o sa observam ca elementul nu este gasit( o eroare de tip KeyNotFoundException o sa fie aruncata). In debug daca ne uitam la ce elemente contine dictionarul, o sa observam ca avem doua elemente cu cheiule pe care le-am astepta, dar totusi nu putem sa facem retrive la date.
Fiecare colectie de tip (cheie,valoare) are implementari diferete, dar in general una sau mai multe elemente sunt grupate intr-un bucket( galeata), pe baza la hash code. Dimensiunea sau distributia pe valori a acestuia difera, dar ce trebuie sa retinem aici este ca fiecare element este adaugat intr-un anumit bucket pe baza unui hash returnat de catre cheie. Dupa ce este identificat bucket-ul, se face o cautare a cheii in bucket-ul respectiv pe baza metodei Equal.
Indiferent de metoda de implementare a dictionarului, cautarea se face pe baza acestor doua metode. Din acesta cauza, in exemplul dat mai sus o sa ne trezim ca elementul nu este gasit niciodata, chiar daca teoretic in colectie avem cheie data.
Pentru toate tipurile de date pe care o sa le folosim pe post de cheie, este nevoie sa facem override la GetHashCode si Equal. Mai jos putem sa gasim un exemplu pentru clasa DoorKey

class Doorkey
{
    int RoomNumber { get; set; }
    int DoorNumber {get; set; }
    public override bool Equals(object obj)
    {
        if( obj == null
            || !( obj is DoorKey ))
        {
            return false
        }
        return RoomNumber == obj.RoomNumber
            && DoorNumber == obj.DoorNumber
    }
    public override int GetHashCode()
{
    return RoomNumber.GetHashCode();
}
}

Pentru metoda GetGashCode, aceasta nu este cea mai buna implementara. Cea mai importanta regula pe care metoda GetHashCode trebuie sa o respecte este ca valoarea returnata sa fie aceiasi pentru un obiect care are aceiasi stare( valoare).
Asa ca, de fiecare data cand lucram cu dictionarele( maps) din .NET, iar cheile sunt reprezentate de tipuri custom, nu trebuie sa uitam sa facem ovveride la GetHashCode si Equals, in caz contrat o sa ne trezim ca nu putem sa obtinem datele pe baza cheii.

Read More

LINQ: ToDictionary

Se da o lista de obiecte care trebuie convertite intr-un dictionar.
O prima implementare la aceasta ar putea sa fie:

Dictionary<string,Car> dictionary=new Dictionary<string, Car>();
            foreach (var car in cars)
            {
                dictionary.Add(car.Code,car);
            }

Putem avea diferite implementări, in diferite moduri. Ce nu trebuie sa uitam ca LINQ ne ofera aceasta posibilitate folosind metoda "ToDictionary".
Cea mai simpla varianta primeste un singur parametru, care specifica cheia key-ul care o sa fie folosit pentru fiecare element care se adauga in dictionar:

Dictionary<string,Car> dictionary= cars.ToDictionary(car => car.Code);

Un alt overload la aceasta metoda ne permite sa specificam si item-ul care se adauga pentru key-ul dat:

Dictionary<string, string> dictionary = cars.ToDictionary(car => car.Code, car => car.Model);

Spor!.

Read More