Існує безліч типів колекцій, добре відомих в інформатиці, але не потрапили в .NET Framework. Деякі з них отримали досить широке поширення, і ваші програми могли б отримати певні вигоди від їх використання. Крім того, більшість з них може бути реалізовано в досить короткі терміни. Не дивлячись на те, що ми не ставимо перед собою за мету зайнятися дослідженням різних типів колекцій, тим не менш, наведемо два приклади колекцій, що істотно відрізняються від колекцій в .NET, і пропонуємо розглянути ситуації, коли застосування власних колекцій може виявитися корисним.
Система непересічних множин
Система непересічних множин (disjoint-set) - це колекція, елементи якої зберігаються у вигляді непересічних множин. Вона відрізняється від колекцій .NET тим, що не дозволяє зберігати в ній елементи. Замість цього утворюється домен елементів, в якому кожен елемент утворює єдине безліч, і визначається послідовність операцій по об'єднанню до більших безлічі. Ця структура даних забезпечує високу ефективність двох операцій:
об'єднання двох підмножин з цілю отримати загальне підмножина;
пошук, визначення підмножини, якому належить елемент (часто використовується, щоб визначити, чи належать два зазначених елемента одній підмножині).
Зазвичай операції з множинами виконуються на рівні елементів-представників - з єдиним представником від кожного безлічі. Операції об'єднання і пошуку приймають і повертають представників, а не цілі безлічі.
Наївна реалізація системи непересічних множин залучає використання колекції для подання кожного безлічі, і злиття колекцій при необхідності. Наприклад, при використанні пов'язаного списку для зберігання кожного безлічі, час їх злиття прямо пропорційно кількості множин а операція пошуку може займати постійне час, якщо кожен елемент має покажчик на представника безлічі.
Реалізація алгоритму Галлера-Фішера (Galler-Fischer) має набагато більш високу складність. Безлічі зберігаються у вигляді «лісу» (безлічі дерев); кожен вузол кожного дерева зберігає покажчик на його батьківський вузол, а коренем дерева є представник безлічі. Щоб забезпечити збалансованість виходять дерев, при злитті дерев менше дерево завжди приєднується до кореня більшого дерева (це вимагає стежити за глибиною дерева). Крім того, операція пошуку стискає шлях від бажаного елемента до його представника. Нижче представлена схематична реалізація цього алгоритму:
Точне вимірювання продуктивності цієї структури даних є досить складним завданням. У найпростішому випадку верхньою межею, що амортизується часу операції в лісі з n елементів є O (log * n), де log * n (ітераційне обчислення логарифма) - кількість застосувань функції обчислення логарифма для отримання результату менше одиниці, тобто, мінімальна кількість появ «log »у нерівності log log log. log n. який просто зберігає сортовані масив. Типовий підхід до вирішення цієї проблеми полягає в рандомізації ієрархії списків (показано на малюнку нижче), що дозволяє отримати очікуване логарифмічна час на вставку, видалення і пошук елементів:
Може так само статися, що ви опинитеся в унікальній ситуації, коли вирішити поставлене завдання буде можливо тільки із застосуванням власної колекції. Ми називаємо їх одноразовими колекціями (one-shot collections). тому що вони є абсолютно новими винаходами, придатними для вирішення певної задачі. Згодом ви можете виявити, що якісь з ваших одноразових колекцій цілком можна використовувати повторно. І в цьому розділі ми познайомимося з однією такою колекцією.
Уявіть таку ситуацію: ви створили біржову інформаційну систему, що постачає продавців шоколадних батончиків інформацією про ціни на різні батончики. Основна таблиця з даними зберігається в пам'яті і містить по одному рядку для батончика кожного типу, що містить поточну ціну на даний батончик. У таблиці нижче представлений приклад цієї таблиці з даними в певний момент часу:
Приклад таблиці з даними в інформаційній системі для продавців батончиків
Продавці батончиків підключаються до системи через сокет TCP, і періодично запитують свіжу інформацію про певний тип батончиків. Типовий запит від продавця має вигляд: «Яка ціна на Twix?». А типова відповідь: «$ 0.93». Кожну секунду в систему надходить десятки тисяч таких запитів.
Виробники батончиків підключаються до системи через сокет UDP і періодично встановлюють нову ціну на свої батончики. Запити від виробників діляться на два підтипи:
«Встановити ціну на Mars рівній $ 0.91». Відповідати на такий запит не потрібно. Кожну секунду в систему надходять тисячі таких запитів.
«Додати новий батончик Snowflakes з початковою ціною $ 0.49». Відповідати на такий запит не потрібно. Таких запитів надходить в систему не більш декількох десятків в день.
Відомо також, що 99.9% операцій читання або оновлення ціни виконується для типів батончиків, що існували до моменту початку торгів, і тільки 0.1% операцій припадає на частку знову доданих батончиків.
Озброївшись цією інформацією, ви вирішили спроектувати структуру даних - колекцію - для зберігання таблиці з даними в пам'яті. Ця структура повинна підтримувати можливість використання в багатопотокової середовищі, тому що сотні потоків виконання можуть одночасно спробувати звернутися до неї. Вам не потрібно турбуватися про збереження даних в деякому постійному сховище - ми досліджуємо наведені цифри щодо тільки для випадку знаходження колекції в пам'яті.
Форма даних і типи запитів диктують необхідність використовувати хеш-таблицю. Синхронізація доступу до хеш-таблиці є складним завданням, яку краще перекласти на плечі ConcurrentDictionary
Одним з можливих рішень може служити безпечний-небезпечний кеш (safe-unsafe cache). Ця колекція є безліччю з двох хеш-таблиць, безпечної таблиці (safe table) і небезпечною таблиці (unsafe table). Безпечна таблиця заповнюється інформацією про типи батончиків, що існували до моменту початку торгів; небезпечна таблиця спочатку порожня. Операції з безпечної таблицею виконуються без блокування, тому що вона не змінюється; нові типи батончиків додаються в небезпечну таблицю. Нижче представлена можлива реалізація цієї структури даних з використанням Dictiornary
Наступним кроком у розвитку цієї структури даних могла б бути періодична припинення торговельних операцій і об'єднання безпечної і небезпечною таблиць. Це ще більше зменшило б потребу в синхронізації для доступу до даних.
Реалізація IEnumerable і інших інтерфейсів
Майже будь-яка колекція в кінцевому рахунку реалізує інтерфейс IEnumerable
На жаль, прямолінійна реалізація інтерфейсу IEnumerable
У кожній ітерації в цьому прикладі викликаються два методу інтерфейсу, що тягне за собою зайві накладні витрати при спробі обійти список і обчислити добуток його елементів. Вбудовування методів інтерфейсів не найпростіше завдання, і якщо JIT-компілятор не вдасться її вирішити, вартість їх викликів вийде досить високою.
Існує кілька рішень, здатних допомогти уникнути зайвих накладних витрат при виклику методів. Коли методи інтерфейсів застосовуються безпосередньо до змінної типу значення, вони викликаються безпосередньо. Тобто, якби змінна enumerator в прикладі вище мала тип значення (а не IEnumerator
Для цього, наприклад, клас List
Це дозволяє писати такий код:
рятує від викликів методів інтерфейсу.
Альтернативне рішення полягає в створенні ітератора посилального типу, але використовує той же трюк з явною реалізацією інтерфейсу - методу MoveNext () і властивості Current. Воно також дозволить викликає програмі використовувати метод і властивість класу безпосередньо, уникнувши накладних витрат на виклики методів інтерфейсу.