адаптеры

@AzaKendler · Регистрация: 30.05.2011

Author24 — интернет-сервис помощи студентам

добрый вечер интересно ваше мнение.
такие вещи как адаптеры, биндеры позиционируются как шибко быстро работающие.
и рекомендуется ими активно пользоваться. Например вместо попыток определить собственную шаблон-функцию сравнения, которая сравнивает входное значение с неким фиксированным значением, рекомендуется юзать биндер, который сделает нам из функции less принимающей 2 параметра для сравнения, функтор принимающий одно значение. Все это делается через создание шаблонных структур ну или классов в которых один из параметров less становится членом, и имеется небезызвестный operator()() который и используют стандартные алгоритмы, когда мы даем на вход сий класс.
Так вот поделитесь мнением, действительно ли через биндеры это шибко быстрее, чем через просто функцию, на ваш взгляд? В процессе работы алгоритма ну например форич, при такой схеме во первых вызывается конструктор столько раз сколько элементов надо пройти, вызывается деструктор столько же раз, ну и вызывается сам operator()(). Это работает действительно быстрее, чем просто вызов какой либо своей функции? Как считаете?

@AzaKendler · 05.11.2011, 13:36 **[ТС]**

Сообщение от rangerx

Повторюсь, "редактор связей" не участвует в работе функции-алгоритма, в ней участвует функтор, cледовательно сравнивать можно только функтор и функцию.

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

Добавлено через 3 минуты

Сообщение от rangerx

Это так сложно проверить(чтобы убедиться, что это не так)?

наверно где то я допустил ошибку. и это интересно. посмотри пожалуйста на приложенные выше картинки - от чего зависит сколько раз вызывается конструктор и деструктор временного объекта. или на твой взгляд объект не временный?
обладают ли временные объекты из стл "особыми" свойствами?

Добавлено через 5 минут

Сообщение от ValeryLaptev

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

согласен - надо брать огромные выборки. но напрашивается вопрос. тенденция с увеличением количества элементов должна будет поменяться? т.е. например на малых объемах выигрывает лямбда или простая функция - увеличиваем на миллионы и...ого го - адаптеры рулят? Это так?
Это важный момент и если есть возможность то хотелось бы увидеть результат тестов тут с теми же что показали парни

@ValeryLaptev · 05.11.2011, 14:16

Сообщение от AzaKendler

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

И инстанцирование шаблона, и редактирование связей работают на этапе создания программы, а не на этапе выполнения.
А вот создание временного объекта - на этапе выполнения.

По поводу малых-больших размеров контейнеров. Прямая аналогия с написанием процедуры. Если процедура вызывается один раз, то смысла ее писать нет. Выгоды от процедуры возникают только тогда, когда она написана один раз, а вызывается много раз.
Другая аналогия: применение двоичного поиска.
При линейном поиске выполняется в среднем n/2 сравнений; при двоичном поиске - log(n) сравнений. Но для применения двоичного поиска надо массив отсортировать., что требует n*log(n) операций. Тогда возникает задача: при каких n выгоден двоичный поиск.
Для этого надо решить неравенство:
k*n/2 > nlog(n) + k*log(n)
чтобы выяснить, при каких k (количество поисков) и n (размер массива) количество операций линейного поиска начинает превышать количество операций при двоичном поиске.

@ForEveR · 05.11.2011, 14:26

C++

#include <algorithm>
#include <vector>
#include <functional>
 
bool more_then_7(int value)
{
        return value > 7;
}
 
int main()
{
        std::vector<int> v(1000000);
        const size_t size = v.size();
        for (size_t i=0;i<size;++i)
        {
#ifdef LAMBDA
                std::find_if(v.begin(), v.end(), [](const int value) {return value > 7;});
#else
                std::find_if(v.begin(), v.end(), more_then_7);
#endif
        }
}

Bash

forever@lavroffff:~/Programs$ g++ -O3 -o map_test map_test.cpp -std=c++0x && time ./map_test 
 
real    0m0.019s
user    0m0.000s
sys 0m0.004s
forever@lavroffff:~/Programs$ g++ -O3 -DLAMBDA -o map_test map_test.cpp -std=c++0x && time ./map_test 
 
