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

овам Скотта Мейерса, в своей книге «Эффективное STL» - пункт 46. Он утверждал, чтоstd::sort примерно на 670% быстрее, чемstd::qsort из-за факта встраивания. Я проверил себя и увидел, что qsort быстрее :(! Может кто-нибудь помочь мне объяснить это странное поведение?

#include <iostream>
#include <vector>
#include <algorithm>

#include <cstdlib>
#include <ctime>
#include <cstdio>

const size_t LARGE_SIZE = 100000;

struct rnd {
    int operator()() {
        return rand() % LARGE_SIZE;
    }
};

int comp( const void* a, const void* b ) {
    return ( *( int* )a - *( int* )b );
}

int main() {
    int ary[LARGE_SIZE];
    int ary_copy[LARGE_SIZE];
    // generate random data
    std::generate( ary, ary + LARGE_SIZE, rnd() );
    std::copy( ary, ary + LARGE_SIZE, ary_copy );
    // get time
    std::time_t start = std::clock();
    // perform quick sort C using function pointer
    std::qsort( ary, LARGE_SIZE, sizeof( int ), comp );
    std::cout << "C quick-sort time elapsed: " << static_cast<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";
    // get time again
    start = std::clock();
    // perform quick sort C++ using function object
    std::sort( ary_copy, ary_copy + LARGE_SIZE );
    std::cout << "C++ quick-sort time elapsed: " << static_cast<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";
}

Это мой результат:

C quick-sort time elapsed: 0.061
C++ quick-sort time elapsed: 0.086
Press any key to continue . . .

Обновить

Эффективный STL 3-е издание (2001)
Глава 7 Программирование с помощью STL
Пункт 46: Рассматривать функциональные объекты вместо функций в качестве параметров алгоритма.

С уважением,

 Matthieu N.16 янв. 2011 г., 22:30
@Noah: Согласно статье 06 об Artima SM: «Я начну с того, что многие из вас найдут неприемлемо проклятое признание: я не писал производственное программное обеспечение более 20 лет, и я никогда не писал производственное программное обеспечение на C ++. " Он называет себя археологом / антропологом языка C ++.
 Matthieu N.16 янв. 2011 г., 22:24
Понимание того, как работает быстрая сортировка, даст вам лучшее представление о том, как ее протестировать, вкратце: 1. используйте массив большего размера, например: 10 ^ 6, затем заполните массив в порядке убывания 999999 ... 4,3 , 2,1 - это приведет к тому, что сортировка станет O (n ^ 2), и это эффективно продемонстрирует, почему встроенные компараторы делают такую ​​большую разницу в этом конкретном алгоритме.
 Matthieu N.16 янв. 2011 г., 22:54
@Chan: Бентли и Макилрой бумаги можно найти здесь:cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol23/issue11/...
 Crazy Eddie16 янв. 2011 г., 22:23
Вы позволили вашему компилятору оптимизировать? Отладочные / неоптимизированные сборки не будут в полной мере использовать преимущества таких вещей, как встраивание.
 templatetypedef16 янв. 2011 г., 22:26
@ Zenikoder - практически нет реализацийqsort или жеsort будет использовать реализацию быстрой сортировки, которая разбивается на входах с обратной сортировкой. Самый распространенный STLsort реализация использует интросорт, который анализирует процедуру быстрой сортировки, чтобы гарантировать, что она никогда не ухудшится до худшего, чем O (n lg n), и я довольно уверен, что Cqsort Для предотвращения этого рутина использует нечто подобное (или, по крайней мере, эвристическое, например, медиану-три).

Ответы на вопрос(7)

Написание точных тестов сложно, поэтому давайтеверньер сделать это для нас! Давайте проверимqsort, std::sort без врезки, иstd::sort с встраиванием (по умолчанию) в векторе миллиона случайных чисел.

// sort.cpp
#define NONIUS_RUNNER
#include <nonius.h++>
#include <random>
#include <algorithm>

// qsort
int comp(const void* a, const void* b) {
    const int arg1 = *static_cast<const int*>(a);
    const int arg2 = *static_cast<const int*>(b);

    // we can't simply return a - b, because that might under/overflow
    return (arg1 > arg2) - (arg1 < arg2);
}

// std::sort with no inlining
struct compare_noinline {
    __attribute__((noinline)) bool operator()(const int a, const int b) {
        return a < b;
    }
};

// std::sort with inlining
struct compare {
    // the compiler will automatically inline this
    bool operator()(const int a, const int b) {
        return a < b;
    }
};

std::vector<int> gen_random_vector(const size_t size) {

    std::random_device seed;
    std::default_random_engine engine{seed()};
    std::uniform_int_distribution<int> dist{std::numeric_limits<int>::min(), std::numeric_limits<int>::max()};

    std::vector<int> vec;
    for (size_t i = 0; i < size; i += 1) {
        const int rand_int = dist(engine);
        vec.push_back(rand_int);
    }

    return vec;
}

// generate a vector of a million random integers
constexpr size_t size = 1'000'000;
static const std::vector<int> rand_vec = gen_random_vector(size);

NONIUS_BENCHMARK("qsort", [](nonius::chronometer meter) {

    // Nonius does multiple runs of the benchm,ark, and each one needs a new
    // copy of the original vector, otherwise we'd just be sorting the same
    // one over and over
    const size_t runs = static_cast<size_t>(meter.runs());
    std::vector<std::vector<int>> vectors{runs};
    std::fill(vectors.begin(), vectors.end(), rand_vec);

    meter.measure([&](const size_t run) {

        std::vector<int>& current_vec = vectors[run];

        std::qsort(current_vec.data(), current_vec.size(), sizeof(int), comp);

        return current_vec;
    });
});

NONIUS_BENCHMARK("std::sort noinline", [](nonius::chronometer meter) {

    const size_t runs = static_cast<size_t>(meter.runs());
    std::vector<std::vector<int>> vectors{runs};
    std::fill(vectors.begin(), vectors.end(), rand_vec);

    meter.measure([&](const size_t run) {

        std::vector<int>& current_vec = vectors[run];

        std::sort(current_vec.begin(), current_vec.end(), compare_noinline{});

        return current_vec;

    });
});

NONIUS_BENCHMARK("std::sort inline", [](nonius::chronometer meter) {

    const size_t runs = static_cast<size_t>(meter.runs());
    std::vector<std::vector<int>> vectors{runs};
    std::fill(vectors.begin(), vectors.end(), rand_vec);

    meter.measure([&](const size_t run) {

        std::vector<int>& current_vec = vectors[run];

        std::sort(current_vec.begin(), current_vec.end(), compare{});

        return current_vec;

    });
});

Компиляция с Apple Clang 7.3.0,

$ clang++ -std=c++14 -stdlib=libc++ -O3 -march=native sort.cpp -o sort
$ ./sort

и запустив его на моем 1.7 ГГц MacBook Air i5, мы получаем

qsort                211 ms +/- 6 ms
std::sort noinline   127 ms +/- 5 ms
std::sort inline      87 ms +/- 4 ms

Такstd::sort без встраивания примерно в 1,7 раза быстрее, чемqsort (возможно, из-за различных алгоритмов сортировки), и врезки ударов, которые примерно в 2,4 раза быстрее. Конечно, впечатляющее ускорение, но гораздо меньше, чем 670%.

: sort был реализован много лет назад. Но std :: sort может быть намного быстрее, потому что std :: sort является быстрой сортировкой с резервной сортировкой кучи. Heapsort - это линейно-динамический алгоритм, означающий, что если у вас есть дважды данные сортировки, время сортировки удваивается. На самом деле он более чем удваивается, потому что он не совсем линейный, но, тем не менее, qsort может быть квадратичным, поэтому для сортировки входных данных требуется больше экспоненциального времени.

 Peter Cordes27 мар. 2016 г., 13:44
Любая библиотекаqsort позаботится о выборе кругов, чтобы избежать наихудшего случая O (n ^ 2) для почти всех входов.std::qsort даже не нужно быть быстрой сортировкой, поэтому он может не иметь никаких входных данных в худшем случае, которые хуже, чем O (n log n)
 Puppy29 янв. 2017 г., 17:42
эээ, квадратичный определенно не экспоненциальный вообще. Вы используете несколько терминов, но кажется, что у вас есть только смутное представление о том, что они означают.
Решение Вопроса

: clock () не является жизнеспособным таймером. Вы должны использовать платформенный таймер с более высоким разрешением, такой как высокопроизводительный таймер Windows. Более того, способ, которым вы вызываете clock (), заключается в том, что сначала текст выводится на консоль, которая включена во время. Это определенно делает тест недействительным. Кроме того, убедитесь, что вы скомпилировали все оптимизации.

Наконец, я скопировал и вставил ваш код и получил 0,016 для qsort и 0,008 для :: sort.

 Chan16 янв. 2011 г., 22:27
@DeadMG: Спасибо! Я перешел в режим выпуска и получил аналогичный результат. Я действительно люблю Скотта Мейерса, и я верю его слову;)
 Billy ONeal16 янв. 2011 г., 22:25
