Sam's tricks

async/await и cancellation

noreply@blogger.com (samius) — Fri, 20 Dec 2013 22:18:00 +0000

Всем привет! Прошу прощения за то что долго не писал. Вынашивал планы родить две больших статьи, но то ли не выносил, то ли не родил. А тут подвернулась тема для маленькой заметочки. Будет приятно, если кому-то пригодится. Итак,

столкнулся недавно с необходимостью отмены асинхронных вычислений, выполненных на async программной модели .NET Framework 4.5. Воспользовался официальным блогом как руководством к действию и получил примерно следующий код:

try
{
    var bytesRead = await stream.ReadAsync(
        buffer, 0, bytesToRead, cancellationToken);
    // some code here
}
catch(TaskCancelledException)
{
    break;
}

Меня смутил подход, при котором индикатором отмены задачи является исключение. Во-первых, у меня предубеждение по поводу использования исключений не по назначению (а здесь оно явно лишнее). Во-вторых, Debug Output окно подзамусоривается текстом о возникших исключениях.

Примечательно то, что при использовании методов Task.ContinueWith исключение TaskCancelledException не возбуждается. Вместо этого мы имеем экземпляр Task, у которого после его отмены свойство IsCanceled установлено в true. Исключение будет возбуждено либо при вызове метода Task.Wait(), либо при обращении к свойству Task.Result.

Все верно, async/await паттерн подразумевает что после старта задачи код получает управление лишь при завершении или отмены задачи. При этом await конструкция вытягивает из задачи результат. Именно это вытягивание и приводит к возбуждению исключения. Обидно, но отказываться от async/await модели не хочется.

Вот тут и пришла идея поднять Task на уровень выше, т.е. await-ить не Task<int>, а Task<Task<int>>, обернув нужный Task в еще один Task с помощью примерно такого кода:

public static Task<Task<T>> Wrap<T>(this Task<T> task)
{
    var tsource = new TaskCompletionSource<Task<T>>();
    task.ContinueWith(tsource.SetResult);
    return tsource.Task;
}

public static Task<Task> Wrap(this Task task)
{
    var tsource = new TaskCompletionSource<Task>();
    task.ContinueWith(tsource.SetResult);
    return tsource.Task;
}

Можем воспользоваться этими методами следующим образом:

var tBytesRead = await stream
    .ReadAsync(buffer, 0, bytesToRead, cancellationToken)
    .Wrap();
if (tBytesRead.IsCanceled)
   break;
var bytesRead = tBytesRead.Result;

Теперь await ловит не только успешно завершенные задачи, но и отмененные. Осталось лишь пощупать IsCanceled и обратиться к свойству Result за результатом операции в случае если она не была отменена.

P.S. Приятный бонус заключается в том, что при моделировании мгновенной отмены операции Task.Delay(100, cancellationToken) подход с оборачиванием задачи показал примерно 4-х кратное преимущество по времени выполнения относительно подхода с поимкой возбужденного исключения.

Посещение чуждых иерархий или посетитель, которого не ждут

noreply@blogger.com (samius) — Tue, 08 Jun 2010 17:35:00 +0000

В прошлом посте я уделил внимание случаю, когда паттерн посетитель требуется прикрутить к некоторой структуре не модифицируя её. Тогда я воспользовался паттерном адаптер. Не так давно я столкнулся с необходимостью прикрутить паттерн посетитель к иерархии, чье множество классов было недоступно для модификации, и идея с паттерном адаптер не показалась мне здравой.

На той же предметной области, что и в прошлом посте, покажу в чем проблема: требовалось класс Engine, который ничего не знает о посетителе, привести к интерфейсу ICarElement, который обеспечивает метод Accept, обращающийся к методу посетителя ICarElementVisitor<TResult>, соответствующий типу Engine. Адаптер решал эту проблему, однако, при необходимости адаптировать к интерфейсу ICarElement значительное количество классов (даже 10), без кодогенератора будет скучно. Каждый адаптер – 12 линий кода. 120 линий кода для адаптации 10 классов – явный перебор, если есть другие решения. А они есть!

Восстановим и упростим предметную область примера:

class CarElement
{ 
}

class Wheel : CarElement
{
}

class Engine : CarElement
{
}
    
class Car : CarElement
{
    public Wheel[] Wheels = Enumerable.Range(1, 4).Select(_ => new Wheel()).ToArray();
    public Engine Engine = new Engine();
}

Я оставил супертип у иерархии частей машины. Он играет только роль обобщающего типа. Если супертипа в вашей иерархии нет - можно вместо него использовать System.Object. Никакой ответственности на супертип CarElement не накладывается. Никаких методов типа Accept он не предоставляет. Считаем, что создатель этой иерархии не задумывался о применении паттерна посетитель.

Но нам хочется воспользоваться паттерном посетитель. Воспроизведу код из предыдущего поста. Единственное отличие – для класса Engine не используется адаптер.

interface ICarElementVisitor<out TResult>
{
    TResult Visit(Wheel visitable);
    TResult Visit(Engine visitable);
    TResult Visit(Car visitable);
}

class GetNameVisitor : ICarElementVisitor<string>
{
    public string Visit(Wheel visitable)
    {
        return "wheel";
    }

    public string Visit(Engine visitable)
    {
        return "engine";
    }

    public string Visit(Car visitable)
    {
        return "car";
    }
}

class GetChildrenVisitor : ICarElementVisitor<IEnumerable<CarElement>>
{
    public IEnumerable<CarElement> Visit(Wheel visitable)
    {
        yield break;
    }

    public IEnumerable<CarElement> Visit(Engine visitable)
    {
        yield break;
    }

    public IEnumerable<CarElement> Visit(Car visitable)
    {
        yield return visitable.Engine;
        foreach (var wheel in visitable.Wheels)
        {
            yield return wheel;
        }
    }
}

Еще раз хочу обратить внимание на то что код конкретных посетителей не зависит от способа диспетчеризации вызовов, и потому инвариантен к диспетчеризации. За диспетчеризацию будет отвечать следующий метод-расширение:

static class CarElementExtensions
{
    public static T Accept<T>(this CarElement element, ICarElementVisitor<T> visitor)
    {
        var wheel = element as Wheel;
        if(wheel != null)
            return visitor.Visit(wheel);

        var engine = element as Engine;
        if (engine != null)
            return visitor.Visit(engine);

        var car = element as Car;
        if (car != null)
            return visitor.Visit(car);

        throw new NotSupportedException();
    }
}

Осталось повторить код теста. Он остался неизменен.

static class Test
{
    public static void TestVisitor()
    {
        var childrenVisitor = new GetChildrenVisitor();
        var nameVisitor = new GetNameVisitor();

        CarElement car = new Car();

        var elements = car.Walk(e => e.Accept(childrenVisitor));
        var elementNames = elements.Select(e => e.Accept(nameVisitor));

        foreach (var elementName in elementNames)
        {
            Console.WriteLine(elementName);
        }
    }

    public static IEnumerable<T> Walk<T>(this T root, Func<T, IEnumerable<T>> next)
    {
        var q = next(root).SelectMany(n => Walk(n, next));
        return new[] { root }.Concat(q);
    }
}

Таким образом, для того чтобы добавить обход по некоторому классу, достаточно внести его в интерфейс посетителя ICarElementVisitor и добавить несколько строк в метод расширение Accept. Этот подход существенно экономнее, чем написание адаптеров к непослушным классам. Осталось только сделать замечание, что представленный в этом посте подход нельзя называть классическим посетителем.

Еще один штрих будет полезен тем, кто уже перешел на .NET 4, либо собирается переходить на него. Написание метода-расширения Accept можно водрузить на рантайм! Вот так:

static class CarElementExtensions
{
    public static T Accept<T>(this CarElement element, ICarElementVisitor<T> visitor)
    {
        return visitor.Visit((dynamic)element);
    }
}

Решение о том, какой из методов интерфейса ICarElementVisitor нужно вызывать для конкретного объекта CarElement, будет принято прямо во время выполнения программы. Полагаю, что это несколько снизит производительность, возможно стоит относиться к этому осторожно при посещении больших иерархий.

Последняя деталь – в связи с неожиданным поведением RuntimeBinder-а, не получается использовать следующую форму объявления интерфейса посетителя:

interface IVisitor<in TVisitable, out TResult>
{
    TResult Visit(TVisitable visitable);
}

interface ICarElementVisitor<out TResult> :
    IVisitor<Wheel, TResult>,
    IVisitor<Engine, TResult>,
    IVisitor<Car, TResult>
{
    //TResult Visit(Wheel visitable);
    //TResult Visit(Engine visitable);
    //TResult Visit(Car visitable);
}

Binder считает что у интерфейса ICarElementVisitor нет методов Visit. Это действительно так, но такое поведение отличается от поведения компилятора C#. Подозрение о том что это баг есть не только у меня.

Код с динамической диспетчеризацией вполне работоспособен с первым объявлением интерфейса ICarElementVisitor в этом посте.

Visitor revisited

noreply@blogger.com (samius) — Fri, 30 Apr 2010 16:15:00 +0000

Сегодня я покажу свое видение паттерна Visitor. У меня складывается впечатление о том что в значительном количестве источников он представлен не самым удачным образом.

Рассмотрим пример из википедии. К сожалению, это типичный такой примерчик посетителя не без недостатков. Я бы даже сказал с ошибками.
Первая и не самая серьезная ошибка примера – то что вложенные элементы Car хранятся в массиве и паттерн Visitor – не лучший способ для перебора этих элементов. Куда проще и нагляднее было бы прикрутить паттерн Composite.
Вторая ошибка серьезнее – обход структуры заложен в методах accept. Я не считаю метод accept подходящим местом для расположения логики обхода структуры.
Я обозначил их для того, чтобы пробегая дальше по определениям сосредотачивать внимание именно на этом аспекте.

Вернемся к началу статьи в Wikipedia:

In object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure it operates on. A practical result of this separation is the ability to add new operations to existing object structures without modifying those structures.

Т.е. нам обещают что операции можно прикручивать на существующую структуру. Однако пример демонстрирует что мы не можем прикрутить обход извне. Более того, расположенная логика обхода в методе accept мешает выполнять другие операции над одиночными элементами структуры. Будучи примененный к Car посетитель CarElementPrintVisitor неизбежно выведет в консоль имена всех элементов машины, хотим мы этого или нет. Любая новая операция обречена выполняться над всей структурой. И об этом ничего не сказано в “определении”. В определении вообще ни слова про обход структуры, но как видно из примера, ничего кроме обхода паттерн делать не умеет. Но зато умеет их делать по-разному.

GoF

Назначение
Описывает операцию, выполняемую с каждым объектом из некоторый структуры. Паттерн посетитель позволяет определить новую операцию, не изменяя классы этих объектов.

Опять ничего про обход в назначении паттерна. Зато об обходе написано далее:

Результаты

Упрощает добавление новых операций. …

Объединяет родственные операции и отсекает те, которые не имеют к ним отношения. …

добавление новых классов ConcreteElement затруднено …

Посещение различных иерархий классов.

Аж на 4-м месте в списке результатов применения после отрицательного результата.
И далее:

Реализация
….
Какой участник несет ответственность за обход структуры. Посетитель должен обойти каждый элемент структуры объектов. Вопрос в том, как туда попасть.

Вот как, должен? А как же операции, не связанные с обходом?

Ответственность за обход можно возложить на саму структуру объектов, на посетителя и на отдельный объект итератор.

На саму структуру объектов – мы уже видели как это делается и к чему приводит.

Другое решение – воспользоваться итератором для посещения элементов. … Поскольку внутренние итераторы реализуются самой структурой объектов, то работа с ними во многом напоминает предыдущее решение, когда за обход отвечает структура.

Ну а почему тогда не композит?

Можно даже поместить алгоритмы обхода в посетитель, хотя закончится это дублированием кода обхода в каждом классе ConcreteVisitor для каждого агрегата ConcreteElement. Основная причина такого решения – необходимость реализовать особо сложную стратегию обхода (?!?!?!?), зависящую от результатов операций над объектами структуры. Этот случай рассматривается в разделе “Пример Кода”.

Если честно, то я не понимаю, откуда дублирование. И в разделе “Пример Кода” обход реализован в методах accept.

Джошуа Кериевски (Рефакторинг с использованием шаблонов) считает что все знакомы с назначением паттерна и пишет просто:

Переместить задачу накопления в реализацию шаблона Visitor, который для накопления информации может посетить каждый класс.

Да и рассматривает он Visitor только лишь в аспекте Move Accumulation to Visitor.

Роберт К. Мартин (Быстрая разработка программ. Принципы, примеры, практика)

Семейство Visitor позволяет добавлять к существующим иерархиям новые методы без обновления этих иерархий.

Отлично, новые методы без обновления этих иерархий! Кстати, чуть ли не единственный случай, где пример Visitor-а не содержит обхода. СОВСЕМ НЕ СОДЕРЖИТ.

The Visitor pattern and multiple dispatch

Its purpose is to provide new operations on a class or set of related classes without actually altering the classes involved.

Пример тоже не содержит обхода.

Попытаемся осмыслить

Итак, все рассмотренные источники (кроме Д. Кериевски) утверждают что паттерн предназначен для обеспечения новых операций без изменений классов структуры объектов. Для меня это ключевая особенность паттерна. Вот почему:

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

Какие еще бывают зайцы кроме обхода?

Валидация объектов (существуют разные причины по которым валидацию следует рассматривать как внешнюю по отношению к объектам операцию)
Вызов метода сохранения объекта в БД, Log файл, рисование на специализированных устройствах
Размазывание объектов по View-шкам GUI и собирание информации с вьюшек обратно в объект (это только пример, совсем не значит что я так делаю)
Получение локализованного наименования объекта
…

В общем все то, что нужно делать специальным способом в зависимости от типа объекта, но что по каким-то причинам не следует вставлять в методы объекта(ов).

Пример: есть Order и Product, которые не знают своих имен, но их надо как-то назвать чтобы представить пользователю. Операция получения названия объекта – внешняя по отношению к Order-у. Все к тому, чтобы воспользоваться посетителем еще раз (если он уже есть). Но если в методе accept класса Order-а реализован обход, то получить название Order-а мы сможем только в случае когда у Order-а нет вложенных объектов.

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

Приведу исходный код примера из википедии, но на C# и значительно упрощенный так, чтобы в нем осталась лишь суть паттерна и ничего более:

interface ICarElementVisitor
{
    void Visit(Wheel wheel);
    void Visit(Engine engine);
}

interface ICarElement
{
    void Accept(ICarElementVisitor visitor);
}

class Wheel : ICarElement
{
    public void Accept(ICarElementVisitor visitor)
    {
        visitor.Visit(this);
    }
}

class Engine : ICarElement
{
    public void Accept(ICarElementVisitor visitor)
    {
        visitor.Visit(this);
    }
}

class CarElementPrintVisitor : ICarElementVisitor 
{
    public void Visit(Wheel wheel)
    {
        Console.WriteLine("wheel");
    }
    public void Visit(Engine engine)
    {
        Console.WriteLine("engine");
    }
}

class Test
{
    public static void TestVisitor()
    {
        var elements = new ICarElement[] {new Engine(), new Wheel()};
        var visitor = new CarElementPrintVisitor();
        foreach (var carElement in elements)
        {
            carElement.Accept(visitor);
        }
    }
}

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

Что мне еще не нравится в этом коде?
Метод

void Visit(Wheel wheel);

не позволяет получить результат применения паттерна напрямую. Единственный способ что-то получить – накопить это что-то в конкретном классе посетителя, либо извне (например в глобальной переменной) и потом забрать значение. Было бы лучше, если бы визитор умел возвращать результат операции. Но опять-таки, если операции разные, то и типы результатов у них будут разные. Тип возвращаемого результата должен передаваться generic параметром интерфейса (а не метода!!! Важно, чтобы все методы Visit интерфейса посетителя меняли тип результата синхронно, а не по отдельности):

TResult Visit(Wheel wheel);

Отлично. Еще бы уметь передать дополнительный аргумент. Хотя это как раз лишнее. Аргумент можно передать непосредственно в класс посетителя.

Итак, интерфейс посетителя будет выглядеть так:

interface ICarElementVisitor<out TResult> 
{
    TResult Visit(Wheel wheel);
    TResult Visit(Engine engine);
    TResult Visit(Car car); 
}

А лучше чуть по-другому:

interface IVisitor<in TVisitable, out TResult>
{
    TResult Visit(TVisitable visitable);
}

interface ICarElementVisitor<out TResult> :
    IVisitor<Wheel, TResult>,
    IVisitor<Engine, TResult>,
    IVisitor<Car, TResult>
{
    //TResult Visit(Wheel visitable);
    //TResult Visit(Engine visitable);
    //TResult Visit(Car visitable);
}

Функционально разницы никакой, просто я побаиваюсь напутать что-то с сигнатурой одного из методов, а вынесение метода Visit в отдельный интерфейс позволяет исключить некоторые ошибки.
(+) ключевые слова in/out в объявлении интерфейса
Если кого-то смущают ключевые слова in и out в списке generic параметров интерфейса, то об этом можно почитать здесь. Для этой статьи они никакой роли не играют и должны быть удалены при использовании кода в версиях языка C# 2.0-3.0
(-) ключевые слова in/out

Интерфейс элемента напротив не должен зависеть от generic параметров, но метод Accept должен уметь работать с разными типами посетителей:

interface ICarElement
{
    TResult Accept<TResult>(ICarElementVisitor<TResult> visitor);
}

Вот собственно реализация конкретного элемента паттерна:

class Wheel : ICarElement
{
    public TResult Accept<TResult>(ICarElementVisitor<TResult> visitor)
    {
        return visitor.Visit(this);
    }
}

Ничего кроме метода Accept! Все как и в стандартных примерах, только угловых скобочек побольше.

Дальше будет элемент посложнее. Помните, в определениях говорилось о том, что паттерн visitor можно применять к существующим структурам не модифицируя их? Покажу как это можно сделать не модифицируя элемент совсем (с помощью адаптера).

class Engine
{
}

class EngineAdapter : ICarElement
{
    public EngineAdapter(Engine engine)
    {
        Engine = engine;
    }
    public Engine Engine { get; private set; }

    public TResult Accept<TResult>(ICarElementVisitor<TResult> visitor)
    {
        return visitor.Visit(Engine);
    }
}

Можно было интерфейс ICarElementVisitor замкнуть на EngineAdapter вместо Engine, если бы это играло какую-то роль.

Теперь составной элемент Car. Обратите внимание на то, что метод Accept не содержит логики обхода!

class Car : ICarElement
{
    public Wheel[] Wheels = Enumerable.Range(1, 4).Select(_ => new Wheel()).ToArray();
    public Engine Engine = new Engine();
        
    public TResult Accept<TResult>(ICarElementVisitor<TResult> visitor)
    {
        return visitor.Visit(this);
    }
}

Дальше код визитора, достающего имена объектов:

class GetNameVisitor : ICarElementVisitor<string>
{
    public string Visit(Wheel visitable)
    {
        return "wheel";
    }

    public string Visit(Engine visitable)
    {
        return "engine";
    }

    public string Visit(Car visitable)
    {
        return "car";
    }
}

Дальше чуть сложнее. Посетитель, который из элементов достает наборы вложенных элементов:

class GetChildrenVisitor : ICarElementVisitor<IEnumerable<ICarElement>>
{
    public IEnumerable<ICarElement> Visit(Wheel visitable)
    {
        yield break;
    }

    public IEnumerable<ICarElement> Visit(Engine visitable)
    {
        yield break;
    }

    public IEnumerable<ICarElement> Visit(Car visitable)
    {
        yield return new EngineAdapter(visitable.Engine);
        foreach (var wheel in visitable.Wheels)
        {
            yield return wheel;
        }
    }
}

Здесь следует обратить на метод посещения составного объекта Car. Проходя по engine элементу он возвращает не сам элемент, а адаптер.

Ну и в конце-концов метод, который демонстрирует поведение паттерна:

public static void TestVisitor()
{
    var childrenVisitor = new GetChildrenVisitor();
    var nameVisitor = new GetNameVisitor();

    ICarElement car = new Car();

    var elements = car.Walk(e => e.Accept(childrenVisitor));
    var elementNames = elements.Select(e => e.Accept(nameVisitor));

    foreach (var elementName in elementNames)
    {
        Console.WriteLine(elementName);
    }
}

static IEnumerable<T> Walk<T>(this T root, Func<T, IEnumerable<T>> next)
{
    var q = next(root).SelectMany(n => Walk(n, next));
    return new[] { root }.Concat(q);
}

Во-первых создаются экземпляры посетителей и составного элемента Car. Далее с помощью метода Walk, представляющего дерево в виде одиночной последовательности и описанного в предыдущем посте, а так же посетителя GetChildrenVisitor, строится набор элементов. Затем набор элементов преобразовывается в набор имен с помощью GetNameVisitor и выводится в консоль циклом foreach.

Итог

Итак, я восстановил функциональность примера из википедии, но избежал недостатков. Перечислю еще раз достоинства такого подхода:

метод accept не содержит логики обхода (это достоинство само по себе, как и вытекающие из него следствия);
логика обхода содержится снаружи иерархии, и это позволяет менять ее не изменяя объектов иерархии;
внешний обход не мешает выполнению других операций, реализованных с помощью паттерна, и более того, позволяет комбинирование обхода с другими операциями;
посетитель, возвращающий результат, позволяет избавиться от накопления данных внутри объектов либо внутри самого посетителя и использовать мощь LINQ в обходе иерархии;
посетитель, возвращающий generic результат, позволяет удобно совмещать одним паттерном множество разнотипных операций.