real    0m0.010s
user    0m0.000s
sys 0m0.004s

Тесты показывают примерно одинаково.

@Mr.X · 05.11.2011, 14:28

Сообщение от rangerx

Сообщение от AzaKendler

Я предполагаю что конструктор вызывается чтолько раз сколько объектов контейнера надо обойти, соответственно столько же раз вызовется деструктор и оператор ()()

Это так сложно проверить(чтобы убедиться, что это не так)?

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

@AzaKendler · 05.11.2011, 17:02 **[ТС]**

Сообщение от ValeryLaptev

И инстанцирование шаблона, и редактирование связей работают на этапе создания программы, а не на этапе выполнения.
А вот создание временного объекта - на этапе выполнения.

собственно нигде и не было сказано нечто противоречащее этой истине.

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

Добавлено через 4 минуты

Сообщение от Mr.X

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

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

C++

template <class BO> class Binder: public unary_function <typename BO::first_argument_type,typename BO::result_type>
 {
 
     BO b;
     typename BO::second_argument_type A2;
 public:
 
  ~Binder(){};
 Binder(const BO& rb,const typename BO::second_argument_type& a2):b(rb),A2(a2){};
 
 result_type operator ()(const argument_type& x)const {return b(x,A2); } //+вызов less
 
 };
 
 
 template <class BO,class T> Binder<BO> construct (const BO& op, const T& v)
 {
 
     return Binder<BO>(op,v);
 };

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

Добавлено через 15 минут
спасибо за ответы всем. Думаю и так понятно что СТЛ рулит, просто хотелось учтонить. Думаю вопрос закрыт

@ForEveR · 05.11.2011, 17:10

AzaKendler, Рулит буст.

@alex_x_x · 05.11.2011, 20:33

на самом деле уверенность, что программа с функторами будет работать быстрее, чем с обычными функциями напоминает рассуждения c#'ков о том, что управляемый код может выполняться быстрее нативного
тем не менее все функторы не более чем попытка имитировать работу функций высшего порядка функциональных языков. и попытка не самая удачная
только с лямбдами алгоритмы наконец стали действительно удобными

@rangerx · 05.11.2011, 21:20

Сообщение от AzaKendler

если я правильно понял - то что называется редактором связи не вызывается каждый раз при создании объекта? объект создается сам?

Редактор связей(например, std::bind2nd) НЕ вызывается при создании объекта, он сам создаёт объект(например, std::binder2nd), который можно использовать в качестве функтора в функции-алгоритме.

Сообщение от AzaKendler

Интересно узнать почему ее работу не надо учитывать?

Потому что она не участвует в том, что происходит внутри функции-алгоритма. Можно даже сделать так

C++

1 2	std::binder2nd< std::greater<int> > more_than_7 = std::bind2nd(std::greater<int>(), 7); std::find_if(v.begin(), v.end(), more_than_7); // more_than_7 функциональный объект

ничего от этого особо не изменится.

Сообщение от AzaKendler

в каждом проходе по элементу вектора работает связка - биндер-конструктор-функтор-деструктор.

Только operator(), который скорее всего будет встроен, т.е. вообще не будет вызываться!(читай про inline функции)

Сообщение от AzaKendler

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

Этот вопрос не отсносится к STL вообще, и к обсуждаемой теме в частности. Почитай про то как передаются объекты в функцию.

Сообщение от AzaKendler

обладают ли временные объекты из стл "особыми" свойствами?

Я не знаю такого термина, как "временные объекты из стл".

Добавлено через 14 минут
alex_x_x, по поводу вышеприведённых тестов. У меня вариант с использованием функтора на gcc 4.1.2 с ключём -O3 работает в два раза быстрее, чем указатель на функцию(что собственно и не удивительно). Почему у вас получается наоборот для меня загадка. Честно говоря я не особо удивлюсь, если выяснится, что встраивание в приведённых выше тестах, по той или иной причине, вообще не производилось, т.е. вызывался напрямую operator().

@alex_x_x · 05.11.2011, 21:25

Сообщение от rangerx

У меня вариант с использованием функтора на gcc 4.1.2 с ключём -O3 работает в два раза быстрее, чем указатель на функцию(что собственно и не удивительно)

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

