当前位置：首页 → 问答吧 → 请c++ 高手调优

请c++ 高手调优

时间：2010-07-26

来源：互联网

本帖最后由 llslls_007 于 2010-07-26 23:44 编辑

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

void permutation(int *array,int N,int * array_bak,int num){
// array 为要进行排列的数组，N array 中元素个数，初值为10，array_bak是排列的数组
//num为排列中数字个数，初值为0
int array_temp[10];
if(num==10){
for(int i=0;i<10;i++)
{
printf("%d",*(array_bak+i));
printf("\n");
}
return;
}
for(int i=0;i<N;i++){
//从array中选择一个数放入排列array_bak中， array中其余的元素拷贝到临时数组array_temp中，
//array_temp就是下个递归调用需要排列的数组
//，直到num==10 表示排列中已有10个数字
array_bak[num]=array[i];
temp_bak=array[i];
if(i==0)
memcpy(array_temp,array+1,sizeof(int)*(N-1));
else if(i==N-1)
memcpy(array_temp,array,sizeof(int)*(N-1));
else
{
memcpy(array_temp,array,sizeof(int)*(i));
memcpy(array_temp+i,array+i+1,sizeof(int)*(N-i-1));
}
permutation(array_temp,N-1,array_bak,num+1);
}
}
template<typename T>
void tem_permutation(list<typename T> &lis ,list<typename T> &lis_bak,int & NUM){
//lis要排列的数组，lis_bak存储排列，NUM标记排列中数字个数
if(10==NUM)
{
for_each(lis_bak.begin(),lis_bak.end(),display);
cout<<endl;
return;
}
for(list<T>::iterator it=lis.begin();it!=lis.end();it++)
{
//把已排列的元素标记为-1，找到不为-1的元素，加入到排lis_bak中，
//递归直到NUM 为10 表示lis_bak中已有10个数字
T temp;
if(*it==-1)
continue;
lis_bak.push_back(*it);
temp=*it;
*it=-1;
NUM++;
tem_permutation(lis,lis_bak,NUM);
*it=temp;
lis_bak.pop_back();
--NUM;
}
}
template<typename T>
void vec_permutation(vector<typename T> &vec,int N,vector<typename T> &vec_bak,int NUM){
//完全按c的思路写的，却比c慢很多
vector<T> vec_temp(10,-1);
T temp;
if(NUM==10)
{
for(int i=0;i<10;i++)
printf("%d",vec_bak[i]);
printf("\n");
return;
}
for(int i=0;i<N;i++){
vec_bak[NUM]=vec[i];
if(i==0)
memcpy(&vec_temp[0],&vec[0]+1,sizeof(int)*(N-1));
else if(i==N-1)
memcpy(&vec_temp[0],&vec[0],sizeof(int)*(N-1));
else
{
memcpy(&vec_temp[0],&vec[0],sizeof(int)*(i));
memcpy(&vec_temp[0]+i,&vec[0]+i+1,sizeof(int)*(N-i-1));
}
vec_permutation(vec_temp,N-1,vec_bak,NUM+1);
}
}

复制代码

作者: llslls_007 发布时间: 2010-07-26

回复 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的差距

  继续等待高人！！！

作者: llslls_007 发布时间: 2010-07-27

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

作者: w_anthony 发布时间: 2010-07-27

回复 w_anthony

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

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

作者: llslls_007 发布时间: 2010-07-27

回复 llslls_007

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

作者: w_anthony 发布时间: 2010-07-27

请c++ 高手调优

热门阅读

热门下载