Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 44
А оптимизация никак не может на этот рейт влиять?
У меня на тестах, при оптимизации O1 и O3 результаты по rate одинаковые. Параметры передаются по значению и скорее всего компилятор не может с этим ничего поделать.
Почему-то так я и подумал. Спасибо!
Компилятор не может с этим ничего поделать, поскольку у вас в конструкторах/деструкторах код, который влияет на результат вычислений (программы). Пустые конструкторы/деструкторы компилятор вполне мог бы вырезать. Надо объектный код смотреть.
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.Кстати, 1.359*2 = 2.718. Я тоже сначала думал о логарифмической зависимости, но получалось константа. Возможно, тут получается сумма какого-то рада из логарифмов, значение которого e/2.
К UPD про rate=5. Сложность алгоритма sort в среднем O(N*logN), а в худшем случае O(N^2). Тут похоже эффект от «плохого» массива.
Запустил ваш код в 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
У меня нет под рукой VS 2013. Попробуйте заменить rand() на rand()*32768+rand().
Заменил, вот результат:
Скорее всего это связано с тем что в С++ 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.
Интересно… Можно отличать по этому признаку компиляторы (до их первого обновления).
На данный момент в 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
(«около» — значит нельзя уверенно сказать, что значение к чему-то стремится)
Попробуйте для интереса тоже забить константу/возрастающую/убывающую последовательность.
>> for_each( mas.begin(), mas.end(), Print() );
Странно я всегда полагал что Print() создаcт анонимный объект, а при заходе в for_each произойдет его копирование. Это какой — то результат оптимизации, что с++ анонимные объекты передает принудительно по ссылке или стандарт?
Странно я всегда полагал что Print() создаcт анонимный объект, а при заходе в for_each произойдет его копирование. Это какой — то результат оптимизации, что с++ анонимные объекты передает принудительно по ссылке или стандарт?
А зачем создавать объект и делать его копирование, если он никому больше, как в самой функции, не нужен? Можно сразу там его один раз и создать.
Я могу согласиться что в этом нет смысла, но С++ не всегда делает то, что кажется нам разумным.
Это стандарт. Оптимизация copy elision. Работает только с анонимными объектами или при возвращении значений из функции. (http://en.cppreference.com/w/cpp/language/copy_elision)
Во-первых, функторы — это из теории категорий. А то, что в статье описано — это функциональные объекты.
Во-вторых, в статье напрашивается рассмотреть move семантику и перемещающие конструкторы.
Ну и в-третьих, писать свои функциональные объекты — это довольно унылое занятие, когда есть bind и лямбды, а печать так вообще делается как
Во-вторых, в статье напрашивается рассмотреть move семантику и перемещающие конструкторы.
Ну и в-третьих, писать свои функциональные объекты — это довольно унылое занятие, когда есть bind и лямбды, а печать так вообще делается как
std::copy(mas.cbegin(), mas.cend(), std::ostream_iterator<int>(std::cout, " "));
Согласен, но не хотелось затрагивать С++11. Думаю, начинающим надо давать материал постепенно и попроще. Такая запись
многих отпугнет.
std::ostream_iterator<int>(std::cout, " ")
многих отпугнет.
В рамках C++, «functors» — это таки вполне устоявшееся название, пусть и неудачное.
К сожалению, «функтор» — чертовски перегруженное слово в русском языке.
В С++ ими традиционно обзывают классы с оператором (); не всякие функциональные объекты, а именно классы; потому что указатели на свободные функции, а также синтаксическое замыкание указателя на объект и указателя на функцию-член (ptr->*member), — не являются функторами.
Вслед за плюсами — функторами обзывают функциональные объекты и в других языках.
В теоркате — отображения категорий с определённой аксиоматикой (выполняется ковариантность)
В хаскелле — тайпкласс Functor — интерфейс, воспроизводящий теоркатовские функторы. Ну и реализации этого тайпкласса для параметризованных типов.
В окамле — параметризованные модули — отображения типов и модулей (по сути, категорий) вообще как бог на душу положит.
В С++ ими традиционно обзывают классы с оператором (); не всякие функциональные объекты, а именно классы; потому что указатели на свободные функции, а также синтаксическое замыкание указателя на объект и указателя на функцию-член (ptr->*member), — не являются функторами.
Вслед за плюсами — функторами обзывают функциональные объекты и в других языках.
В теоркате — отображения категорий с определённой аксиоматикой (выполняется ковариантность)
В хаскелле — тайпкласс Functor — интерфейс, воспроизводящий теоркатовские функторы. Ну и реализации этого тайпкласса для параметризованных типов.
В окамле — параметризованные модули — отображения типов и модулей (по сути, категорий) вообще как бог на душу положит.
Интересный момент про создание копий функторов, не знал об этом. Пишут что это проблема библиотечного хидера algorithm в целом. В принципе она зависит от имплементации (некоторые версии STL могут быть свободны от этого косяка), но в большинстве имплементаций создаются копии.
В общем случае проблема лечится использованием std::reference_wrapper
В общем случае проблема лечится использованием std::reference_wrapper
Compare sort_criterion;
sort( mas.begin(), mas.end(), std::cref(sort_criterion) );
А как в этом случае себя будут вести лямбда функции?
Надо полагать, что как указатели на функции, если ничего не захватывают из области видимости, откуда создаются; и как объекты с конструкторами по умолчанию в другом лсучае.
Во-первых, в C++ нет никаких лямбда-функций, есть лямбда-выраженин, и генерируемые из них замыкания.
Если лямбда выражение без захвата, то у типа-замыкания определён non-explicit оператор приведения к указателю на функцию с соответствующей сигнатурой.
Поскольку алгоритмы принимают действие с выводом типов, приведение к указателю на функцию в них происходить не может, происходит обычное копирование объекта, но поскольку он пустой, это в целом равносильно копированию указателя на функцию.
Если лямбда выражение без захвата, то у типа-замыкания определён non-explicit оператор приведения к указателю на функцию с соответствующей сигнатурой.
Поскольку алгоритмы принимают действие с выводом типов, приведение к указателю на функцию в них происходить не может, происходит обычное копирование объекта, но поскольку он пустой, это в целом равносильно копированию указателя на функцию.
Помимо вышесказанного, за счёт встраивания копирования в результате вообще может не быть, и в этом можно убедиться, сравнив машинный код для обычного for по итератору, для range-based for и для std::for_each с замыканием.
Если бы это было не так, то алгоритмы вроде for_each никто бы не использовал из-за abstraction penalty.
Если бы это было не так, то алгоритмы вроде for_each никто бы не использовал из-за abstraction penalty.
Кстати, при использовани libc++ (это реализация стандартной библиотеки в Clang), rate получается очень маленьким.
Укажите компилятор, только из изучения комментариев понял что у вас vs2013. «починили» стандартную библиотеку? надо посмотреть в код, а то раньше там параметр шаблона не передавался по цепочке вложенному вызову, что приводило к забавным результатам
Попробуйте добавить
ПС: Я не проверял, просто гипотеза
const это укажет компилятору что вызов метода не изменит передаваемый экземпляр функтора и копировать его нет необходимости, он ведь все равно не изменится :)void operator() (int value) constПС: Я не проверял, просто гипотеза
Не работает, я проверял :)
Добавил const для случая с сортировкой — результат сохраняется как и у 0serg. Скорее всего компилятор и так понял нас правильно.
Для интереса решил дело усложнить, добавив в operator() счётчик его вызовов. Количество вызовов конструктора осталось прежним. Количество вызовов operator() — O(NlnN), ничего противоестественного не произошло.
Для интереса решил дело усложнить, добавив в operator() счётчик его вызовов. Количество вызовов конструктора осталось прежним. Количество вызовов operator() — O(NlnN), ничего противоестественного не произошло.
Графики
ctr_rate — вызовы конструктора на один элемент, cmp_rate — вызовы operator() на один элемент.
Сортировка убывающей последовательности:
Сортировка массива из нулей:
Сортировка случайного массива:
Сортировка убывающей последовательности:
Сортировка массива из нулей:
Сортировка случайного массива:
Из этой статьи, на примере for_each, я узнал, что в шаблон в качестве класса можно передавать функцию. Это всегда так было?
Нет, в качестве класса можно только передать класс-функтор, обычно у которого переопределён оператор (). Но в качестве параметра шаблона может быть не только класс, но и любое скалярное значение, включая функцию.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Небольшое исследование по использованию функторов в стандартной библиотеке STL С++