@AzaKendler · 05.11.2011, 23:01 **[ТС]**

rangerx, прокомментируй пожалуйста тот кусок кода который я вставил. вызовы идут в том порядке о котором я говорим. при сборке из шаблона генерится биндер с нужными типами и далее по списку его класс и далее лесс. при запуске вызыватся биндер, который создает класс, соответственно вызывается конструктор класса. далее ты прав работает только функтор - алгоритм использует оператор ()() для своих нужд в котором вызывается еще и лесс. после того как это отработало, и лесс а затем и оператор ()() вернул фальс, вызвается деструктор класса и алгоритм переходит к следующему элементу вектора. И все повторяется. В дебаге наблюдается именно такая последовательность. Растолкуй непонимающему, каким чудесным образом будет реализовано встраивание, и встраивание чего? биндера? так он в любом случае сгенерит временный объект с оператором()(). Про временные объекты стл - это я так намекал, что неужто если я использую стл - поведение временных объектов будет чем то отличаться? т.е. конструкторы не вызываются, деструкторы тоже.

@AzaKendler · 05.11.2011, 23:36 **[ТС]**

Я немножко наврал. все деструкторы будут вызваны в конце. ровно по количеству созданных временных объектов.
На последней картиночке простой тест. найти значение меньше 7, работает справно выводит шастерку.
на первых трех картиночках показано что вызывается. И вызывается это столько раз, сколько нужно чтобы найти шестерочку. конструкторы не пометил - это и так очевидно.

Видимо это из за дебага такие шаги? И если будет собран релиз, то все будет оптимизировано...и?
в алгоритм в место вызова встроится код функтора из класса и все? ну или сам класс. так чтоли?

@AzaKendler · 05.11.2011, 23:47 **[ТС]**

не совсем понятно.

@alex_x_x · 05.11.2011, 23:55

Не по теме:

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

@rangerx · 06.11.2011, 14:13

Сообщение от alex_x_x

при чем собственно указатель на функцию

При том, что функции-алгоритмы принимают указатель на функцию. Если идёт обращение к функции через указатель, то она не может быть встроенной по определению, потому как у inline функций нет адресов(это вообще не функции в привычном пониманиии этого слова). Если есть обращение через указетель, то есть и реальная функция(не встроенная). Хотя, Майерс в книге "Эффективное использовании STL" пишет, что в принципе такие оптимизации, о которых ты говоришь всё же возможны, но на практике такое встретить практически нереально. А вот operator() будет встроен гарантированно. Поэтому функторы использовать эффективнее(по крайней мере на большинстве компиляторов), о чём собственно и написанно у тех же Страуструпа, Майерса...

@alex_x_x · 06.11.2011, 14:32

не вижу чем встраивание оператора функционального объекта может быть проще встраивания тела функции - это не соответствует логике
без общих слов и ссылок на авторитетов
на моей машине gcc показывает обратный результат

@~~LosAngeles~~ · 06.11.2011, 14:41

на хабре уже проверяли с O3 разницы нет между функциями и функторами

