qsort 与 std::sort 的性能?

问题描述

根据 Scott Meyers 的说法，在他的 Effective STL 书中 - 第 46 项.他声称std::sort 比 std::qsort 由于内联的事实.我测试了自己，发现 qsort 更快 :( ！谁能帮我解释一下这种奇怪的行为?

According to Scott Meyers, in his Effective STL book - item 46. He claimed that std::sort is about 670% faster than std::qsort due to the fact of inline. I tested myself, and I saw that qsort is faster :( ! Could anyone help me to explain this strange behavior?

#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 << "
";
    // 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 << "
";
}

这是我的结果:

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

更新

Effective STL 第三版(2001 年)
第 7 章 STL 编程
第 46 条:将函数对象而不是函数视为算法参数.

Effective STL 3rd Edition ( 2001 )
Chapter 7 Programming with STL
Item 46: Consider function objects instead of functions as algorithm parameters.

推荐答案

std::clock() 不是可行的计时时钟.您应该使用特定于平台的更高分辨率计时器，例如 Windows 高性能计时器.更重要的是，您调用 clock() 的方式是首先将文本输出到控制台，该控制台包含在时间中.这肯定会使测试无效.此外，请确保您使用所有优化进行编译.

std::clock() is not a viable timing clock. You should use a platform-specific higher resolution timer, like the Windows High Performance Timer. More than that, the way that you call clock() is that first, text is output to the console, which is included in the time. This definitely invalidates the test. In addition, make sure that you compiled with all optimizations.

最后，我复制并粘贴了您的代码，qsort 为 0.016，std::sort 为 0.008.

Finally, I copied and pasted your code, and got 0.016 for qsort and 0.008 for std::sort.

这篇关于qsort 与 std::sort 的性能?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！