+1 за фактический бенчмаркинг.
 Puppy16 янв. 2011 г., 22:33
@ Oo Tiib: выводимый текст не означает, что он не выводится одновременно. Что если буфер несколько больше первого, но меньше второго? Теперь он должен сбрасываться перед вторым вызовом, но не при первом вызове. О, Боже. Я не очень счастлив, потому что я исправил все вышеперечисленные проблемы, и теперь qsort стал намного быстрее. :(
 Öö Tiib16 янв. 2011 г., 22:29
Похоже, что текст выводится в обоих случаях, поэтому он не может сделать результат недействительным.
 Billy ONeal17 янв. 2011 г., 01:04
@DeadMG:std::qsort требует "Возвращаемое значение этой функции должно представлять, считается ли elem1 меньшим, равным или большим, чем elem2, возвращая, соответственно, отрицательное значение, ноль или положительное значение."operator< не соответствует этому требованию (в частности, он возвращает только 0 или 1). Проверьте, чтобы убедиться, чтоstd::sort а такжеstd::qsort дают те же результаты в вашем тестировании :) (просто меняется- в< результаты вqsort возвращаю неправильный ответ для меня)

элементов и перемещаем его в раздел данных) и компилируем

g++ -Wall -O2 -osortspeed sortspeed.cpp