@ValeryLaptev 1069 / 848 / 60 Регистрация: 30.04.2011 Сообщений: 1,659
	05.11.2011, 14:16	22
	Сообщение от AzaKendler если я правильно понял - то что называется редактором связи не вызывается каждый раз при создании объекта? объект создается сам? Страуструп расписал что биндер - это функция-шаблон, за которой спрятан еще и класс шаблон который она создает, и который содержит тот самый функтор используемый алгоритмами. Накропав и запустив - наблюдал именно такой эффект редактор связей, ивашка, фишка - как ее не назови - она инстанцирует шаблон класса и генерит его временный экземпляр. Интересно узнать почему ее работу не надо учитывать? в каждом проходе по элементу вектора работает связка - биндер-конструктор-функтор-деструктор. это мы и сравнивали с простой функцией ну и с лямбдой. Если я ошибаюсь - буду рад изменить мнение на более точное И инстанцирование шаблона, и редактирование связей работают на этапе создания программы, а не на этапе выполнения. А вот создание временного объекта - на этапе выполнения. По поводу малых-больших размеров контейнеров. Прямая аналогия с написанием процедуры. Если процедура вызывается один раз, то смысла ее писать нет. Выгоды от процедуры возникают только тогда, когда она написана один раз, а вызывается много раз. Другая аналогия: применение двоичного поиска. При линейном поиске выполняется в среднем n/2 сравнений; при двоичном поиске - log(n) сравнений. Но для применения двоичного поиска надо массив отсортировать., что требует nlog(n) операций. Тогда возникает задача: при каких n выгоден двоичный поиск. Для этого надо решить неравенство: kn/2 > nlog(n) + k*log(n) чтобы выяснить, при каких k (количество поисков) и n (размер массива) количество операций линейного поиска начинает превышать количество операций при двоичном поиске. 1

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	05.11.2011, 20:33	27
	на самом деле уверенность, что программа с функторами будет работать быстрее, чем с обычными функциями напоминает рассуждения c#'ков о том, что управляемый код может выполняться быстрее нативного тем не менее все функторы не более чем попытка имитировать работу функций высшего порядка функциональных языков. и попытка не самая удачная только с лямбдами алгоритмы наконец стали действительно удобными 0

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	05.11.2011, 21:25	29
	Сообщение от rangerx У меня вариант с использованием функтора на gcc 4.1.2 с ключём -O3 работает в два раза быстрее, чем указатель на функцию(что собственно и не удивительно) при чем собственно указатель на функцию на момент компиляции кода компилятор четко знает какая функция будет передана алгоритму - соответсвенно вполне жестко может ее инлайнить в алгоритм функтор может выигрывать, только если непосредственно операция сравнения в нем както дико оптимизирована, что маловероятно 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772
	05.11.2011, 23:36 [ТС]	31
	Я немножко наврал. все деструкторы будут вызваны в конце. ровно по количеству созданных временных объектов. На последней картиночке простой тест. найти значение меньше 7, работает справно выводит шастерку. на первых трех картиночках показано что вызывается. И вызывается это столько раз, сколько нужно чтобы найти шестерочку. конструкторы не пометил - это и так очевидно. Видимо это из за дебага такие шаги? И если будет собран релиз, то все будет оптимизировано...и? в алгоритм в место вызова встроится код функтора из класса и все? ну или сам класс. так чтоли? Миниатюры 0