Замечу так же, что никакого дублирования логики обхода в каждом классе ConcreteVisitor, как это было написано в GoF, не намечается.

Надеюсь, что моя статья позволит читателям использовать паттерн Visitor более эффективно.

З.Ы.
Респект тем кто дочитал до конца.

LINQ-ом по деревьям (часть 2)

noreply@blogger.com (samius) — Sun, 11 Apr 2010 22:19:00 +0000

В предыдущей части я рассказал о том, как ходить по деревьям LINQ-ом и о том какие проблемы с производительностью может породить цепочка перечислителей.
Итак, в бенчмарке присутствуют следующие методы:

Walk

С прошлого поста заменил ~~Enumerable.Repeat(root, 1)~~ на new [] {root}.

public static IEnumerable<T> Walk<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var q = next(root).SelectMany(n => Walk(n, next));
    return new []{root}.Concat(q);
}

Walk2

Слегка оптимизированная версия Walk, где методы SelectMany и Concat развернуты в конечный автомат yield return:

public static IEnumerable<T> Walk2<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    yield return root;
    foreach (var child in next(root))
    {
        foreach (var node in Walk2(child, next))
        {
            yield return node;
        }
    }
}

Эта версия Walk метода покажет нам ценность такого переписывания. Я не буду пропагандировать ни за ни против, просто предоставлю данные, а решать пусть будет каждый сам за себя, пользоваться ли высокоуровневыми методами, либо эквивалентными циклами.

WalkS

WalkS – обход с помощью структуры Stack<T>. Это самый простой способ преобразования callstack-а в структуру данных.

public static IEnumerable<T> WalkS<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var stack = new Stack<T>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var x in next(current).Reverse())
        {
            stack.Push(x);
        }
    }
}

Здесь использован метод Enumerable.Reverse чисто для сохранения порядка обхода в соответствии с оригинальным методом Walk. Но гоняться в бенчмарке будет немного другой метод:

WalkS2

У этой модификации используется 2 стека (Stack<T>). Второй заменяет Enumerable.Reverse.

public static IEnumerable<T> WalkS2<T>(
    this T root,
    Func<T, IEnumerable<T>> next)
{
    var stack = new Stack<T>();
    var stack2 = new Stack<T>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var x in next(current))
        {
            stack2.Push(x);
        }
        foreach (var x in stack2)
        {
            stack.Push(x);
        }
        stack2.Clear();
    }
}

WalkL

В очередной модификации вместо Stack<T> используется односвязный список.

class ListNode<T>
{
    public T Value { get; private set; }
    public ListNode<T> Next { get; private set; }

    public ListNode(T value, ListNode<T> next)
    {
        Value = value;
        Next = next;
    }
}
public static IEnumerable<T> WalkL<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var list = new ListNode<T>(root, null);
    while (list != null)
    {
        var current = list;
        list = list.Next;
        yield return current.Value;

        foreach (var x in next(current.Value).Reverse())
        {
            list = new ListNode<T>(x, list);
        }
    }
}

Но воевать будет не она, а та что использует 2 односвязных списка:

WalkL2

Последняя модификация, учавствующая в бенчмарке использует один список для замены callstack-а, другой вместо Enumerable.Reverse().

public static IEnumerable<T> WalkL2<T>(
    this T root,
    Func<T, IEnumerable<T>> next)
{
    var list = new ListNode<T>(root, null);
    while (list != null)
    {
        var currentNode = list;
        var nextNode = list.Next;
        yield return currentNode.Value;

        ListNode<T> tmpList = null;
        foreach (var v in next(currentNode.Value))
        {
            tmpList = new ListNode<T>(v, tmpList);
        }

        if(tmpList != null)
        {
            for (; tmpList != null; tmpList = tmpList.Next)
            {
                nextNode = new ListNode<T>(tmpList.Value, nextNode);
            }
        }
        list = nextNode;
    }
}

Depth

В бенчмарке учавствует еще один метод, который тоже обходит дерево, но при этом не пытается выпрямить его узлы в последовательность. Подсчет глубины конкретного двоичного дерева в чисто рекурсивной форме. Этот метод будет эталоном скорости.
Вслед за методом GetDepth привел класс узла дерева, на котором проходил бенчмарк.

public static int GetDepth<T>(this Node<T> node)
{
    return (node == null)
        ? 0
        : 1 + Math.Max(
            node.Left.GetDepth(),
            node.Right.GetDepth());
}

public class Node<T>
{
    public Node(T value, Node<T> left, Node<T> right)
    {
        Value = value;
        Left = left;
        Right = right;
    }
    public T Value { get; set; }
    public Node<T> Left { get; set; }
    public Node<T> Right { get; set; }
}

Забег №1

Случайным образом перемешанный массив индексов [0..N] подается на вход алгоритму, строящему двоичное дерево (без балансировки). Полученное дерево скармливается вышеуказанным методам Walk* и у полученного IEnumerable<int> извлекается последний элемент Enumerable.Last ().
Результаты первого забега (по оси x кол-во элементов, по y – время обхода в секундах):

Следующим образом выглядит таблица времен обхода дерева из 10М элементов:

Метод обхода	Время
Walk	00:00:24.7759974
Walk2	00:00:10.8108170
WalkS2	00:00:03.5185059
WalkL2	00:00:02.7030328
Depth	00:00:01.0753161

Что-то здесь не так. Судя по графику, нерекурсивные методы значительно быстрее, но я не увидел зависимости графиков рекурсивных методов от глубины дерева… И деревья-то подсовывались не слишком глубокие. Глубина дерева из случайно перемешанного набора из 20М индексов не превышала 60. При таком подходе, увеличивая вдвое число элементов, мы будем получать увеличение глубины дерева лишь на единицу. Геометрическая, блин, прогрессия! Страшно подумать, сколько нужно элементов, для того чтобы достичь глубины 1000 :(
Но кое-какие выводы можно сделать и из этого забега:

Методы Walk и Walk2 идут ноздря в ноздрю и значительного перевеса не наблюдается, хотя и foreach-и немного опережают высокоуровневые методы SelectMany+Concat.
Нерекурсивные методы WalkS2 и WalkL2 достаточно близки к эталонному Depth
Односвязные списки немного шустрее чем Stack<T>.

Забег №2

То же самое двоичное дерево, но исходные данные теперь не перемешаны, потому получается вырожденное в список дерево, чья глубина будет равна числу элементов. Элементов будет мало, но теперь дерево будет сосредоточено в глубину.

Что интересно, рекурсивные методы Walk и Walk2 не осилили дерево глубиной 12000 и отвалились с StackOverflowException. Однако метод GetDepth работал стабильно (~~полагаю что JIT распознал хвостовую рекурсию и преобразовал рекурсию в цикл~~ это не так, спасибо Пельмешко за внимательность. GetDepth-у для исключения нужно глубину 65000).

Этот эксперимент показывает нелинейную зависимость рекурсивных методов Walk и Walk2 от глубины дерева и совершенно ничего не показывает о нерекурсивных методах WalkS2, WalkL2 и рекурсивном ~~но преобразованном в цикл~~ методе GetDepth. Т.е. их зависимость от глубины на этом графике не видна. Время, которое показывали три последних метода на обходе 10000 элементов не превышало 0.001 секунды.

Итого:

Рекурсивная комбинация перечислителей представляет опасность переполнения стека на глубинах дерева от 10К. На глубинах дерева до 1000 рекурсивными перечислителями вполне можно пользоваться и их производительность хоть и уступает нерекурсивным методам, но может быть вполне приемлема для множества задач.

P.S.

На RSDN Sinix-ом был приведен другой метод выпрямления рекурсивных комбинаций перечислителей. Нетрудно увидеть схожесть его метода с представленными мной. Отличия в сигнатуре (принимает коллекцию узлов), в порядке обхода (нет Reverse), да и в стек он помещает не узлы, а перечислители узлов. Не знаю, в чем фокус, но его метод работает примерно в 2 раза медленнее WalkS2, представленного мной (с Reverse-ом с помощью дополнительного стека). Ну и собственно название, UngroupRecurseEnumerator сбивает с толку. Это тот же самый обход дерева.

P.P.S.

В этой статье упоминается Range через yield foreach:

static IEnumerable<int> FromTo(int b, int e)
{
    if (b > e)
        yield break;
    yield return b;
    yield foreach FromTo(b + 1, e);
}

А вот и наш ответ Чемберлену

static IEnumerable<int> FromTo(int b, int e)
{
    return b.WalkL2(i =>
         (i < e)
            ? new int[] { i+1 } 
            : new int[] {});
}

Не столь красивый, но не требующий изменения языка.
А yield foreach все-таки сила!

Upd.

Я таки написал версию GetDepth с хвостовой рекурсией:

public static int GetDepthC<T>(this Node<T> node)
{
    return GetDepthCps(node, d => d);
}

static int GetDepthCps<T>(Node<T> node, Func<int, int> cont)
{
    return (node == null)
       ? cont(1)
       : GetDepthCps(node.Left, leftDepth =>
            GetDepthCps(node.Right, rightDepth =>
                cont(Math.Max(leftDepth, rightDepth))));
}

Естественно я не ожидал что C# ее выпрямит в цикл. А вот F# выпрямляет!
Если будут пожелания, можно в другой раз написать что-то вроде "CPS для чайников". Толку, правда, будет немного в рамках C#. Но разжевать предмет можно попробовать.

LINQ-ом по деревьям

noreply@blogger.com (samius) — Fri, 02 Apr 2010 19:23:00 +0000

Сегодня покажу универсальный код обхода любых деревьев с однотипными узлами.

public static class TreeWalker
{
    public static IEnumerable<T> Walk<T>(T root, Func<T, IEnumerable<T>> next)
    {
        var q = next(root).SelectMany(n => Walk(n, next));
        return Enumerable.Repeat(root, 1).Concat(q);
    }
}

За исключением нескольких отличий, этот метод похож на Enumerable.SelectMany. Отличия:

В качестве первого аргумента принимается один элемент (корень дерева), а не последовательность.
Метод рекурсивно применяется ко всем элементам, полученным с помощью делегата next из исходного.

Области применения

Для начала прогуляемся по дереву каталогов файловой системы:

foreach(var dir in TreeWalker.Walk(@"d:\Test", Directory.GetDirectories))
{
     Console.WriteLine(dir);
}

Однако, гулять – не главный бенефит этого метода. Главный – “выпрямлять” деревья для того чтобы по ним можно было гулять LINQ-ом.

Еще один пример - собрать только листовые узлы у TreeView можно такой конструкцией

var q = from rootNode in treeVew1.Nodes.Cast<TreeNode>()
        from node in TreeWalker.Walk(rootNode, n => n.Nodes.Cast<TreeNode>())
        where node.Nodes.Count == 0
        select node;

Совсем не обязательно обходить дерево целиком. Например, при работе с двоичными деревьями поиска, с помощью метода Walk можно находить минимальный, максимальный элемент и даже делать поиск конкретного элемента за время соразмерное высоте дерева (при сбалансированном дереве – O(log N)).

Пусть у нас есть дерево из узлов следующего вида:

public class Node<T>
{
    public Node(T value, Node<T> left, Node<T> right)
    {
        Value = value;
        Left = left;
        Right = right;
    }
    public T Value { get; private set; }
    public Node<T> Left { get; private set; }
    public Node<T> Right { get; private set; }
}

Тогда для поиска минимального элемента потребуется следующий вспомогательный метод:

public static IEnumerable<Node<T>> NextLeft<T>(this Node<T> root)
{
    if (root.Left != null)
        yield return root.Left;
}

Тогда найти узел с минимальным элементом двоичного дерева можно следующей конструкцией:

TreeWalker.Walk(root, r => r.NextLeft()).Last();

Для поиска узла с конкретным элементом потребуется более хитрая вспомогательная функция, которая будет возвращать подузлы Left или Right в зависимости от результата сравнения значения текущего узла с искомым значением.

А если к функции получения дочерних узлов добавить маркировку пройденных узлов, то из метода Walk получится алгоритм “поиск в глубину” для графов.

Особенности реализации

Вместо Enumerable.Repeat(root, 1) можно было сделать new [] { root}, но я хотел сделать акцент на другом.

Как можно заметить, метод Walk ленив. Притом что его можно считать рекурсивным (он использует себя в определении своего тела), он не вызывает себя рекурсивно при обращении, а возвращает управление сразу же, возвращая перечислитель. Однако, агрессивное использование стека при работе метода никуда не делось, более того, оно более агрессивно, по сравнению с обычным рекурсивным методом. Все дело в том, что при погружении в дерево выстраиваются в цепочку активные перечислители на манер вложенных декораторов, длина цепочки которых пропорционален глубине погружения в дерево.

next(root).SelectMany добавляет в цепочку свои перечислители (полагаю что больше одного, лениво лезть в рефлектор). Над ним надстраивается Сoncat перечислитель.

Даже если дерево состоит только лишь из одного корневого элемента, вызовы IEnumerator<T>.MoveNext(), IEnumerator<T>.Current будут выполнены каскадно через 2-3 (а может и больше) перечислителей.

Итого, обход дерева высотой в несколько сот тысяч элементов с хорошей вероятностью может завершиться StackOverflowException (udated: 12000 элементов достаточно)… Даже если не завершится, цена вызова по цепочке перечислителей длиной в несколько глубин дерева может серьезно сказаться на производительности приложения. Ведь для получения очередного элемента нужно сделать два таких сверхглубоких вызова (MoveNext и Current).

Естественно, ситуацию можно изменить за счет переписывания метода Walk с какой-нибудь структурой данных, эмулирующей стек вызовов (например, Stack<T>). Но я пока в этом необходимости не испытываю. StackOverflowException я видел только на тестовых данных (двоичное дерево из миллиона элементов). А на тех данных, с которыми приходилось работать методу Walk, проблем с производительностью или с переполнением стека нет. Даже не было повода замеров производительности метода Walk с целью выявить зависимость времени выполнения от глубины дерева.

Если кому-то вопрос производительности и/или нерекурсивный вариант Walk метода окажется интересным, дайте знать в комментариях. А пока будем считать что я поделился красивым но не очень быстрым способом обхода деревьев с помощью LINQ-а.

P.S.

На авторство не претендую, аналогичный подходы к обходу деревьев я определенно встречал, единственное что я сделал – обобщил его, представил и предостерег от использования с деревьями больших глубин.

Монады для чайников

noreply@blogger.com (samius) — Tue, 01 Dec 2009 15:04:00 +0000

Вот и я написал собственное введение в монады. Нет, вовсе не потому что я разобрался в этом вопросе лучше других. Мне кажется, что мое введение будет проще чем другие, т.к. оно требует только лишь знаний языка C# и базовых знаний LINQ, и не потребует опыта в функциональном программировании. Я не обещаю, что после прочтения этого поста вы будете понимать и уметь использовать монады. Я только лишь покажу, что же это такое. Но все равно, после преодоления моего поста, должно сложиться хотя бы поверхностное представление о предмете. Полагаю, что вы уже сможете понимать, о чем речь, когда столкнетесь с упоминанием монад в будущем.

Тем же, кто уже знаком в достаточной мере с монадами, но все равно решит прочитать мой пост, предлагаю выразить критику, буду рад.

Значительная часть блогов лишь мельком затрагивает понятие монады чтобы рассказать о каком-нибудь монадном парсер-комбинаторе, асинхронном workflow или о чем-то пострашнее. Некоторые блоги и материалы отталкиваются от математики, комбинирования чистых функций, пользы монадах в функциональном программировании и прочей теории. А я предлагаю пожевать знакомые большинству концепции и повести читателя не от простого к сложному, а от уже знакомого к более простому.

Знакомство

Полагаю, что многие из разработчиков C# пользуются методом Enumerable.SelectMany либо вложенными друг в друга from clause. На всякий случай напомню, что from clause транслируется компилятором в вызов SelectMany. Тем, кто не понимает эти конструкции (читай не привыкнул к ним) рекомендую начать к ним привыкать как можно скорее. Это не сложно, к хорошему быстро привыкаешь. Вот статья, где упоминаются вложенные from конструкции - Query Expression Basics.

Рассмотрим следующий запрос в форме Query Expression:

IEnumerable<City> cityQuery =
    from country in countries
    from city in country.Cities 
    select city;

Его можно записать в следующем виде:

IEnumerable<City> cityQuery = countries
    .SelectMany(country => country.Cities);

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

IEnumerable<TResult> SelectMany<TSource, TResult>(
   this IEnumerable<TSource> source,
   Func<TSource, IEnumerable<TResult>> selector)

Напомню её назначение:

Проецирует каждый элемент последовательности в объект IEnumerable<T> и объединяет результирующие последовательности в одну последовательность.

Думаю, стоит обратить внимание на одну деталь:

именно проецирует (связывает), а не выбирает. То что у объекта типа Country есть свойство со списком городов – это лишь совпадение. Для проекции мы могли бы использовать не только свойство Cities, а любой другой способ получения списка городов, будь они записаны в файле, в базе данных или возвращены веб-сервисом. Да и вместо класса страны мог быть ее числовой код.

Вобщем, знакомьтесь, SelectMany это и есть монада! Точнее ее часть… Точнее часть одной из монад… Но это пока не важно. Важно то, что если вы раньше не были знакомы с монадами, то теперь вы можете в ответ на вопрос “знаете ли вы что такое монады, используете ли их?” отвечать “А-то!!!” и многозначительно ухмыляться.

Дабы избежать недопонимания, отметём все лишнее, что было помянуто. Сначала исключим Query Expressions (это from … select…). Они к монадам не имеют ровно никакого отношения. Это только синтаксический сахар, который может быть применен в том числе и к монадным вычислениям (позже об этом вспомним). Вообще любое Query Expressions выражение можно записать в эквивалентной форме в стандартном синтаксисе (чем и занимается компилятор) без потери функциональности. Усугубится только вид выражения, да и то не всегда.

Ленивые вычисления (это я про итераторы IEnumerable<T>) тоже не имеют прямого отношения к монадам. Вместо IEnumerable<TSource> и IEnumerable<TResult> мы могли бы использовать List<TSource> и List<TResult> без потери работоспособности выражения. Разве что оно стало бы менее обобщенным, и позволяло бы работать только со списками. Т.е. IEnumerable<T> тоже левый тип.

Extension method-ы не имеют отношения к монадам. Это всего лишь удобная форма записи вызова функций через точку (как если бы это был метод экземпляра).
Итого: тип IEnumerable<?> заменяю на некий C<?>, чтобы не мозолил глаза. Нам не важно что там за тип, главное что это generic тип. Настолько не важно, что я заменю его сразу на M<?> (позже станет ясно, почему именно M). А так же выкину ключевое слово this и заменю название метода SelectMany на более традиционное Bind (в языке Haskell это будет “>>=”). Вот что получилось:

M<U> Bind<T,U>(M<T> source, Func<T, M<U>> selector);

Мы получили что-то более широкое, чем SelectMany. Я бы сказал, что мы получили целый класс функций, и SelectMany вместе с типом IEnumerable<?> определенно принадлежит к этому классу. Пора, пожалуй ввести определение монады, а после я покажу, близкие к природе SelectMany монады.

Определение монады

Монадой называется тройка (M, Return, Bind) где

М – одноаргументный generic тип M<T>
Return – функция, конструирующий экземпляр монадного типа М<T>
Bind – функция, связывающая монадные вычисления

Более того, тройку должны связывать 3 монадных закона. О них можно почитать в любом материале о монадах, потому я не буду акцентировать на них внимание.

Пожуём немного определение…
Тип M из определения - это тот самый тип M, которым я выше заменил IEnumerable в сигнатуре метода SelectMany. Он называется монадным типом.

Фунция Return – это функция, которая должна сгенерировать экземпляр монадного типа из экземпляра типа T (generic параметра типа M). Так, если нам требуется определить функцию Return для уже знакомой нам монады (с функцией SelectMany в качестве функции Bind), то она могла бы быть реализованной следующим образом:

IEnumerable<T> Return<T>(T value)
{
    return new T[] { value };
}

Функция Bind связывает монадное вычисление M<T> с монадным результатом М<U> с помощью функции проекции Func<T, M<U>>.

Итого, если мы возьмем определение монады, рассмотрим его в приложении к типу IEnumerable<T>, то тройка (IEnumerable<T>, Return, SelectMany) формально представляет монаду IEnumerable. Выполнение упомянутых монадных законов проверять не будем. Пост и так получился довольно длинным, хотя сложного в этом ничего нет. Заинтригованные читатели смогут проверить выполнение монадных законов сами.

Но тут я ввожу всех в заблуждение. Формально монада называется по названию монадного типа, но монады IEnumerable нет ни в каких анналах. Есть монада List (The List Monad). Так вот, тройка (IEnumerable<T>, Return, SelectMany) – это реализация монады List в .NET платформе.

Итак, после того, как мы узнали, что такое монада, конструкцией SelectMany все еще можно делать разные удобные вещи, какие мы могли делать до того, как узнали, что оно имеет отношение к монадам. Например, можно связывать коллекции с коллекциями и выпрямлять всё в одну коллекцию. Важно отметить, что в результате монадного связывания мы всегда получаем на выходе монадный тип, к которому можно применять связывание и далее.

Рассмотрим более глубокий пример:

var query = 
    from country in countries
    from city in country.Cities
    from street in city.Streets
    select streets;

Eго можно записать в следующей форме:

var query = countries
    .SelectMany(country => country.Cities)
    .SelectMany(city => city.Streets);

Может показаться что эти формы эквивалентны, но это не так. Результаты будут совпадать, но способы их получения разные. Вторая форма записи применяет последовательно SelectMany к результатам, полученным в предыдущих вычислениях. Т.е. сначала берется набор стран, потом SelectMany вычисляет плоскую последовательность всех городов стран, к ней применяется SelectMany, вычисляющий плоскую последовательность улиц всех городов.

Монадные вычисления используют другую стратегию. Для каждой страны находятся улицы городов страны, а затем улицы городов склеиваются в единую последовательность. Вот как это может выглядеть:

var query = countries.SelectMany(
                country => country.Cities.SelectMany(
                    city => city.Streets));

Или так, если записать в нотации без Extension Methods

var query = SelectMany(countries, country =>
                SelectMany(country.Cities, city => 
                    city.Streets));

Это и есть использование воплощения монады List в C#.
(Театральная пауза)
Вы спрашиваете:

-Это и есть та самая монада? Что делает обычный метод SelectMany монадой?

Я отвечаю:

- Да, это она самая! Выполнение монадных законов наделяет этот метод особенной магией и позволяет вызывать его, получать результат, а потом к результату применять его снова сквозь типы, обстоятельства, время, вытаскивая нужную нам трансформацию из любых глубин!

Наверняка вы пока не разделяете мой восторг, но меня просто прёт!

Монада List, вообще говоря, не самая простая монада из списка стандартных монад. Но вот так получилось, что познакомились мы сперва именно с ней. Тем легче будет перейти к более простым монадам.

Если честно, пытался я постичь более простые монады до понимания сути монады List. Не получалось, т.к. их смысл ускользал от меня. Вам я представлю возможность постичь их смысл через монаду List.

The Maybe Monad

В случае с коллекциями мы уже привыкли к тому, что в каждой коллекции элементов может быть много. Вообразим теперь коллекцию, в которой может быть не более одного элемента. Т.е. либо есть элемент, либо нет ни одного. Третьего не дано. От примера со странами, городами, улицами и домами перейдем к другому примеру:

Программа открывает файл, читает из него строку и ищет в базе данных значение, соответствующее этой строке. Если на каком-то этапе происходит ошибка, возвращается null.

Нет, не нравится. В файле может быть несколько строк, в базе данных может быть несколько значений… Не наш случай. Да и условие задачи стырено отсюда. Так же не очень интересно складывать 5 и Nothing (как здесь).

Возьмем Смерть Кащея! Это есть игла, которая в яйце, которое в утке, утка на сундуке. Дуб, зайцы, селезни, и т.п. – кыш с пляжа! Нам требуется написать программу, которая сможет достать Смерть Кащея, если она там действительно есть, и не сломается, если чего-то не хватает. Т.е. мы не уверены, есть ли сундук, что в сундуке действительно есть утка. Яйцо в утке тоже не факт, что есть. Ну и т.п. Неожиданности вроде двух яиц внутри утки нас не интересуют по условию задачи.

Можем воспользоваться каскадом вложенных if-ов, либо последовательностью выражений if(…==null) return null. Но мы-то тут с монадами знакомимся, а не с if-ами!

Монада List нам почти подходит. Если у сундука есть коллекция уток, у утки коллекция яиц, у яйца коллекция иголок. Можно записать решение в виде последовательного применения SelectMany:

var query = сундуки
    .SelectMany(сундук => сундук.Утки)
    .SelectMany(утка => утка.Яйца)
    .SelectMany(яйцо => яйцо.Иглы);
var смертьКащеяНайдена = query.Any();

Либо в виде монадного связывания:

var query = сундуки.SelectMany(сундук =>
                сундук.Утки.SelectMany(утка =>
                    утка.Яйца.SelectMany(яйцо =>
                        яйцо.Иглы)));
var смертьКащеяНайдена = query.Any();

получилось довольно компактно, но вот вместо коллекций уток, яиц и игл хорошо бы воспользоваться чем-то более простым. Нам не нужны здесь коллекции на самом деле. Тип Nullable<T> подошел бы вместо коллекций, не будь у него ограничения на тип параметра (только структуры). Впрочем, если вся наша предметная область описана структурами, то вполне подойдет.

Введем класс Maybe<T>, который будет устроен в точности как Nullable<T>, но без ограничений на тип T. Я его прямо скопирую из блога Wes Dyer-а вместе с реализацией метода SelectMany и ToMaybe (это аналог нашей функции Return):

class Maybe<T>
{
    public readonly static Maybe<T> Nothing = new Maybe<T>();
    public T Value { get; private set; }
    public bool HasValue { get; private set; }
    Maybe()
    {
        HasValue = false;
    }
    public Maybe(T value)
    {
        Value = value;
        HasValue = /*true;*/ (value != null);
    }
}

public static Maybe<U> SelectMany<T, U>(
     this Maybe<T> m,
     Func<T, Maybe<U>> k)
{
    if (!m.HasValue)
        return Maybe<U>.Nothing;
    return k(m.Value);
}

public static Maybe<T> ToMaybe<T>(this T value)
{
    return new Maybe<T>(value);
}

Я немного модифицировал конструктор типа Maybe, чтобы он мог принимать null-ы и возвращать экземпляр со свойством HasValue равным false (модификация будет работать только с reference типами. Инициализация Maybe Value-типами всегда будет возвращать экземпляр со значением).

Тогда выражение примет вид:

var query = сундук.ToMaybe().SelectMany(сундук => 
     сундук.Утка.ToMaybe().SelectMany(утка => 
         утка.Яйцо.ToMaybe().SelectMany(яйцо => 
             яйцо.Игла.ToMaybe())));
var смертьКащеяНайдена = query.HasValue;

Знакомьтесь – монада Maybe. Связывает каскад вычислений, каждое из которых может окончиться ничем, тогда последующие вычисления не потребуются.

Не уговаривайте меня, что if(сундук.Утка != null) проще чем монада. Я сегодня лишь демонстрирую монаду Maybe, а не склоняю к отказу от if-ов :)

