Поделиться через

The Working Programmer

  • Статья

.NET-наборы: работаем с C5. Часть 2

Ted Neward

Ted NewardС возвращением!

В первой части этой серии я кратко рассмотрел библиотеку C5 (Copenhagen Comprehensive Collection Classes for C#), набор классов, дополняющих (если не заменяющих) классы System.Collections, поставляемые с библиотекой исполняющей среды Microsoft .NET Framework. Эти две библиотеки в немалой степени перекрывают друг друга отчасти потому, что в C5 стараются следовать многим из идиом, заложенных в .NET Framework Class Library (FCL), а отчасти потому, что конкретный тип набора можно представить далеко не бесконечными способами. (Трудно вообразить индексируемый набор вроде Dictionary или List, не поддерживающий языковой синтаксис индексируемых свойств: без операторов «[]» в C# и «()» в Visual Basic.) Однако там, где FCL-наборы утилитарны, в C5-наборах идут на один или два шага дальше, и именно таким моментам мы посвятим свое время.

(Заметьте, что эти две библиотеки также весьма вероятно различаются по производительности в некоторых областях, на которые не преминут указать защитники и критики с обеих сторон. Кстати, в документации на C5-наборы обсуждаются некоторые вопросы производительности. Вместе с тем я воздержусь от оценок производительности по той простой причине, что, как правило, все, что доказывает тот или иной эталонный тест, относится к одному конкретному случаю или набору ситуаций; кто-то получит производительность на один-два пункта выше, чем другой, но это вовсе не значит, что так будет во всех случаях. Я не хочу сказать, что все эталонные тесты бесполезны — лишь то, что в эталонном тесте важен контекст. А читателям настоятельно рекомендую взять свои сценарии, преобразовать их в какой-то эталонный тест и проверить на нем обе библиотеки, просто чтобы понять, если заметная разница в их сценариях.)

Реализации

Прежде всего кратко рассмотрим различные реализации наборов, предоставляемые C5. И вновь, как уже говорилось в прошлый раз, разработчикам, использующим C5, обычно незачем беспокоиться о применяемой реализации, кроме того случая, когда они решают, какую реализацию надо создать, — в остальных ситуациях на наборы следует ссылаться по типу интерфейса. (Описание типов интерфейсов см. в первой части из этой серии статей по ссылке msdn.microsoft.com/magazine/jj883961 или в документации C5 на bit.ly/UcOcZH.) Ниже дан список реализаций с краткими пояснениями.

  • CircularQueue<T> реализует как IQueue<T>, так и IStack<T>, предоставляя либо FIFO-семантику IQueue<T> (через Enqueue и Dequeue), либо LIFO-семантику IStack<T> (через Push и Pop). Поддерживаются связанным списком, увеличиваемым по мере необходимости.
  • ArrayList<T> реализует IList<T>, IStack<T> и IQueue<T>; поддерживается массивом.
  • LinkedList<T> реализует IList<T>, IStack<T> и IQueue<T>, используя двунаправленный список узлов.
  • HashedArrayList<T> реализует IList<T>, поддерживается массивом, но на внутреннем уровне также поддерживает хеш-таблицу для эффективного поиска позиции элемента в списке. Кроме того, не допускает дубликатов в списке (поскольку они не позволили бы вести поиск по хеш-таблице).
  • HashedLinkedList<T> реализует IList<T>, поддерживается связанным списком, и подобно своему родственному интерфейсу, поддерживаемому массивом, использует внутреннюю хеш-таблицу для оптимизации операций поиска.
  • WrappedArray<T> реализует IList<T>, обертывает одноразмерный массив. Преимущество этого класса в том, что он просто «дополняет» массив, делая его гораздо более быстрым в рамках функциональности C5 — в противоположность копированию элементов из массива в ArrayList<T>.
  • SortedArray<T> реализует IIndexedSorted<T>, а значит, данный набор можно индексировать и сортировать — об этом мы вскоре поговорим. Он хранит свои элементы отсортированными и не допускает дубликатов.
  • TreeSet<T> реализует IIndexedSorted<T> и IPersistedSorted<T> и поддерживается балансируемым красно-черным деревом (balanced red-black tree), что отлично подходит для вставки, удаления и сортировки. Как и все множества, не допускает дубликатов.
  • TreeBag<T> реализует IIndexedSorted<T> и IPersistedSorted<T>, поддерживается балансируемым красно-черным деревом, но в основном является «контейнером» (иногда называемым мультимножеством [multiset]), а это подразумевает, что он допускает дубликаты.
  • HashSet<T> реализует IExtensible<T> и поддерживает множество (не допуская дубликатов) хеш-таблицей с линейным связыванием в цепочки. Это обеспечивает быстрый поиск.
  • HashBag<T> реализует IExtensible<T> и поддерживает контейнер (дубликаты допускаются) хеш-таблицей с линейным связыванием в цепочки, опять же обеспечивая быстрый поиск.
  • IntervalHeap<T> реализует IPriorityQueue<T>, используя кучу интервалов (interval heap), хранящуюся как массив пар, делая очень эффективным извлечение либо max-, либо min-конца очереди с приоритетами (priority queue).

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

Функциональность

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

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

Рис. 1. Создание представлений набора

[TestMethod]
public void GettingStarted()
{
  IList<String> names = new ArrayList<String>();
  names.AddAll(new String[]
    { "Hoover", "Roosevelt", "Truman", "Eisenhower", "Kennedy" });
// Выводим элемент 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]);
}

Это представление поддерживается исходным списком, т. е., если исходный список по какой-либо причине изменится, представление тоже изменится. На рис. 2 видно, что представления являются потенциально изменяемыми.

Рис. 2. Представления являются потенциально изменяемыми

[TestMethod]
public void ViewExploration()
{
  IList<String> names = new ArrayList<String>();
  names.AddAll(new String[]
    { "Washington", "Adams", "Jefferson",
      "Hoover", "Roosevelt", "Truman",
      "Eisenhower", "Kennedy" });
  IList<String> postWWII = names.View(4, names.Count - 4);
  Assert.AreEqual(postWWII.Count, 4);
  IList<String> preWWII = names.View(0, 5);
  Assert.AreEqual(preWWII.Count, 5);
  Assert.AreEqual("Washington", preWWII[0]);
  names.Insert(3, "Jackson");
  Assert.AreEqual("Jackson", names[3]);
  Assert.AreEqual("Jackson", preWWII[3]);
}

Как показывает этот тест, изменение нижележащего списка (names) означает, что представления, определенные на его основе (в данном случае представление preWWII), тоже обнаружат изменение своего содержимого, поэтому теперь первым элементом в представлении является «Washington», а не «Hoover».

Однако по возможности C5 будет сохранять незыблемость представления; например, если вставка осуществляется перед началом набора (где C5 может выполнить вставку, не изменяя содержимое представления «preWWII»), то содержимое представления останется неизменным:

[TestMethod]
public void ViewUnchangingExploration()
{
  IList<String> names = new ArrayList<String>();
  names.AddAll(new String[]
    { "Hoover", "Roosevelt", "Truman", "Eisenhower", "Kennedy" });
  IList<String> preWWII = names.View(0, 2);
  Assert.AreEqual(preWWII.Count, 2);
  names.InsertFirst("Jackson");
  Assert.AreEqual("Jackson", names[0]);
  Assert.AreEqual("Hoover", preWWII[0]);
}

Неизменяемые (защищаемые) наборы С появлением стилей и концепций функционального программирования основной акцент сместился на неизменяемые данные и объекты — по большей части из-за того, что неизменяемые объекты дают много преимуществ; кроме того, многие разработчики находят неизменяемые объекты более простыми в понимании и предсказуемыми. Вследствие этого возникла концепция неизменяемых наборов — независимо от того, являются ли объекты внутри набора неизменяемыми, сам набор фиксирован и не разрешает никаких изменений (добавления или удаления) элементов в наборе. (Заметьте, что вы можете увидеть предварительную версию неизменяемых наборов, выпущенную в NuGet, в блоге MSDN Base Class Library (BCL) по ссылке bit.ly/12AXD78.)

Внутри C5 неизменяемые наборы обрабатываются созданием экземпляров наборов-оболочек вокруг набора, содержащего интересующие вас данные; эти наборы являются защищаемыми (guarded) и используются в классическом проектировочном шаблоне Decorator:

public void ViewImmutableExploration()
{
  IList<String> names = new ArrayList<String>();
  names.AddAll(new String[]
    { "Hoover", "Roosevelt", "Truman", "Eisenhower", "Kennedy" });
  names = new GuardedList<String>(names);
  IList<String> preWWII = names.View(0, 2);
  Assert.AreEqual("Hoover", preWWII[0]);
  names.InsertFirst("Washington");
  Assert.AreEqual("Washington", names[0]);
}

Если кто-то попытается написать код, который добавляет или удаляет элементы из этого списка, C5 быстро отвадит его от этой идеи: исключение генерируется при вызове любого «модифицирующего» метода (Add, Insert, InsertFirst и т. д.).

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

Рис. 3. Защищаемые (неизменяемые) наборы

public void IWannaBePresidentToo(IList<String> presidents)
{
  presidents.Add("Neward");
}
[TestMethod]
public void NeverModifiedCollection()
{
  IList<String> names = new ArrayList<String>();
  names.AddAll(new String[]
    { "Hoover", "Roosevelt", "Truman","Eisenhower", "Kennedy" });
  try
  {
    IWannaBePresidentToo(new GuardedList<String>(names));
  }
  catch (Exception x)
  {
    // Это ожидаемо! Должно быть ReadOnlyException.
  }
  Assert.IsFalse(names.Contains("Neward"));
 }

И вновь, когда метод IWannaBePresidentToo пытается модифицировать переданный ему набор (что, безусловно, плохой стиль со стороны программиста, который писал этот код, но, увы, в наши дни так много плохого кода), генерируется исключение.

Кстати, на случай, если вы предпочитаете, чтобы набор не генерировал исключение, а просто «молча» отклонял попытку модификации (на мой взгляд это не слишком корректно, но кому-то такая функциональность может понадобиться), то сравнительно несложно собрать собственную версию GuardedArray<T>, которая именно так и делает.

События Иногда модификация наборов — как раз то, что вам нужно разрешать, но при условии, что вы будете знать, что набор модифицирован. Честно говоря, вы могли бы крутить поток, и он неопределенно долго крутился бы по набору, сравнивая его содержимое с содержимым на предыдущей итерации, однако это было бы не только ужасающей растратой процессорного времени, но и весьма проблематичным в написании и сопровождении, так что такое решение было бы худшим из возможных и уж точно куда хуже, чем простое использование набора, поддерживающего события. Все наборы в C5 позволяют вызывать делегаты, когда над набором выполняются определенные операции (рис. 4).

Рис. 4. «Когда я стану президентом…»

[TestMethod]
public void InaugurationDay()
{
  IList<String> names = new ArrayList<String>();
  names.AddAll(new String[]
    { "Hoover", "Roosevelt", "Truman", "Eisenhower", "Kennedy" });
  names.ItemsAdded +=
    delegate (Object c, ItemCountEventArgs<string> args)
  {
    testContextInstance.WriteLine(
      "Happy Inauguration Day, {0}!", args.Item);
  };
  names.Add("Neward");
  Assert.IsTrue(names.Contains("Neward"));
}

Конечно, обработчик событий можно написать как лямбду; просто в таком виде немного нагляднее видны реальные типы аргументов. Первый аргумент, как предписывают каноны, — это сам набор.

На расстоянии NuGet

Ни одна из частей C5 не могла быть построена на основе .NET FCL (помимо упора на интерфейсы, поддерживаемые FCL), но самое ценное в C5 то, что она сделана, протестирована, и ее можно установить командой NuGet «Install-Package».

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

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

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