同一个小算法的实现 C++和Pascal效率不同(300)

地质灾害

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#1
全组合问题。C++执行的速度比Pascal代码快一倍。可能是Pascal代码写得不好吧 哪里可以改进?C++代码如下#include <iostream>#include "math.h"#include "windows.h"using namespace std;#define USE_TEXT_BUFFERunsigned int TextBufferLen = 1024;unsigned int LoopTimes = 20;inline void BufferText(char * buf,const char * str,int lf){ if ((strlen(str)+strlen(buf))+lf>TextBufferLen) { cout<<buf;
buf[0]=0;
} strcat(buf,str);
if(lf) strcat(buf,"/n");}void OutputCombinations(int cnt,char **data){ unsigned long i,k;
#ifdef USE_TEXT_BUFFER char* buf=(char*)malloc(TextBufferLen+1);
buf[0]=0;
#endif for(i=1;i<pow(2,cnt)-1;i++) { if(i & 1) #ifdef USE_TEXT_BUFFER BufferText(buf,data[0],0);
#else
cout<<data[0];
#endif for(k=1;k<cnt;k++) { if((i>>k) & 1) #ifdef USE_TEXT_BUFFER BufferText(buf,data[k],0);
#else
cout<<data[k];
#endif } #ifdef USE_TEXT_BUFFER BufferText(buf,"/n",0);
#else
cout<<endl;
#endif } #ifdef USE_TEXT_BUFFER cout<<buf;
free(buf);
#endif} int main(int argc, char *argv[]){ DWORD Tick;
unsigned long n;
cout<<"the number of elements for testing:/n";
cin>>n;
cout<<"the string buffer size:/n";
cin>>TextBufferLen;
cout<<"how many calls:/n";
cin>>LoopTimes;
char **data=(char**)malloc(n*sizeof(char*));
cout<<"Initialize array/n";
for(Tick=0;Tick<n;Tick++) { data[Tick]= new char[2];
data[Tick][0]=65+Tick;
data[Tick][1]=0;
} cout<<"Test begin
/n";
Tick=GetTickCount();
for(int i=1;i<=LoopTimes;i++) { OutputCombinations(n,data);
} Tick=GetTickCount()-Tick;
cout<<"Test end/n";
cout<<"Time ellapsed: "<<Tick<<" milliseconds/n";
cout<<"Time used by each call: "<<Tick/LoopTimes<<" milliseconds/n";
for(Tick=0;Tick<n;Tick++) { delete []data[Tick];
} free(data);
system("pause");
return 0;}Pascal代码如下program Composite;{$APPTYPE CONSOLE}uses SysUtils, Math, Windows;var TextBufferLen:Cardinal = 1024;
LOOP_TIMES:Cardinal = 20;procedure GetString(Data:array of string);var i,j,k:Cardinal;
s:string;
begin
j:=Length(Data);
s:='';
for i:=1 to Trunc(IntPower(2,j))do
begin
if (i and 1)>0 then
s:=s+Data[0];
for k:=1 to j-1do
if ((i shr k) and 1)>0 then
s:=s+Data[k];
s:=s+#10;
if Cardinal(Length(s))>TextBufferLen then
begin
write(s);
s:='';
end;
end;
write(s);
end;
var Tick:Cardinal;
n:Cardinal;
Data:array of string;
begin
Writeln('the number of elements for testing:');
Readln(n);
Writeln('the string buffer size:');
Readln(TextBufferLen);
Writeln('how many calls:');
Readln(LOOP_TIMES);
SetLength(Data,n);
Writeln('Initialize array');
for Tick:=0 to n-1do
Data[Tick]:=Chr(65+Tick);
Writeln('Test begin
');
Tick:=GetTickCount();
for n:=1 to LOOP_TIMESdo
GetString(Data);
Tick:=GetTickCount()-Tick;
Writeln('Test end');
Writeln('Time ellapsed: ',Tick,' milliseconds');
Writeln('Time used by each call: ',Tick div LOOP_TIMES,' milliseconds');
Readln;
SetLength(Data,0);
end.
 
T

terry_zhou82

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#2
怎么会呢?不是一直都在说PASCAL是世界上最快的编译器吗?
 
T

tandxu

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#3
编译是快,运行时慢点,但是也不会慢这么多吧。。。。。
 
R

roadexplorer

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#4
s:=s+Data[k];这句太烂,如何不慢
 
B

briankuo

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#5
pascal 里面,不用 string ,改用 PChar 操作,看性能怎样
 
R

roadexplorer

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#6
string也可以用,关键不要s:=s+Data[k];
 
S

szf

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#7
var s: String;...s := s + char(or String)这种写法实际是上重新分配堆内存,并修改s的引用位置,如果在循环语句中使用这种写法,效率当然低了。正确写法之一是在循环语句前先用SetLength(s, Len)动态分配足够的内存,然后用索引下标变量进行赋值处理。
 
U

ufo

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#8
[:D]地质灾害也是老江湖了,怎么会犯这小错误。字符串的重新组合是效率很低的,在注重性能时尤其要避免。这里建议用 array of char 数组。用预先SetLength(s, Len),再s这种方式访问,我不记得是否会引起写复制,可以测试一下。
 

我爱PASCAL

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#9
用预先SetLength(s, Len),再s这种方式访问,我不记得是否会引起写复制,可以测试一下。 ——绝对不会例:function TrimAllSpace(Str: string): string;var I, J, StrLen: Integer;
begin
StrLen := Length(Str);
if StrLen = 0 then
Exit;
SetLength(Result, StrLen);
J := 0;
for I := 1 to StrLendo
if str<>#32 then
begin
Inc(J);
Result[J] := Chr;
end;
Delete(Result,J+1,StrLen-J);
end;
 
U

ufo

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#10
to:我爱PASCAL, 我写了点测试代码,然后跟踪了一下汇编,发现在循环内使用s这种方式还是不经济的。虽然在循环内最多会出现一次写复制。具体如下:在循环内delphi会自动插入@UniquesTringA这么一个过程调用,这是检查是否需要写复制的代码。在UniquesTringA代码内部分摘抄如下:……mov ecx,[edx-$08]//edx保存了字符串指向的首字符地址,首字符前8个字节保存了引用计数(引用计数4字节,串长4字节)。dec ecx //ecx减去一jz,+$32 //如果为零,跳转到出栈返回……调用写复制过程$32偏移,出栈返回由此可见,在第一次进入循环时,如果字符串引用计数大于1的,会引发一次写复制,后续循环时便不会再写复制。只是在长循环时多一个过程调用(每次s:=X时都会调用),还是有些性能损失的。在追求高性能时,用 array of char为好,没有这些额外的代码。
 
U

ufo

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#11
再补充一下例子代码本例中由于字符串引用计数为1,没有额外的字符串引用它,所以没发生写复制。procedure TForm1.Button1Click(Sender: TObject);var ss: string;
i: integer;
begin
ss:= '早睡早起'+ datetostr(date);
memo1.Lines.Append('原始字符串地址:'+inttostr(integer(ss)));
for i:= 1 to 5do
begin
ss:= 'Y';
memo1.Lines.Append('地址后续:'+inttostr(integer(ss)));
end;
end;
 
S

simb

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#13
你如果需要做测试那么建议采用和C++同样的数据类型和模型。这样的测试才准确啊
 
T

terry_zhou82

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#14
有人贴出更改后的代码吗?修改后到底差多少啊?
 

我爱PASCAL

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#15
To: ufoString是改变才复制,我想在第一次改变时就会复制,复制后有了新的空间,不会再复制但是只要不将STRING赋给其它STRING,则不会复制,所以效率应该不会有所影响.但是你这个提醒很重要,我也需要检查下我的代码中有没有这种情况出现.
 

我爱PASCAL

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#16
C++和PASCAL的效率没有多少对比头,首先要保证两段代码完全等价,然后对比两者编译后的汇编,就知道谁更快.
 
C

creation-zy

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#17
Pascal编译器在默认情况下会对数据元素的访问进行越界检查,可以通过{$R-}关闭之。
 
W

wr960204

Unregistered / Unconfirmed
GUEST, post messages is not allowed!
#19
楼主的意思是说Delphi代码的效率高吧?我把你的代码分别用VC和Delphi编译.VC用的是2005.Release /O2最佳速度优化.参数是:10,1024,10VC的结果:Time ellapsed: 2032 millisecondsTime used by each call: 203 millisecondsDelphi的结果:Time ellapsed: 297millisecondsTime used by each call: 29milliseconds分明是Delphi代码的效率高很多啊.不过我和以前同事比拼过Delphi和VC的编译器.基本上算法一样的情况,效率大致一样,些许微小差异看一看成误差.