The Identity Monad

Для понимания монады Identity потребуется представить списки с точностью одним обязательным элементом. Можно так же представить тип Maybe с отсутствующим флагом о наличии значения.

Так же нам потребуется упростить задачу о Смерти Кащея: теперь в сундуке есть в точности одна утка, в утке есть яйцо, в яйце есть игла. Никаких неожиданностей.

Вводим тип Identity и соответствующие ему методы (снова спасибо Wes Dyer-у):

class Identity<T>
{
    public T Value { get; private set; }
    public Identity(T value) { this.Value = value; }
}

public static Identity<T> ToIdentity<T>(this T value)
{
    return new Identity<T>(value);
}

public static Identity<U> SelectMany<T, U>(this Identity<T> id, Func<T, Identity<U>> k)
{
    return k(id.Value);
}

Теперь мы можем записать решение с помощью последовательных применений SelectMany:

var query = сундук.ToIdentity()
    .SelectMany(сундук => сундук.Утка.ToIdentity())
    .SelectMany(утка => утка.Яйцо.ToIdentity())
    .SelectMany(яйцо => яйцо.Игла.ToIdentity());
var смертьКащея = query.Value;

Решение задачи о Смерти Кащея с использованием Identity монады будет выглядеть так:

var query =
    сундук.ToIdentity().SelectMany(сундук =>
        сундук.Утка.ToIdentity().SelectMany(утка => 
            утка.Яйцо.ToIdentity().SelectMany(яйцо => 
                яйцо.Игла.ToIdentity())));
var смертьКащея = query.Value;

Решение такой постановки задачи гораздо проще записать без монады:

var смертьКащея = сундук.Утка.Яйцо.Игла;

Впрочем, как сказал автор статьи о монадах на rsdn.ru,

Такая монада находит применение с монадными трансформерами, которые в данной статье не рассматриваются. Будем считать, что это чисто иллюстративный простейший пример.

В отношении Identity монады мне добавить нечего.

Пристегиваем Query Expression (припудрим сахаром)

Внимательный читатель наверняка обратил внимание, что при том что утка, яйцо и игла имеют кол-во экземпляров не более одного, название метода связывания остается “SelectMany”, будто сущностей может быть больше одной. Вот тут пришла пора вспомнить Query Expressions.

В спецификации языка C# можно найти информацию о том, что Query Expressions может быть смаппирован в функцию со следующей сигнатурой:

C<V> SelectMany<T,U,V>(
    C<T> source,
    Func<T,C<U>> selector,
    Func<T,U,V> resultSelector);

При внимательном анализе можно заметить, что это функция есть более общая форма известной нам Bind (SelectMany), где к значению типа T и результату работы селектора C<U> применяется еще одна функция, возвращающая некоторое значение V, потом с помощью функции Return (ToMaybe) возвращается монадный тип с параметром V. Именно эта функция SelectMany используется компилятором для трансляции Query Expression выражений.
Назначение третьего аргумента выяснить оказалось несложно (покажу чуть позже).
Вот код более навороченной функции SelectMany:

static Maybe<V> SelectMany<T, U, V>(
    this Maybe<T> m,
    Func<T, Maybe<U>> k,
    Func<T, U, V> s)
{
    return m.SelectMany(x => k(x).SelectMany(y => s(x, y).ToMaybe()));
}

Пока примем его на веру. Теперь можно скомпилировать и выполнить следующий код:

static void Main()
{
    var m = from x in 1.ToMaybe()
            from y in 2.ToMaybe()
            from z in 3.ToMaybe()
            select x + y + z;
    Console.WriteLine(m.HasValue);
}

Посмотрев на результат с помощью Reflector-а можно увидеть (отформатировано мной):

Console.WriteLine(
    1.ToMaybe()
       .SelectMany(
           x => 2.ToMaybe(), 
           (x, y) => new { x = x, y = y })
       .SelectMany(<>h__TransparentIdentifier0 => 
           3.ToMaybe(), 
           (<>h__TransparentIdentifier0, z) => 
               ((<>h__TransparentIdentifier0.x + <>h__TransparentIdentifier0.y) + z))
       .HasValue);

Похоже что компилятор преобразовал исходный код так, как если бы он был написан следующим образом:

static void Main()
{
    var m = from x in 1.ToMaybe()
        from y in 2.ToMaybe()
        select new {x, y}
        into t
        from z in 3.ToMaybe()
        select t.x + t.y + z;
    Console.WriteLine(m.HasValue);
}

И дейсвтительно, если посмотреть Reflector-ом на результат компиляции этого выражения, мы увидим

Console.WriteLine(
    1.ToMaybe()
        .SelectMany(
            x => 2.ToMaybe(), 
            (x, y) => new { x = x, y = y })
        .SelectMany(
            t => 3.ToMaybe(),
           (t, z) => ((t.x + t.y) + z))
        .HasValue);

что в точности есть результат предыдущей декомпиляции с точностью до именования идентификатора t.

Внимательно сопоставим выражение QueryExpression с декомпилированным выражением:
from x in 1.ToMaybe() было преобразовано в 1.ToMaybe() и подано первым аргументом первого SelectMany метода.

from y in 2.ToMaybe() было преобразовано в 2.ToMaybe() и подано вторым аргументом первого SelectMany метода. Третьим аргументом стало сопоставление паре (x, y) выражения new { x, y }.

Результатом этих действий будет new { x, y }.ToIdintity(), который подается на вход второго метода SelectMany. Так же туда подается 3.ToMaybe() и выражение второго select clause.

Таким образом, трехаргументный SelectMany метод подставляется во все выражения from ? in expr, кроме самого первого. Третьим аргументом этого метода становится выражение в select clause, и если такого нет, то оно синтезируется компилятором искусственно. Это не совсем соответствует монадным связываниям выражений, однако на результате сказываться не должно.

Теперь можно делать выводы о том, что же делает супер версия SelectMany и как она реализована. Приведу вариант реализации без использования синтаксиса Extension Method:

static Maybe<V> SelectMany<T, U, V>(
    this Maybe<T> m,
    Func<T, Maybe<U>> k,
    Func<T, U, V> s)
{
    return SelectMany(
        m,
        x => SelectMany(
                k(x),
                y => s(x, y).ToMaybe()));
    //return m.SelectMany(x => k(x).SelectMany(y => s(x, y).ToMaybe()));
}

Внимание! Внешний метод SelectMany (двухаргументный) принимает значение m и лямбда функцию. Если значение m пусто, то внешний метод тут же возвращает Nothing, иначе он подаст m.Value на вход к переданной лямбда-функции и вернет ее результат. В свою очередь лямбда-функция устроена так, что она проверит результат выполнения метода k над первым аргументом. И если он Nothing, вернет Nothing. Иначе вернет результат выполнения метода s над x и y, завернутый в монадный тип Maybe. Итак, в случае наличия значения в m, и наличия значения в результате k(m.Value), выполнится s(m.Value, k(m.Value).Value) и результат обернется в монадный тип Maybe.

Точно так же мы могли бы определить сперва большой трехаргументный метод SelectMany, а потом выразить малый двухаргументный через большой. Возможно читателю будет интересно проделать это самостоятельно.

Ну в общем, надеюсь теперь понятно, почему связывающие методы Bind в C# принято называть “SelectMany”. Это связано с Query Expression паттерном, позволяющим записывать монадные преобразования в удобном синтаксисе. В то же время, мы могли бы малые методы SelectMany назвать и Bind и SelectOne и как-нибудь по другому, ничего бы не изменилось.

Заключение

Надеюсь, что с помощью данного поста удалось выяснить

что монады не так страшны, как их название
что читатели уже знакомы в какой-то мере с монадными вычислениями (в лице монады List, реализованной в LINQ-е)
что Query Expression связывает с монадами только лишь укороченный синтаксис, который можно пристегнуть к монаде с помощью доопределения более развернутого метода SelectMany (который даже имеет другую форму, нежели монадный Bind).
что существуют другие монады кроме той, что реализована в LINQ-е, и что их можно использовать в языке C# (правда польза монад Maybe и Identity осталась нераскрыта в данном посте)

Остались за бортом довольно интересные монады такие как Error, State, Parser, Continuation, Async. По поводу монады Async нужно сказать отдельно. В языке F# она заняла целую нишу, связанную с асинхронными вычислениями, возможно такую же обширную, как монада List в C#. Почитать о ней вместе с другими монадами можно по ссылке [4] (см. ниже).
Не буду обещать, что расскажу о них в ближайшее время, вместо этого предлагаю заинтересовавшимся шагнуть в мир монад самостоятельно, используя следующие ссылки:

Ссылки

Бесконечное решето Эратосфена

noreply@blogger.com (samius) — Mon, 19 Oct 2009 20:52:00 +0000

Во время выполнения одного из упражнений учебника по языку Haskell Р. Душкина, меня посетила мысль, что упражнение можно выполнить и на языке C# в духе Haskell.

Упражнение заключалось в реализации функции для получения бесконечного списка простых чисел с помощью алгоритма ”решет о Эратосфена”. Надеюсь на то, что автор учебника не обидится на меня за то, что я привел тут решение задачи. Оно же почти в том же виде описано на wikipedia (ссылка выше на решето). Мое же решение отличается от опубликованного лишь тем, что четные числа я вычернкул загодя:

primes :: [Integer]
primes = 2 : sieve [3, 5..]
       where
         sieve (p:ps) = p : sieve [x | x <- ps, x `mod` p > 0]

Нет, я не подглядывал и решение на Haskell в википедии обнаружил уже после того, как решил поделиться мыслями на эту тему. Мысли были примерно следующего характера:

Круто, ведь несколько раз мне приходилось реализовывать решето Эратосфена, и ни разу не пришло в голову реализовать его для бесконечного списка! Всегда требовалось задавать порог-размер решета. Беда даже не в том, что нужен порог, а в том, что нужно его тщательно подбирать для каждой задачи. Слишком малый порог грозит тем, что размера решета не хватит, а слишком большой опасен тем, что приложение будет слишком много времени тратить на ненужный счет.
Впрочем, в C# есть механизмы для работы с бесконечными последовательностями. Ну или почти бесконечными.

Подумал я так, и решил повторить решение на C#:

public static IEnumerable<int> GetPrimes()
{
  yield return 2;
  var sieve = Generate(3, 2);

  while(true)
  {
      var p = sieve.First();
      yield return p;

      sieve = sieve.Where(x => x % p > 0);
  }
}
static IEnumerable<int> Generate(int start, int step)
{
  for (int i = start; ; i += step)
      yield return i;
}

По ходу написания ощутил, что в C# таки нет некоторых инструментов, но в остальном реализация на C# почти полностью соответсвует представленному выше решению на Haskell, потому я решение на Haskell не буду комментировать.

Код на C# вполне рабочий. Первым делом он возвращает 2, затем берет последовательность нечетных чисел больше 2 и на каждой итерации делает следующее: берет первое число p из последовательности и навешивает на последовательность фильтр, выкидывающий все что делится нацело на p.

Итак, отличия этого кода от решения на Haskell.

В C# нет типа BigInt (неограниченного целого). Потому решение на C# ограничено типом Int32.
В C# нет встроенного генератора бесконечного списка. Enumerable.Range требует ограничителя диапазона и не воспринимает шаг. Впрочем, легко написать свой генератор, что я и сделал.
В C# недоступен механизм рекурсии для работы с бесконечными списками. Ну т.е. рекурсия сама по себе есть, но воспользовавшись ей мы получим переполнение стека не дойдя до второго члена последовательности. Потому рекурсивное определение списка пришлось заменить на цикл с изменяемым состоянием. Да, решение на C# императивно. Ну да ладно, хоть состояние изменяемое, но оно невидимое клиенту изменяемое состояние.

Вот, пожалуй, и все отличия, подмеченные мной с первого раза. Все да не все. Что-то заставляет скомпилированный код на C# доставать 1000-е простое число в 5 раз дольше, чем выполняется код на интерпретаторе Haskell!!! Нет, это не шутка. А если попросить Haskell обойтись ограниченным целым (Int32), то он работает в 20 раз быстрее C#-а!!!

Все дело в том, что Haskell на каждой итерации выполняет фильтрацию над хвостом бесконечного списка, а C# выполняет фильтрацию над всей бесконечной последовательностью. Т.е. при поручении очередного элемента каждый раз требуется пройти часть бесконечной последовательности с самого начала, но уже с новыми условиями для фильтрации, которые добавляются на каждой итерации. Далее представлен слегка оптимизированный вариант на C#:

public static IEnumerable<int> GetPrimes1()
{
  yield return 2;
  var sieve = Generate(3, 2);

  Func<int, bool> predicate = x => true;

  while (true)
  {
      var p = sieve.First();
      yield return p;
      predicate = predicate.And(x => x % p > 0);

      sieve = Generate(p, 2)
          .Where(predicate);
  }
}

static Func<T, bool> And<T>(this Func<T, bool> p1, Func<T, bool> p2)
{
  return t => p1(t) && p2(t);
}

Теперь последовательности не просматриваются каждый раз сначала, вместо этого на каждой итерации генерируется новая последовательность нечетных чисел и на нее накладываются фильтры, которые пришлось накопить в локальной переменной. Здесь можно заметить что накапливать можно не условия фильтрации, а сами простые числа, которые можно подставить в неизменное условие фильтрации.

public static IEnumerable<int> GetPrimes2()
{
  yield return 2;
  var primes = new List<int> {2};
  var sieve = Generate(3, 2);

  Func<int, bool> predicate = x => primes.All(p => x % p > 0);

  while (true)
  {
      var p = sieve.First();
      yield return p;
      primes.Add(p);

      sieve = Generate(p, 2)
          .Where(predicate);
  }
}

Впрочем, последние две версии решета на C# уже уверенно обгоняют интерпретатор Haskell-а. Вот только оригинальное решето Эратосфена они напоминают лишь отдаленно. И сильно смахивают на проверку делением на предварительно найденные простые числа. Следующее решение на языке F#:

let primes =
  let gen n = seq { n..2..System.Int32.MaxValue }
  let f (sieve, filter) =
      let p = sieve |> Seq.filter filter |> Seq.hd
      Some(p, (gen p, (fun x -> filter x && x % p > 0)))
  Seq.unfold f (gen 3, (fun _ -> true))
  |> Seq.append [2]

Оно больше всего соответствует варианту GetPrimes1() на C#, хотя написано без явно изменяемого состояния. В библиотеке F# имеется тип для представления больших целых, но я им здесь не воспользовался.

Выводы

Хоть .NET и имеет средства для работы с бесконечными последовательностями, но к сожалению, пользоваться ими далеко не так удобно, как могло бы быть. Но основная мысль не об этом. Мое знакомство с Haskell-ем, пока еще поверхностное, позволило по новому взглянуть на известные ранее алгоритмы и инструменты.

Сага о болте и тени

noreply@blogger.com (samius) — Tue, 19 May 2009 19:51:00 +0000

Преамбула

Году в 2002-м, а может в 2003-м, когда я еще работал в одном небезызвестном НИИ произошла эта история, которая окончилась ничем.

