вторник, 1 декабря 2009 г.

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

Вот и я написал собственное введение в монады. Нет, вовсе не потому что я разобрался в этом вопросе лучше других. Мне кажется, что мое введение будет проще чем другие, т.к. оно требует только лишь знаний языка 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] (см. ниже).
    Не буду обещать, что расскажу о них в ближайшее время, вместо этого предлагаю заинтересовавшимся шагнуть в мир монад самостоятельно, используя следующие ссылки:

    Ссылки

    1. http://www.rsdn.ru/article/funcprog/monad.xml
    2. http://blogs.msdn.com/wesdyer/archive/2008/01/11/the-marvels-of-monads.aspx
    3. http://weblogs.asp.net/podwysocki/archive/2008/10/13/functional-net-linq-or-language-integrated-monads.aspx
    4. http://blogs.msdn.com/lukeh/archive/2007/08/19/monadic-parser-combinators-using-c-3-0.aspx
    5. http://www.haskell.org/all_about_monads/html/index.html

    вторник, 20 октября 2009 г.

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

    Во время выполнения одного из упражнений учебника по языку 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.
    1. В C# нет типа BigInt (неограниченного целого). Потому решение на C# ограничено типом Int32.
    2. В C# нет встроенного генератора бесконечного списка. Enumerable.Range требует ограничителя диапазона и не воспринимает шаг. Впрочем, легко написать свой генератор, что я и сделал.
    3. В 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-ем, пока еще поверхностное, позволило по новому взглянуть на известные ранее алгоритмы и инструменты.

    среда, 20 мая 2009 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Ходил пару дней в недоумении: потом меня образумил батя (он как раз из касты математиков в том НИИ). Батя мне сказал, что я со своим болтом отбросил тень на членов высшей касты.
    Disclaimer (особый вид интеллектуальной индульгенции)
    Вообще-то у меня плохая память, богатая фантазия, и это все неправда.
    ЗЫ. А прототип - настоящий.

    четверг, 30 апреля 2009 г.

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

    Рассмотрим один прием, помогающий выводить типы (на авторство не претендую) на примере мемоизации. В двух словах, если кто не вкурсе, мемоизация – это техника оптимизации (подвид кэширования), используемая для избежания вызовов функций с повторяющимися аргументами. Множество примеров реализации мемоизации на 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. Но душа захотела реюза описанного ранее метода мемоизации функции одного аргумента. Мне пока известно два способа сделать реюз:
    1. Применить последовательно мемоизацию к каждому аргументу, что привлечет к появлению множества экземпляров словарей (не интересно для дальнейшего обсуждения)
    2. Применить мемоизацию к методу, который принимает аргумент-комбинацию двух аргументов, а возвращает результат вызова метода 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 анонимного типа. Далее этот компарер используется для построения словаря.

    суббота, 11 апреля 2009 г.

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

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

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

    Как решалась эта задача раньше (точнее как я ее решал в ВУЗ-е): брались классы-вершины и классы-ребра, и под них писался алгоритм. Я использовал алгоритм Дейкстры для случаев с неотрицательными весами (кстати, алгоритму 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. И кто сказал, что библиотеки для работы с графами должны быть Объектно-Ориентированными?

    пятница, 10 апреля 2009 г.

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

    Последнее время часто использую методы с обобщенными аргументами. Довольно часто приходится сравнивать значения обобщенных типов между собой, сравнивать с 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)

    Хранилище записей фиксированной длины
    Хранилище записей фиксированной длины (часть 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 пул открытых соединений с возможностью безопасной записи? Возможно... Какие-то противоречивые чувства меня раздирают. Одно ясно точно: надо больше смотреть по сторонам.