Dependency Injection та Inversion of Control контейнер

Одним з найпоширеніших методів зменешення звязаності компонентів алпікації є заміна обєктів конкретного типу на інтерфейси, що сьогодні я постараюсь коротенько описати.

Dependency Injection

Отож наша тестова аплікація умовно працюватиме з базою даних, відповідно маємо клас DbRepository який начебто реалізує роботу з базою даних та клас WithoutDI який як понятно з назви не використовує фічу про яку я сьогодні пишу, а умовно містить в собі певну логіку яка виконується перед тим як працювати з даними збереженими в БД.

На прикладі ци виглядатиме наступним чином:

   1: /// <summary>

   2: /// Class without Dependency Injection

   3: /// </summary>

   4: class WithoutDI

   5: {

   6:     DbRepository _repository = new DbRepository();

   7:  

   8:     public void UseRepo()

   9:     {

  10:         // Dummy logic.

  11:  

  12:         Console.WriteLine("I am " + this.GetType().Name + " and I work with " + _repository.GetType().Name);

  13:     }

  14: }

Як видно з коду наш клас має жорстку привязку до класу DbRepository і відповідно, якщо ми захочемо замінити репозиторій на інший то нам також придеться зайти в клас WithoutDI і змінити назву класу(DbRepository ) на нову. Ще одна проблема, яка не одразу кидається в очі, це те, що відтестуватитакий клас складно так як він в теорії працює з реальною базою даних і відповідно виклик любого з методів буде мати вплив на дані в базі. Отож ми трохи змінюємо код і в результаті отримуємо щось типу:

   1: /// <summary>

   2: /// Class with Dependency Injection

   3: /// </summary>

   4: class WithDI

   5: {

   6:     private IRepository _repository;

   7:  

   8:     public WithDI(IRepository repository)

   9:     {

  10:         _repository = repository;

  11:     }

  12:  

  13:     public void UseRepo()

  14:     {

  15:         // Dummy logic.

  16:  

  17:         Console.WriteLine("I am " + this.GetType().Name + " and I work with " + _repository.GetType().Name);

  18:     }

  19: }

В даному випадку ми приймаємо репозиторій з яким ми будемо працювати в конструкторі, при цьому не конкретний а інтерфейс, що в свою чергу дозволяє передати туди любий обєкт який наслідує цей інтерфейс. Наприклад якщо в нас є декілька реалізацій репозиторіїв то ми можемо використати їх наступним чином:

   1: WithDI withDbDi = new WithDI(new DbRepository());

   2: WithDI withFileDi = new WithDI(new FileRepository());

   3:  

   4: withDbDi.UseRepo();

   5: withFileDi.UseRepo();

В першому випадку ми будемо працювати з репозиторієм бази даних, а в другому з репозиторієм який зберігає дані в файл.

Inversion of Control

IOC контейнер це абстракція яка виносить реєстрацію всіх залежностей в одне місце і автоматично створює необхідні обєкти там де вони потрібні. Опис в мене получився не дуже зрозумілий так що краще розглянемо на прикладі. Я створив простенький клас основною метою якого є реєстрація та повернення створених обєктів. Ось його код:

   1: /// <summary>

   2: /// My as simple as possible IOC 

   3: /// </summary>

   4: class IOC

   5: {

   6:     Dictionary<string, object> dependencies = new Dictionary<string, object>();

   7:  

   8:     public void Register(string name, object obj)

   9:     {

  10:         dependencies.Add(name, obj);

  11:     }

  12:  

  13:     public object Resolve(string name)

  14:     {

  15:         return dependencies[name];

  16:     }

  17: }

Код не містить жодних перевірок і тд для того щоб була зрозуміла основна ідея.

Використати його дуже просто

   1: IOC ioc = new IOC();

   2:  

   3: ioc.Register("someRepo", new DbRepository());

   4: ioc.Register("OtherRepo", new FileRepository());

