请c++ 高手调优

llslls_007

以下3个函数分别用c 数组 ，c++ list  和 c++ vector 分别实现 0-9 10个数的全排列
输出 ，编译器为CC,工作中尝试过c++改写c程序，发现速度也有慢些，用c++一直担心
速度问题。
c 用时间 10秒钟
c++ vector 完全是模仿c写的 却要 30多秒钟（不知道为何）
c++ list    则是要5分钟 （不能忍受）

请大侠帮忙指出慢在哪？

1. void permutation(int *array,int N,int * array_bak,int num){  
   
2.           // array 为要进行排列的数组 ，N array 中元素个数，初值为10，array_bak是排列的数组
   
3.            //num为排列中数字个数，初值为0
   
4. 
   
5.                  int array_temp[10];   
   
6.           if(num==10){
   
7.           for(int i=0;i<10;i++)
   
8.              {
   
9.                  printf("%d",*(array_bak+i));
   
10.                  printf("\n");
    
11.               }
    
12.             return;
    
13.           }
    
14.           for(int i=0;i<N;i++){
    
15.            //从array中 选择一个数放入排列array_bak中， array中其余的元素拷贝到临时数组array_temp中，
    
16.             //array_temp就是下个递归调用需要排列的数组
    
17.             //，直到num==10 表示排列中已有10个数字
    
18.           
    
19.              array_bak[num]=array[i];
    
20.             temp_bak=array[i];
    
21.             if(i==0)         
    
22.                     memcpy(array_temp,array+1,sizeof(int)*(N-1));
    
23.             else if(i==N-1)
    
24.                     memcpy(array_temp,array,sizeof(int)*(N-1));
    
25.             else
    
26.                     {
    
27.                          memcpy(array_temp,array,sizeof(int)*(i));
    
28.                       memcpy(array_temp+i,array+i+1,sizeof(int)*(N-i-1));
    
29.                      }
    
30.             permutation(array_temp,N-1,array_bak,num+1);
    
31.             
    
32.            }
    
33.           }
    
34. 
    
35. template<typename T>
    
36. void  tem_permutation(list<typename T> &lis ,list<typename T> &lis_bak,int & NUM){
    
37.   //lis要排列的数组，lis_bak存储排列，NUM标记排列中数字个数  
    
38. if(10==NUM)
    
39.           {
    
40.       for_each(lis_bak.begin(),lis_bak.end(),display);
    
41.       cout<<endl;
    
42.       return;
    
43.     }
    
44.   for(list<T>::iterator it=lis.begin();it!=lis.end();it++)
    
45.      {
    
46.        //把已排列的元素标记为-1，找到不为-1的元素，加入到排lis_bak中，
    
47.     //递归直到NUM 为10 表示lis_bak中已有10个数字
    
48.      
    
49.      T temp;
    
50.        if(*it==-1)
    
51.                 continue;
    
52.        lis_bak.push_back(*it);      
    
53.        temp=*it;
    
54.        *it=-1;
    
55.        NUM++;
    
56.        tem_permutation(lis,lis_bak,NUM);
    
57.        *it=temp;         
    
58.        lis_bak.pop_back();
    
59.        --NUM;
    
60.      }  
    
61. }
    
62. 
    
63. 
    
64. 
    
65. template<typename T>         
    
66. void vec_permutation(vector<typename T> &vec,int N,vector<typename T> &vec_bak,int NUM){
    
67.         //完全按c的思路写的，却比c慢很多
    
68.          
    
69.           vector<T> vec_temp(10,-1);
    
70.         T temp;
    
71.         if(NUM==10)
    
72.                 {
    
73.                  for(int i=0;i<10;i++)
    
74.                   printf("%d",vec_bak[i]);
    
75.                   printf("\n");
    
76.                   return;
    
77.                  }
    
78.          for(int i=0;i<N;i++){
    
79.             vec_bak[NUM]=vec[i];
    
80.           
    
81.           if(i==0)
    
82.              memcpy(&vec_temp[0],&vec[0]+1,sizeof(int)*(N-1));
    
83.           else if(i==N-1)
    
84.             memcpy(&vec_temp[0],&vec[0],sizeof(int)*(N-1));
    
85.           else
    
86.             {
    
87.                memcpy(&vec_temp[0],&vec[0],sizeof(int)*(i));
    
88.                memcpy(&vec_temp[0]+i,&vec[0]+i+1,sizeof(int)*(N-i-1));
    
89.             }
    
90.            vec_permutation(vec_temp,N-1,vec_bak,NUM+1);
    
91.            }
    
92.         }
    
93. 
    

复制代码

*********************************************************************
再添加一种：采用c++ 标准库算法 next_permutation 时间为27秒 ，如果把display 函数中的
           printf 函数改为 cout 则需要5分钟 ，难道printf 和cout 的io 效率 相差这么大？
           是缓冲区设置的问题吗？
void nt_permutation(vector<int> & vec){
        sort(vec.begin(),vec.end());
        while(next_permutation(vec.begin(),vec.end() ) ){
                for_each(vec.begin(),vec.end(),display );
                cout<<endl;
        }

llslls_007

回复 1# llslls_007


    哎，我自己顶个先！！！

  在 c++ vector 实现中 ，把69行
69.  vector<T> vec_temp(10,-1);
       改为：
   
     vector<T> vec_temp;
        vec_temp.reserve(10);

   效率更高高，避免每次递归调用中临时变量 vec_temp 都要初始化
  10个int 为-1，节省了300多万次初始化， 速度提升到21秒左右
  但和c 数组的实现还有 10s的差距

  继续等待高人！！！

w_anthony

LZ这个不是C与C++的速度差异，而是栈上分配变量与堆上分配变量的速度差异。
你这段C代码都是栈上面定义的，而C++的vector却是堆上new出来，你说该怎么比较？
或许可以把C这段也改成malloc比较下速度试试。

llslls_007

回复 3# w_anthony


    恩，明天按照你的思路，把临时变量都改成全局变量

免得分配了，速度应该就差不多了吧

w_anthony

回复 4# llslls_007


    我测试了一下，不计算printf输出时间，C那段耗时0.4秒多，C++的vector那段耗时23秒多，C那段改成malloc+free耗时9秒多，C++那段vector的vec_temp改成static类型变量耗时也是0.4秒左右。
可以看出绝大多数时间还是消耗在内存分配和构造函数执行上面。

/*************************************************************/

想错了，vec_temp不能是static变量，否则递归下去会把数据搞乱。

hellioncu

搞不懂LZ想要怎么样的一个结果

llslls_007

回复 6# hellioncu


     同样的思路，想把c++ 做得和 c 一样快

hellioncu

回复  hellioncu


     同样的思路，想把c++ 做得和 c 一样快
llslls_007 发表于 2010-07-28 10:11

    那不可能的，访问vector、list跟数组自然开销要大。
c++又不是不能用数组，何必一定要vector、list呢

ah13k

注意你的流和内存分配。

自己测试malloc和new得速度。另外当然还有delete和free

注意printf比stream快的多。

llslls_007

回复 1# llslls_007


    printf   和 cout  相差这么大？