Статья для тех, кому интересна реализация библиотеки boolinq из предыдущего моего поста. В этой статье я копну в исходники и покажу несколько интересных приёмов, которые позволили сделать библиотеку «ленивой» и расширяемой.
Прежде чем мы посмотрим в код библиотеки, хотелось бы обратить ваше внимание на STL. Это стандартная библиотека шаблонов, содержит контейнеры, алгоритмы и т.д. Одним из самых интересных элементов библиотеки является сущность — итератор. Итераторы были придуманы для того чтобы быть прослойкой между контейнерами и алгоритмами. Чтобы любой алгоритм можно было применить к любому контейнеру (ну почти любые).
На первый взгляд — всё хорошо. Алгоритмы и контейнеры связаны через промежуточную сущность — итератор. Но это только на первый взгляд, если присмотреться к коду:
Есть один минус у STL-итераторов не заметный на первый взгляд, итераторы Java этого минуса лишены.
Да, это
Таким образом мы имеем одну сущность, можем спросить её есть ли ещё элементы в последовательности, запросить элемент и запросить перейти к следующему элементу. На самом деле также не помешают методы
Ну а дальше не трудно догадаться как выглядят все классы библиотеки — это обертки над таким Range-ем. Например WhereRange выглядит так:
В двух словах: класс принимает в конструктор другой Range, из которого ему предстоит брать элементы, и предикат, определяющий принадлежность каждого из элементов к результирующей выборке. Имеются 2 переменных, определяющих найдено ли значение «с начала» и «с конца» Range-а. Функции seekFront() и seekBack() непосредственно занимаются поиском следующего front-а и следующего back-а.
Собственно все другие Range-и выглядят похожим образом. Следующей проблемой стало, свести использование к точечной нотации…
С одной стороны хотелось сделать использование методов также как они используются в .NET LINQ, но ведь в C++ нет Extension Methods как в C#:
С другой стороны хотелось сделать библиотеку расширяемой… и тут пришла такая мысль)) Сверху всех Range-ей будет обернут класс Linq, при вызове преобразующих последовательность методов — оборачиваться будет вложенный в Linq класс, а класс Linq так и будет оставаться сверху всех.
Каждому классу Range-а сделал по оборачивающему классу Mixin-у следующего вида:
Потом, отнаследовал класс Linq от всех необходимых Mixin-ов:
Хотел отдельно остановиться на этой функции. Она примечательна тем, что уж очень мне хотелось прибить двойной реверс последовательности. Причём прибить не ошибкой компиляции, а по-хорошему. Код класса довольно прост:
Всё в этом коде именно так, как вы ожидали: методы работающие с front и back — изменены на противоположные, но среди них затерялась дружественная функция. А Дружественная она затем, чтобы подлезть к приватному полю — оборачиваемому Range-у, вот собственно код этой функции:
Да! Функция не одна — их целых две. Первая работает как должна — оборачивает Range нашим ReaverseRange-ем (тут происходит неявный вызов конструктора). Вторая же, наоборот разворачивает ReverseRange. Важно что это происходит на уровне компиляции, а не на этапе выполнения. Но это ещё не самое сложное — ад начался когда я попытался изобразить это в Mixin-е:
Опять же таки — первый Mixin не делает ничего необычного, а вот второй на стадии компиляции выявляет тип
Идея была в следующем, пусть создает свой волшебный Range-класс, затем создаёт Mixin-класс по образу и подобию других Mixin-ов. А после этого создаёт свой класс CustomLinq и использует его при создании начальной последовательности (отнаследоваться от Linq не получится, ибо его Mixin-ы будут оборачивать все не в CustomLinq, а в Linq):
вместо:
Ну и пользователь может обойтись без всего этого и вовсе не использовать точечную нотацию. Ведь можно написать код и так:
Проведу тест специально для интересующихся: будем считать дисперсию случайной величины. Сначала найдём среднее значение всех нечетных элементов вектора, затем посчитаем среднеквадратичное отклонение нечетных элементов от среднего.
1. Сгенерируем 100 млн псевдослучайных элементов:
2. Напишем алгоритм на языке C++
3. Напишем алгоритм на boolinq
Не смотрите, что в коде на C++ не используются итераторы. Код с итераторами я написал, но позвольте не выкладывать его — он абсолютно аналогичный. Теперь скомпилируем в релизе в MS Visual C++ 2010 и запустим на моей машине…
Boolinq, конечно, немного (на треть) проигрывает — но опять же таки зависит от задач. По идее нужно все методы тестировать отдельно. Кстати, .NET LINQ проигрывает аналогу на циклах гораздо-гораздо сильнее.
В ближайшем будущем планируется добавить классу Linq методы
Что не так с итераторами?
Прежде чем мы посмотрим в код библиотеки, хотелось бы обратить ваше внимание на 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.