Сидел я на одной из местного пошиба весенних конференций, слушал про достижения "передовой" науки. Скучно было хоть режь… Как правило там докладывают про то, в чем мало кто понимает, причем из года в год одно и то же, но обязательно все хлопают в ладоши. Одним из докладов был доклад одной моей сотрудницы Лены (тогда она еще работала там, сейчас уже нет). Доклад Лены заставил меня проснуться.

Проблематика заключалась в следующем: перед нашими математиками (а я принадлежал касте простых программистов) стояли задачи счета на геометрии, описываемой в виде аналитически заданных поверхностей и их комбинаций. Для чего говорить не буду, кто знает – поймет, а кто не знает – не важно это... Задачи они решали, и по всей видимости, не один десяток лет. Проблема была в том, чтобы быстро и качественно описывать эту геометрию для непростых случаев.

Задание уравнений поверхностей происходило в текстовом виде в DSL, который напоминал мне многострочный лес регулярных выражений. Беда была в том, что язык этот был абсолютно чужд всему человеческому, понять его мне не посчастливилось. Геометрии, которые нужно было задавать были довольно большими, задавать их в текстовом виде было безобразно сложно. Посмотреть на эту геометрию глазами можно было, но не сразу. Для того чтобы посмотреть на картинку, нужно было скормить описание специально разработанной библиотеке (я ее буду называть движок ), которая могла отвечать на пространственные запросы типа лежит ли точка P в теле с именем X.

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

Несложно представить, что процесс описания геометрии занимал очень много времени.
Работа сотрудницы Лены заключалась в том, чтобы предоставить интерактивный 3D редактор, позволяющий оперировать примитивными телами и транслирующий набор примитивных тел в DSL для последующего счета. Набор примитивов (сфера, плоскость, труба и т.п.) обладает известным при рендеригне набором точек, потому рендерить такие тела гораздо проще, чем извлекать информацию о точках из пространства с набором аналитических формул. Вроде бы были проблемы при построении набора примитивов по готовому текстовому описанию геометрии.

А болт тут вот причем: т.к. показывать реальные картинки актуальных для обсчетов геометрий на конференции было нельзя, а даже и видеть их могло только очень ограниченное кол-во сотрудников, то все работы с написанием и отладкой интерактивного редактора происходили на простенькой сцене с болтом (в хорошем смысле слова).

Представим ее:

Плоскость обозначающая стену. Т.е. по одну сторону от плоскости стена, по другую - не стена. Может я стену сам придумал, не помню;
На некотором расстоянии от стены находится полусфера, обозначающая шляпку болта. Полусфера - это комбинация сферы и плоскости;
В полусфере вырезан шлиц, как нехитрая комбинация трех плоскостей, выкусывающих кусок шляпки болта;
Цилиндр, соединяющий шляпку со стеной и уходящий в стену на некоторое расстояние.

Резьбы у болта не было. Ограничены квадриками ведь.
Лене удалось построить действительно интерактивный редактор сцен. Вживую я его не видел, видел только слайды презентации. Но не о работе Лены речь.

Сама история

До конца конференции я тогда не досидел. Пришла в голову мысль собрать движок на кодогенерации, которая тогда стала доступна прямо из .NET-а.

Сварганил свой DSL. Нет, назвать это DSL, либо своим язык не поворачивается. Что-то вроде языка было сделано с тем расчетом, чтобы записывать уравнения поверхностей и операции над поверхностями в привычной для программиста форме, так чтобы нехитрыми манипуляциями над текстом можно было привести описание геометрии в исходные коды на C#, скомпилировать и выполнить в рантайме. Т.е. никаких парсеров, лексеров и т.п. не было. Это был полу-C#. Мне нужно было только доказательство состоятельности концепта, потому над деталями я не парился.

За два рабочих дня я слабал что-то (назовем это прототипом):

Это что-то (тогда) поразило воображение своей скорострельностью. Плоский срез усложненной сцены с болтом прототип строил пол секунды. Прототип не имел ограничений на класс поверхностей, как видите, я добавил в стену штрихи, а к болту присобачил резьбу Архимеда!

Я не пытался заменить редактор сцены Лены, я имел надежду написать транслятор из родного DSL в мой с тем чтобы обеспечить более быстрый прострел пространства и решения сопряженных задач (таких как расстояние от точки до тела), которые использовались дальше в части долгих многонедельных числодробилках. Ожидал 100 кратное увеличение производительности движка (и это без возможностей инлайнинга, тогда JIT еще не умел инлайнить даже методы структур). Что так много, спросите вы? Просто реализация старого движка не была предельно эффективна, и было ей много лет. Тогда я помнил конкретные цифры из доклада на конференции, сейчас помню только порядок ускорения, который тогда прикинул на пальцах.

Показал тогда прототип сотрудникам, начальнику своего отдела, начальнику соседней лаборатории, где работала Лена, все были поражены. Подумал, что до математиков дойдет слушок и занялся своей непосредственной работой. По началу переживал, что что-то не идут математики.

Прошло года 2-3, Лена уже не работала в институте, я уже тоже паковал чемоданы. Перебирая барахло на винте наткнулся на прототип, рисующий болт, подумал чего добру пропадать? Надо сказать, что я не строил планов на научную степень, просто было обидно за идею.

Поймал начальника отдела математиков, а тот был как раз заказчиком того интерактивного редактора, что написала Лена. Разговор получился ни о чём. Да, как бы проблема производительности старого движка есть, но есть и другие проблемы. Старый движок сейчас переписывает одна девочка с фортрана на Watcom C++, ожидается некоторое улучшение производительности. Более кардинальные меры им не требуются.

Ходил пару дней в недоумении: потом меня образумил батя (он как раз из касты математиков в том НИИ). Батя мне сказал, что я со своим болтом отбросил тень на членов высшей касты.

Disclaimer (особый вид интеллектуальной индульгенции)

Вообще-то у меня плохая память, богатая фантазия, и это все неправда.
ЗЫ. А прототип - настоящий.

Вывод типов с помощью Fake функций

noreply@blogger.com (samius) — Wed, 29 Apr 2009 20:30:00 +0000

Рассмотрим один прием, помогающий выводить типы (на авторство не претендую) на примере мемоизации. В двух словах, если кто не вкурсе, мемоизация – это техника оптимизации (подвид кэширования), используемая для избежания вызовов функций с повторяющимися аргументами. Множество примеров реализации мемоизации на C# можно найти здесь. Оттолкнемся от мемоизации функции одного аргумента, описанного Wes Dyer-ом, одним из разработчиков компилятора C#.

public static Func<TKey, TResult> Memoize<TKey, TResult>(this Func<TKey, TResult> func)
{
 if (func == null)
     throw new ArgumentNullException("func");

 var cache = new Dictionary<TKey, TResult>();
 TResult result;

 return key => (cache.TryGetValue(key, out result))
     ? result
     : (cache[key] = func(key));
}

Мой вариант отличается только тем, что я переменную result внес в замыкание вместо того, чтобы объявить ее внутри тела возвращаемой функции. Сделал я это только для того, чтобы не писать фигурные скобки в определении тела функции. Все красиво и наглядно, но допустим возникла необходимость мемоизации функции двух переменных.

Мемоизация функции двух аргументов

Решать можно по-разному. Например, модифицировать реализацию мемоизации функции одной переменной, т.е. фактически переписать ее заново:

public static Func<T1, T2, TResult> Memoize<T1, T2, TResult>(this Func<T1, T2, TResult> func)
{
 if (func == null)
     throw new ArgumentNullException("func");

 var cache = new object[0].ToDictionary(
     x => new { k1 = default(T1), k2 = default(T2) },
     x => default(TResult));

 return (k1, k2) =>
 {
     TResult result;
     var key = new { k1, k2 };

     return (cache.TryGetValue(key, out result))
         ? result
         : (cache[key] = func(k1, k2));
 };
}

Здесь я воспользовался тем, что анонимный тип, который генерируется компилятором обладает всем необходимым для того, чтобы использовать его в качестве ключа словаря. Небольшая сложность заключалась в том, чтобы объявить переменную словаря с анонимным типом ключа, но выручил метод Enumerable.ToDictionary. Но душа захотела реюза описанного ранее метода мемоизации функции одного аргумента. Мне пока известно два способа сделать реюз:

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

Итого, требуется применить мемоизацию к следующему методу (записанному условно):

Func<?, TResult> func2 = (? x) => func(x.t1, x.t2);

Проблема здесь в том, что комбинированный аргумент представлен анонимным типом, указать который проблематично. Стандартных Tuple-ов нет, да и неизвестно, будут ли они обладать теми же свойствами, что и анонимные типы, будет ли возможность использовать их в качестве ключа словаря?

Итого, есть метод с сигнатурой Func<?, TResult>, записать тело которого мы можем, но не можем сказать компилятору, что за тип кроется за знаком “?” (достаточно было бы указать тип хотя бы в одном из мест, отмеченных знаком “?” в определении анонимного метода).

Вот тут-то и выручит нас метод, который ничего не делает:

static Func<T, TResult> MakeFunc<T, TResult>(T _, Func<T, TResult> func)
{
 return func;
}

Метод MakeFunc абсолютно бесполезен во времени выполнения. Однако он помогает вывести тип “?”. Записать этот тип в коде мы все равно не сможем, но это и не требуется.

Вот как компилятор теперь может выявить тип метода: первым аргументом MakeFunc мы указываем экземпляр анонимного типа, а т.к. тип T первого аргумента совпадает с типом аргумента метода Func<T, TResult> второго аргумента метода MakeFunc, то компилятор теперь знает, что подразумевается под типом T в выражении Func<T, TResult>.

Теперь следующее выражение

var func2 = MakeFunc(
 new { A1 = default(T1), A2 = default(T2) },
 x => func(x.A1, x.A2));

в точности указывает компилятору, что func2 это метод, принимающий аргумент анонимного типа, и имеющий тело, которое возвращает TResult, обращаясь к оригинальному методу func, растаскивая анонимный тип на аргументы. Теперь к методу func2 можно применить мемоизацию:

public static Func<T1, T2, TResult> Memoize<T1, T2, TResult>(this Func<T1, T2, TResult> func)
{
 if (func == null)
     throw new ArgumentNullException("func");

 var func2 = MakeFunc(
     new { A1 = default(T1), A2 = default(T2) },
     x => func(x.A1, x.A2));

 var func2m = func2.Memoize();

 return (t1, t2) => func2m(new { A1 = t1, A2 = t2 });
}

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

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

Потому еще один пример, где описанный мной прием может пригодитсья:

Вывод типа IEqualityComparer<?> для анонимного типа.

Преамбула проста: когда-то не так давно я решил, что если не заморачиваться на эффективности, то можно не писать классы компареров каждый раз, а создать адаптер, который бы принимал функции GetHashCode и Equals и представлял бы их экземпляром IEqualityComparer<T>. Выглядит это чудо так:

public static IEqualityComparer<T> CreateAdapter<T>(
 Func<T, T, bool> equals,
 Func<T, int> getHashCode)
{
 if (equals == null)
     throw new ArgumentNullException("equals");

 if (getHashCode == null)
     throw new ArgumentNullException("getHashCode");

 return new EqualityComparerAdapter<T>(equals, getHashCode);
}

class EqualityComparerAdapter<T> : IEqualityComparer<T>
{
 readonly Func<T, T, bool> _equals;
 readonly Func<T, int> _getHashCode;

 public EqualityComparerAdapter(Func<T, T, bool> equals, Func<T, int> getHashCode)
 {
     _equals = equals;
     _getHashCode = getHashCode;
 }

 public bool Equals(T x, T y)
 {
     return _equals(x, y);
 }

 public int GetHashCode(T obj)
 {
     return _getHashCode(obj);
 }
}

Между делом – довольно удобная штука, позволяющая экономить на описании класса, но не в случае когда тип T – анонимный. Вот такой вспомогательный метод

static IEqualityComparer<T> InferComparer<T>(
 T _,
 Func<T, T, bool> equals,
 Func<T, int> gethashCode)
{
 return CreateAdapter(equals, gethashCode);
}

позволяет вывести тип компарера для анонимного типа.

var pairComparer = InferComparer(
 pair,
 (x, y) => x.Key.SequenceEqual(y.Key),
 x => x.Key.Aggregate(0, (h, s) => h ^ s.GetHashCode()));

Эта конструкция создает IEqualityComparer для анонимного типа, свойство Key которого является коллекцией строк. Таким образом сравниваются экземпляры по совпадению коллекций строк, и хэшкод вычисляется по набору строк свойства Key анонимного типа. Далее этот компарер используется для построения словаря.

Обобщение фундаментальных алгоритмов.

noreply@blogger.com (samius) — Fri, 10 Apr 2009 22:01:00 +0000

Иногда удивляюсь, насколько время меняет подходы к реализации и использованию фундаментальных алгоритмов, которым много лет!

Возникла задача. Пост не о ней, но все же я приведу исходники. Задача заключалась в том, чтобы найти кратчайший путь в графе. Даже не задача, а упражнение, для тех кто немного знаком с теорией графов.

Как решалась эта задача раньше (точнее как я ее решал в ВУЗ-е): брались классы-вершины и классы-ребра, и под них писался алгоритм. Я использовал алгоритм Дейкстры для случаев с неотрицательными весами (кстати, алгоритму 50 лет в этом году!). Естественно, что использование реализации алгоритма под конкретные типы невозможно для других типов вершин и ребер. О реюзе даже речи не идет.

Потом под веяниями ООП стали использовать абстрактные типы данных (вершин и ребер), либо их интерфейсы. Многие алгоритмы стало можно использовать многократно, стали появляться библиотеки для работы с теми же графами. ООП - хорошо, но что делать, если вершины моего графа - целые числа, либо классы, которые писал не я? Ну да, писать wrapper-адаптеры. Не всегда это удобно, требуется их кэшировать, чтобы не плодились, сравнивать, и т.д. Но у ООП найдется на все проблемы по решению.

Гораздо более гибким подходом было бы абстрагироваться не от типов данных (вершин и ребер), а от способа работы с ними. Это как Array.Sort(IComparer). В случае поиска на графах, плюс такого подхода еще и в том, что графы можно задавать как списками смежности, так и матрицами весов. Но для использования такого подхода все еще требуется реализация интерфейса, работающего с конкретными данными. Гибко, но не очень.

И тут приходят делегаты. Нет, не делегаты. Если рассматривать делегаты как аналог указателям на методы, то с приходом указателей на метод и делегатов в этом плане ничего не изменилось. А вот когда пришли (в .net) лексические замыкания в совокупности с анонимными методами, вот тогда, видимо, и наступил переломный момент. Наступил, но не все его заметили. Лямбда-выражения подлили масла в огонь, и теперь использовать обобщенные методы одно удовольствие (хотя сами лямбды в обобщении алгоритма участия не принимают):

var edjes = new[]
{
  new { s = 1, t = 2 },
  new { s = 2, t = 3 },
  new { s = 3, t = 4 },
  new { s = 4, t = 5 },
  new { s = 2, t = 4 },
  new { s = 2, t = 1 },
};

var pathes = Dijkstra.ComputePathes(
  1,
  v => edjes.Where(_ => _.s == v),
  (v, e) => e.t,
  e => 1);

CollectionAssert.AreEqual(
  new[] { new { s = 1, t = 2 } },
  pathes(2).ToArray());

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

Вот реализация алгоритма Дейкстры:

class Dijkstra
{
  public static Func<V, IEnumerable<E>> ComputePathes<V, E>(
      V s,
      Func<V, IEnumerable<E>> adjacentEdjes,
      Func<V, E, V> dest,
      Func<E, double> weight,
      IEqualityComparer<V> equalityComparer)
  {
      if (adjacentEdjes == null)
      {
          throw new ArgumentNullException("adjacentEdjes");
      }

      if (dest == null)
      {
          throw new ArgumentNullException("dest");
      }

      weight = weight ?? new Func<E, double>(_ => 1.0);
    
      equalityComparer = equalityComparer ?? EqualityComparer<V>.Default;

      var distancesFromS = new Dictionary<V, double>(equalityComparer) { { s, 0 } };

      // метод нахождения расстояния от указанной вершины до s.
      double tmp;
      Func<V, double> distanceFromS = v =>
          distancesFromS.TryGetValue(v, out tmp) ? tmp : double.PositiveInfinity;

      // запомненные пути (из какой вершины по какому ребру пришли в данную вершину).
      var sourceVertices = new[] { s }.ToDictionary(
          x => x,
          x => new { source = x, edje = default(E) },
          equalityComparer);

      // множество не вершин, кратчайший путь до которых не вычислен.
      var F = new HashSet<V> { s };

      while (F.Count > 0)
      {
          // Найти вершину с минимальным расстоянием от s
          var w = F.Aggregate(
              F.First(),
              (c, v) => distanceFromS(c) < distanceFromS(v) ? c : v);

          F.Remove(w);

          foreach (E e in adjacentEdjes(w))
          {
              V v = dest(w, e);
              double distanceToV = distanceFromS(w) + weight(e);
              if (distanceFromS(v) > distanceToV)
              {
                  // обновить расстояние.
                  distancesFromS[v] = distanceToV;
                  F.Add(v);
                  // запомнить откуда пришли.
                  sourceVertices[v] = new { source = w, edje = e };
              }
          }
      }

      // вернуть метод вычисления последовательности ребер.
      return x =>
      {
          var edges = new List<E>();

          while(sourceVertices.ContainsKey(x) && !equalityComparer.Equals(x, s))
          {
              var w = sourceVertices[x];
              edges.Add(w.edje);
              x = w.source;
          }

          edges.Reverse();
          return edges;
      };
  }
}

На удивление - это всего лишь один метод, который довольно хорошо коррелирует с псевдокодом по ссылке выше. Потому комментировать я его не буду за исключением нескольких моментов:

Первое - то что отличает алгоритм от псевдокода: набора вершин нет. Это специфика той задачи, которую я решал с помощью алгоритма Дейкстры. В той задаче число вершин определяется комбинаторными законами, в то время как число допустимых переходов весьма ограничено. Потому вводить все вершины в алгоритм смысла нет. Алгоритм довольствуется только исходной вершиной и достижимыми из нее.

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

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

double tmp;
Func<V,double> distanceFromS = v =>
    distancesFromS.TryGetValue(v, out tmp) ? tmp : double.PositiveInfinity;

содержит потенциальный баг. А именно, переменная tmp должна быть объявлена внутри анонимного метода! Я же использовал замыкание переменной tmp только для того, чтобы сэкономить на фигурных скобках и ключевом слове return, которые пришлось бы добавить, помести я переменную в тело метода. Полагаю, что этот код не будет распараллеливаться.

Вернемся к обсуждению прелестей обобщенных реализаций алгоритмов.

