Раскраска графов с помощью простого поиска с возвратом. Часть 2
Прежде чем я начну, короткое замечание: поздравления с наилучшими пожеланиями Дэвиду Джонсону, текущему президенту моей alma mater, Университета Ватерлоо. Королева назначила его следующим Генерал-Губернатором Канады и он приступает к своим полномочиям в октябре. Для тех из вас, кто не знаком с политической структурой Канады, Ее Величество Елизавета II является главой государства, Генерал-Губернатор является ее прямым представителем в Канаде и, таким образом является (в основном номинально, но иногда и реально) главой государства.
Продолжим!
Хорошо, у нас есть класс нашего графа. В общих чертах алгоритм поиска цветов будет следующим: для каждого узла графа найти набор «возможных цветов», а затем постепенно уменьшать этот набор для каждого узла до тех пор, пока мы не удостоверимся, что соответствующей цветовой схемы не существует, или пока не найдем в точности по одному цвету для каждого узла. Таким образом, нам нужен тип для представления набора возможных цветов.
Прежде всего, какой тип должен представлять цвет? В BCL существует перечисление Color, но то ли это, что нам нужно? Мы, скорее всего будем задавать вопросы типа: «использует ли эта цветовая схема раскраски графа только три цвета?», а не вопросы типа: «является ли это раскраской графа, которая использует зеленый, синий и оранжевый цвета?» Точные цвета нам, на самом деле, не важны. Давайте представим цвет в виде целого числа от 0 до max – 1. Если захотим, мы всегда сможем найти соответствие между целыми числами и цветами.
Обратите внимание, что это проектное решение сразу приводит к нескольким возможным неоднозначностям; в последний раз мы говорили о том, что узлы дерева мы также представляем целыми числами. Если бы меня это действительно беспокоило, то я мог бы создать две разные структуры, содержащие целое число, скажем, GraphNode и GraphColor. Это позволило бы компилятору говорить мне, если бы я случайно попытался присвоить цвет переменной, которая логически является узлом.
Это непростой выбор. На одной чаше весов лежат время и усилия на реализацию и сопровождения ненужных структур данных, а на другой чаше – время и усилия, потраченные на неожиданные ошибки. Стоит ли результат потраченных усилий? Мне кажется, что в этом случае – нет. Пока что я не собираюсь реализовывать эти структуры данных.
Итак, цвет – это простое целое число. Я хочу представить набор простых целых чисел. Класс HashSet<int> кажется подходящим готовым решением, но с его использованием связан ряд проблем. Во-первых, изменяемость (mutable); частично, целью этого упражнения является программирование в «неизменяемом» стиле. Во-вторых, он тяжеловесный; для хранения набора целых чисел он выделяет массивы, хэш-блоки и всякую такую ерунду.
Если мы хотим ограничить задачу, мы можем создать намного более эффективное решение для представления набора целых чисел, нежели HashSet<int>. Давайте в качестве примера предположим, что мы никогда не будем пытаться раскрасить граф более чем 32 цветами, что кажется вполне разумным. В этом случае мы можем представить набор целых чисел с помощью одного 32 битового целого путем использования его в качестве битового набора. Целые числа уже являются неизменяемыми, так что кажется вполне естественным создать неизменяемый набор на основе целого числа.
С таким подходом нам даже не нужен дополнительный тип, оборачивающий целое число. Мы можем просто использовать тип integer. Однако в отличие от наших предыдущих примеров с узлами графа и цветами, нам нужно иметь дополнительные операции с этим типом, например «перебрать все возможные элементы». Это очень похоже на настоящий абстрактный тип данных, так что вполне разумно создать настоящий тип, а не использовать тип целого числа напрямую.
// Сверхдешевый неизменяемый набор целых чисел от 0 до 31;
// просто удобная оболочка над битовыми операции с типом int.
internal struct BitSet : IEnumerable<int>
{
public static BitSet Empty { get { return default(BitSet); } }
private readonly int bits;
private BitSet(int bits) { this.bits = bits; }
public bool Contains(int item)
{
Debug.Assert(0 <= item && item <= 31);
return (bits & (1 << item)) != 0;
}
public BitSet Add(int item)
{
Debug.Assert(0 <= item && item <= 31);
return new BitSet(this.bits | (1 << item));
}
public BitSet Remove(int item)
{
Debug.Assert(0 <= item && item <= 31);
return new BitSet(this.bits & ~(1 << item));
}
IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
public IEnumerator<int> GetEnumerator()
{
for(int item = 0; item < 32; ++item)
if (this.Contains(item))
yield return item;
}
}
Давайте опять рассмотрим этот код построчно.
Как и в случае с классом графа, я сделал этот тип внутренним. Поскольку я знаю, что этим классом буду пользоваться только я, то я могу не проверять выход за границы диапазона, не использовать исключения и все такое. Если бы это был открытый тип в составе BCL, то я бы добавил более детальную проверку выхода за границы, чтобы удостовериться в том, что элементы на самом деле являются целыми числами в диапазоне от 0 до 31; вместо этого, я просто воспользовался проверочными утверждениями режима отладки.
Я сделал этот тип значимым (value type), поскольку неизменяемый набор целых чисел логически можно трактоваться как значение, кроме того, этот тип очень маленький с точки зрения содержащихся в нем данных.
Но в отличие от класса графа, в данном случае я подчеркнул деталь реализации набора путем именования класса BitSet, вместо, скажем SmallIntegerSet. Я непоследователен? Нет, я просто смотрю на проблему с разных точек зрения. Мне кажется, что в этом случае правильнее будет подчеркнуть, что этот тип прежде всего является механизмом, а не носителем определенной семантики. Я не уверен, почему это именно так.
Я мог бы реализовать более функциональный интерфейс, например ICollection<int>, но он включает ненужные мне операции, как, например, возможность изменять коллекцию. Вместо использования готового интерфейса необычным, сбивающим с толку способом, я просто реализовал стандартный интерфейс – IEnumerable<int>, который я могу корректно реализовать, а затем добавить два дополнительных метода – Add и Remove, которые делают то, что мне нужно.
Я использую стандартный шаблон неизменяемых объектов, который заключается в предоставлении статического свойства, возвращающего пустую коллекцию. Оно не является обязательным, поскольку default(BitSet) делает все, что нужно. Однако использование BitSet.Empty более читабельно, а также из названия понятно, что в результате вы получите пустую коллекцию. В качестве закрытых данных я использовал знаковое целое вместо беззнакового. Несколько безопаснее использовать в качестве битового массива uint, поскольку в этом случае вероятность столкнуться с проблемой представления знакового бита значительно ниже. Однако в этом случае вам придется везде использовать явные приведения типов, что будет выглядеть просто ужасно. Мне кажется, что математика здесь достаточно проста, чтобы мы могли проверить ее корректность не беспокоясь через чур о проблеме со знаком.
Конструктор, принимающий внутреннее состояние является закрытым; это лишает вызывающий код возможности установить несколько битов одновременно. Ведь если вызывающему коду нужен int с одновременно выставленными битами, то зачем он вообще использует BitSet? Очевидно, что тогда он способен выполнить соответствующие битовые операции в собственном коде. Принцип YAGNI, опять говорит о том, что не следует предоставлять ненужную дополнительную функциональность.
Методы Contains, Add и Remove, как уже было сказано ранее, не проверяют корректность своих аргументов, поскольку тип предназначен для внутреннего использования. Отладочные проверочные утверждения сообщат вызывающему коду о том, что инвариант, ожидаемый этим кодом, нарушен.
Вы можете подумать о том, почему метод GetEnumerator использует цикл и yield return, а не реализован следующим образом:
public IEnumerator<int> GetEnumerator()
{
return
from item in Enumerable.Range(0, 32)
where this.Contains(item)
select item;
}
Поняли ли вы, почему я предпочел вариант с циклом, несмотря на мою сильную любовь использовать вместо них запросы?
Обратите внимание на то, что я не стал реализовать специальные версии операторов последовательности (sequence operators), в виде методов расширения, хотя и мог бы. Например, я не добавил свойство Count. Оригинальная реализация метода Count() вызовет метод GetEnumerator, который, как мы видели, переберет все 32 значения. Но определение количества установленных битов в массива – это вес Хемминга, а для его определения существует множество хорошо определенных алгоритмов. Мы, например, можем воспользоваться алгоритмом, обычно приписываемым Кернигану (Kernighan) (хотя за всю историю программирования он был независимо открыт несколько раз). Этот алгоритм сбрасывает младший бит, до тех пор, пока все установленные биты не будут сброшены, и говорит о том, сколько раз он это сделал:
public int Count()
{
int remaining = this.bits;
int count = 0;
while(remaining != 0)
{
remaining &= (remaining - 1);
count++;
}
return count;
}
Стоимость выполнения этого алгоритма пропорционально количеству установленных битов, что не требует постоянного перебора всех 32 элементов. Но кого это волнует? 32 – это достаточно маленькое число. Опять-таки, давайте не будем добавлять ненужную сложность, пока эмпирические данные полученные путем профилирования не скажут о том, что простой способ перебора битового набора влечет за собой непозволительно большие издержки.
Обратите внимание, что я реализовал метод Contains(), вместо того, чтобы использовать существующий метод расширения. Если бы я использовал метод расширения, то очевидно, у меня не было бы возможности вызывать метод Contains() внутри GetEnumerator, поскольку такой вызов привел бы к переполнению стека. Тогда мне бы пришлось поместить логику работы с битами в метод GetEnumerator, а поскольку я в любом случае собирался реализовывать эту логику, то мне показалось разумнее поместить ее в отдельный метод для общего использования.
Мы опять создали простейший маленький кусочек кода, но при этом по ходу дела приняли множество проектных решений. Главный вопрос, который лег в основу всего дизайна следующий: «разумно ли предположить, что у нас не будет более 32 цветов?» Мы можем элементарно расширить это количество до 64 путем использования типа long вместо int, однако дальнейшее увеличение количества цветов станет значительно сложнее.
В следующий раз: давайте наконец решим задачу посложнее и создадим алгоритм, который решает задачу определения цветов.