Я получаю в результате

C quick-sort time elapsed: 3.48
C++ quick-sort time elapsed: 1.26

Также будьте осторожны с современными «зелеными» процессорами, которые могут быть настроены на работу с переменной скоростью в зависимости от нагрузки системы. Когда тестирование такого поведения может свести вас с ума (на моей машине я установил два небольших скриптаnormal а такжеfast что я могу использовать при тестировании скорости).

 650217 янв. 2011 г., 01:29
@Billy ONeal: я думал, что вы имели в виду RDTSC, и это очень мило, но глобально. И нет, clock () является счетчиком для каждого процесса. Видетьcs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_19.html
 Billy ONeal17 янв. 2011 г., 01:35
@ 6502: glibc! = Стандарт c. Обычно я верю в эти вещинаходятся осуществляется с точки зренияrdtsc, но ОС отслеживает временные метки, когда выполняет переключение контекста, и восстанавливает эти значения, когда контекст возвращается измеряемому процессу.
 Billy ONeal16 янв. 2011 г., 22:50
«Зеленые» процессоры не имеют значения, если вы используете счетчики производительности (как вы должны делать для значимых результатов тестов)
 650216 янв. 2011 г., 22:59
Счетчики производительности хороши, но часы не так уж плохи, если вы не пытаетесь измерить мелочи. Кроме того, clock () относится к каждому процессу, счетчики производительности являются глобальными.
 Billy ONeal17 янв. 2011 г., 00:49
@ 6502: у тебя все наоборот. Счетчики производительности на процесс, часы глобальные.

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

Если заголовок C определяет встроенную реализацию qsort вместо реализации внутри библиотеки и компилятор поддерживает косвенное встраивание функции, тогда qsort может быть таким же быстрым, как std :: sort.

тавимую производительность. Причина в том, что C ++sort имеет тенденцию заметно битьqsort заключается в том, что компилятор может встроить выполняемые сравнения, поскольку у компилятора есть информация о типе того, какая функция используется для выполнения сравнения. Вы запускали эти тесты с включенной оптимизацией? Если нет, попробуйте включить его и снова запустить этот тест.

 Chan16 янв. 2011 г., 22:24
Спасибо! Я использую Visual Studio, и я действительно не знаю, как включить оптимизацию.
 Chan16 янв. 2011 г., 22:28
@Billy ONeal: я переключился на Release и получил ожидаемый результат. Счастливого ^ _ ^!
 Billy ONeal16 янв. 2011 г., 22:24
@Chan: переключиться на использование сборки "Release". Также убедитесь, что вы не запускаете программу из визуальной студии для своих тестов - такие вещи, как отладчики, изменят временные характеристики вашей программы.

В своем коде вы начинаете с прикосновенияичных и * ary_copy *, поэтому они постоянно находятся в кешеQSort, В течениеQSort, * ary_copy * может быть выселен. На времястанд :: сортироватьэлементы должны быть извлечены из памяти или больше (читатьпомедленнее) уровень кэша. Это, конечно, будет зависеть от размера вашего кеша.

Попробуйте отменить тест, то есть начать с запускастанд :: сортировать.

Как указали некоторые люди; увеличение массива сделает тест более справедливым. Причина в том, что большой массив с меньшей вероятностью помещается в кеш.

 Wexxor13 июл. 2013 г., 00:37
Я удивлен, что никто не упомянул какие-либо стратегии для измерения фактической эффективности кода. Вы можете написать крошечную программу, которая сортирует несколько сотен элементов, загружать все в ваш кэш L1 и копировать это в рекордно короткие сроки, но это никоим образом не будет отражать вашу реальную программу, работающую в системе с несколькими сотнями других активные процессы, выполняющие переключение контекста, потому что вы привязаны к вычислениям, а планировщик вас ненавидит, сортируя набор данных размером с Нью-Джерси. Сделайте ваш бенчмарк похожим на реальное приложение.

Ваш ответ на вопрос