Отсутствие каких либо ограничений на типы данных позволяет оперировать вершинами V и ребрами E, ничего не требуя от них. Это здорово! Вершинами может быть все: числа, строки, сайты, города... Это позволяет тестировать реализацию алгоритма на элементарных типах данных. Задача, под которую я писал эту реализацию, обладает довольно сложновообразимыми типами данных. Тесты алгоритма на этих типах очень непрозрачны и нелаконичны. Обобщение позволило мне писать простые и понятные тесты (часть теста в начале поста). В качестве бонуса для себя я получил возможность реюза этого алгоритма тут же не отходя от кассы, при решении сопутствующей задачи анализа возможностей переходов по ребрам из первой задачи. Во втором случае не требовался кратчайший путь, достаточно было лишь установления факта существования пути на других типах данных, но писать специальный алгоритм для решения этой задачи стимула небыло.
Отсутствие ограничений на типы позволило так же сконцентрироваться именно на реализации фундаментального алгоритма, а не на его поведении в рамках конкретной системы. Создание вершин, перебор ребер-переходов, вычисление весов - все это осталось за бортом. Реализация алгоритма приобрела вид, очень близкий к псевдокоду на википедии. Если кому-то придется поддерживать этот алгоритм, он без труда это сделает, даже не вникая в задачу, в рамках которой используется этот алгоритм.
Задание управляющих методов делегатами позволяет гибко настраивать работу алгоритма, позволяет использовать преимущества лексических замыканий при обращении к алгоритму (делегаты тут и не причем, я хотел сказать функциональные типы, но в C# за них делегаты).
Анонимные типы и лексические замыкания позволили вернуть накопленные в ходе расчета данные в удобном для использования виде. Не потребовалось описывать дополнительные типы для хранения результатов счета.

P.S. И кто сказал, что библиотеки для работы с графами должны быть Объектно-Ориентированными?

Comparer с обобщенными методами

noreply@blogger.com (samius) — Fri, 10 Apr 2009 17:47:00 +0000

Последнее время часто использую методы с обобщенными аргументами. Довольно часто приходится сравнивать значения обобщенных типов между собой, сравнивать с default(T). Конструкции типа

while (!EqualityComparer<T>.Default.Equals(t, default(t))
{
    // do something
}

довольно сильно утомляют глаз. Следующий класс здорово облегчает жизнь:

public static class Comparer
{
    public static int Compare<T>(T a, T b)
    {
        return Comparer<T>.Default.Compare(a, b);
    }

    public static bool Equals<T>(T a, T b)
    {
        return EqualityComparer<T>.Default.Equals(a, b);
    }

    public static bool IsNullOrDefault<T>(T value)
    {
        return Equals(default(T), value);
    }
}

Теперь можно писать так:

while (!Comparer.Equals(t, default(t))
{
    // do something
}

И даже так:

while (!Comparer.IsNullOrDefault(t))
{
    // do something
}

Естественно, это имеет смысл только для сравнения компарером по-умолчанию.

Хранилище записей фиксированной длины (часть IV)

noreply@blogger.com (samius) — Thu, 09 Apr 2009 21:30:00 +0000

Хранилище записей фиксированной длины
Хранилище записей фиксированной длины (часть II)
Хранилище записей фиксированной длины (часть III)

Давно обещанное сравнение производительности хранилища с SQLite. Если честно, вся эта эпопея с хранилищем утомила меня. Делов на копейку, а растянул уже на полгода. Смысл теста незатейлив. Требуется сохранить много-много пар {Guid, int}, а потом произвести некоторое количество запросов записи по Guid ключу, и сверить соответствующий ему int. Поиски делаются из разных потоков.

Для тестирования пресловутого хранилища и SQLite базы данных используется один и тот же код, который работает со следующим интерфейсом:

interface IStorage : IDisposable
{
   void StoreGuidsAndInts(Guid[] guids);

   void InitStorage();

   int GetInt32FromRecordByKey(Guid id);
}

Вот, собственно, код теста:

private const int RecordCount = 200000;
private static readonly int SearchCount = Math.Min(100000, RecordCount);

private static Guid[] GenereateGuids()
{
    var ids = new Guid[RecordCount];

    for (int i = 0; i < ids.Length; i++)
    {
        ids[i] = Guid.NewGuid();
    }
    return ids;
}

static void StressStorageTest(IStorage storage)
{
    Guid[] ids = GenereateGuids();

    Stopwatch sw1 = Stopwatch.StartNew();

    storage.StoreGuidsAndInts(ids);

    Console.WriteLine(
        "Быстрая вставка новых записей ({0} штук) - {1}", 
        RecordCount, 
        sw1.Elapsed);


    Stopwatch swInit = Stopwatch.StartNew();

    storage.InitStorage();

    Console.WriteLine("Инициализация индексированного хранилища - {0}", swInit.Elapsed);

    int searchCount = SearchCount;
    var syncRoot = new object();

    var rnd = new Random();

    var callbacks = new List<WaitCallback>(searchCount);

    for (int i = 0; i < searchCount; i++)
    {
        int index = rnd.Next(RecordCount);

        callbacks.Add(
            _ =>
            {
                int value = storage.GetInt32FromRecordByKey(ids[index]);
                Assert.AreEqual(index, value);
                if (Interlocked.Decrement(ref searchCount) == 0)
                {
                    lock (syncRoot)
                    {
                        Monitor.Pulse(syncRoot);
                    }
                }
            });
    }

    var sw2 = Stopwatch.StartNew();

    foreach (var callback in callbacks)
    {
        ThreadPool.QueueUserWorkItem(callback);
    }

    lock (syncRoot)
    {
        Monitor.Wait(syncRoot);
    }

    Console.WriteLine("Проверка индекса ({0} поисков - {1}", SearchCount, sw2.Elapsed);
}

Извиняюсь, долго не медитировал над кодом, хотя суть должна быть понятна. Заряжаем хранилища набором Guid-ов, создаем список делегатов, которые берут Guid по случайному индексу, просят хранилище вернуть индекс идентификатора, сравнивают индексы. Закидываем список делегатов (вот так вот грубо) в пул потоков и ждем когда декрементируется счетчик поисков. Хранилище, основанное на хранилище записей, не сильно сложно (относительно хранилища на SQLite).

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

class IndexedTestStorage : IndexedStorage<TestHeader, TestRow, Guid>, IStorage
{
    private Stream _bufferedStream;
    private BinaryWriter _writer;

    public IndexedTestStorage(Stream stream)
        : base(
            stream,
            Encoding.Default,
            TestRow.IdColumn,
            new DictionaryIndex<Guid>())
    {
    }

    public void StoreGuidsAndInts(Guid[] guids)
    {
        _bufferedStream = new BufferedStream(Stream);
        _writer = new BinaryWriter(_bufferedStream);
        for (int i = 0; i < guids.Length; i++)
        {
            _writer.Write(guids[i].ToByteArray());
            _writer.Write(i);
        }

        _bufferedStream.Flush();
    }

    public void InitStorage()
    {
        base.Initialize();
    }

    public int GetInt32FromRecordByKey(Guid id)
    {
        return GetRow(id).Int32Value;
    }

    public override void Dispose()
    {
        base.Dispose();
        _bufferedStream.Dispose();
        _writer.Close();
    }

    public TestRow GetRow(Guid id)
    {
        return GetRow(GetIndex(id));
    }

    public TestRow AddNewRow(Guid id)
    {
        return InsertRow(id);
    }
}

С вариантом реализации через SQLite пришлось повозиться. Открытие и закрытие соединения - слишком дорогая операция. Делать открытие и закрытие соединения на каждое обращение - непозволительная роскошь. Пришлось пойти окружными путями и использовать соединение из разных тредов, обеспечивая самостоятельно гарантию того, что соединение не будет использовано из разных тредов одновременно. Фактически пришлось организовать пул открытых соединений (это довольно безопасно, пока нет одновременной записи).

Вот код:

class SQLiteStorage: IStorage
{
    private readonly string _path;
    private readonly Stack<SQLiteConnection> _connectionPool = new Stack<SQLiteConnection>();
    private readonly object _syncRoot = new object();

    public SQLiteStorage()
    {
        string path1 = Path.GetFullPath(@"..\..\StreamStorage\sqlitedb.s3db");

        _path = Path.GetFullPath("sqlitedb.s3db");
        if (File.Exists(_path))
        {
            File.Delete(_path);
        }

        File.Copy(path1, _path);
    }

    private SQLiteConnection GetConnection()
    {
        lock (_syncRoot)
        {
            if (_connectionPool.Count > 0)
            {
                return _connectionPool.Pop();
            }
        }

        var result = new SQLiteConnection("Data Source=" + _path);
        result.Open();
        return result;
    }

    private void ReturnToPool(SQLiteConnection connection)
    {
        lock(_syncRoot)
        {
            _connectionPool.Push(connection);
        }
    }

    public void Dispose()
    {
        foreach(var connection in _connectionPool)
        {
            connection.Dispose();
        }
        _connectionPool.Clear();
    }

    public void StoreGuidsAndInts(Guid[] guids)
    {
        var connection = GetConnection();
        Action<string> simpleCommand = text =>
        {
            using (var cmd = new SQLiteCommand(text, connection))
                cmd.ExecuteNonQuery();
        };
        var insertCommand = new SQLiteCommand(connection)
        {
            CommandText =
                "INSERT INTO [TestTable] ([Id], [IntValue]) VALUES (@Id, @Value)"
        };
        var valueParameter = insertCommand.Parameters.Add("@Value", System.Data.DbType.Int32);
        var id1Parameter = insertCommand.Parameters.Add("@Id", System.Data.DbType.Guid);

        //connection.Open();
        simpleCommand("BEGIN");

        try
        {
            for (int i = 0; i < guids.Length; i++)
            {
                id1Parameter.Value = guids[i];
                valueParameter.Value = i;
                insertCommand.ExecuteNonQuery();
            }

            simpleCommand("COMMIT");
        }
        finally
        {
            //connection.Close();
            ReturnToPool(connection);
        }
    }

    public void InitStorage()
    {
    }

    public int GetInt32FromRecordByKey(Guid id)
    {
        var connection = GetConnection();
        var getIntValueCommand = new SQLiteCommand(connection)
        {
            CommandText = "SELECT [IntValue] FROM [TestTable] WHERE [Id] = @Id"
        };
        var idParameter = getIntValueCommand.Parameters.Add("@Id", System.Data.DbType.Guid);

        idParameter.Value = id;

        //connection.Open();
        object obj = getIntValueCommand.ExecuteScalar();
        //connection.Close();
        ReturnToPool(connection);
        return Convert.ToInt32(obj);
    }
}

Места, где я поначалу пытался открывать и закрывать соединения, остались закомментированы. Сами тесты:

[Test]
public void StressIndexedStorageTest()
{
    using(var stream = new FileStream(
        "Storage.tmp",
        FileMode.Create,
        FileAccess.ReadWrite,
        FileShare.None,
        128,
        FileOptions.RandomAccess))
    using (var storage = new IndexedTestStorage(stream))
    {
        StressStorageTest(storage);
    }
}

[Test]
public void StressSQLiteTest()
{
    using (var storage = new SQLiteStorage())
    {
        StressStorageTest(storage);
    }
}

Ну и наконец, результаты:

StressIndexedStorageTest
Быстрая вставка новых записей (200000 штук) - 00:00:00.0763303
Инициализация индексированного хранилища - 00:00:00.1788403
Проверка индекса (100000 поисков) - 00:00:01.4525583

StressSQLiteTest
Быстрая вставка новых записей (200000 штук) - 00:00:10.6895979
Инициализация индексированного хранилища - 00:00:00.0000385
Проверка индекса (100000 поисков) - 00:00:12.0554961

При открытии и закрытии соединения на каждый запрос по индексу, время SQLite составило больше минуты на 100000 запросов. Должен признать, SQLite с пулом открытых соединений оказался достаточно быстр для нужд проекта! Но он слил. Ни в коем случае не испытываю радости по этому поводу. Описанный мной тест не может претендовать на объективность. Слишком специфичны условия (одиночные обращения к хранилищу из разных потоков)... В защиту SQLite тот факт, что он хранит индекс в файле, в то время, как мое хранилище использует словарь в памяти.

При тестировании варианта хранилища с индексом в файле, разница в производительности между SQLite и моим хранилищем тает (SQLite уступает лишь в 2 раза). Безусловно, SQLite годится на гораздо большее, чем хранилище записей фиксированной длины. Однако, предпочтение было отдано хранилищу записей по ряду причин: В основном, из-за прозрачной организации файла. Еще одна причина - ощутимо более быстрое добавление записей, чем в таблицу SQLite. Последняя: к моменту обсуждения возможности использования SQLite (начало ноября) времени на переделку не было, хотя много времени и не требовалось. Надо как-то подытожить 4 длинных поста на тему хранилища: Велосипеды - вещь в себе, особенно узкоспециализированные. Они могут дать неплохое преимущество перед инструментами широкого профиля. Но, время потраченное на исследование доступных инструментов, вполне может окупить время, потраченное на написание велосипеда. Данный велосипед безусловно порвал SQLite по производительности, хотя производительность SQLite-а (с пулом открытых соединений) вполне могла удовлетворить требованиям задачи.

Потрачено на написание хранилища записей фиксированной длины было около 3х рабочих дней. Смог бы я за это время грамотно прикрутить к SQLite пул открытых соединений с возможностью безопасной записи? Возможно... Какие-то противоречивые чувства меня раздирают. Одно ясно точно: надо больше смотреть по сторонам.

Хранилище записей фиксированной длины (часть III)

noreply@blogger.com (samius) — Sun, 16 Nov 2008 09:20:00 +0000

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

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

public interface IStorageIndex<TKey>
{
    void Initialize(IEnumerable<TKey> keys, Func<int, TKey> readKeyFunc);

    int GetIndex(TKey key);

    void InsertIndex(TKey key, int rowIndex);
}

Метод инициализации индекса принимает последовательность всех ключей (забегая вперед отмечу, что ленивую последовательность), и метод получения ключа по заданному индексу. Полагаю, что такой метод инициализации должен удовлетворить некоторое кол-во реализаций индексов (строящихся в памяти, или на диске). Метод GetIndex - собственно то, ради чего и задумывался индекс. Он должен вернуть индекс записи с указанным ключем. Метод InsertIndex добавляет в индекс информацию о положении новой записи. Простоты ради я избавился от метода удаления записи из индекса. Простейшая реализация индекса выглядит так (комментировать не буду):

public class DictionaryIndex<TKey> : IStorageIndex<TKey>
{
    private readonly Dictionary<TKey, int> _indices = new Dictionary<TKey, int>();

    public void Initialize(IEnumerable<TKey> keys, Func<int, TKey> readKeyFunc)
    {
        int index = 0;
        foreach(TKey key in keys)
        {
            _indices[key] = index++;
        }
    }

    public int GetIndex(TKey key)
    {
        int result;
        return _indices.TryGetValue(key, out result)
            ? result
            : -1;
    }

    public void InsertIndex(TKey key, int rowIndex)
    {
        _indices.Add(key, rowIndex);
    }
}

Кстати, именно подобный индекс основанный на словаре успешно трудится уже около двух месяцев в некоторых заведениях ;) страны. Теперь опишу базовый класс индексированного хранилища записей. Для индесированного по одной колонке хранилища нам потребуется еще один generic параметр TKey, который будет представлять тип колонки, по которой проводится индексирование. Конструктор индексированного хранилища принимает дополнительные параметры - колонку, по которой проводится индексирование и реализацию индекса:

public class IndexedStorage<THeader, TRow, TKey> : StreamStorage<THeader, TRow>
    where THeader : RowBase<THeader>
    where TRow : RowBase<TRow>
{
    private readonly Column<TKey> _keyColumn;
    private readonly IStorageIndex<TKey> _index;

    protected IndexedStorage(Stream stream, Encoding encoding, Column<TKey> keyColumn, IStorageIndex<TKey> index)
        : base(stream, encoding)
    {
        if(index == null)
        {
            throw new ArgumentNullException("index");
        }
        if(keyColumn == null)
        {
            throw new ArgumentNullException("keyColumn");
        }
   
        if(keyColumn.Columns != RowBase<TRow>.ColumnCollection)
        {
            throw new ArgumentException();
        }
        _keyColumn = keyColumn;
        _index = index;
    }
    ...
}

Методы, потребующиеся для инициализации индекса (чтение ключа записи по указанному номеру и чтение последовательности ключей всех записей)

private TKey ReadKey(int index)
{
    return ReadValue(_keyColumn, index);
}

private IEnumerable<TKey> LoadKeys()
{
    int length = Length;

    using (var notOwnedStream = new NotOwnedStreamProxy(Stream))
    using (var bufferedStream = new BufferedStream(notOwnedStream))
    using (var reader = new BinaryReader(bufferedStream))
    {                   
        byte[] buffer =
            new byte[RowBase<TRow>.ColumnCollection.Size - _keyColumn.Size];
         bufferedStream.Position = RowBase<THeader>.ColumnCollection.Size + _keyColumn.Offset;

        for (int i = 0; i < length; i++)
        {
            yield return _keyColumn.ReadValue(reader);
         
            if (i < length - 1)
            {
                reader.ReadBytes(buffer.Length);
            }
        }
    }
}

второй метод потребует комментариев. Дело в том, что я его изуродовал, пытаясь выжать производительность. Самая простая его реализация - вызов в цикле вышеописанного метода ReadKey(int index) безобразно долго работает. Дело в том, что при таком подходе потребуется большое (по числу записей) количество операций Seek. Хоть изменения позиции и небольшие, но сама операция на FileStream (а это основной сценарий использования этого хранилища) все равно занимает значительное время. Вместо операции Seek я решил использовать чтение в буфер, размер которого равен размеру записи без ключевого поля. Т.е. прочитав первый ключ и вчитав в этот буфер дальнейшее содержимое, позиция потока оказывается ровно перед ключем следующего поля. Еще одна оптимизация - использование буферизованного потока дает небольшое преимущество перед чтением напрямую. Небольшое, но я решил им все же воспользоваться. Потому потребовался другой экземпляр BinaryReader. Вся эта оптимизация привела к следующей проблеме: при освобождении BufferedStream, равно как и BinaryReader-а для чтения из буферизованного стрима, освобождается несущий стрим хранилища. Решений может быть несколько: постараться не освобождать эти сущности (хранить их в полях класса), либо оградить несущий стрим от деструктивных воздействий вспомогательных сущностей. Я предпочел второе, хоть и пришлось много постучать по кнопкам: пришлось реализовать хитрый proxy для класса Stream, который делегирует все методы и свойства низлежащему стриму, за исключением метода Close(). Этот класс я худобедно назвал NotOwnedStreamProxy. Полные его исходники приводить не буду, ограничусь выбранными наугад методами (остальные выглядят похожим образом):

public override void Close()
{
    // BaseStream.Close(); ВСЕ РАДИ ТОГО, ЧТОБЫ НЕ ДОПУСТИТЬ ВЫЗОВ ЭТОГО!!!
    base.Close();
}

public override int EndRead(IAsyncResult asyncResult)
{
    return BaseStream.EndRead(asyncResult);
}

public override void EndWrite(IAsyncResult asyncResult)
{
    BaseStream.EndWrite(asyncResult);
}

public override int ReadByte()
{
    return BaseStream.ReadByte();
}

И не говорите! Сам не в восторге. Метод инициализации базового индексированного хранилища теперь выглядит так:

protected override void Initialize()
{
    lock (SyncRoot)
    {
        base.Initialize();

        _index.Initialize(LoadKeys(), ReadKey);
    }
}

Еще пара нехитрых методов базового индексированного хранилища:

protected int GetIndex(TKey key)
{
    lock(SyncRoot)
    {
        return _index.GetIndex(key);
    }
}

protected TRow InsertRow(TKey key)
{
    int newRowIndex;
    lock(SyncRoot)
    {
        newRowIndex = Length;

        _index.InsertIndex(key, newRowIndex);

        Length += 1;
        WriteValue(_keyColumn, newRowIndex, key);
    }

    return GetRow(newRowIndex);
}

Осталось чуть-чуть. Уже добрались до конкретного индексированного хранилища:

class IndexedStorage : IndexedStorage<TestHeader, TestRow, Guid>
{
    public IndexedStorage(Stream stream)
        : base(
            stream,
            Encoding.Default,
            TestRow.IdColumn,
            new DictionaryIndex<Guid>())
    {
        base.Initialize();
    }

    public TestRow AddNewRow(Guid id)
    {
        return InsertRow(id);
    }

    public TestRow GetRow(Guid id)
    {
        return GetRow(GetIndex(id));
    }
}

Класс TestRow описан в конце первого поста о хранилище записей.

В следующий раз приведу результаты стресс-тестирования этого безобразия в сравнении с SQLite.

Хранилище записей фиксированной длины (часть II)

noreply@blogger.com (samius) — Mon, 03 Nov 2008 19:37:00 +0000

В предыдущем посте (Хранилище записей фиксированной длины) было описано все необходимое для класса хранилища. Теперь можно приступать к реализации хранилища.

Напомню: хранилище - надстройка над классом Stream для хранения типизированных записей фиксированной длины и некого заголовка. Класс хранилища параметризован двумя generic параметрами: типом заголовка хранилища и типом записи хранилища:

public class StreamStorage<THeader, TRow> : StreamStorage, IDisposable
    where THeader : RowBase<THeader>
    where TRow : RowBase<TRow>
{
    private readonly object _syncRoot = new object();
    private readonly Stream _stream;
    private readonly BinaryWriter _writer;
    private readonly BinaryReader _reader;
    private int _length;

    protected StreamStorage(
        Stream stream,
        Encoding encoding)
    {
        _stream = stream;
        encoding = encoding ?? Encoding.Default;

        if (stream.CanWrite)
        {
            _writer = new BinaryWriter(_stream, encoding);
        }
        if (stream.CanRead)
        {
            _reader = new BinaryReader(_stream, encoding);
        }
    }

    public void Dispose()
    {
        if (_writer != null)
        {
            _writer.Close();
        }
        if(_reader != null)
        {
            _reader.Close();
        }
        _stream.Close();
    }

Конструктор хранилища принимает поток данных, в котором хрянятся записи и кодировку для записи строковых полей (реализацию строковых колонок я пока не приводил). Метод Dispose() освобождает ресурсы. Следом короткая форма доступа к экземплярам коллекций колонок заголовка и записи хранилища:

static ColumnCollection HeaderColumns
    {
        get { return RowBase<THeader>.ColumnCollection; }
    }

    static ColumnCollection RowColumns
    {
        get { return RowBase<TRow>.ColumnCollection; }
    }

Затем доступ к ридеру, райтеру и собственно потоку данных:

protected BinaryWriter Writer
    {
        get
        {
            if (_writer == null)
            {
                throw new NotSupportedException();
            }
            return _writer;
        }
    }

    protected BinaryReader Reader
    {
        get
        {
            if (_reader == null)
            {
                throw new NotSupportedException();
            }
            return _reader;
        }
    }

    protected Stream Stream
    {
        get { return _stream; }
    }

    protected object SyncRoot { get { return _syncRoot; } }

Далее серия методов, производящих строки. Есть небольшие проблемы в том каким образом создавать экземпляры TRow и THeader, ведь экземпляры строк требуют экземпляр хранилища и свой индекс при создании, т.е. мы не можем воспользоваться их конструктором по умолчанию.

Можно было параметризовать хранилище фабрикой строк и фабрикой заголовка, но я пришел к решению предусмотреть расширение через Template Method.

protected virtual TRow CreateRowInstance(int index)
    {
        return CreateRowInstance<TRow>(this, index);
    }

    protected virtual THeader CreateHeaderInstance()
    {
        return CreateRowInstance<THeader>(this, 0);
    }

    private static T CreateRowInstance<T>(StreamStorage storage, int index)
        where T : RowBase<T>
    {
        return (T)Activator.CreateInstance(typeof(T), storage, index);
    }

    protected TRow GetRow(int index)
    {
        lock (SyncRoot)
        {
            return CreateRowInstance(index);
        }
    }

    public THeader Header { get; private set; }

Такое решение позволит без дополнительных усилий создавать экземпляры строк, которые принимают в конструкторе экземпляр хранилища и индекс. Пример строки TestRow из предыдущего поста принимает именно такой набор параметров. Если потребуется изменить сигнатуру конструктора записи, то производный класс хранилища сможет перекрыть методы CreateRowInstance и CreateHeaderInstance.

Далее способ управления размером хранилища:

protected int Length
    {
        get
        {
            return _length;
        }
        set
        {
            if (value < 0)
            {
                throw new ArgumentOutOfRangeException("value");
            }

            long streamLength = HeaderColumns.Size + RowColumns.Size * value;

            lock (SyncRoot)
            {
                Stream.SetLength(streamLength);

                _length = value;
            }
        }
    }

Реализация свойства Length практически не нуждается в комментариях. Она устанавливает длину потока данных руководствуясь размером заголовка, размером записи и требуемым кол-вом записей. Метод установки позиции потока для чтения или записи значения:

private void SetPosition(int rowIndex, Column column)
    {
        if (column == null)
        {
            throw new ArgumentNullException("column");
        }

        int pos;
        if (ReferenceEquals(column.Columns, HeaderColumns))
        {
            pos = column.Offset;
        }
        else
        {
            if (ReferenceEquals(column.Columns, RowColumns))
            {
                if (rowIndex < 0 || rowIndex >= Length)
                {
                    throw new ArgumentOutOfRangeException("rowIndex");
                }
                pos = HeaderColumns.Size + RowColumns.Size * rowIndex + column.Offset;
            }
            else
            {
                throw new ArgumentException("", "column");
            }
        }

        if (Stream.Position != pos)
        {
            Stream.Position = pos;
        }
    }

Написано много, но смысл простой: если колонка относится к заголовку, то установить позицию потока к смещению колонки. Если колонка относится к типу записи - установить позицию потока руководствуясь размером заголовка, размером записи, индексом записи и смещением колонки.

Следует заметить, что этот метод не будет работать адекватно при идентичных типах TRow и THeader. Проверку на такое совпадение я опустил. Если потребуется сделать что-то подобное, то лучше указать тип заголовка без колонок.

Теперь сердце хранилища - методы чтения и записи значений:

public override T ReadValue<T>(Column<T> column, int rowIndex)
    {
        if (column == null)
        {
            throw new ArgumentNullException("column");
        }
        lock (SyncRoot)
        {
            SetPosition(rowIndex, column);
            return column.ReadValue(Reader);
        }
    }

    public override void WriteValue<T>(Column<T> column, int rowIndex, T value)
    {
        if (column == null)
        {
            throw new ArgumentNullException("column");
        }
        lock (SyncRoot)
        {
            SetPosition(rowIndex, column);
            column.WriteValue(Writer, value);
        }
    }

Осталось всего ничего - код инициализации хранилища:

protected virtual void Initialize()
    {
        Header = CreateHeaderInstance();

        if (RowColumns.Size == 0)
        {
            CreateRowInstance(0); // вызвать инициализацию колонок записи.
        }

        int headerSize = HeaderColumns.Size;
        if (Stream.Length == 0)
        {
            Stream.SetLength(headerSize);
            Header.Initialize();
        }
        else
        {
            _length = (int)((Stream.Length - headerSize) / RowColumns.Size);

            if (headerSize + Length * RowColumns.Size != Stream.Length)
            {
                throw new InvalidOperationException("Unexpected stream length.");
            }
        }
    }

Сам по себе этот код не сложен, но тащит за собой одну проблему: кто-то его должен вызывать. Но это не может быть конструктор хранилища, потому как метод инициализации использует виртуальные методы. В отличие от C++, в C# виртуальные методы могут быть вызваны из конструктора базового класса, но существует опасность что перекрытые методы могут использовать поля производного класса, которые еще не будут проинициализированы. Потому из конструктора StreamStorage этот метод я вызывать не стал. Не нравится мне так же решение с отложенной инициализацией, где пришлось бы чуть ли не во всех методах вставлять проверку на наличие инициализации. Отказ от Template Method в пользу параметризации хранилища фабриками строк тоже не идеальное решение. Ведь одно из очевидных решений - реализация фабрик в классе произвольного хранилища. Но тогда будут сложности с передачей таких фабрик через конструктор класса StreamStorage.

Хорошим решением этой проблемы стало бы решение сделать класс StreamStorage не расширяемым (sealed), опубликовать методы GetRow(int index), свойство Length и при необходимости расширения использовать композицию... Но, при реализации индексированного хранилища потребуется доступ к BinaryReader, BinaryWriter, Stream-у и даже к корню синхронизации. Не хотелось бы делать эти вещи общедоступными, потому было принято решение расширять хранилище через наследование (вариант понапихать всю необходимую функциональность в один класс кажется мне скверным).

Итого обязанность вызова метода Initialize назначается на классы, расширяющие StreamStorage. Резюме: в итоге этого поста завершена реализация хранилища записей с фиксированной длинной, с доступом к записям по индексу, с потокобезопасным доступом к полям записей. Для того, чтобы воспользоваться хранилищем, нужно определить два типа записей (один для заголовка) примерно как TestRow в предыдущем посте, определить свой класс хранилища, унаследовавшись от StreamStorage<THeader, TRow> и предоставить доступ к методам GetRow(int index) и способу управления размером хранилища.

При необходимости производное хранилище может реализовать интерфейс списка (IList), организовать кэширование записей и вести себя как полноценная коллекция. Напомню, что методы ReadValue и WriteValue у хранилища чисто вспомогательные, что они нужны для базового класса RowBase, и что обращение к полям по задумке должно происходить через свойства класса записи, например как в TestRow из предыдущего поста. Впрочем, методы ReadValue и WriteValue не мешают, а даже немного дополняют функциональность хранилища возможностью получать доступ к значениям не создавая экземпляры записей, потому я не стал предпринимать попыток скрыть эти методы.

В следующем посте расскажу о способах индексации этого хранилища.

Хранилище записей фиксированной длины

noreply@blogger.com (samius) — Wed, 29 Oct 2008 19:32:00 +0000

Хранилище записей фиксированной длины (часть II) Случилось вдруг создать такой велосипед, который хранил бы в файле записи фиксированной длины и позволял бы ими оперировать. Почему бы не воспользоваться базой данных? На самом деле этот велосипед должен предоставлять локальный кэш одной из таблиц центральной БД в системе, в разработке которой я принимаю участие. Требования к нему специфические:

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

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

Организацию хранилища записей я позаимствовал у классов ADO. Таблица - набор записей, у таблицы есть набор колонок, доступ к значению поля записи определен на пересечении таблицы, колонки и записи (точнее ее индекса в таблице).

Отличия от класса DataTable в способе хранения данных. Данные хранятся в физическом потоке (Stream) и доступ к ним осуществляется через классы BinaryReader/BinaryWriter.

Начну, пожалуй, с реализации базового класса нетипизированной колонки. Будут и типизированные, но нетипизированные нужны для складывания их в коллекцию колонок:

public class Column
   {
       private readonly int _offset;
       private readonly int _size;
       private readonly ColumnCollection _columns;

       protected Column(ColumnCollection columns, int offset, int size)
       {
           if (columns == null)
           {
               throw new ArgumentNullException("columns");
           }
           _columns = columns;
           _offset = offset;
           _size = size;
       }

       public int Offset { get { return _offset; } }

       public int Size { get { return _size; } }

       public ColumnCollection Columns { get { return _columns; } }
   }

Здесь все просто. Каждая колонка знает размер значения в байтах, свою коллекцию колонок и смещение относительно начала записи. Все это запоминается в констуркторе колонки. Далее класс типизированной колонки. Типизированная колонка абстрактная, т.к. читать и писать данные придется с помощью BinaryReader/BinaryWriter-а, а они не имеют generic методов для чтения/записи значений.

public abstract class Column<T> : Column
    {
        protected Column(ColumnCollection columns, int offset, int size)
            : base(columns, offset, size)
        {
        }

        public abstract T ReadValue(BinaryReader reader);
        public abstract void WriteValue(BinaryWriter writer, T value);
    }

Типичный класс колонки:

class Int32Column : Column<int>
    {
        public Int32Column(ColumnCollection columns, int offset)
            : base(columns, offset, 4)
        {
        }

        public override int ReadValue(BinaryReader reader)
        {
            return reader.ReadInt32();
        }

        public override void WriteValue(BinaryWriter writer, int value)
        {
            writer.Write(value);
        }
    }

Таких классов несколько, не буду приводить код каждого из них, все они подобны. Немного отличается только класс строковой колонки, но о ней возможно позже. Обратите внимание, что класс типизированной колонки скрытый! Это объясняется тем, что я не собираюсь предоставлять возможность создания колонок сложных типов. Ограничусь лишь некоторыми примитивными. Класс коллекции колонок содержит в себе список колонок и число байт, требуемое для записи данных во всех колонках.

public class ColumnCollection
    {
        private readonly List<Column> _columns = new List<Column>();
        private int _size;

        public Column<int> AddInt32Column()
        {
            return AddInt32Column(this.Size);
        }

        public Column<int> AddInt32Column(int offset)
        {
            return AddColumn(new Int32Column(this, offset));
        }

        private Column<T> AddColumn<T>(Column<T> column)
        {
            _size = Math.Max(_size, column.Offset + column.Size);
            _columns.Add(column);
            return column;
        }

        public int Size { get { return _size; } }
    }

Коллекция колонок является так же производящим классом для типизированных колонок. Для каждого типа колонки (а их у меня чуть больше, чем только Int32Column) определено два метода создания экземпляра колонки: первый метод добавляет колонку в конец записи (указывает Offset, равный текущему размеру коллекции колонок в байтах), а второй - позволяет указать Offset вручную. Это потребуется для так называемых union полей.

Вот что из себя представляет базовый тип хранилища:

public abstract class StreamStorage
    {
        public abstract T ReadValue<T>(Column<T> column, int rowIndex);
        public abstract void WriteValue<T>(Column<T> column, int rowIndex, T value);
    }

Всего лишь два абстрактных метода, позволяющий писать и читать значения, соответствующие указанным колонкам и индексу записи. Этот базовый тип нужен для объявления базового типа записи. Хотел я параметризовать тип записи типом хранилища и тип хранилища типом записи, и возможно смог бы это сделать, но меня посетила идея, что у файла должен быть заголовок. И что заголовок - это второй тип записи. Т.е. хранилище надо параметризовывать двумя типами записи, но тогда каждую запись надо будет параметризовывать типом хранилища, в котором 2 типа записи... Но это все лишнее. Записи от хранилища не нужно ничего, кроме возможности обратиться к вышеуказанным методам. Потому базовый тип хранилища не имеет generic параметров. А базовый тип записи имеет generic параметр - конкретный тип записи:

public class RowBase<TRow>
        where TRow : RowBase<TRow>
    {
        private static readonly ColumnCollection s_columns = new ColumnCollection();
        public static ColumnCollection ColumnCollection { get { return s_columns; } }

        private readonly int _index;
        private readonly StreamStorage _storage;

        protected RowBase(StreamStorage storage, int index)
        {
            _storage = storage;
            _index = index;
        }

        public virtual void Initialize()
        {
        }

        public int GetIndex()
        {
            return _index;
        }

        public StreamStorage GetStorage()
        {
            return _storage;
        }

        protected T ReadValue<T>(Column<T> column)
        {
            return _storage.ReadValue(column, GetIndex());
        }

        protected void WriteValue<T>(Column<T> column, T value)
        {
            _storage.WriteValue(column, GetIndex(), value);
        }
    }

Базовый класс записи со спецификацией типа (т.е. все записи одного типа) привязаны к одному экземпляру коллекции колонок. Сделано это лишь для проверок. Для работоспособности хранилища интересен лишь размер записи, который определен в коллекции колонок и смещения самих колонок относительно записи. Но хранилище так же будет знать экземпляр коллекции колонок для проверки экземпляров колонок, которые приходят на публичные методы чтения и записи значений. Базовый класс записи содержит в себе ссылку на экземпляр хранилища, свой индекс, и определяет защищенные методы для чтения и записи значений.

Надеюсь, что код конкретной записи прояснит все что не ясно:

public class TestRow : RowBase<TestRow>
    {
        private static readonly Column<Guid> s_GuidColumn = ColumnCollection.AddGuidColumn();
        private static readonly Column<int> s_Int32Column = ColumnCollection.AddInt32Column();

        public TestRow(StreamStorage storage, int index)
            : base(storage, index)
        {
        }

        public Guid GuidValue
        {
            get { return ReadValue(s_GuidColumn); }
            set { WriteValue(s_GuidColumn , value); }
        }

        public int Int32Value
        {
            get { return ReadValue(s_Int32Column); }
            set { WriteValue(s_Int32Column, value); }
        }

        public override void Initialize()
        {
            base.Initialize();
            GuidValue = Guid.NewGuid();
            Int32Value = 0;
        }
    }

Итак, тип конкретной записи определяет колонки (статические поля), которые создает обращаясь к статической коллекции колонок, определенной у базового типа записи. Тип конкретной записи определяет свойства экземпляра записи. Реализация каждого свойства обращается к базовым методам чтения/записи значения и передает соответствующий экземпляр колонки. При обращении к свойству записи происходит передача колонки и номера записи хранилищу и вызывается метод чтения либо записи значения из хранилища.

О том, как устроено хранилище - в другой раз. Впрочем, наверняка идея уже ясна.

Asynchronous Stream Copying

noreply@blogger.com (samius) — Wed, 24 Sep 2008 20:14:00 +0000

Не так давно возникла необходимость копирования данных неопределенного размера в из одного потока данных (System.IO.Stream) в другой максимально быстрым образом. Речь шла о передаче больших файлов по локальной сети.

Самый простой способ выполнить требуюмую операцию - в цикле читать кусок данных из source потока и затем писать его в destination поток. При таком подходе время копирования данных складывается из суммарного времени чтения и суммарного времени записи, однако, теоретический нижний предел выполнения такой операции - суммарное время работы с самым медленным потоком.

Как приблизиться к теоретическому пределу? Ответ очевиден: читать очередную порцию данных во время записи предыдущей порции, т.е. выполнять работу по обмену с потоками одновременно. Что для этого потребуется? Управление потоками, объекты синхронизации? Вовсе нет. Задача выполнима в рамках паттерна IAsyncResult.

Далее я представлю метод, который копирует данные из потока в поток до тех пор, пока source поток не вернет 0 байт, но не больше чем указано в параметре count. Метод не очень большой (весь файл занимает около 100 строк вместе с объявлением класса и импортом пространств имен), но я разобью его на логические куски, так чтобы было удобнее комментировать. При желании куски можно будет сложить, и они будут работать.

Итак, объявление метода и проверка параметров:

public static long CopyData(Stream source, Stream destination, long count, int bufferSize)
{
    if (source == null)
        throw new ArgumentNullException("source");

    if (destination == null)
        throw new ArgumentNullException("destination");

    if (count < 0L)
        throw new ArgumentOutOfRangeException("count");

    if (bufferSize <= 0)
        throw new ArgumentOutOfRangeException("bufferSize");

    if(count == 0L)
        return 0L;

Метод возвращает число фактически скопированных байт. Оно может быть не равно параметру count в случае, если source поток достиг конца. Ничего интересного тут пока нет. Комментарии к этому куску опущу. А дальше они понадобятся:

    long totalBytes2Read = count;
  
    byte[] readingBytes = null;

    int bytesRead = 0;
    byte[] readBytes = null;

    int bytes2Write = 0;
    byte[] writingBytes = null;
     
    int bytesWrited = 0;
    byte[] freeBuffer = null;

    long totalWritedBytes = 0L;

    IAsyncResult asyncReadResult = null;
    IAsyncResult asyncWriteResult = null;

В порядке объявления:

totalBytes2Read - счетчик байт, которые осталось прочитать из потока source;
readingBytes - буфер данных, куда будут читаться данные. По мере прочтения буфер попадет в переменную readBytes;
bytesRead - число байт, фактически вчитанных в буфер;
readBytes - буфер, ожидающий записи в destination. После начала записи он будет храниться в переменной writingBytes;
bytes2Write - число прочитаных байт, но в другой переменной, соответствующей буферу, ожидающему записи;
writingBytes и bytesWrited - это записываемые байты и их число (число ранее вчитанных байт);
freeBuffer - освободившийся после записи буфер. При необходимости он будет использован заново, а это весьма вероятно;
asyncReadResult и asyncWriteResult - это результаты операций BeginRead и BeginWrite соответственно.

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

Сами границы этапов я оформил анонимными методами. Дело в том, что некоторые из них из управляющего кода вызываются больше одного раза, а оформлять настоящие методы и передавать в них много параметров и результатов мне показалось неуклюжим подходом. Итак, начало и конец чтения:

Action beginRead = () =>
    {
        var size = (int) Math.Min(bufferSize, totalBytes2Read);
        asyncReadResult = source.BeginRead(
            readingBytes = freeBuffer ?? (new byte[size]),
            0,
            size,
            null,
            null);
    };

    Action endRead = () =>
    {
        bytes2Write = bytesRead = source.EndRead(asyncReadResult);
        readBytes = readingBytes;
        totalBytes2Read -= bytesRead;
    };

beginRead первым делом определяет размер данных, которые нужно заказать source потоку. Далее он анализирует наличие свободного буфера и при отсутствии его создает новый. Размер создаваемого буфера может быть меньше, чем указанно в параметре bufferSize, т.к. по достижении конца заказанного в count диапазона полноразмерный буфер не нужен. Далее полученный буфер (свободный, либо вновь созданный) записывается в переменную readingBytes и source потоку заказывается чтение в этот буфер куска данных, равному size.

Результат выполнения операции BeginRead записывается в локальную переменную. endRead завершает операцию чтения у потока source, получает фактический размер прочитанных байт и размазывает его по двум переменным. Хватило бы одной переменной, но у них разные назначения. Далее буфер, в который мы читали становится буфером, ожидающим записи. И в конце декрементируется счетчик оставшихся для чтения байт.

Action beginWrite = () => asyncWriteResult = destination.BeginWrite(
        writingBytes = readBytes,
        0,
        bytesWrited = bytes2Write,
        null,
        null);

    Action endWrite = () =>
    {
        destination.EndWrite(asyncWriteResult);
        freeBuffer = writingBytes;
        totalWritedBytes += bytesWrited;
    };

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

Заключающий кусок кода - управляющая часть метода:

    beginRead();

    while (totalBytes2Read > 0L)
    {
        endRead();

        if (bytesRead <= 0)
            break;

        if (totalBytes2Read > 0L)
            beginRead();

        if (asyncWriteResult != null)
            endWrite();

        beginWrite();
    }

    endWrite();

    return totalWritedBytes;
}

Начинается управляющий кусок всегда с начала чтения. Дальше, в цикле, отслеживающим счетчик прочитанных байт, первым делом завершаем операцию чтения. Когда мы только вошли в цикл, то чтение только что начато, но пока оно не завершено, делать больше нечего - только ждать конца чтения. Затем анализируется число прочитанных байт. Если 0 - завершаем цикл. Читать больше нечего. Если есть что читать (работа со счетчиками ведется в операции endRead), то начинаем очередное чтение. Далее анализируется поле asyncWriteResult, для того, чтобы понять, начата ли операция записи. На первой итерации цикла оно пусто, т.е. окончание чтения пропускается. Во всех остальных итерациях будет ожидание завершения записи. После завершения записи - открываем новую операцию записи.

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

Для тестирования производительности я использовал производный от MemoryStream класс, который перекрывая соответствующие методы, регулировал время обращения к нему с помощью метода Thread.Sleep(int). Действительно, при больших объемах данных и малых размерах буфера время работы предложенного мной метода стремится к теоретическому пределу, а именно - к времени работы самого медленного потока. Даже при случайном распределении величины искувственной задержки для потоков, время копирования существенно меньше суммы времен работы с каждым из потоков.

Аналогичным способом можно оформить конвертирование файлов, либо другие асинхронные операции, выполняемые циклически. P.S. Надеюсь, что кому-нибудь пригодится данный подход. Мне кажется, что он довольно изящный )))