В місці де нам потрібний обєкт просто викликаємо метод Resolve з іменем обєкту який ми хочемо отримати.

   1: /// <summary>

   2: /// Class with Dependency Injection

   3: /// </summary>

   4: class WithIOC

   5: {

   6:     private IRepository _repository;

   7:  

   8:     public WithIOC(IOC ioc)

   9:     {

  10:         _repository = (IRepository)ioc.Resolve("someRepo");

  11:     }

  12:  

  13:     public void UseRepo()

  14:     {

  15:         // Dummy logic.

  16:  

  17:         Console.WriteLine("I am " + this.GetType().Name + " and I work with " + _repository.GetType().Name + "recieved from IOC");

  18:     }

  19: }

Таким чином в нас для того щоб змінити один репозиторій на інший треба просто зарєеструвати в одному місці той обєкт якй нам потрібно і відповідно всюди по коду де витягується обєкт за цим іменем буде повернено інший обєкт.

Тобто в нас в коді є одне місце в якому можна керувати тим яким репозиторієм ми будемо користуватись і в випадку коли ми тестуємо код або змінюємо тип репозиторія ми можемо зробити це в одному місці, простою зміною обєкту який пхається в ІОС. Спільне використання цих технік сприєя не лише кращому тестуванню, але й має багато інших позитивних моментів Для кращого розуміння вартує перечитати ще декілька статей на тему, бо головною метою для себе поставив лише короткий опис, а сама тема досить фундаментальна і її знання обовязкове.

Стаття Мартіна Фовлера: http://martinfowler.com/articles/injection.html

Код: https://github.com/BatsIhor/DI_and_IOC_demo/

Алгоритми. Пошук через об'єднання та швиде об'єднання

Union Find один з базових алгоритмів і він демонструє як простий алгоритм може бути використаний для досить таки серйозних задач. Отож для початку я покажу малюнок для того щоб заманити вас почитати а далі перейду до пояснень.

https://www.facebook.com/note.php?note_id=469716398919

http://griffsgraphs.com/2012/07/02/a-facebook-network/

Ці малюнки фактично відображають звязки між користувачами в соціальних мережах, і працювати з ними досить таки важко, адже наприклад фейсбук має більше як пів мільярда активних користувачів. Павутина яку вони створюють дуже обємна її не те що важко описати її ще й потрібно обробляти, а обробка відбувається постійно. Часто в соц мережах ми можемо побачити повідомлення про те, що якась особа має з вами стільки то спільних друзів і можливо ви її знаєте. Отож побудований певний алогритм, який дає можливість просто визначити звязаних між собою людей навіть через декілька проміжних ланок.

Union Find дає змогу на основі звязків між елементами легко визначити чи будь який з величезного набору елементів звязаний з іншим елементом цього набору без використання купи циклів та інших “важких” операції.

Давайте розглянемо такий приклад:

Маємо вхідні дані:

Розмір масиву – 10

Звязки між елементами

1:2    2:3    3:4    8:2    5:7

Необхідно визначити чи елементи 1 та 8 зєднані та чи 0 і 5 зєднані.

Перш за все створимо масив:

індекси масиву: 0 1 2 3 4 5 6 7 8 9

дані в масиві   : 0 1 2 3 4 5 6 7 8 9

Тут необхідне невеличке пояснення, перш за все індекси масиву це фактично положення елементів в масиві. Так як в сішарппі нумерація починається з 0 ми маємо відповідні індекси. Це незмінні дані які просто вказують на комірку масиву, відповідно якщо мені треба пятий елемент масиву я вказую індекс [5] тобто вказую індекс елементу який нам треба витягнути.

Дані в масиві я записав відповідно до їх положення в масиві, тобто в даному прикладі елемент за індексом [4] = 4.

