Comments 44
А оптимизация никак не может на этот рейт влиять?
0
У меня на тестах, при оптимизации O1 и O3 результаты по rate одинаковые. Параметры передаются по значению и скорее всего компилятор не может с этим ничего поделать.
0
Почему-то так я и подумал. Спасибо!
0
Компилятор не может с этим ничего поделать, поскольку у вас в конструкторах/деструкторах код, который влияет на результат вычислений (программы). Пустые конструкторы/деструкторы компилятор вполне мог бы вырезать. Надо объектный код смотреть.
+7
rate зависит от степени отсортированности массива, это видно, если наполнять массив разными данными.
Я, честно говоря, ожидал увидеть логарифмическую зависимость, но пока её наблюдать не приходится.
UPD: Заполнил массив как
Я, честно говоря, ожидал увидеть логарифмическую зависимость, но пока её наблюдать не приходится.
Код
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
class Compare
{
public:
static int num;
Compare()
{
num++;
}
Compare(const Compare& compare)
{
num++;
}
~Compare()
{
}
bool operator() (int v1, int v2)
{
return v1 < v2;
}
};
int Compare::num = 0;
int main()
{
vector<int> mas;
for(int step = 1; step <= 3; ++step){
cout << "---- step " << step << endl;
for(int size = 1; size < 1e7; size *= 2){
mas.resize(size);
for( int k = 0; k < size; k++ ) mas[k] = rand();
Compare::num = 0;
sort( mas.begin(), mas.end(), Compare() );
cout << setw(7) << size << setw(7) << setprecision(4) << ((float)Compare::num/(float)size) << endl;
}
}
return 0;
}
Результат выполнения: размер массива - rate
>g++ habrasort.cpp -o habrasort && habrasort
---- step 1
1 4
2 2
4 1
8 1
16 1.125
32 1.313
64 1.422
128 1.422
256 1.477
512 1.441
1024 1.431
2048 1.452
4096 1.448
8192 1.456
16384 1.451
32768 1.442
65536 1.437
131072 1.428
262144 1.413
524288 1.39
1048576 1.38
2097152 1.367
4194304 1.362
8388608 1.359
---- step 2
1 4
2 2.5
4 1.5
8 1.125
16 0.9375
32 1.25
64 1.391
128 1.469
256 1.406
512 1.443
1024 1.454
2048 1.444
4096 1.45
8192 1.46
16384 1.456
32768 1.449
65536 1.438
131072 1.434
262144 1.412
524288 1.39
1048576 1.38
2097152 1.368
4194304 1.362
8388608 1.359
---- step 3
1 4
2 2
4 1.5
8 1.375
16 1.063
32 1.219
64 1.359
128 1.391
256 1.395
512 1.486
1024 1.449
2048 1.462
4096 1.446
8192 1.465
16384 1.448
32768 1.443
65536 1.438
131072 1.428
262144 1.413
524288 1.39
1048576 1.381
2097152 1.367
4194304 1.362
8388608 1.359
>g++ habrasort.cpp -o habrasort -O3 && habrasort
---- step 1
1 4
2 2
4 1
8 1
16 1.125
32 1.313
64 1.422
128 1.422
256 1.477
512 1.441
1024 1.431
2048 1.452
4096 1.448
8192 1.456
16384 1.451
32768 1.442
65536 1.437
131072 1.428
262144 1.413
524288 1.39
1048576 1.38
2097152 1.367
4194304 1.362
8388608 1.359
---- step 2
1 4
2 2.5
4 1.5
8 1.125
16 0.9375
32 1.25
64 1.391
128 1.469
256 1.406
512 1.443
1024 1.454
2048 1.444
4096 1.45
8192 1.46
16384 1.456
32768 1.449
65536 1.438
131072 1.434
262144 1.412
524288 1.39
1048576 1.38
2097152 1.368
4194304 1.362
8388608 1.359
---- step 3
1 4
2 2
4 1.5
8 1.375
16 1.063
32 1.219
64 1.359
128 1.391
256 1.395
512 1.486
1024 1.449
2048 1.462
4096 1.446
8192 1.465
16384 1.448
32768 1.443
65536 1.438
131072 1.428
262144 1.413
524288 1.39
1048576 1.381
2097152 1.367
4194304 1.362
8388608 1.359
UPD: Заполнил массив как
for( int k = 0; k < size; k++ ) mas[k] = 1e7 - k;
— получил число, стремящееся к 5.0
Кстати, 1.359*2 = 2.718. Я тоже сначала думал о логарифмической зависимости, но получалось константа. Возможно, тут получается сумма какого-то рада из логарифмов, значение которого e/2.
0
К UPD про rate=5. Сложность алгоритма sort в среднем O(N*logN), а в худшем случае O(N^2). Тут похоже эффект от «плохого» массива.
0
Запустил ваш код в 2013 студии с полной оптимизацией.
Результат
---- step 1 1 2 2 2 4 1 8 0.5 16 0.25 32 0.125 64 0.4375 128 0.3594 256 0.3438 512 0.3652 1024 0.373 2048 0.3711 4096 0.4006 8192 0.3885 16384 0.3855 32768 0.3741 65536 0.3645 131072 0.3445 262144 0.3098 524288 0.2511 1048576 0.1682 2097152 0.1093 4194304 0.05469 8388608 0.02734 ---- step 2 1 2 2 2 4 1 8 0.5 16 0.25 32 0.125 64 0.2969 128 0.3359 256 0.3906 512 0.3789 1024 0.3701 2048 0.3916 4096 0.3936 8192 0.3824 16384 0.3782 32768 0.3759 65536 0.3668 131072 0.3447 262144 0.3085 524288 0.2512 1048576 0.1682 2097152 0.1093 4194304 0.05469 8388608 0.02734 ---- step 3 1 2 2 2 4 1 8 0.5 16 0.25 32 0.125 64 0.2969 128 0.3828 256 0.4375 512 0.3652 1024 0.373 2048 0.396 4096 0.395 8192 0.385 16384 0.3817 32768 0.3804 65536 0.3666 131072 0.3458 262144 0.3095 524288 0.2514 1048576 0.168 2097152 0.1093 4194304 0.05469 8388608 0.02734
0
У меня нет под рукой VS 2013. Попробуйте заменить rand() на rand()*32768+rand().
0
Заменил, вот результат:
Скорее всего это связано с тем что в С++ 11 поменяли реализацию, об этом указано на en.cppreference.com/w/cpp/algorithm/sort
а именно:
Complexity
until C++11: O(N·log(N)), where N = std::distance(first, last) comparisons on average.
since C++11: O(N·log(N)), where N = std::distance(first, last) comparisons.
Результат с rand()*32768+rand()
---- step 1 1 2 2 2 4 1 8 0.5 16 0.25 32 0.125 64 0.3438 128 0.4531 256 0.4141 512 0.3535 1024 0.3877 2048 0.3799 4096 0.3833 8192 0.3851 16384 0.383 32768 0.3881 65536 0.3911 131072 0.3884 262144 0.3914 524288 0.3899 1048576 0.3899 2097152 0.3896 4194304 0.3901 8388608 0.3901 ---- step 2 1 2 2 2 4 1 8 0.5 16 0.25 32 0.125 64 0.2969 128 0.3359 256 0.3555 512 0.377 1024 0.4082 2048 0.3843 4096 0.3877 8192 0.3982 16384 0.3973 32768 0.39 65536 0.3889 131072 0.3894 262144 0.3907 524288 0.3897 1048576 0.3899 2097152 0.3902 4194304 0.3901 8388608 0.3899 ---- step 3 1 2 2 2 4 1 8 0.5 16 0.25 32 0.125 64 0.3438 128 0.3594 256 0.3438 512 0.3945 1024 0.376 2048 0.3828 4096 0.396 8192 0.3813 16384 0.389 32768 0.3897 65536 0.3906 131072 0.3906 262144 0.3899 524288 0.3908 1048576 0.3903 2097152 0.3904 4194304 0.3897 8388608 0.3899
Скорее всего это связано с тем что в С++ 11 поменяли реализацию, об этом указано на en.cppreference.com/w/cpp/algorithm/sort
а именно:
Complexity
until C++11: O(N·log(N)), where N = std::distance(first, last) comparisons on average.
since C++11: O(N·log(N)), where N = std::distance(first, last) comparisons.
0
Интересно… Можно отличать по этому признаку компиляторы (до их первого обновления).
На данный момент в gcc 4.8.1 такие результаты (с флагом -std=c++11 не меняются):
(«около» — значит нельзя уверенно сказать, что значение к чему-то стремится)
Попробуйте для интереса тоже забить константу/возрастающую/убывающую последовательность.
На данный момент в gcc 4.8.1 такие результаты (с флагом -std=c++11 не меняются):
размер | rate | массив M
-------+------------+------------------------
1 | 4 | любой
>> 1 | 1.25 | M[i] == M[j]
>> 1 | 1.33 | M[i] < M[i+1]
>> 1 | 5 | M[i] > M[i+1]
>> 1 | около 1.39 | M[i] == i % 2 ? 10 : 11
>> 1 | около 1.34 | M[i] == i % 3 ? 10 : 11
(«около» — значит нельзя уверенно сказать, что значение к чему-то стремится)
Попробуйте для интереса тоже забить константу/возрастающую/убывающую последовательность.
0
>> for_each( mas.begin(), mas.end(), Print() );
Странно я всегда полагал что Print() создаcт анонимный объект, а при заходе в for_each произойдет его копирование. Это какой — то результат оптимизации, что с++ анонимные объекты передает принудительно по ссылке или стандарт?
Странно я всегда полагал что Print() создаcт анонимный объект, а при заходе в for_each произойдет его копирование. Это какой — то результат оптимизации, что с++ анонимные объекты передает принудительно по ссылке или стандарт?
0
А зачем создавать объект и делать его копирование, если он никому больше, как в самой функции, не нужен? Можно сразу там его один раз и создать.
0
Я могу согласиться что в этом нет смысла, но С++ не всегда делает то, что кажется нам разумным.
0
Это стандарт. Оптимизация copy elision. Работает только с анонимными объектами или при возвращении значений из функции. (http://en.cppreference.com/w/cpp/language/copy_elision)
+3
Во-первых, функторы — это из теории категорий. А то, что в статье описано — это функциональные объекты.
Во-вторых, в статье напрашивается рассмотреть move семантику и перемещающие конструкторы.
Ну и в-третьих, писать свои функциональные объекты — это довольно унылое занятие, когда есть bind и лямбды, а печать так вообще делается как
Во-вторых, в статье напрашивается рассмотреть move семантику и перемещающие конструкторы.
Ну и в-третьих, писать свои функциональные объекты — это довольно унылое занятие, когда есть bind и лямбды, а печать так вообще делается как
std::copy(mas.cbegin(), mas.cend(), std::ostream_iterator<int>(std::cout, " "));
+6
Согласен, но не хотелось затрагивать С++11. Думаю, начинающим надо давать материал постепенно и попроще. Такая запись
многих отпугнет.
std::ostream_iterator<int>(std::cout, " ")
многих отпугнет.
0
В рамках C++, «functors» — это таки вполне устоявшееся название, пусть и неудачное.
+1
К сожалению, «функтор» — чертовски перегруженное слово в русском языке.
В С++ ими традиционно обзывают классы с оператором (); не всякие функциональные объекты, а именно классы; потому что указатели на свободные функции, а также синтаксическое замыкание указателя на объект и указателя на функцию-член (ptr->*member), — не являются функторами.
Вслед за плюсами — функторами обзывают функциональные объекты и в других языках.
В теоркате — отображения категорий с определённой аксиоматикой (выполняется ковариантность)
В хаскелле — тайпкласс Functor — интерфейс, воспроизводящий теоркатовские функторы. Ну и реализации этого тайпкласса для параметризованных типов.
В окамле — параметризованные модули — отображения типов и модулей (по сути, категорий) вообще как бог на душу положит.
В С++ ими традиционно обзывают классы с оператором (); не всякие функциональные объекты, а именно классы; потому что указатели на свободные функции, а также синтаксическое замыкание указателя на объект и указателя на функцию-член (ptr->*member), — не являются функторами.
Вслед за плюсами — функторами обзывают функциональные объекты и в других языках.
В теоркате — отображения категорий с определённой аксиоматикой (выполняется ковариантность)
В хаскелле — тайпкласс Functor — интерфейс, воспроизводящий теоркатовские функторы. Ну и реализации этого тайпкласса для параметризованных типов.
В окамле — параметризованные модули — отображения типов и модулей (по сути, категорий) вообще как бог на душу положит.
0
Интересный момент про создание копий функторов, не знал об этом. Пишут что это проблема библиотечного хидера algorithm в целом. В принципе она зависит от имплементации (некоторые версии STL могут быть свободны от этого косяка), но в большинстве имплементаций создаются копии.
В общем случае проблема лечится использованием std::reference_wrapper
В общем случае проблема лечится использованием std::reference_wrapper
Compare sort_criterion;
sort( mas.begin(), mas.end(), std::cref(sort_criterion) );
0
А как в этом случае себя будут вести лямбда функции?
0
Надо полагать, что как указатели на функции, если ничего не захватывают из области видимости, откуда создаются; и как объекты с конструкторами по умолчанию в другом лсучае.
0
Во-первых, в C++ нет никаких лямбда-функций, есть лямбда-выраженин, и генерируемые из них замыкания.
Если лямбда выражение без захвата, то у типа-замыкания определён non-explicit оператор приведения к указателю на функцию с соответствующей сигнатурой.
Поскольку алгоритмы принимают действие с выводом типов, приведение к указателю на функцию в них происходить не может, происходит обычное копирование объекта, но поскольку он пустой, это в целом равносильно копированию указателя на функцию.
Если лямбда выражение без захвата, то у типа-замыкания определён non-explicit оператор приведения к указателю на функцию с соответствующей сигнатурой.
Поскольку алгоритмы принимают действие с выводом типов, приведение к указателю на функцию в них происходить не может, происходит обычное копирование объекта, но поскольку он пустой, это в целом равносильно копированию указателя на функцию.
+1
Помимо вышесказанного, за счёт встраивания копирования в результате вообще может не быть, и в этом можно убедиться, сравнив машинный код для обычного for по итератору, для range-based for и для std::for_each с замыканием.
Если бы это было не так, то алгоритмы вроде for_each никто бы не использовал из-за abstraction penalty.
Если бы это было не так, то алгоритмы вроде for_each никто бы не использовал из-за abstraction penalty.
0
Кстати, при использовани libc++ (это реализация стандартной библиотеки в Clang), rate получается очень маленьким.
0
Укажите компилятор, только из изучения комментариев понял что у вас vs2013. «починили» стандартную библиотеку? надо посмотреть в код, а то раньше там параметр шаблона не передавался по цепочке вложенному вызову, что приводило к забавным результатам
0
Попробуйте добавить
ПС: Я не проверял, просто гипотеза
const
это укажет компилятору что вызов метода не изменит передаваемый экземпляр функтора и копировать его нет необходимости, он ведь все равно не изменится :)void operator() (int value)
const
ПС: Я не проверял, просто гипотеза
0
Не работает, я проверял :)
0
Добавил const для случая с сортировкой — результат сохраняется как и у 0serg. Скорее всего компилятор и так понял нас правильно.
Для интереса решил дело усложнить, добавив в operator() счётчик его вызовов. Количество вызовов конструктора осталось прежним. Количество вызовов operator() — O(NlnN), ничего противоестественного не произошло.
Для интереса решил дело усложнить, добавив в operator() счётчик его вызовов. Количество вызовов конструктора осталось прежним. Количество вызовов operator() — O(NlnN), ничего противоестественного не произошло.
Графики
ctr_rate — вызовы конструктора на один элемент, cmp_rate — вызовы operator() на один элемент.
Сортировка убывающей последовательности:
Сортировка массива из нулей:
Сортировка случайного массива:
Сортировка убывающей последовательности:
Сортировка массива из нулей:
Сортировка случайного массива:
0
Из этой статьи, на примере for_each, я узнал, что в шаблон в качестве класса можно передавать функцию. Это всегда так было?
0
Нет, в качестве класса можно только передать класс-функтор, обычно у которого переопределён оператор (). Но в качестве параметра шаблона может быть не только класс, но и любое скалярное значение, включая функцию.
0
Точнее, указатель на неё.
0
Это одно и то же :)
#include <iostream>
using namespace std;
void foo()
{
std::cout << "bar\n";
}
int main() {
(*&**&**&*&****&*foo)();
return 0;
}
0
Действительно, параметром шаблона может быть функция, а не только указатель на неё. Не знал.
0
Sign up to leave a comment.
Небольшое исследование по использованию функторов в стандартной библиотеке STL С++