Readonly Auto-Implemented Properties

noreply@blogger.com (samius) — Mon, 22 Sep 2008 20:31:00 +0000

Вчера расстроился по поводу реализации auto-implemented properties в C# 3.0. Началось все с того, что прочитав документацию по этому вопросу довольно продолжительное время назад, и встретив там цитату

To create a readonly auto-implemented property, give it a private set accessor.

считал, что auto-implemented readonly свойства имеют отношение к ключевому слову readonly. Вот цитата из описания этого ключевого слова:

The readonly keyword is a modifier that you can use on fields. When a field declaration includes a readonly modifier, assignments to the fields introduced by the declaration can only occur as part of the declaration or in a constructor in the same class.

Именно на эту статью в документации ведет гиперссылка из статьи про auto-implemented свойства. Воображение рисовало такую реализацию этого нововведения компилятором, где бы код

class Foo
{
  public int MyProperty { get; private set; }

  public Foo(int p)
  {
      MyProperty = p;
  }
}

соответствовал бы следующей реализации:

class Foo
{
  private readonly int _autoGeneratedReadonlyField;

  public Foo(int p)
  {
      autoGeneratedReadonlyField = p;
  }

  public int MyProperty
  {
      get { return _autoGeneratedReadonlyField; }
  }
}

Таким образом, такая реализация auto-implemented свойства с private set аксессором, максимально соответствовала бы документации. Так получилось, что довольно долго я считал, что readonly auto-implemented свойства нельзя модифицировать нигде, кроме конструктора класса (либо статического конструктора, если свойство статическое). Оказалось, что private set не генерит ничего кроме private аксессора к свойству, обращение к которому разрешено из кода любого метода или свойства класса, либо вложенных классов.