В коді це виглядає досить просто:

   1: class QuickFindUF

   2:     {

   3:         int[] id = new int[10];

   4:  

   5:         public QuickFindUF()

   6:         {

   7:             for (int i = 0; i < id.Length; i++)

   8:             {

   9:                 id[i] = i;

  10:             }

  11:         }

  12: .................................

Ми просто в конструкторі заповнюємо масив необхідними даними.

Обєднання

Операція обєднування буде робити досить просту річ вона буде змінювати дані в масиві таким чином що значення записане за індексом буде вказувати на елемент з яким ця комірка звязана.

Виконаємо команду обєднування 1:2 в результаті обєднання ми отримаємо

індекси масиву: 0 1 2 3 4 5 6 7 8 9

дані в масиві :   0 2 2 3 4 5 6 7 8 9

Тобто елемент за індекосом [1] звязаний з елементом на який вказує його значення тобто з елементом за індексом [2]

якщо зараз ми виконаємо ще декілька обєдань то по черзі отримаємо

2:3

індекси масиву: 0 1 2 3 4 5 6 7 8 9

дані в масиві :   0 3 3 3 4 5 6 7 8 9

3:4

індекси масиву: 0 1 2 3 4 5 6 7 8 9

дані в масиві :   0 4 4 4 4 5 6 7 8 9

8:2

індекси масиву: 0 1 2 3 4 5 6 7 8 9

дані в масиві :   0 4 4 4 4 5 6 7 4 9

5:7

індекси масиву: 0 1 2 3 4 5 6 7 8 9

дані в масиві :   0 4 4 4 4 7 6 7 4 9

Отож після кроку 2:3 ми змінили всі числа 2 на 3, відповідно, якщо ми хочемо взнати чи 2 та 3 обєднані ми просто порівнюємо їхні значення в даному випадку значення за індексом [2] та значення за індексом [3] однакові що означає що вони звязані.

Наступний крок обєднав значення з індексами 3:4 ми пройшлись по масиву з змінили всі 3 на 4 відповідно тепер значення за індексами [1][2][3][4] містять однакові значення що означає що вони обєднані.

Крок 8:2 змінив значення в елементі за індексом [8] на 4 тобто ди до списку обєднаних елементів додали ще одни елемент. Тепер якщо взяти значення за індексами доприкладу [2] та [8] ми можемо їх досить леко порівняти і зробити висновок що це два елементи обєднані бо мають однакове значення.

Останнє обєднання 5:7 створило ще одну множину елементів візповідно змінивши значення за індексом [5] на 7.

Давайте опишемо код який робить це обєднання:

   1: public void Union(int p, int q) 

   2: {

   3:     int pid = id[p];

   4:     int qid = id[q];

   5:  

   6:     for (int i = 0; i < id.Length; i++)

   7:     {

   8:         if (id[i] == pid)

   9:         {

  10:             id[i] = qid;

  11:         }

  12:     }

  13: }

Як бачимо ми просто приймаємо індекси елементів які необхідно обєднати беремо їхні дані, і проходячись по масиву замінюємо всі значення значення pid на значення qid. Це водночас найбільший недолік цієї реалізації, нам постійно необхідно проходитись по всьому масиву а це досить затратна операція.

Оптимальнішим варіантом виконання цього алгоритму буде не заміна всіх елементів в масиві на те з чим ми обєднуємо, а побудова дерева.

Я просто викладу варіант цього алгоритму і варіант Quick Union пропоную вам далі зрозібратись як вони працють.

Union Find

   1: using System;

   2:  

   3: namespace Quick_FindUF_2_2

   4: {

   5:     class Program

   6:     {

   7:         static void Main(string[] args)

   8:         {

   9:             QuickFindUF quickFind = new QuickFindUF();

  10:  

  11:             // Connecting

  12:             while (true)

  13:             {

  14:                 string leftItem = Console.ReadLine();

  15:                 int p = int.Parse(leftItem);

  16:  

  17:                 //ExitPoint

  18:                 if (p == -1)

  19:                     break;

  20:  

  21:                 string rightItem = Console.ReadLine();

  22:                 int q = int.Parse(rightItem);

  23:  

  24:                 quickFind.Union(p, q);

  25:  

  26:             }

  27:  

  28:             // Check if points are connected.

  29:             string leftItem1 = Console.ReadLine();

  30:             int p1 = int.Parse(leftItem1);

  31:  

  32:             string rightItem1 = Console.ReadLine();

  33:             int q1 = int.Parse(rightItem1);

  34:  

  35:             if (quickFind.IsConnected(p1, q1))

  36:             {

  37:                 Console.WriteLine("Connected");

  38:                 Console.ReadLine();

  39:             }

  40:         }

  41:     }

  42:  

  43:     class QuickFindUF

  44:     {

  45:         int[] id = new int[10];

  46:  

  47:         public QuickFindUF()

  48:         {

  49:             for (int i = 0; i < id.Length; i++)

  50:             {

  51:                 id[i] = i;

  52:             }

  53:         }

  54:  

  55:         public bool IsConnected(int p, int q)

  56:         {

  57:             return id[p] == id[q];

  58:         }

  59:  

  60:         public void Union(int p, int q)

  61:         {

  62:             int pid = id[p];

  63:             int qid = id[q];

  64:             for (int i = 0; i < id.Length; i++)

  65:             {

  66:                 if (id[i] == pid)

  67:                 {

  68:                     id[i] = qid;

  69:                 }

  70:                 Console.Write("{0} ", id[i]);

  71:             }

  72:             Console.WriteLine();

  73:         }

  74:     }

  75: }

Quick Union

   1: using System;

   2:  

   3: namespace Quick_Union_2_3

   4: {

   5:     class Program

   6:     {

   7:         static void Main(string[] args)

   8:         {

   9:             QuickUnion quickUnion = new QuickUnion();

  10:  

  11:             // Connecting

  12:             while (true)

  13:             {

  14:                 string readLine = Console.ReadLine();

  15:                 int p = int.Parse(readLine);

  16:                 int pRoot = quickUnion.FindRoot(p);

  17:  

  18:                 string readLine1 = Console.ReadLine();

  19:                 int q = int.Parse(readLine1);

  20:                 int qRoot = quickUnion.FindRoot(q);

  21:  

  22:                 //ExitPoint

  23:                 if (p == -1)

  24:                     break;

  25:  

  26:                 quickUnion.Union(pRoot, qRoot);

  27:  

  28:             }

  29:  

  30:             // Check if points are connected.

  31:             string readLine2 = Console.ReadLine();

  32:             int p1 = int.Parse(readLine2);

  33:  

  34:             string readLine3 = Console.ReadLine();

  35:             int q1 = int.Parse(readLine3);

  36:  

  37:             if (quickUnion.IsConnected(p1, q1))

  38:             {

  39:                 Console.WriteLine("Connected");

  40:                 Console.ReadLine();

  41:             }

  42:         }

  43:     }

  44:  

  45:     internal class QuickUnion

  46:     {

  47:         int[] id = new int[10];

  48:  

  49:         public QuickUnion()

  50:         {

  51:             for (int i = 0; i < id.Length; i++)

  52:             {

  53:                 id[i] = i;

  54:             }

  55:         }

  56:  

  57:         public void Union(int p, int q)

  58:         {

  59:             id[p] = id[q];

  60:             

  61:             for (int i = 0; i < id.Length; i++)

  62:             {

  63:                 Console.Write("{0} ", id[i]);

  64:             }

  65:             Console.WriteLine();

  66:         }

  67:  

  68:         public bool IsConnected(int p, int q)

  69:         {

  70:             return id[p] == id[q];

  71:         }

  72:  

  73:         public int FindRoot(int item)

  74:         {

  75:  

  76:             while (item != id[item])

  77:             {

  78:                 item = id[item];

  79:             }

  80:  

  81:             Console.WriteLine("Root {0}", item);

  82:             return item;

  83:         }

  84:     }

  85: }

 

Код на гітхабі: https://github.com/BatsIhor/Algorithms/

опис алгоритмів від Седжвіка рекомендую почитати : http://algs4.cs.princeton.edu/15uf/ 

Там можна знайти більше алгоритмів, я буду добавляти їх туди по мірі вивчення.

Будь які коментарі та зауваження вітаються )