Эх, люблю я бенчмарки проводить  Вот и в этот раз не выдержал и написал тест. Все ту же быструю сортировку в двух вариантах: явная рекурсия и эмуляция через стек.
| Код | #include <iostream>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <climits>
#include <cstdlib>
#include <ctime>
// Возвращает медиану из первого, последнего и серединного элемента.
template <typename Iterator, typename Comparer>
inline Iterator find_pivot(Iterator begin, Iterator end,
const Comparer &cmp) {
Iterator middle = begin + (end - begin) / 2;
if (cmp(*begin, *middle) && cmp(*(end - 1), *begin)
|| !cmp(*begin, *middle) && !cmp(*(end - 1), *begin))
return begin;
else if (cmp(*(end - 1), *middle) && cmp(*begin, *(end - 1))
|| !cmp(*(end - 1), *middle) && !cmp(*begin, *(end - 1)))
return end - 1;
return middle;
}
template <typename Iterator, typename Comparer>
inline Iterator partition(Iterator begin, Iterator end, Iterator pivot,
const Comparer &cmp) {
typename std::iterator_traits<Iterator>::value_type pivotValue(*pivot);
std::iter_swap(pivot, end - 1);
Iterator p = std::partition(begin, end - 1, std::bind2nd(cmp, pivotValue));
iter_swap(p, end - 1);
return p;
}
template <typename Iterator, typename Comparer>
void rec_qsort(Iterator begin, Iterator end,
const Comparer &cmp = Comparer()) {
if (end - begin > 1) {
Iterator pivot = find_pivot(begin, end, cmp);
pivot = partition(begin, end, pivot, cmp);
if (pivot - begin > end - pivot) {
rec_qsort(begin, pivot, cmp);
rec_qsort(pivot + 1, end, cmp);
} else {
rec_qsort(pivot + 1, end, cmp);
rec_qsort(begin, pivot, cmp);
}
}
}
template <typename Iterator>
void rec_qsort(Iterator begin, Iterator end) {
rec_qsort(begin, end,
std::less<typename std::iterator_traits<Iterator>::value_type>());
}
template <typename Iterator, typename Comparer>
void qsort(Iterator begin, Iterator end, const Comparer &cmp = Comparer()) {
// глубина рекурсии не превышает log_2(n), где n - длина сортируемой
// последовательности
std::pair<Iterator, Iterator> stack[
sizeof(typename std::iterator_traits<Iterator>::difference_type) *
CHAR_BIT];
size_t top = 0;
stack[top++] = std::make_pair(begin, end);
while (top) {
--top;
begin = stack[top].first;
end = stack[top].second;
while (end - begin > 1) {
Iterator pivot = find_pivot(begin, end, cmp);
pivot = partition(begin, end, pivot, cmp);
if (pivot - begin > end - pivot) {
stack[top++] = std::make_pair(begin, pivot);
begin = pivot + 1;
} else {
stack[top++] = std::make_pair(pivot + 1, end);
end = pivot;
}
}
}
}
template <typename Iterator>
void qsort(Iterator begin, Iterator end) {
qsort(begin, end,
std::less<typename std::iterator_traits<Iterator>::value_type>());
}
class timer {
clock_t start_;
public:
timer() : start_(clock()) { }
double elapsed() {
return 1.0 * (clock() - start_) / CLOCKS_PER_SEC;
}
void reset() {
start_ = clock();
}
};
int myrandom() {
return rand() * (RAND_MAX + 1) + rand();
}
int main() {
const size_t arraySize = 40000000;
srand(time(NULL));
std::vector<int> a(arraySize), b;
std::generate(a.begin(), a.end(), myrandom);
b = a;
timer t;
rec_qsort(a.begin(), a.end());
std::cout << "Recursion:\t" << t.elapsed() << " sec" << std::endl;
t.reset();
qsort(b.begin(), b.end());
std::cout << "No recursion:\t" << t.elapsed() << " sec" << std::endl;
} |
Результаты:
GCC 3.4.5 (MinGW)
| Цитата | Recursion: 7.797 sec
No recursion: 7.781 sec
Recursion: 7.797 sec
No recursion: 7.766 sec
Recursion: 7.812 sec
No recursion: 7.782 sec
Recursion: 7.797 sec
No recursion: 7.781 sec
Recursion: 7.797 sec
No recursion: 7.859 sec |
VC 8.0:
| Цитата | Recursion: 8.61 sec
No recursion: 8.719 sec
Recursion: 8.656 sec
No recursion: 8.766 sec
Recursion: 8.625 sec
No recursion: 8.781 sec
Recursion: 8.61 sec
No recursion: 8.765 sec
Recursion: 8.656 sec
No recursion: 8.735 sec |
Вот такая забавная картина, не находите?
Так стоит ли заморачиваться с ручной эмуляцией стека ради пары процентов производительности, которые в зависимости от компилятора могут оказаться и на той, и на другой стороне? ИМХО, нет.
В данном случае можно было оценить верхний предел глубины рекурсии, однако выделяя под стек массив постоянного размера мы в любом случае рискуем молчаливо вылететь за его пределы. Используя же динамический массив мы рискуем свести на нет все призрачные преимущества эмуляции рекурсии. |
) 