求一组合算法,800多万个组合,要求时间控制在0.5秒以下(C2.4G,512M),你们有多少个能够做到? ( 积分: 90 )

呵呵，不好意思不知什么时候在(i3 shl 8)时加了一个“//”,是没有问题的！
另外，不知你们发现了没有我上面的代码写错了，分配了两次空间
－－
SetLength(Data,iLength)

p := GetMemory(iLength*sizeof(TData));
＝＝
就是因为SetLength(Data,iLength)
这一句增加了约0.0930秒的时间。

这是最快的代码，用时0.094秒：
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
procedure TForm1.Button3Click(Sender: TObject);
type
TData = packed Record
data :array[0..6]of byte;
end;

var
iLength:integer;
m,i1,i2,i3,i4,i5,i6,i7: integer;
pData : ^TData;
time:TTime;
Data:array of TData;
pointer;

begin

time := now;
ilength := 8347680;
p := GetMemory(iLength*sizeof(TData));
pData := p;
for i1 := 1 to 30 do
for i2 := i1+1 to 31 do
for i3 := i2+1 to 32 do
for i4 := i3+1 to 33 do
for i5 := i4+1 to 34 do
for i6 := i5+1 to 35 do
for i7 := i6+1 to 36 do
begin
with pData^ do
begin
data[0]:= i1;
data[1]:= i2;
data[2]:= i3;
data[3]:= i4;
data[4]:= i5;
data[5]:= i6;
data[6]:= i7;
end;
inc(pData);
end;

freeMem(p, iLength*sizeof(TData));
time := now - time;
showmessage('用时：'+Format('%0.4f',[time*24*60*60]) + '秒');

end;
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
creation-zy最新代码在在我的机上最用时0.1400秒，是比较稳定的。

一次分配内存然后用指针用操作是最快的。只需要0.0940秒。

下面给出一个集中了全部四种计算方式的完整版（使用了高精度计时API）：

