Работающий программист

.NET-наборы: начинаем работу с C5

Тэд Ньюард

 

Ted NewardЯ должен сделать одно признание.

Днем я работаю как кроткий .NET-разработчик на консалтинговую фирму Neudesic LLC. А по ночам, когда моя жена и сыновья спят, я украдкой выхожу из дома с лэптопом в руке, направляюсь в свое тайное местечко (заведение у Денни на 148-й улице) и… пишу код на Java.

Да, ребята, я живу двойной жизнью: как .NET-разработчик и как разработчик на Java (или точнее, Java Virtual Machine [JVM]). Одно из интересных преимуществ такой двойной жизни — я вижу области, где в Microsoft .NET Framework если некоторые замечательные идеи, которые можно вернуть в JVM. Одна из таких идей — настраиваемые атрибуты, которые были введены в JVM в версии Java5 (где-то в 2005 году) под названием «аннотации». Но верно и обратное: некоторые вещи, которые реализованы в CLR и .NET Base Class Library (BCL) неправильно (или, по крайней мере, недостаточно правильно, если вас это задевает), а в JVM — правильно. Одна из таких областей лежит в основе .NET BCL, и это наборы.

Наборы: критика

Отчасти дефект .NET-наборов кроется в том факте, что группа BCL дважды написала глупые вещи: один раз для .NET Framework 1.0/1.1 до появления обобщений и второй — в .NET Framework 2.0 после того, как обобщения стали частью CLR, поскольку наборы без строго типизированных версий — просто ерунда. Это автоматически означало, что одна из них была обречена на провал, и оставалось в основном ждать, когда появятся какие-нибудь расширения или дополнения к этой библиотеке. (В Java избежали конкретно этой проблемы путем «замены» необобщенных версий на обобщенные, что было возможно только благодаря тому, как Java обрабатывала обобщения. Но вникать в это здесь я не стану.) И помимо расширений, появившихся в виде LINQ в Visual Studio 2008 и C# 3.0, библиотека наборов никогда не пользовалась особой популярностью после версии 2.0, в которой по большей части заново реализовали классы System.Collections в новом пространстве имен (System.Collections.Generic, SCG) строго типизированных версий.

Однако, что важнее, архитектура .NET-наборов, похоже, была больше сфокусирована на том, чтобы выпустить на волю хоть что-то практичное и полезное из версии 1.0, и никто не попытался глубоко продумать архитектуру наборов и то, как их можно было бы расширить. Это была одна из областей, в которой .NET Framework на самом деле развивалась параллельно с миром Java (подозреваю, что неумышленно). Когда поставлялась Java 1.0, она включала набор базовых утилитарных наборов. Но в их архитектуре было несколько проколов (самым вопиющим из которых было решение по классу Stack — LIFO-набору [last-in-first-out], прямо расширяющему класс Vector, который, по сути, был ArrayList). После Java 1.1 несколько инженеров в Sun Microsystems стали упорно трудиться над переписыванием классов наборов. Они стали известны под названием Java Collections и начали поставляться с Java 1.2.

Так или иначе, в .NET Framework потом переработали свои классы наборов и сделали это идеально в том смысле, что они по крайней мере во многом совместимы с существующими SCG-классами. К счастью, исследователи из Копенгагенского университета информационных технологий в Дании создали отличное дополнение для SCG-классов: библиотеку, которую они назвали Copenhagen Comprehensive Collection Classes for C#, или C5 для краткости.

Логистика C5

Начнем с того, что C5 можно найти по ссылке itu.dk/research/c5; там же вы найдете историю версий и ссылку на книгу по C5 (в PDF), хотя эта книга устарела уже на несколько версий данной библиотеки. В качестве альтернативы C5 доступен через NuGet: достаточно ввести команду Install-Package C5. Заметьте, что C5 написан в версиях как для Visual Studio, так и для Mono, поэтому, когда NuGet устанавливает пакет, он добавляет ссылки на две сборки: C5.dll и C5Mono.dll. Одна из них лишняя, так что удалите ту сборку, которая вам не нужна. Чтобы изучить C5-наборы с помощью серии исследовательских тестов, я создал Visual C# Test Project и добавил C5 в этот проект. Помимо этого, единственное значимое изменение в коде — два выражения using:

using SCG = System.Collections.Generic;
using C5;

Причина для этого псевдонима проста: C5 «заново реализует» несколько интерфейсов и классов, которые имеют те же имена, что и в SCG-версии, поэтому такой вариант позволяет сохранить доступным старые вещи, но под очень коротким префиксом (например, IList<T> — это C5-версия, а SCG.IList<T> — «классическая» версия из SCG).

Кстати, если этим заинтересуются юристы, C5 является проектом с открытым исходным кодом с лицензией MIT, что дает вам гораздо больше возможностей в модификации или расширении некоторых C5-классов, чем в случае лицензии GNU General Public License (GPL) или GNU Lesser General Public License (LGPL).

Обзор архитектуры C5

Глядя на подход к архитектуре C5, кажется, что он похож на стиль SCG в том отношении, что наборы разбиваются на два «уровня»: интерфейса (описывает интерфейс и ожидаемое поведение данного набора) и реализации (обеспечивает код для одного или более необходимых интерфейсов). SCG-классы используют эту идею, но в некоторых случаях не следуют ей, например мы не получаем никакой гибкости в терминах реализации SortedSet<T> (подразумевая выбор вариантов на основе массивов, связанных списков или хеша, каждый из которых имеет разных характеристики, относящиеся к производительности вставки, обхода и др.). В ряде случаев в SCG-классах просто нет определенных типов наборов, в частности круговой очереди (где после прохода последнего элемента в очереди итерация вновь начинается с первого элемента этой очереди) или простого набора-контейнера (bag collection) (который не предлагает никакой функциональности, кроме хранения элементов, что исключает ненужные издержки сортировки, индексации и т. д.).

Согласен, что для среднего .NET-разработчика это вряд ли покажется большой потерей. Но во многих приложениях, когда во главу угла ставится производительность, выбор класса набора, подходящего для решаемой задачи, становится гораздо важнее. Конструируется ли этот набор лишь раз, а потом часто проходится? Или этот набор будет часто добавляться и удаляться, но проходится редко? Если этот набор занимает центральное место в некой функции приложения (или в самом приложении), разница между этими случаями будет подобна разнице между «Ух ты, да эта программа просто летает!» и «Ну, в целом, программа нравится пользователям, жаль только, что она очень медленная».

Один из базовых принципов в C5 — разработчики должны «писать код для интерфейсов, а не реализаций», и C5 предлагает более десятка различных интерфейсов, описывающих, что должен предоставлять нижележащий набор. Основа всего этого — ICollection<T>; он гарантирует базовое поведение наборов, но от него мы находим IList<T>, IIndexed<T>, ISorted<T> и ISequenced<T>, и это лишь начало списка. Вот полный список интерфейсов, взаимосвязей с другими интерфейсами и их гарантий.

  • SCG.IEnumerable<T> — обеспечивает перечисление элементов. Все наборы и словари являются перечисляемыми.
  • IDirectedEnumerable<T> — позволяет указывать направление перечисления элементов.
  • ICollectionValue<T> — набор значений. Не поддерживает изменение, является перечисляемым, знает, сколько элементов в нем содержится, и умеет копировать их в массив.
  • IDirectedCollectionValue<T> — набор значений, который может быть обращен в набор значений с обратным порядком.
  • IExtensible<T> — набор, в который можно добавлять элементы.
  • IPriorityQueue<T> — расширение IExtensible<T>, позволяющее эффективно находить (и удалять) элементы с наименьшим и наибольшим значениями.
  • ICollection<T> — расширение IExtensible<T>, из которого можно еще и удалять элементы.
  • ISequenced<T> — набор, элементы которого могут появляться в определенной последовательности (определяется либо порядком вставки, либо упорядочением элементов).
  • IIndexed<T> — последовательный набор, элементы которого доступны по индексу.
  • ISorted<T> — последовательный набор, в котором элементы появляются в порядке увеличения; последовательность элементов определяется их сравнением. Позволяет эффективно находить предшествующий или последующий элемент (в наборе) для указанного элемента.
  • IIndexedSorted<T> — индексируемый и сортируемый набор. Позволяет эффективно определять, сколько элементов больше или равно указанному элементу x.
  • IPersistentSorted<T> — сортируемый набор, позволяющий эффективно создавать моментальные снимки, т. е. копии только для чтения, которые не затрагиваются изменениями исходного набора.
  • IQueue<T> — FIFO-очередь (first-in-first-out) с поддержкой индексации.
  • IStack<T> — LIFO-стек (last-in-first-out).
  • IList<T> — индексируемый, а значит, и последовательный набор, где порядок элементов определяется вставками и удалениями. Наследует от SCG.IList<T>.