@rangerx 2022 / 1621 / 489 Регистрация: 31.05.2009 Сообщений: 3,005
	06.11.2011, 14:13	34
	Сообщение от alex_x_x при чем собственно указатель на функцию При том, что функции-алгоритмы принимают указатель на функцию. Если идёт обращение к функции через указатель, то она не может быть встроенной по определению, потому как у inline функций нет адресов(это вообще не функции в привычном пониманиии этого слова). Если есть обращение через указетель, то есть и реальная функция(не встроенная). Хотя, Майерс в книге "Эффективное использовании STL" пишет, что в принципе такие оптимизации, о которых ты говоришь всё же возможны, но на практике такое встретить практически нереально. А вот operator() будет встроен гарантированно. Поэтому функторы использовать эффективнее(по крайней мере на большинстве компиляторов), о чём собственно и написанно у тех же Страуструпа, Майерса... 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772
		1
	адаптеры 04.11.2011, 20:03. Показов 4324. Ответов 35 Метки нет (Все метки) добрый вечер интересно ваше мнение. такие вещи как адаптеры, биндеры позиционируются как шибко быстро работающие. и рекомендуется ими активно пользоваться. Например вместо попыток определить собственную шаблон-функцию сравнения, которая сравнивает входное значение с неким фиксированным значением, рекомендуется юзать биндер, который сделает нам из функции less принимающей 2 параметра для сравнения, функтор принимающий одно значение. Все это делается через создание шаблонных структур ну или классов в которых один из параметров less становится членом, и имеется небезызвестный operator()() который и используют стандартные алгоритмы, когда мы даем на вход сий класс. Так вот поделитесь мнением, действительно ли через биндеры это шибко быстрее, чем через просто функцию, на ваш взгляд? В процессе работы алгоритма ну например форич, при такой схеме во первых вызывается конструктор столько раз сколько элементов надо пройти, вызывается деструктор столько же раз, ну и вызывается сам operator()(). Это работает действительно быстрее, чем просто вызов какой либо своей функции? Как считаете? 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772
	05.11.2011, 13:36 [ТС]	21
	Сообщение от rangerx Повторюсь, "редактор связей" не участвует в работе функции-алгоритма, в ней участвует функтор, cледовательно сравнивать можно только функтор и функцию. если я правильно понял - то что называется редактором связи не вызывается каждый раз при создании объекта? объект создается сам? Страуструп расписал что биндер - это функция-шаблон, за которой спрятан еще и класс шаблон который она создает, и который содержит тот самый функтор используемый алгоритмами. Накропав и запустив - наблюдал именно такой эффект редактор связей, ивашка, фишка - как ее не назови - она инстанцирует шаблон класса и генерит его временный экземпляр. Интересно узнать почему ее работу не надо учитывать? в каждом проходе по элементу вектора работает связка - биндер-конструктор-функтор-деструктор. это мы и сравнивали с простой функцией ну и с лямбдой. Если я ошибаюсь - буду рад изменить мнение на более точное Добавлено через 3 минуты Сообщение от rangerx Это так сложно проверить(чтобы убедиться, что это не так)? наверно где то я допустил ошибку. и это интересно. посмотри пожалуйста на приложенные выше картинки - от чего зависит сколько раз вызывается конструктор и деструктор временного объекта. или на твой взгляд объект не временный? обладают ли временные объекты из стл "особыми" свойствами? Добавлено через 5 минут Сообщение от ValeryLaptev Об эффективности использования, что и пытаются доказать измерениями. Поэтому и нужно проверить на много миллионных массивах... согласен - надо брать огромные выборки. но напрашивается вопрос. тенденция с увеличением количества элементов должна будет поменяться? т.е. например на малых объемах выигрывает лямбда или простая функция - увеличиваем на миллионы и...ого го - адаптеры рулят? Это так? Это важный момент и если есть возможность то хотелось бы увидеть результат тестов тут с теми же что показали парни 0

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	05.11.2011, 14:28	24
	Сообщение от rangerx Сообщение от AzaKendler Я предполагаю что конструктор вызывается чтолько раз сколько объектов контейнера надо обойти, соответственно столько же раз вызовется деструктор и оператор ()() Это так сложно проверить(чтобы убедиться, что это не так)? Ну а если поизучать алгоритм for_each, то можно заметить, что он возвращает функтор, оператор () которого вызывался для всех обойденных объектов, и в котором за время обхода могла накопиться нужная пользователю информация. 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	05.11.2011, 17:10	26
	AzaKendler, Рулит буст. 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772
	05.11.2011, 23:01 [ТС]	30
	rangerx, прокомментируй пожалуйста тот кусок кода который я вставил. вызовы идут в том порядке о котором я говорим. при сборке из шаблона генерится биндер с нужными типами и далее по списку его класс и далее лесс. при запуске вызыватся биндер, который создает класс, соответственно вызывается конструктор класса. далее ты прав работает только функтор - алгоритм использует оператор ()() для своих нужд в котором вызывается еще и лесс. после того как это отработало, и лесс а затем и оператор ()() вернул фальс, вызвается деструктор класса и алгоритм переходит к следующему элементу вектора. И все повторяется. В дебаге наблюдается именно такая последовательность. Растолкуй непонимающему, каким чудесным образом будет реализовано встраивание, и встраивание чего? биндера? так он в любом случае сгенерит временный объект с оператором()(). Про временные объекты стл - это я так намекал, что неужто если я использую стл - поведение временных объектов будет чем то отличаться? т.е. конструкторы не вызываются, деструкторы тоже. 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772
	05.11.2011, 23:47 [ТС]	32
	не совсем понятно. 0

@alex_x_x
	05.11.2011, 23:55 #33
	Не по теме: хороший вопрос, тут надо хорошо разбираться в компиляторной оптимизации, чтобы ответить по сущетсву, без общих слов 0

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	06.11.2011, 14:32	35
	не вижу чем встраивание оператора функционального объекта может быть проще встраивания тела функции - это не соответствует логике без общих слов и ссылок на авторитетов на моей машине gcc показывает обратный результат 0

@~~LosAngeles~~ Заблокирован
	06.11.2011, 14:41	36
	на хабре уже проверяли с O3 разницы нет между функциями и функторами 0