procedure TForm1.Button1Click(Sender: TObject);
type
TData=packed record
case Integer of
0: (
IntData:Integer;
Ext1,Ext2,Ext3:Byte;
);
1: ( Bytes:array[0..6]of Byte )
end;
var
i,m:Integer;
i1,i2,i3,i4,i5,i6,i7:Byte;
Data:array of TData;
pData:^TData;
Frq,tx,ty,t,t0,t1,t2,t3:Int64;
begin
QueryPerformanceFrequency(Frq);
QueryPerformanceCounter(tx);
SetLength(Data,8347680);
QueryPerformanceCounter(ty);
t:=ty-tx
//Time for SetLength
{ #0 -- just for }
i:=0;
for i1:=1 to 30 do
for i2:=i1+1 to 31 do
for i3:=i2+1 to 32 do
for i4:=i3+1 to 33 do
for i5:=i4+1 to 34 do
for i6:=i5+1 to 35 do
for i7:=i6+1 to 36 do
begin
Data.Bytes[0]:=i1;
Data.Bytes[1]:=i2;
Data.Bytes[2]:=i3;
Data.Bytes[3]:=i4;
Data.Bytes[4]:=i5;
Data.Bytes[5]:=i6;
Data.Bytes[6]:=i7;
Inc(i);
end;
QueryPerformanceCounter(tx);
t0:=tx-ty;
{ #1 -- for and with }
i:=0;
for i1:=1 to 30 do
for i2:=i1+1 to 31 do
for i3:=i2+1 to 32 do
for i4:=i3+1 to 33 do
for i5:=i4+1 to 34 do
for i6:=i5+1 to 35 do
for i7:=i6+1 to 36 do
begin
with Data do
begin
Bytes[0]:= i1;
Bytes[1]:= i2;
Bytes[2]:= i3;
Bytes[3]:= i4;
Bytes[4]:= i5;
Bytes[5]:= i6;
Bytes[6]:= i7;
end;
Inc(i);
end;
QueryPerformanceCounter(ty);
t1:=ty-tx;
{ #2 -- for and with and Integer }
i:=0;
for i1:=1 to 30 do
for i2:=i1+1 to 31 do
for i3:=i2+1 to 32 do
for i4:=i3+1 to 33 do
begin
m:=(i1 shl 24) or (i2 shl 16) or (i3 shl 8) or i4;
for i5:=i4+1 to 34 do
for i6:=i5+1 to 35 do
for i7:=i6+1 to 36 do
begin
with Data do
begin
IntData:=m;
Ext1:=i5;
Ext2:=i6;
Ext3:=i7;
end;
Inc(i);
end;
end;
QueryPerformanceCounter(tx);
t2:=tx-ty;
{ #3 -- for and Pointer and with }
pData:=@Data[0];
for i1:=1 to 30 do
for i2:=i1+1 to 31 do
for i3:=i2+1 to 32 do
for i4:=i3+1 to 33 do
for i5:=i4+1 to 34 do
for i6:=i5+1 to 35 do
for i7:=i6+1 to 36 do
begin
with pData^ do
begin
Bytes[0]:=i1;
Bytes[1]:=i2;
Bytes[2]:=i3;
Bytes[3]:=i4;
Bytes[4]:=i5;
Bytes[5]:=i6;
Bytes[6]:=i7;
end;
Inc(pData);
end;
QueryPerformanceCounter(ty);
t3:=ty-tx;
ShowMessage(Format('耗时(秒): SetLength> %.4f #0> %0.4f #1> %.4f #2> %.4f #3> %.4f',[t/Frq,t0/Frq,t1/Frq,t2/Frq,t3/Frq]));
SetLength(Data,0);
end;


下面是几组试验数据:
耗时(秒): SetLength> 0.1190 #0> 0.2843 #1> 0.1697 #2> 0.1482 #3> 0.1996
耗时(秒): SetLength> 0.1138 #0> 0.2923 #1> 0.1665 #2> 0.1478 #3> 0.2063
耗时(秒): SetLength> 0.1152 #0> 0.2921 #1> 0.1659 #2> 0.1533 #3> 0.1998
耗时(秒): SetLength> 0.1125 #0> 0.2888 #1> 0.1683 #2> 0.1462 #3> 0.1992
耗时(秒): SetLength> 0.1125 #0> 0.2919 #1> 0.1639 #2> 0.1471 #3> 0.1996

呵呵，不同的机器的结果不同啊。
看我的结果。
－－－－－－－－－－－－－
耗时(秒): SetLength> 0.0820 #0> 0.2066 #1> 0.0868 #2> 0.0768 #3> 0.0690
耗时(秒): SetLength> 0.0832 #0> 0.2095 #1> 0.0804 #2> 0.0738 #3> 0.0711
耗时(秒): SetLength> 0.0869 #0> 0.2195 #1> 0.0783 #2> 0.0725 #3> 0.0718
耗时(秒): SetLength> 0.0874 #0> 0.2214 #1> 0.0759 #2> 0.0722 #3> 0.0708
耗时(秒): SetLength> 0.0850 #0> 0.2102 #1> 0.0766 #2> 0.0717 #3> 0.0694
耗时(秒): SetLength> 0.0834 #0> 0.2087 #1> 0.0767 #2> 0.0737 #3> 0.0700
－－－－－－－－－－－－－－－－－－－－－
我机器是CD305,2.26G,1G内存。

从结果看来，＃２用的ＣＰＵ最少，在你的机上测试因为你的ＣＰＵ比较慢，所以＃２得到了最好的结果；但是在我的机上测试时因为我的ＣＰＵ比你的快，所以我＃３的测试得到了最好的结果。

但是有一点必需清楚，SetLength会用大量的时间，因为用SetLength会对内存进行初始化。如果用GetMemory的话我的机的占用时间是０.０００１４４。

呵呵，没想到在兄台的机器上SetLength比循环赋值还要慢... 既然我们会重写每一个字
节，GetMemory应该是最好的方式了。
我的CPU是Mobile版的，可能有些布线和qqjm兄的不一样，结果有较大差别，呵呵

不知道qqjm兄有没有精力把#2和#3再结合一下呢？

努力干活ing~ 共同进步~~

呵呵，早就在搞了。
代码：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
procedure TForm1.Button2Click(Sender: TObject);
type
TData=packed record
case Integer of
0: (
IntData:Integer;
ExtData:array[0..2]of Byte );
1: ( Data:array[0..6]of Byte )
end;
var
m:integer;
i1,i2,i3,i4,i5,i6,i7:Byte;
pData:^TData;
pointer;
Frq,tx,ty,t,t0,t1,t2,t3:Int64;
str:string;
strList:Tstrings;
Const
iLength :integer =8347680 ;
begin
strList :=TstringList.Create;
try
QueryPerformanceFrequency(Frq);
QueryPerformanceCounter(tx);
p := GetMemory(iLength*sizeof(TData));
QueryPerformanceCounter(ty);
t := ty-tx;
QueryPerformanceCounter(tx);
pData:= p;
for i1:=1 to 30 do
for i2:=i1+1 to 31 do
for i3:=i2+1 to 32 do
for i4:=i3+1 to 33 do
begin
m:=(i1 shl 24) or (i2 shl 16) or (i3 shl 8) or i4;
for i5:=i4+1 to 34 do
for i6:=i5+1 to 35 do
for i7:=i6+1 to 36 do
begin
with pData^ do
begin
IntData:=m
//一次写入前4个Byte
ExtData[0]:=i5;
ExtData[1]:=i6;
ExtData[2]:=i7;
end;
Inc(pData);
end;
end;
QueryPerformanceCounter(ty);
t0 := ty-tx;
QueryPerformanceCounter(tx);
pData := p;
for i1 := 1 to 30 do
for i2 := i1+1 to 31 do
for i3 := i2+1 to 32 do
for i4 := i3+1 to 33 do
for i5 := i4+1 to 34 do
for i6 := i5+1 to 35 do
for i7 := i6+1 to 36 do
begin
with pData^ do
begin
data[0]:= i1;
data[1]:= i2;
data[2]:= i3;
data[3]:= i4;
data[4]:= i5;
data[5]:= i6;
data[6]:= i7;
end;
inc(pData);
end;
QueryPerformanceCounter(ty);
t1 := ty-tx;
QueryPerformanceCounter(tx);
pData:= p;
for i1:=1 to 30 do
for i2:=i1+1 to 31 do
for i3:=i2+1 to 32 do
for i4:=i3+1 to 33 do
begin
m:=(i1 shl 24) or (i2 shl 16) or (i3 shl 8) or i4;
for i5:=i4+1 to 34 do
for i6:=i5+1 to 35 do
for i7:=i6+1 to 36 do
begin
with pData^ do
begin
IntData:=m
//一次写入前4个Byte
ExtData[0]:=i5;
ExtData[1]:=i6;
ExtData[2]:=i7;
end;
Inc(pData);
end;
end;
QueryPerformanceCounter(ty);
t2 := ty-tx;
QueryPerformanceCounter(tx);
pData := p;
for i1 := 1 to 30 do
for i2 := i1+1 to 31 do
for i3 := i2+1 to 32 do
for i4 := i3+1 to 33 do
for i5 := i4+1 to 34 do
for i6 := i5+1 to 35 do
for i7 := i6+1 to 36 do
begin
with pData^ do
begin
data[0]:= i1;
data[1]:= i2;
data[2]:= i3;
data[3]:= i4;
data[4]:= i5;
data[5]:= i6;
data[6]:= i7;
end;
inc(pData);
end;
QueryPerformanceCounter(ty);
t3 := ty-tx;
str := Format('耗时(秒): SetLength> %.6f ＃２-1> %0.4f ＃３-1> %0.4f ＃２-2> %0.4f ＃３-2> %0.4f '
,[t/Frq,t0/Frq ,t1/Frq,t2/Frq ,t3/Frq]);
showmessage(str);
if FileExists('C:/2.txt') then strList.LoadFromFile('C:/2.txt');
strList.Add(str);
strList.SaveToFile('C:/2.txt');
finally
freeMem(p, iLength*sizeof(TData));
strList.Free;
end;
end;



＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
结果：
耗时(秒): SetLength> 0.000141 ＃２-1> 0.0937 ＃３-1> 0.0702 ＃２-2> 0.0672 ＃３-2> 0.0714
耗时(秒): SetLength> 0.000142 ＃２-1> 0.1043 ＃３-1> 0.0715 ＃２-2> 0.0699 ＃３-2> 0.0727
耗时(秒): SetLength> 0.000141 ＃２-1> 0.0979 ＃３-1> 0.0711 ＃２-2> 0.0654 ＃３-2> 0.0756
耗时(秒): SetLength> 0.000142 ＃２-1> 0.1046 ＃３-1> 0.0715 ＃２-2> 0.0709 ＃３-2> 0.0733
耗时(秒): SetLength> 0.000144 ＃２-1> 0.0937 ＃３-1> 0.0699 ＃２-2> 0.0653 ＃３-2> 0.0726
耗时(秒): SetLength> 0.000142 ＃２-1> 0.0940 ＃３-1> 0.0714 ＃２-2> 0.0691 ＃３-2> 0.0780
耗时(秒): SetLength> 0.000142 ＃２-1> 0.0942 ＃３-1> 0.0702 ＃２-2> 0.0667 ＃３-2> 0.0722
耗时(秒): SetLength> 0.000143 ＃２-1> 0.0928 ＃３-1> 0.0728 ＃２-2> 0.0658 ＃３-2> 0.0719
耗时(秒): SetLength> 0.000142 ＃２-1> 0.0974 ＃３-1> 0.0783 ＃２-2> 0.0690 ＃３-2> 0.0725
耗时(秒): SetLength> 0.000143 ＃２-1> 0.0948 ＃３-1> 0.0700 ＃２-2> 0.0675 ＃３-2> 0.0708
耗时(秒): SetLength> 0.000142 ＃２-1> 0.0940 ＃３-1> 0.0698 ＃２-2> 0.0673 ＃３-2> 0.0719

真想不到最后的结果是这样的。。。。。

恩，学到不少，不知道还有没有其他方法。

进化论告诉我们，优秀的基因互相结合会产生更加优秀的东西[]
现在，有这么多的“杂交品种”可供楼主选择，哈哈

ps: 置于显示，可以用TDrawGrid，在绘制事件中根据行列坐标读取内存信息，IntToStr后
显示给用户，完全不用拼接后在文本控件中显示。

我的天呀,这种速度,以前想也不敢想呀,学到东西了.

改进后的核心是减少了负值的次数，由7次减少为4次
IntData:=m
//一次写入前4个Byte
ExtData[0]:=i5;
ExtData[1]:=i6;
ExtData[2]:=i7;
我提供一更省时间的结构
struct zhuheint
{
unsigned int i1;
unsigned int i2;
};


最内层循环改为：
for (unsigned int o= n+1
o<36
o++)
{
a[xiabiao].i1 = (i << 24) | (j << 16) | (k << 8) | l;
a[xiabiao].i2 = (m << 16) | (n << 8) | o;
xiabiao++;
}


我机器运行时间0.108秒，比我第一次提出的节省了3/4的时间。麻烦哪位大虾转为delphi的看看

解的代码：
randomize();
int j=0;
for (int i = 0
i<100
i++)
{
j = random(TOTALKINDS);
int l1 = (a[j].i1 >> 24) &amp
0x000000ff;
int l2 = (a[j].i1 >> 16) &amp
0x000000ff;
int l3 = (a[j].i1 >> 8) &amp
0x000000ff;
int l4 = a[j].i1 &amp
0x000000ff;
int l5 = (a[j].i2 >> 16) &amp
0x000000ff;
int l6 = (a[j].i2 >> 8) &amp
0x000000ff;
int l7 = a[j].i2 &amp
0x000000ff;
Memo1->Lines->Add(IntToStr(l1)
+&quot;,&quot;+IntToStr(l2)
+&quot;,&quot;+IntToStr(l3)
+&quot;,&quot;+IntToStr(l4)
+&quot;,&quot;+IntToStr(l5)
+&quot;,&quot;+IntToStr(l6)
+&quot;,&quot;+IntToStr(l7));
}

with Data do
begin
Int1:=m;
Int2:=(i5 shl 24) or (i6 shl 16) or (i7 shl 8);
end;
Inc(i);

（#2为一个Int+3个Byte赋值，#5为两个Int赋值）
#2> 0.1615 #5> 0.1633
#2> 0.1690 #5> 0.1649
#2> 0.1643 #5> 0.1653
#2> 0.1611 #5> 0.1666

——两者似乎无甚差别... （但是，比起7个Byte版本的耗时(0.150)，普遍慢了一点点）

其实时间主要花费在界面的输出上了.免去输出我的可以不到300毫秒完成.

program Project2;

{$APPTYPE CONSOLE}

uses
SysUtils, Windows;

const
Max = 36;
var
I1, I2, I3, I4, I5, I6, I7 : Integer;
Count : Integer;
begin
Count := 0;
for I1 := 1 to Max - 6 do
for I2 := I1 + 1 to Max - 5 do
for I3 := I2 + 1 to Max - 4 do
for I4 := I3 + 1 to Max - 3 do
for I5 := I4 + 1 to Max - 2 do
for I6 := I5 + 1 to Max - 1 do
for I7 := I6 + 1 to Max do
begin
Inc(Count);
{
不输出到屏幕只有300毫秒
输出到屏幕非常费时,最好不要输出.等死你啊
}
//writeln(Format('%.8d: %.2d;%.2d;%.2d;%.2d;%.2d;%.2d;%.2d',
// [Count, I1,I2,I3,I4,I5,I6,I7]));
end;

MessageBox(0, PChar(Format('共%d种组合!', [Count])), '', MB_OK or MB_ICONINFORMATION);
end.

楼上的，请注意审题，如果只要Count，算几个乘除法就可以了，何必多层循环呢？

楼上的也注意,我的求出了所有的组合,紧紧没有输出而已.要输出的话把我的中间的注释去掉就行了.只是屏幕打印太毫时间.也可以存起来一起输出

to:wr960204 你的组合在那里？？ 你注释了输出后，你的代码只是取得了组合的个数而已。

你也要注意了，现在的代码生成这个组合只需要不到100毫秒。

真有意思...

看来算法的优化真的很有深度,值得研究再研究.

精彩!!!
C2.3G,DDR256M,再加根256M的内存,速度能提高多少.

好东西,呵呵.