В терминах реализаций в C5 довольно много всего, в том числе есть круговые очереди, списки на основе массивов и связанных списков, списки на основе хешированных массивов и хешированных связанных списков, обернутые массивы (wrapped arrays), сортируемые массивы, множества на основе деревьев и контейнеров и т. д.

Стиль кодирования в C5

К счастью, C5 не требует значительных перемен в стиле кодирования и, что еще важнее, поддерживает все LINQ-операции (так как построена поверх SCG-интерфейсов, из которых исходят корни методов расширения LINQ), поэтому в некоторых случаях вы можете работать с C5-набором на этапе конструирования без изменения любого окружающего его кода. Пример тому вы найдете на рис. 1.

Рис. 1. Начинаем работать с C5

// Это C5-наборы IList и ArrayList, а не SCG
IList<String> names = new ArrayList<String>();
names.AddAll(new String[] { "Hoover", "Roosevelt", "Truman",
  "Eisenhower", "Kennedy" });
// Выводим список
Assert.AreEqual("[ 0:Hoover, 1:Roosevelt, 2:Truman, 3:Eisenhower," +
  " 4:Kennedy ]", names.ToString());
// Выводим элемент 1 ("Roosevelt") в этом списке
Assert.AreEqual("Roosevelt", names[1]);
Console.WriteLine(names[1]);
// Создаем представление списка,
// включающее президентов после Второй Мировой войны
IList<String> postWWII = names.View(2, 3);
// Выводим элемент 2 ("Kennedy") в этом представлении
Assert.AreEqual("Kennedy", postWWII[2]);
// Перечисляем и выводим представление списка
// в обратном хронологическом порядке
Assert.AreEqual("{ Kennedy, Eisenhower, Truman }",
  postWWII.Backwards().ToString());

Даже без изучения документации на C5 довольно легко понять, что происходит в этих примерах.

Сравнение реализаций наборов C5 и SCG

Это была лишь верхушка айсберга в отношении C5. В следующей статье мы рассмотрим некоторые практические примеры использования реализаций наборов C5 вместо SCG и ряд преимуществ такой замены. А тем временем советую не дожидаться следующей статьи: проделайте все, что нужно с NuGet, скачайте C5 и начните исследовать ее самостоятельно — вам будет чем заняться в этот период.

Удачи в кодировании!


Тэд Ньюард (Ted Neward) — консультант по архитектуре в компании Neudesic LLC. Автор и соавтор многочисленных книг, в том числе «Professional F# 2.0» (Wrox, 2010), более сотни статей, часто выступает на многих конференциях по всему миру; кроме того, имеет звание Microsoft MVP в области C#. С ним можно связаться по адресу ted@tedneward.com, если вы заинтересованы в сотрудничестве с его группой. Также читайте его блог blogs.tedneward.com и заметки на Twitter.com/tedneward.

Выражаю благодарность за рецензирование статьи эксперту Иммо Лэндверту (Immo Landwerth).