Итого, использование readonly auto-implemented свойств не имеет никакого отношения к readonly полям класса. Зачем же тогда в документации стоит эта ссылка на описание ключевого слова readonly? Думаю, что кроме меня есть еще жертвы дезинформации.

Вообще говоря, поведение private set модификатора auto-implemented свойства выбрано правильно. И такое поведение нужно, но кроме этого нужна адекватная документация. Все же, эмуляция readonly полей нужна. И на форуме в RSDN было предложено несколько вариантов синтаксиса, которые могли бы быть реализованы. Например,

public readonly string MyString { get; }

public int Property { get; readonly set; }

public int Property { readonly; }

Удобен был бы способ инициализации таких свойств при объявлении (по аналогии с полями).

Расширения для System.Enum

noreply@blogger.com (samius) — Sat, 30 Aug 2008 05:25:00 +0000

Довольно странно, что языковые средства расширяются от версии к версии платформы, однако нововведения как-правило не затрагивают те части FCL, что знакомы нам с .NET 1.0. Речь пойдет о способах скрыть неуклюжие обращения к методам класса System.Enum, и добавить кое-какую функциональность. Определимся со списком целей:

метод object Enum.Parse(Type, string): приходится дважды указывать тип перечислителя (один раз аргументом метода, другой для приведения результата). Попытаемся подсахарить;
метод bool Enum.IsDefined(Type, object) так же требует указания типа перечислителя. В случае, когда тип перечислителя уже зашит в аргументе это лишнее. Например, когда требуется проверить принадлежность значения перечислителя к набору констант перечислителя без применения конструкции switch. Подсахарить;
проверка на наличие установленного флага выглядит слишком громоздко для использования в операторах ветвления:
```
if(FileAccess.Read == (fileAccess & FileAccess.Read)) { ... }
```
Еще хуже выглядит проверка на наличие сразу нескольких флагов. Определим метод, который с небольшим оверхедом по производительности скрасит конструкцию. (Наверняка, в Nemerle есть соответствующие макросы)

Для реализации задуманного потребуется два класса. Один - generic класс, в котором будут определены методы для работы с перечислителями а так же кое-какие статические поля, обеспечивающие работу этих методов:

public static class EnumExtensions<TEnum>
   where TEnum : struct, IComparable, IConvertible, IFormattable
{
}

Обратите внимание на ограничения параметра типа. Я постарался выбрать ограничения, максимально близкие к типу enum, просто для того, чтобы компилятор и intellisense не позволяли использовать этот класс для других типов. На самом деле ни одно из ограничений не понадобится для реализации требуемой функциональности. Они фиктивны. К сожалению, не удалось исключить создание типов аля EnumExtensions<int>. При создании таких типов можно добиться двух эффектов: исключения TypeInitializationException, либо ограниченной работоспособности. В данном конкретном случае предпочитаю избежать TypeInitializationException.

Второй класс нужен только для объявления extension-методов, т.к. они не могут быть определены в generic-классах:

public static class EnumExtensions
{
}

Начнем с метода Parse. В generic-классе определим следующий метод:

public static TEnum Parse(string value)
{
   return (TEnum)Enum.Parse(typeof(TEnum), value);
}

В классе для extension методов определим метод-обертку для вышеописанного:

public static TEnum Parse<TEnum>(this string value)
   where TEnum : struct, IComparable, IConvertible, IFormattable
{
   return EnumExtensions<TEnum>.Parse(value);
}

Обращаться к методу-расширению можно в следующей форме:

var mode = modeString.Parse<FileMode>();

Для реализации метода IsDefined(TEnum value) потребуется хранение набора констант, полученных с помощью метода Enum.GetValues(Type). Дело в том, что подглядев реализацию метода Enum.IsDefined(Type, object), я понял что меня не устраивает такое количество выполняемого кода для проверки значения на допустимость. Даже цена получения массива значений в Enum.GetValues(Type) слишком высока для обращения к этому методу более одного раза! Добавим в generic-класс следующий код:

private static readonly TEnum[] s_values = GetValues();

private static TEnum[] GetValues()
{
   return (typeof(TEnum).IsEnum)
       ? (TEnum[])Enum.GetValues(typeof(TEnum))
       : new TEnum[]{};
}

public static int IndexOf(TEnum value)
{
   return Array.IndexOf(s_values, value);
}

public static bool IsDefined(TEnum value)
{
   return IndexOf(value) > -1;
}

В порядке объявления: s_values - статическое поле для хранения массива величин типа TEnum. Инициализируется в объявлении. Статический метод GetValues проверяет, является ли тип TEnum перечислителем, и возвращает массив значений перечислителя, либо пустой массив, избегая исключения TypeInitializationException (оно непременно возникнет при возбуждении исключения ArgumentException при обращении к методу Enum.GetValues(Type) во время инициализации типа ExtensionMethods<TEnum>). Методы IndexOf и IsDefined тривиальны.

Отмечу только, что я не гарантирую их работоспособность при использовании типов, отличных от enum, которые смогли пролезть через набор ограничений Type-параметра (примитивные типы int, long,... и некоторые пользовательские типы). Уверен, что при желании читатель сможет самостоятельно реализовать достойное поведение этих методов для типов, отличных от enum. Думаю, что самым достойным здесь будет возбуждение исключения NotSupportedException.

Да, метод GetIndex(TEnum) получился в качестве бонуса, и я не вижу необходимости скрывать его. Может оказаться полезным. Добавим соответствующие extension-методы в класс EnumExtensions (не generic-класс):

public static int GetIndex<TEnum>(this TEnum value)
   where TEnum : struct, IComparable, IConvertible, IFormattable
{
   return EnumExtensions<TEnum>.IndexOf(value);
}

public static bool IsDefined<TEnum>(this TEnum value)
   where TEnum : struct, IComparable, IConvertible, IFormattable
{
   return EnumExtensions<TEnum>.IsDefined(value);
}

Вот код, проверяющий работу метода IsDefined и демонстрирующий обращение к нему через extension-метод:

Assert.IsTrue(FileMode.Open.IsDefined());

Assert.IsFalse(((FileMode)1000).IsDefined());

Получился весьма элегантный способ проверки значений на принадлежность к набору констант. Приступим к реализации метода bool HasFlags(TEnum value, TEnum flags). Не сложно реализовать такой метод с помощью обращения к методу ulong IConvertible.ToUInt64(IFormatProvider), однако производительность такого решения будет не на высоте (как минимум 4 операции boxing-а, 2 обращения к extern методам, 2 unboxing-а). Так же этот метод будет оперировать 64-х разрядными величинами, даже в тех случаях, когда перечислитель основан на более коротких типах.

Недавно пришло в голову, что динамически сгенерированный метод для соответствующего enum-типа может быть вполне приемлемым по производительности решением. Следующий метод определяет динамический метод DynamicMethod и делегирует генерацию кода переданному в качестве аргумента методу.

private static DynamicMethod BuildHasFlagsMethod(Type enumType, Action<ILGenerator> ilGenAction)
{
   var method = new DynamicMethod(
       "HasFlagMethod",
       typeof(bool),
       new Type[] { enumType, enumType },
       typeof(EnumExtensions).Module);

   var il = method.GetILGenerator();
   ilGenAction(il);
   return method;
}

Я не зря параметризовал этот метод параметром Type, в то время как в generic-классе известен тип TEnum. Для оптимизации работы JIT-компилятора и объема генерируемого им машинного кода следует выносить методы, не использующие явно типы generic аргументов, в не generic-классы. В рамках этого поста я буду располагать такие методы в generic-классе, но буду подразумевать, что читатель вынесет их во вспомогательный класс (если, конечно, статья окажется полезной для него, и он решит воспроизвести код).

Следующие два метода генерируют код реализации метода HasFlags. Первый генерирует хорошую реализацию, а второй - реализацию, которая выбрасывает исключение NotSupportedException. Вторая реализация пригодится для перечислителей без атрибута [Flags], либо для типов, не являющихся enum-ами.

static void EmitHasFlags(ILGenerator il)
{
   il.Emit(OpCodes.Ldarg_1);
   il.Emit(OpCodes.Ldarg_0);
   il.Emit(OpCodes.Ldarg_1);
   il.Emit(OpCodes.And);
   il.Emit(OpCodes.Ceq);
   il.Emit(OpCodes.Ret);
}

static void EmitThrowException(ILGenerator il)
{
   var ctor = typeof(NotSupportedException).GetConstructor(new Type[] { });
   il.Emit(OpCodes.Newobj, ctor);
   il.Emit(OpCodes.Throw);
}

Метод EmitHasFlags записывает два аргумента в стек для выполнения операций логического умножения и сравнения результата со втрорым аргументом, выполняет операции умножения и сравнения, затем возвращает результат. Операция логического умножения может быть выполнена только над примитивными типами, потому необходимо гарантировать обращение к этому методу генерации только при корректном generic-аргументе.

private static readonly Func<TEnum, TEnum, bool> s_hasFlagsMethod;

public static bool IsFlags { get; private set; }

static EnumExtensions()
{
   IsFlags = HasFlagsAttribute(typeof(TEnum));

   Action<ILGenerator> ilGenAction;
   if(IsFlags)
       ilGenAction = EmitHasFlags;
   else
       ilGenAction = EmitThrowException;

   var method = BuildHasFlagsMethod(typeof(TEnum), ilGenAction);

   s_hasFlagsMethod = (Func<TEnum, TEnum, bool>)method.CreateDelegate(
       typeof(Func<TEnum, TEnum, bool>));
}

internal static bool HasFlagsAttribute(Type enumType)
{
   return enumType.GetCustomAttributes(typeof(FlagsAttribute), false).Length > 0;
}

public static bool HasFlags(TEnum value, TEnum flags)
{
   return s_hasFlagsMethod(value, flags);
}

В порядке объявления: s_hasFlagsMethod - делегат для сгенерированного метода; IsFlags - свойство, указывающее на наличие атрибута [Flags] у типа TEnum. Это еще один полезный бонус, который можно оставить опубликованным; далее - статический конструктор.

Остановимся на нем подробнее: Первым делом он инициирует свойство IsFlags значением, возвращаенным методом HasFlagsAttribute(Type). Затем выбирается метод для генерации кода. При значении свойства IsFlags, равном true, можно гарантировать, что TEnum - enum тип, т.к. компилятор не даст применить атрибут [Flags] к любому другому типу, кроме enum. Однако, варьируя условие выбора метода генерации IL кода, можно добиться генерации рабочего метода для целых типов TEnum, при необходимости. Я, правда, такой необходимости не вижу. Для целых методов нет нужды обращаться к динамически сгенерированному коду, потому как можно определить методы обычным образом.

Наконец, реализация метода HasFlags(TEnum, TEnum), которая делегирует динамически сгенерированному методу. Объявление соответствующего extension-метода:

public static bool HasFlags<TEnum>(this TEnum value, TEnum flags)
   where TEnum : struct, IComparable, IConvertible, IFormattable
{
   return EnumExtensions<TEnum>.HasFlags(value, flags);
}

Использование этого метода может быть например таким:

if(fileAccess.HasFlags(FileAccess.Read)) { ... }

Предлагаю сравнить этот кусок кода с аналогичным выше. Думаю, что этот информативнее. Однако, не следует использовать этот метод в критичном по производительности коде.

P.S. Код для проверки флагов в типе int может выглядеть так:

public static bool HasFlags(this int value, int flags)
{
   return flags == (value & flags);
}

...
if(myIntValue.HasFlags(0x80)) { ... }

P.P.S Пробовал сгенерировать код с помощью Expression. Вот что вышло:

var valueParam = Expression.Parameter(typeof(TEnum), "value");
var flagsParam = Expression.Parameter(typeof(TEnum), "flags");
Expression body = Expression.Equal(
    flagsParam,
    Expression.And(valueParam, flagsParam));

В последней строке получил исключение: System.InvalidOperationException: The binary operator And is not defined for the types 'System.IO.FileAccess' and 'System.IO.FileAccess'.. Получается, что il.Emit(OpCodes.And); можно выполнить над Enum-ом, а Expression.And - нет. Был искренне удивлен.

Короткий синтаксис ADO .NET (часть IV)

noreply@blogger.com (samius) — Fri, 15 Aug 2008 07:57:00 +0000

Короткий синтаксис ADO .NET (часть I)
Короткий синтаксис ADO .NET (часть II)
Короткий синтаксис ADO .NET (часть III)

В предыдущих частях было описано все что необходимо для обращения к БД за один вызов, кроме разве что передачи параметров. В ADO .NET уже проделана вся работа по унифицированному способу задания параметров. Осталось лишь воспользоваться им.

Задумка в том, чтобы объявлять параметры к команде в том же обращении (ExecuteReader, ExecuteScalar либо ExecuteNonQuery) через запятые. Для каждого параметра достаточно передать только 2 значения - имя параметра и значение параметра. А тип параметра будет определяться типом значения. Определим следующий класс:

public class Parameter
{
    public string ParameterName { get; private set; }

    public DbType DbType { get; private set; }

    public object Value { get; private set; }

    private Parameter(string name, DbType type, object value)
    {
        ParameterName = name;
        DbType = type;
        Value = value;
    }

    public void ApplyParameter(IDbCommand command)
    {
        IDbDataParameter parameter = command.CreateParameter();
        parameter.ParameterName = ParameterName;
        parameter.DbType = DbType;

        if (ReferenceEquals(Value, null))
        {
            parameter.Value = DBNull.Value;
        }
        else
        {
            parameter.Value = Value;
        }

        command.Parameters.Add(parameter);
    }

    ...
}

Метод ApplyParameter создает унифицированным способом экземпляр параметра, передает ему хранящиеся в экземпляре имя, унифицированный тип и значение параметра, добавляет созданный параметр в коллекцию параметров команды. Обратите внимание, что конструктор класса Parameter объявлен с private модификатором видимости. Это потому, что я параноидально опасаюсь создания экземпляров с типом параметра не согласованным со значением параметра. Определение типов параметра возьмет на себя серия производящих методов.

Метод ConvertToObject<T>(T? value) конвертирует переданные nullable значения в object тип. В сочетании с методом ApplyParameter они удачно проецируют nullable типы на значения параметров.

internal static object ConvertToObject<T>(T? value)
    where T : struct
{
    if (value.HasValue)
    {
        return value.Value;
    }
    else
    {
        return null;
    }
}

public static Parameter Make(string name, string value)
{
    return new Parameter(name, DbType.String, value);
}

public static Parameter Make(string name, Guid? value)
{
    return new Parameter(name, DbType.Guid, ConvertToObject(value));
}

public static Parameter Make(string name, int? value)
{
    return new Parameter(name, DbType.Int32, ConvertToObject(value));
}

public static Parameter Make(string name, bool? value)
{
    return new Parameter(name, DbType.Boolean, ConvertToObject(value));
}

public static Parameter Make(string name, double? value)
{
    return new Parameter(name, DbType.Double, ConvertToObject(value));
}

public static Parameter Make(string name, DateTime? value)
{
    return new Parameter(name, DbType.DateTime, ConvertToObject(value));
}

public static Parameter Make(string name, decimal? value)
{
    return new Parameter(name, DbType.Decimal, ConvertToObject(value));
}

Таким образом, обращение

Make("@Value", (int?)null)

сформирует параметр целого типа со значением DbNull.Value. Почему производящие методы, а не перегруженные конструкторы? Просто в некоторых случаях могут потребоваться делегаты (например Func<string, int?, Parameter>), а делегат можно создать только для метода. Для добавления списка параметров к методам Execute*** воспользуемся ключевым словом params.

Вот обновленный интерфейс IDbDriver:

public interface IDbDriver
{
    IDbConnection MakeConnection();

    IDbCommand MakeCommand(IDbConnection connection, string commandText, params Parameter[] parameters);
    IDbCommand MakeCommand(string text, params Parameter[] parameters);

    int ExecuteNonQuery(string commandText, params Parameter[] parameters);
    int ExecuteNonQuery(IDbConnection connection, string commandText, params Parameter[] parameters);

    void ExecuteReader(Action<IDataReader> action, string commandText, params Parameter[] parameters);
    void ExecuteReader(IDbConnection connection, Action<IDataReader> action, string commandText, params Parameter[] parameters);
}

Не составит сложности модифицировать методы Execute*** и протянуть параметр parameters до метода MakeCommand. Вот его новая реализация:

public IDbCommand MakeCommand(IDbConnection connection, string commandText, params Parameter[] parameters)
{
    if (connection == null)
    {
        throw new ArgumentNullException("connection");
    }
    var result = connection.CreateCommand();

    result.CommandText = commandText;
    foreach (Parameter parameter in parameters)
    {
        parameter.ApplyParameter(result);
    }
    return result;
}

Осталось привести пример обращения к БД для выполнения команды с параметром:

[TestMethod]
public void ExecuteReaderRealTest()
{
    var dbDriver = new DbDriver(
        "Data Source=localhost;Initial Catalog=Northwind;Integrated Security=True",
        SqlClientFactory.Instance);

    DataTable table = new DataTable();
    dbDriver.ExecuteReader(
         table.Load,
         "SELECT * FROM [Order Details] WHERE UnitPrice > @Price",
         Parameter.Make("@Price", 20));

    Assert.IsTrue(table.Rows.Count > 0);
}

И в заключение содержательной части пример с выполнением более чем одной команды в рамках одного соединения:

static void LoadTable(DataTable table, IDbCommand command)
{
    using (var reader = command.ExecuteReader())
    {
        table.Load(reader);
    }
}

[TestMethod]
public void MultiCommandTest()
{
    var dbDriver = new DbDriver(
        "Data Source=localhost;Initial Catalog=Northwind;Integrated Security=True",
        SqlClientFactory.Instance);

    var dataSet = new DataSet();
    var orderDetails = dataSet.Tables.Add("Order Details");
    var orders = dataSet.Tables.Add("Orders");

    int orderId = 10248;

    using (var connection = dbDriver.MakeConnection())
    {
        var orderIdParameter = Parameter.Make("@OrderId", orderId);
      
        Func<string, IDbCommand> makeCommand =
            x => dbDriver.MakeCommand(connection, x, orderIdParameter);
                    
        using (var selectOrders = makeCommand("SELECT * FROM Orders WHERE OrderId = @OrderId"))
        using (var selectDetails = makeCommand("SELECT * FROM [Order Details] WHERE OrderId = @OrderId"))
        using (connection.CreateSession())
        {
            LoadTable(orders, selectOrders);
            LoadTable(orderDetails, selectDetails);
        }
    }

    Assert.IsTrue(orderDetails.Rows.Count > 0);
}

Обратите внимание, для короткой записи создания команды я использовал анонимный метод, который использует один экземпляр класса Parameter для формирования всех команд. При чтении DataSet наборов данных довольно часто используется одинаковый набор параметров при обращении к БД за разными таблицами. На этом и сыграл. Запись получилась компактной и наглядной. В первом посте я поведал об истории моего собеседования.

Надеюсь, что теперь вы меня поймете, что используя такую обвязку к ADO .NET не мудрено забыть кое-что из последовательности действий, описываемых в MSDN... Применяя такую обвязку к ADO, будьте внимательны на собеседованиях ;)

Содержательная часть серии постов об короткой нотации ADO .NET закончилась. Осталось только поудивляться тому, что разработчики Microsoft все необходимое сделали сами, как то инвариантные относительно движка БД способы создания соединений, команд, параметров команд, и даже предусмотрели инвариантные типы параметров. Однако, по каким-то причинам Microsoft просто не довела эту кухню до этого логического конца. Почему-то их логическим концом стал безумный кодогенератор дизайнера адаптеров данных, который генерирует дикое количество нечитаемого кода, завязанного на тип БД. Если разработчик работает с SqlServer, то дизайнер генерирует соединения SqlConnection, команды SqlCommand, параметры SqlParameter и совершенно не ясно, как модифицировать этот код для работы с другим движком БД, либо с несколькими. К тому же, вся документация ADO .NET кишит примерами, завязанными на конкретные движки БД. Скромно замечу, что преподнесенный мной код обвязки абсолютно инвариантен к типу БД. Но заслуга в этом разработчиков Microsoft.

Короткий синтаксис ADO .NET (часть III)

noreply@blogger.com (samius) — Fri, 15 Aug 2008 04:46:00 +0000

Короткий синтаксис ADO .NET (часть I)
Короткий синтаксис ADO .NET (часть II)
Короткий синтаксис ADO .NET (часть IV)

Приступим к созданию соединений и команд. Я для этого предпочитаю использовать некий класс DbDriver, параметризованный ConnectionString-ом и соответствующим DbProviderFactory классом. DbDriver создает соединения сразу же инициированные ConnectionString-ом, и команды, инициированные соединением. Следующий интерфейс как раз описывает эту сущность:

public interface IDbDriver
{
    IDbConnection MakeConnection();

    IDbCommand MakeCommand(IDbConnection connection, string commandText);
    IDbCommand MakeCommand(string text);

