qsort vs std :: sort的性能？ [英] Performance of qsort vs std::sort?

问题描述

Scott Meyers在他的有效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 *）b）; 
} 
 
 int main（）{
 int ary [LARGE_SIZE]; 
 int ary_copy [LARGE_SIZE]; 
 //生成随机数据
 std :: generate（ary，ary + LARGE_SIZE，rnd（））; 
 std :: copy（ary，ary + LARGE_SIZE，ary_copy）; 
获取时间
 std :: time_t start = std :: clock（）; 
 //使用函数指针快速排序C 
 std :: qsort（ary，LARGE_SIZE，sizeof（int） comp）; 
 std :: cout<< C quick-sort time elapsed：< static_cast< double>（clock（） -  start）/ CLOCKS_PER_SEC< \\\
; 
 //再次获取时间
 start = std :: clock（）; 
 //使用函数对象执行快速排序C ++ 
 std :: sort（ary_copy，ary_copy + LARGE_SIZE）; 
 std :: cout<< C ++ quick-sort time elapsed：< static_cast< double>（clock（） -  start）/ CLOCKS_PER_SEC< \\\
; 
} 
  

这是我的结果：

$ b b

  C快速排序时间已过：0.061 
 C ++快速排序时间已过：0.086 
按任意键继续。 。 。 
  

更新

Effective STL 3rd Edition（2001）

第7章使用STL编程

项目46：将函数对象而不是函数视为算法参数。

最好的问候，

解决方案

std :: clock不是可行的时钟。您应该使用特定于平台的更高分辨率定时器，例如Windows高性能定时器。更重要的是，你调用clock（）的方式是，首先，文本输出到控制台，这包括在时间。这肯定会使测试失效。

最后，我复制并粘贴了你的代码，对于qsort为0.016，对std :: sort为0.008。 / p>

According 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 << "\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";
}

This is my result:

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

Update

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

Best regards,

解决方案

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.

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

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