Внутренность boolinq для взрослых

    Статья для тех, кому интересна реализация библиотеки boolinq из предыдущего моего поста. В этой статье я копну в исходники и покажу несколько интересных приёмов, которые позволили сделать библиотеку «ленивой» и расширяемой.




    Что не так с итераторами?


    Прежде чем мы посмотрим в код библиотеки, хотелось бы обратить ваше внимание на STL. Это стандартная библиотека шаблонов, содержит контейнеры, алгоритмы и т.д. Одним из самых интересных элементов библиотеки является сущность — итератор. Итераторы были придуманы для того чтобы быть прослойкой между контейнерами и алгоритмами. Чтобы любой алгоритм можно было применить к любому контейнеру (ну почти любые).

    На первый взгляд — всё хорошо. Алгоритмы и контейнеры связаны через промежуточную сущность — итератор. Но это только на первый взгляд, если присмотреться к коду:

    int sum = 0;
    for (std::vector<int>::iterator it = candles.begin(); it != candles.end(); it++)
        sum += it->ClosePrice;

    Есть один минус у STL-итераторов не заметный на первый взгляд, итераторы Java этого минуса лишены.

    int sum = 0;
    Iterator it = al.iterator(); 
    while (it.hasNext()) {    
        it = it.next();
        sum += it.ClosePrice;
    }

    Да, это .begin() и .end() — это две части одной сущности. Если бы эти две части взять и объединить в одну сущность… Сказано — сделано (идея заимствована у Александреску из презентации «Iterators Must Go»):

    template<typename TIter> 
    class IterRange
    {
    public:
        typedef typename std::iterator_traits<TIter>::value_type value_type;
        
        IterRange(TIter b, TIter e)
            : b(b), e(e)
        {
        }
    
        bool empty()
        {
            return (b == e);
        }
    
        value_type popFront()
        {
            assert(!empty());
            return *(b++);
        }
    
        value_type popBack()
        {
            assert(!empty());
            return *(--e);
        }
    
        value_type front()
        {
            assert(!empty());
            return *b;
        }
    
        value_type back()
        {
            assert(!empty());
            TIter tmp = e;
            return *(--tmp);
        }
    
    private:
        TIter b;
        TIter e;
    };

    Таким образом мы имеем одну сущность, можем спросить её есть ли ещё элементы в последовательности, запросить элемент и запросить перейти к следующему элементу. На самом деле также не помешают методы back() и popBack().

    Ну а дальше не трудно догадаться как выглядят все классы библиотеки — это обертки над таким Range-ем. Например WhereRange выглядит так:

    template<typename R, typename F> 
    class WhereRange
    {
    public:
        typedef typename R::value_type value_type;
        
        WhereRange(R r, F f)
            : r(r), f(f)
            , frontReady(false)
            , backReady(false)
        {
        }
    
        bool empty() 
        { 
            if (!frontReady)
                seekFront();
            return r.empty();
        }
    
        value_type popFront() 
        { 
            if (!frontReady)
                seekFront();
    
            auto tmp = *this;
            r.popFront();
            frontReady = false;
            return tmp.front();
        }
    
        value_type popBack() 
        {
            // аналогично
        }
    
        value_type front()
        { 
            if (!frontReady)
                seekFront();
            return r.front();
        }
    
        value_type back() 
        { 
            // аналогично
        }
    
    private:
        void seekFront()
        {
            while(!r.empty() && !f(r.front()))
                r.popFront();
            frontReady = true;
        }
    
        void seekBack()
        {
            // аналогично
        }
    
    private:
        R r;
        F f;
        bool frontReady;
        bool backReady;
    };

    В двух словах: класс принимает в конструктор другой Range, из которого ему предстоит брать элементы, и предикат, определяющий принадлежность каждого из элементов к результирующей выборке. Имеются 2 переменных, определяющих найдено ли значение «с начала» и «с конца» Range-а. Функции seekFront() и seekBack() непосредственно занимаются поиском следующего front-а и следующего back-а.

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

    Хочу точечную нотацию


    С одной стороны хотелось сделать использование методов также как они используются в .NET LINQ, но ведь в C++ нет Extension Methods как в C#:

    int max = arr.Where(...).OrderBy(...).Select(...).Max();

    С другой стороны хотелось сделать библиотеку расширяемой… и тут пришла такая мысль)) Сверху всех Range-ей будет обернут класс Linq, при вызове преобразующих последовательность методов — оборачиваться будет вложенный в Linq класс, а класс Linq так и будет оставаться сверху всех.

    Каждому классу Range-а сделал по оборачивающему классу Mixin-у следующего вида:

    template<template<typename> class TLinq, typename R>
    class WhereRange_mixin
    {
    public:
        template<typename F>
        TLinq<WhereRange<R,F> > where(F f) const
        {
            return boolinq::where(((TLinq<R>*)this)->r,f);
        }
    };

    Потом, отнаследовал класс Linq от всех необходимых Mixin-ов:

    template<typename R>
    class Linq
        : public SkipRange_mixin<Linq,R>
        , public TakeRange_mixin<Linq,R>
        , public WhereRange_mixin<Linq,R>
        , public SelectRange_mixin<Linq,R>
        , public ReverseRange_mixin<Linq,R>
        , public OrderByRange_mixin<Linq,R>
        // ... много классов ...
    {
    public:
        typedef typename R::value_type value_type;
    
        Linq(const R & r)
            : r(r)
        {
        }
    
        bool empty()          { return r.empty();    }
        value_type popFront() { return r.popFront(); }
        value_type popBack()  { return r.popBack();  }
        value_type front()    { return r.front();    }
        value_type back()     { return r.back();     }
    
    public:
        R r;
    };


    Реверсирование порядка элементов


    Хотел отдельно остановиться на этой функции. Она примечательна тем, что уж очень мне хотелось прибить двойной реверс последовательности. Причём прибить не ошибкой компиляции, а по-хорошему. Код класса довольно прост:

    template<typename R>
    class ReverseRange
    {
    public:
        typedef typename R::value_type value_type; 
        
        ReverseRange(R r)
            : r(r) 
        {
        }
    
        bool empty()          { return r.empty();    }
        value_type popFront() { return r.popBack();  }
        value_type popBack()  { return r.popFront(); }
        value_type front()    { return r.back();     }
        value_type back()     { return r.front();    }
    
        template<typename R2>
        friend R2 reverse(ReverseRange<R2> r); // smart needed
    
    private:
        R r;
    };

    Всё в этом коде именно так, как вы ожидали: методы работающие с front и back — изменены на противоположные, но среди них затерялась дружественная функция. А Дружественная она затем, чтобы подлезть к приватному полю — оборачиваемому Range-у, вот собственно код этой функции:

    template<typename R>
    ReverseRange<R> reverse(R r)
    {
        return r;
    }
    
    // Unwrap for double-reverse case
    template<typename R>
    R reverse(ReverseRange<R> r)
    {
        return r.r; // smart
    }

    Да! Функция не одна — их целых две. Первая работает как должна — оборачивает Range нашим ReaverseRange-ем (тут происходит неявный вызов конструктора). Вторая же, наоборот разворачивает ReverseRange. Важно что это происходит на уровне компиляции, а не на этапе выполнения. Но это ещё не самое сложное — ад начался когда я попытался изобразить это в Mixin-е:

    template<template<typename> class TLinq, typename R>
    class ReverseRange_mixin
    {
    public:
        TLinq<ReverseRange<R> > reverse() const
        {
            return boolinq::reverse(((TLinq<R>*)this)->r);
        }
    };
    
    // Unwrap for double-reverse case
    template<template<typename> class TLinq, typename T>
    class ReverseRange_mixin<TLinq,ReverseRange<T> >
    {
    public:
        TLinq<T> reverse() const
        {
            return boolinq::reverse(((TLinq<ReverseRange<T> >*)this)->r);
        }
    };


    Опять же таки — первый Mixin не делает ничего необычного, а вот второй на стадии компиляции выявляет тип Linq<ReverseRange<XxxRange<...>>> и разворачивает его в Linq<XxxRange<...>>. Мозг сломал пока добился компилируемого кода.

    Как пользователю расширять библиотеку?


    Идея была в следующем, пусть создает свой волшебный Range-класс, затем создаёт Mixin-класс по образу и подобию других Mixin-ов. А после этого создаёт свой класс CustomLinq и использует его при создании начальной последовательности (отнаследоваться от Linq не получится, ибо его Mixin-ы будут оборачивать все не в CustomLinq, а в Linq):

    boolinq::from<CustomLinq>(arr)

    вместо:

    boolinq::from(arr)

    Ну и пользователь может обойтись без всего этого и вовсе не использовать точечную нотацию. Ведь можно написать код и так:

    using namespace boolinq;
    int sum = sum(select(where(from(arr), [](...){...}), [](...){...}));


    Тесты производительности


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

    1. Сгенерируем 100 млн псевдослучайных элементов:

    srand(0xDEADBEEF);
    std::vector<int> vec(100000000, 0);
    
    for (unsigned i = 0; i < vec.size(); i++)
        vec[i] = rand();

    2. Напишем алгоритм на языке C++

    // Находим среднее значение нечётных элементов
    double sum = 0;
    int count = 0;
    for (unsigned i = 0; i < vec.size(); i++)
    {
        if (vec[i] % 2 == 1)
        {
            sum += vec[i];
            count++;
        }
    }
    double avgValue = sum / count;
    
    // Считаем среднеквадратичное отклонение нечетных элементов от avgValue
    double disperSum = 0;
    for (unsigned i = 0; i < vec.size(); i++)
        if (vec[i] % 2 == 1)
            disperSum += (vec[i] - avgValue)*(vec[i] - avgValue);
    double disper = disperSum / count;
    

    3. Напишем алгоритм на boolinq

    // Находим среднее значение нечётных элементов
    double avgValue = from(vec).where( [](int a){return a%2 == 1;})
                               .cast<double>()
                               .avg();
    
    // Считаем среднеквадратичное отклонение нечетных элементов от avgValue
    double disper = from(vec).where(  [](int a){return a%2 == 1;})
                             .select([=](int a){return (a-avgValue)*(a-avgValue);})
                             .cast<double>()
                             .avg();

    Не смотрите, что в коде на C++ не используются итераторы. Код с итераторами я написал, но позвольте не выкладывать его — он абсолютно аналогичный. Теперь скомпилируем в релизе в MS Visual C++ 2010 и запустим на моей машине…
    Код на C++ 1207 ms
    Код на C++ с итераторами 1224 ms
    Код на boolinq 1564 ms

    Boolinq, конечно, немного (на треть) проигрывает — но опять же таки зависит от задач. По идее нужно все методы тестировать отдельно. Кстати, .NET LINQ проигрывает аналогу на циклах гораздо-гораздо сильнее.

    В ближайшем будущем планируется добавить классу Linq методы .begin() и .end() для обратной совместимости с STL.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 17

      +14
      Даёшь неделю C++ на Хабре!
        +1
        Фишка с reverse мне понравилась. FP-style 8)
        • НЛО прилетело и опубликовало эту надпись здесь
            +1
            Думаете ему бы понравилось?)
            • НЛО прилетело и опубликовало эту надпись здесь
                +2
                Он работает С++-программистом в фейсбуке. Так что перешел, если только духовно, да и то, похоже возращается.
            +1
            Цитата:
            [ тут идет код итерирующий range «от» и «до»]
            Есть один минус у STL-итераторов не заметный на первый взгляд, итераторы Java этого минуса лишены.
            [тут идет код итерирующий от «начала» до «конца»]

            не чувствуете разницу? :) подсказка:
            std::accumulate( begin(), advance( begin(), size()/2 ) );
              +1
              Take/Skip?
                0
                то есть менять алгоритм вместо смены диапазона? :)
                  0
                  Нет. Функции Take/Skip позволяют отбросить с начала и с конца записи.
                    0
                    Можно сделать так:

                    boolinq::from(vec.begin(), vec.begin() + vec.size()/2).where(...) ....
                    
              +1
              Все гениально — просто!
              *(вот теперь я понимаю, почему мой код называют сложным)
                +2
                Ценю Вашу работу. Активно использую LINQ в C# и разного рода itertools/filter/map/reduce/any/генераторы списков в Python. Очень неплохо иметь похожие механизмы в С++.
                  +1
                  Автор крут. rly.
                    +2
                    На вашем месте я бы все-таки не использовал неявные конструкторы преобразования типов там, где это явно не требуется.

                    Например, зачем вам неявный разворот последовательности, если для этой цели предполагается использовать явную функцию reverse?

                    Кроме того, ваши диапазоны (***Range) невозможно нормально передать в функцию, поскольку их тип постоянно меняется (а писать всюду шаблоны — тоже не лучший выход). Хотелось бы полиморфную обертку к ним.
                      +2
                      Тогда это уже не шаблонная библиотека получится… И скорость заметно упадёт.
                        0
                        Я же не говорю, что подобное будет применяться повсеместно! Когда можно обойтись шаблонами — останутся шаблоны.

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

                    Самое читаемое