    int ExecuteNonQuery(string commandText);
    int ExecuteNonQuery(IDbConnection connection, string commandText);

    void ExecuteReader(Action<IDataReader> action, string commandText);
    void ExecuteReader(IDbConnection connection, Action<IDataReader> action, string commandText);
}

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

Методы выполнения команд (ExecuteNonQuery и ExecuteReader) перегружены со следующей целью. Один вариант принимает соединение, создает и инициирует команду, открывает открывает соединение (если не было открыто), выполняет команду, закрывает (если было закрыто), уничтожает команду и возвращает результат. Второй вариант - создает соединение, вызывает первый вариант, после чего уничтожает соединение.

public class DbDriver : IDbDriver
{
    public DbDriver(string connectionString, DbProviderFactory providerFactory)
    {
        if (providerFactory == null)
        {
            throw new ArgumentNullException("providerFactory");
        }
        ProviderFactory = providerFactory;
        ConnectionString = connectionString;
    }

    public string ConnectionString { get; private set; }

    public DbProviderFactory ProviderFactory { get; private set; }

    public IDbConnection MakeConnection()
    {
        IDbConnection result = ProviderFactory.CreateConnection();
        result.ConnectionString = ConnectionString;
        return result;
    }

    public IDbCommand MakeCommand(IDbConnection connection, string commandText)
    {
        if (connection == null)
        {
            throw new ArgumentNullException("connection");
        }
        var result = connection.CreateCommand();
        result.CommandText = commandText;
        return result;
    }

    public IDbCommand MakeCommand(string commandText)
    {
        return MakeCommand(MakeConnection(), commandText);
    }
    ....
}

Выше приведена реализация конструктора класса и производящих методов. Надеюсь, что комментарии излишни. Далее реализация методов, выполняющих команды:

public int ExecuteNonQuery(string commandText)
{
    using (var connection = MakeConnection())
    {
        return ExecuteNonQuery(connection, commandText);
    }
}

public int ExecuteNonQuery(IDbConnection connection, string commandText)
{
    if (connection == null)
    {
        throw new ArgumentNullException("connection");
    }

    using (var command = MakeCommand(connection, commandText))
    using (connection.CreateSession())
    {
        return command.ExecuteNonQuery();
    }
}

public void ExecuteReader(IDbConnection connection, Action<IDataReader> action, string commandText)
{
    if (connection == null)
    {
        throw new ArgumentNullException("connection");
    }

    using (var command = MakeCommand(connection, commandText))
    using (connection.CreateSession())
    using (var reader = command.ExecuteReader())
    {
        action(reader);
    }
}

public void ExecuteReader(Action<IDataReader> action, string commandText)
{
    using (var connection = MakeConnection())
    {
        ExecuteReader(connection, action, commandText);
    }
}

Методы Execute*** делают попытку открыть соединение в самый последний момент перед обращением к команде и закрывают соединение, если оно было закрыто перед вызовом, сразу после выполнения команды. Повторюсь, гибкость метода CreateSession позволяет одними методами работать как с первоначально закрытым соединением с БД, так и с уже октрытым. ExecuteReader принимает Action<IDataReader>. Это связано с тем, что IDataReader должен быть освобожден до закрытия соединения. Если метод ExecuteReader будет закрывать соединение, т.е. если соединение было закрыто перед вызовом, то к тому моменту требуется прочитать все что надо из IDataReader-а. Метод ExecuteScalar я даже не стал включать в пример, т.к. он работает полностью аналогично методу ExecuteReader.

Unit тесты приводить не буду. Но один интеграционный, пожалуй приведу. Он довольно показателен по части того, что достигнуто:

[TestMethod]
public void ExecuteReaderRealTest()
{
    var dbDriver = new DbDriver(
        "Data Source=localhost;Initial Catalog=Northwind;Integrated Security=True",
        SqlClientFactory.Instance);

    DataTable table = new DataTable();

    dbDriver.ExecuteReader(
        reader => table.Load(reader),
        "SELECT OrderId FROM [Order Details]");

    Assert.IsTrue(table.Rows.Count > 0);
}

Код, что отвечает непосредственно за обращение к БД занимает всего 3 строчки. В рамках обращения к одному методу выполняются действия, перечисленные в конце первой части этой серии постов.

Почти все! Не хватает только чего-то для работы с параметрами команд. А это в следующем посте...

Короткий синтаксис ADO .NET (часть II)

noreply@blogger.com (samius) — Thu, 14 Aug 2008 11:58:00 +0000

Короткий синтаксис ADO .NET (часть I)
Короткий синтаксис ADO .NET (часть III)
Короткий синтаксис ADO .NET (часть IV)

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

анализировала состояние указанного соединения, и открывала бы его, если оно не открыто;
гарантированно закрывала бы соединение после использования, в случае если соединение было первоначально закрыто;
обращение к такой конструкции не занимало бы много места.

Отличный повод воспользоваться конструкцией using и интерфейсом IDisposable чтобы избежать конструкция try/finally. Вот код требуемой сущности:

public class ConnectionSession : IDisposable
{
   public ConnectionSession(IDbConnection dbConnection)
   {
       if (dbConnection == null)
       {
           throw new ArgumentNullException("dbConnection");
       }
       DbConnection = dbConnection;

       WasOpened = ConnectionState.Open == (DbConnection.State & ConnectionState.Open);

       if (!WasOpened)
       {
           DbConnection.Open();
       }
   }

   public IDbConnection DbConnection { get; private set; }
   public bool WasOpened { get; private set; }

   public void Dispose()
   {
       if (!WasOpened)
       {
           DbConnection.Close();
       }
   }
}

Прежде чем начну комментировать код, хочу заметить, что в связи с грядущим переходом на C# 3.0, я начинаю пробовать на вкус новый синтаксис. Однако, все или почти все можно повторить на C# 2.0.

Как я уже сказал, интерфейс IDisposable реализован чисто для поддержания короткого синтаксиса using. Сей объект не нуждается в финализации и DbConnection сам будет освобождать необходимые ресурсы при сборке мусора. Быть может когда-нибудь я уделю связке using/IDisposable больше внимания.

Почему я использовал IDbConnection интерфейс, вместо базового класса DbConnection? Очень просто. При тестировании я могу подменить объект без средств тестирования, использующих инструментацию сборок. Для генерации mock объектов и заглушек (stub) я использую Rhino Mocks. Это первая библиотека мокогенераторов, которую я использую, и очень доволен ей. Пока не было поводов переходить на другие. А с новым синтаксисом (для .NET 3.5) я просто обожаю Rhino (это не реклама! Rhino Mocks - бесплатная библиотека и мне за упоминание о ней никто не платит).

В постах я буду приводить некоторые тесты, но далеко не все, которые пишу.

[TestMethod]
   public void UsingConstructionWithOpenedConnectionTest()
   {
       var connection = MockRepository.GenerateStub<IDbConnection>();

       connection.Stub(x => x.State).Return(ConnectionState.Closed);

       using (new ConnectionSession(connection))
       {
           connection.AssertWasCalled(x => x.Open());
           connection.AssertWasNotCalled(x => x.Close());
       }

       connection.AssertWasCalled(x => x.Close());
   }

   [TestMethod]
   public void UsingConstructionWithClosedConnectionTest()
   {
       var connection = MockRepository.GenerateStub<IDbConnection>();

       connection.Stub(x => x.State).Return(ConnectionState.Open);

       using (new ConnectionSession(connection))
       {
           connection.AssertWasNotCalled(x => x.Open());
       }

       connection.AssertWasNotCalled(x => x.Close());
   }

Несмотря на то, что в каждом тесте рекомендуется проверять не более одного условия, я напичкал их множеством условий, потому как я тестировал поведение ConnectionSession в рамках конструкции using. Это уже даже не unit тест, а некий интеграционный. Unit тесты класса ConnectionSession я опустил. Их больше, чем хотелось бы вставлять в пост. Оговорки в условиях к ConnectionSession (вначале поста) нужны для безопасного использования соединения в области действия нескольких вложенных блоков using для ConnectionSession объектов. В рамках C# 3.0 будет удобен следующй extension метод:

public static class ConnectionSessionExtensions
{
    public static ConnectionSession CreateSession(this IDbConnection connection)
    {
        return new ConnectionSession(connection);
    }
}

это позволит писать код в стиле

using (connection.CreateSession())
{
    return command.ExecuteNonQuery();
}

Довольно емкий смысл вложен в одну строчку:

если соединение не открыто, то открыть его, если было закрыто, то закрыть после выхода из блока.

Уже этот код позволит многим сделать обращения к ADO (и не только) более лаконичными. Но на этом не остановимся, продолжение следует.

Короткий синтаксис ADO .NET (часть I)

noreply@blogger.com (samius) — Mon, 11 Aug 2008 19:07:00 +0000

Короткий синтаксис ADO .NET (часть II)
Короткий синтаксис ADO .NET (часть III)
Короткий синтаксис ADO .NET (часть IV)

Да, есть такая технология, пока. Можно даже сказать была, или почти была. Но ADO .NET еще поживет какое-то время. Не хотелось бы обсуждать недостатки этого динозавра в сравнении с LINQ to SQL или Entity Framework, либо ORM подходами. Это не тема данного поста.

Здесь лишь примем факт, что ADO .NET еще пока актуально, хоть и сильно сдает позиции. На этой технологии уже много что написано, и еще пишется, и кое-что будет написано. Хочу обратить внимание, что несмотря на повсеместное засилье ADO в среде .NET разработчиков (до последнего времени), пользоваться ADO в чистом виде довольно неудобно, громоздко. Многие вероятно видали код, сгенерированный дизайнером для DbAdapter-ов, DbCommand и их параметров... А про кол-во манипуляций, необходимых для выполнения запроса и закрытия всех щелей за собой для очистки совести, есть целая история.

История о том, как я проходил собеседование в одну контору на позицию удаленного разработчика. Надо заметить, что вакансия была с заманчивой почасовой оплатой, соразмерной ставке freelancer-а. Интервьюера в большей степени интересовали навыки работы с WinForms и ADO .NET. На вопросы о WinForms я довольно резво ответил (как мне показалось), но с ADO - поплавал: Меня попросили набросать код для чтения каких-либо данных из таблицы БД в DataTable прямо в ICQ. Я что-то быстро набросал и отправил набросок. На что последовал ответ: "Ваш код работать не будет!". Это меня довольно сильно смутило. Я смотрел на этот код и не мог понять, что же в нем не так. Когда я его вставил в Visual Studio и попробовал выполнить, меня озарило: я забыл открыть DbConnection. О чем и поведал интервьюеру.

Заверения о том, что я обычно тестирую свой код и то что такие ляпы не выходят из под моего пера в продакшн, не подействовали на собеседника. Но и сразу отказ я не получил. Мне было позволено задать пару наводящих вопросов и подождать до того, как со мной свяжутся. За пару наводящих вопросов выяснилось, что работа, мягко говоря, не фантан: имеется 250 (или около того) набросков форм, кои надо выполнить в WinForms и сваять для них запросы к 250-ти таблицам. Никакого творчества, инициативы, рефакторинга, тестирования не подразумевалось. Нужно было выдать bug free код как можно быстрее и сделать это как можно ближе к способам, описываемым в MSDN (M$ way).

Понятно, что заклинание использования ADO должно было отскакивать от кандидата как "Отче наш" от послушника в монастыре! Я рад, что мне не предложили эту работу. Я застрелился бы наверное на 10-ой форме. Однако, оправдывает мою забывчивость лишь то, что я не один год работал со своим заклинанием, которое в работе с ADO было на порядок удобнее, чем то что предлагал MSDN. А сейчас мои заклы (заклинания) стали еще удобнее. Именно о том, как может быть удобно с ADO .NET, будет мой пост (может пару или тройку, как попрет).

Попробую перечислить действия, необходимые для выполнения запроса и уборки за собой в общем случае для типа команды ExecuteReader:

Создать DbConnection. Вообще его можно создать обратившись к конструктору, например, SqlConnection. Но в .NET 2.0 появился более правильный путь (через DbProviderFactories, что требует дополнительных манипуляций);
Указать ConnectionString;
Создать DbCommand. Мы можем создать ее через конструктор, либо попросить это сделать connection;
Указать текст команды;
Создать и заполнить свойства необходимых параметров. Тобишь имена, типы, значения;
Добавить параметры в коллекцию параметров команды;
Открыть соединение (именно это я забыл сделать на собеседовании);
Выполнить команду и получить объект DbDataReader;
Вчитать данные из ридера;
Закрыть и уничтожить ридер (можно просто уничтожить);
[Вообще на предыдущем этапе многие и бросают и все работает, но я доведу до конца.] Уничтожить команду. Вопрос, конечно философский, но раз команда реализует IDisposable, то уничтожить ее дело чести для меня, не вдаваясь в подробности реализации. А подробности бывают разные. Конечно, если мы хотим сделать reuse этой команды, то уничтожать ее не надо пока;
Закрыть соединение (процедура крайне желательная, если не последует другая команда сразу за выполнением очередной);
Уничтожить соединение.

Использование DbDataAdapter-а лишь расширит этот перечень. Ничего не забыл? :) Сосредотачиваясь на таком объеме инструкций легко забыть, для чего идешь в БД... Шутка! Но не без доли правды. Так вот, есть трюки, позволяющие сделать это все в рамках одного вызова большого метода. И этот вызов будет сосредоточен в одном месте, охвачен одним взглядом, а не размазан по коду дизайнера подальше от глаз программиста.

На авторство приемов я не претендую. Вполне допускаю, что они были известны до меня, и может быть где-то опубликованы. Но я не сталкивался ни с чем подобным до сих пор. Пока перекур. Блог свежий, пока народ подтянется (если подтянется вообще), все задуманное будет описано.

Трюк с generic-ами.

noreply@blogger.com (samius) — Mon, 11 Aug 2008 19:03:00 +0000

Сегодня покажу как можно одной строчкой прикрутить к классу некоторую функциональность с учетом типа класса. К сожалению, данный трюк имеет ограничения, но все же я им часто пользуюсь.

Приведу случай из реальной жизни. В системе, в разработке которой я принимаю участие, требуется довольно много разных данных сохранять в xml. Поначалу мы много использовали xml сериализацию. Требовалось уметь сериализовывать и десериализовывать 5 или 6 типов графов. Единственное, что было общее у этих графов - необходимость сериализации в файл, в строку. Вполне естевственно, что после появления второй иерархии объектов для сериализации, возникло желание использовать общий код для сериализации и десериализации графов. Приходила в голову идея использовать внешнюю утилиту, однако использование внешней утилиты показалось не очень красивым (требовалась передача типа корня сериализации во внешний метод):

Foo foo = XmlUtils.DeserializeFromFile(typeof(Foo), "Foo.xml");

или

Foo foo = XmlUtils.DeserializeFromFile<Foo>("Foo.xml");

а душе хотелось полета:

Foo foo = Foo.DeserializeFromFile("Foo.xml");

Таким образом, требуется определить статический метод, который бы для типа Foo возвращал результат типа Foo, а для типа Bar возвращал бы результат типа Bar. Есть средство. Определим хитрый базовый класс:

public class XmlSerializationRoot<TRoot>
   where TRoot : XmlSerializationRoot<TRoot>
{
   public static TRoot DeserializeFrom(TextReader reader)
   {
       if (reader == null)
           throw new ArgumentNullException("reader");

       return (TRoot)CreateSerializer().Deserialize(reader);
   }

   public static TRoot DeserializeFrom(Stream stream)
   {
       if (stream == null)
           throw new ArgumentNullException("stream");

       using (StreamReader reader = new StreamReader(stream))
           return DeserializeFrom(reader);
   }

   public static TRoot DeserializeFromString(string xml)
   {
       using (TextReader reader = new StringReader(xml))
           return DeserializeFrom(reader);
   }

   public static TRoot DeserializeFromFile(string fileName)
   {
       using (TextReader reader = File.OpenText(fileName))
           return DeserializeFrom(reader);
   }

   private static XmlSerializer CreateSerializer()
   {
       return new XmlSerializer(typeof(TRoot));
   }

   public void SerializeTo(TextWriter writer)
   {
       if (writer == null)
           throw new ArgumentNullException("writer");

       CreateSerializer().Serialize(writer, this);
   }

   public string SerializeToString()
   {
       StringBuilder builder = new StringBuilder();
       using (StringWriter writer = new StringWriter(builder))
           this.SerializeTo(writer);

       return builder.ToString();
   }

   public void SerializeToFile(string fileName)
   {
       using (StreamWriter writer = File.CreateText(fileName))
           this.SerializeTo(writer);
   }

   public void SerializeTo(Stream stream)
   {
       using (StreamWriter writer = new StreamWriter(stream))
           this.SerializeTo(writer);
   }
}

Особый интерес представляют статические методы десериализации. Методы сериализации были внесены до кучи, чтобы пример был полным. Вообще говоря, класс XmlSerializationRoot не будет являться базовым классом для классов с возможностью сериализации. Базовым классом для них будет XmlSerializationRoot<T>. Т.е. при следующем объявлении класса Foo

class Foo : XmlSerializationRoot<Foo>
{
}

мы получим ситуацию, где класс Foo наследует определенные у класса XmlSerializationRoot<Foo> методы. Теперь можно пользоваться этими методами через идентификатор типа Foo:

Foo foo = Foo.DeserializeFromFile("foo.xml");

В качестве завершающего штриха предлагаю выделить интерфейс

public interface IXmlSerializable
{
   void SerializeTo(TextWriter writer);
   void SerializeToFile(string fileName);
   void SerializeTo(Stream stream);
   string SerializeToString();
}

и поддержать его классом XmlSerializationRoot. Теперь мы сможем вызывать методы сериализации не зная типа сохраняемого объекта. Теперь буду писать гадости про этот подход.

Данный подход навязывает ограничение наследования на разрабатываемые классы. При необходимости наследования классов от другого класса, использование усложняется, однако, можно объявить собственные методы и делегировать их вспомогательному классу. Например:
```
class Foo : SomeBaseClass // наследуемся от чего-то другого
{
   public static Foo DeserializeFromFile(string fileName)
   {
       return XmlSerializationRoot<Foo>.DeserializeFromFile(fileName);
   }
}
```
В данном случае потребуется убрать constraint у класса XmlSerializationRoot. В принципе, он объявлен формально для контроля за способом использования функциональности, и не требуется для компиляции методов класса.
Resharper ругается на использование методов базового класса через идентификатор производного типа. Можно подкрутить его настройки, вставить управляющий комментарий, либо просто игнорировать данные сообщения.
Пользуясь этим подходом мы не можем прочитать что-то из файла, а потом разобраться, что это было. Но в этом виноват не только сей подход, а так же устройство XML сериализации в FCL.
Если требуется объявить только статические методы, то мы не сможем объявить базовый класс с модификатором static. Если объявим, то не сможем унаследовать от него.

Хоть область применения данного подхода не широка, но иногда это то что надо. Например, при необходимости подсчета экземпляров классов разного типа.

P.S. Хочу обратить внимание, что в данном посте не шла речь о корректности данного подхода к сериализации в архитектурном плане. Это лишь пример издевательства над языком. Однако, данный код отлично работал и был удобно используемым, пока мы не перешли на более тяжелый (но более гибкий) способ сериализации через XmlDocument.

Вывод типов (Type Inference) в С# 2.0

noreply@blogger.com (samius) — Mon, 11 Aug 2008 18:05:00 +0000

Довольно часто использую вывод типов чисто в декларативных целях. Представим ситуацию, когда требуется объявить массив пар (KeyValuePair<string, int>). Ситуация не частая, но на ее примере я покажу пару незатейливых приемов.

KeyValuePair<string, int>[] pairs = new KeyValuePair<string, int>[] {
  new KeyValuePair<string, int>("A", 0),
  new KeyValuePair<string, int>("B", 1)
};

Код довольно простой, но выглядит громоздко. Попробуем что-нибудь сделать с объявлением элементов массива: Введем вспомогательный метод MakePair:

static KeyValuePair<K, V> MakePair<K, V>(K key, V value)
{
  return new KeyValuePair<K, V>(key, value);
}

С учетом введенного метода, объявление массива можно переписать следующим образом:

KeyValuePair<string, int>[] pairs = new KeyValuePair<string, int>[] {
  MakePair("A", 0),
  MakePair("B", 1)
};

Следующий метод позволит переложить ответственность за создание экземпляра массива на компилятор:

public static T[] MakeArray<T>(params T[] items)
{
return items;
}

Таким образом, вышеописанный пример превращается в прилично читаемый код:

KeyValuePair<string, int>[] pairs = MakeArray(
  MakePair("A", 0),
  MakePair("B", 1));

Код приведенных методов настолько прост, что может быть расположен прямо по месту использования. Однако, я предпочитаю объявлять такие вещи в классе Utils, либо Tools (как шарахнет сверху).

Подсветка синтаксиса

noreply@blogger.com (samius) — Mon, 11 Aug 2008 11:48:00 +0000

Первое, с чем столкнулся при попытке вставить пост с примерами - сложности с подсветкой синтаксиса и форматированием кода примеров. Однако, довольно быстро нашел статью, как все побороть. Спасибо проекту SyntaxHighlighter, thanks to Neil Kilbride (статья здесь). Будет время, напишу о процессе прикручивания этого проекта к блогу.

[+/-] скрытый текст

Инструкция по вставке скрытого текста