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

以福彩36选7为蓝本,800多万个不重复组合,你们可以将时间压缩到多少？我用creation-zy的组合代码，不显示都已经超出了一秒，但是有一个人居然可以在0.281秒处理完成(T2250,512M),但仅循环也都要0.262秒呀(带进度条),仅有的0.02秒就是用来赋组合出来的值?他是怎么做到的呀?

这个到底是什么算法呀,800多万个组合,居然只要0.281秒就可以完成.

这个内存该怎么控制突然暴增带来的负面呀? (他的内存增加只占40M左右,总占用量大约为60M以下)任务管理器中

使用creation-zy的算法,前几次使用都超过数秒,组合几次之后,可以在2秒内实现,但是离0.281秒,那相差太远了.

不知道他有没有取巧的成份,如果没有,那么这个算法的确值得探讨.

又代码么？

这应该是他的算法写得好。
我以试过，2G的CPU在内存中修改200M的数据约0.31秒。
如果7字节一条记录，,8,347,680个记录就占55.72M的内存，只要算法写得好0.28秒内得到这个组合不是不可能的。
有没有相关的代码，我正在看《Delphi算法与数据结构》，有空也研究一下这个。

要比快吗?

去研究一下快速排算法,那可是世界上最快的算法了

800万 0.5秒内不算快吧?

没有代码,我看到他的程序.0.28秒还不算快?仅是循环不赋值就已经是0.26了

研究了一下，834多万组合加上显示0.49秒，给分吧
(P4,2.8G ,512M内存)

void __fastcall TForm1::Button1Click(TObject *Sender)
{
const int TOTALKINDS = 8347680;
LARGE_INTEGER litmp;
LONGLONG QPart1,QPart2;
double dfMinus, dfFreq, dfTim;
QueryPerformanceFrequency(&litmp);
dfFreq = (double)litmp.QuadPart;// 获得计数器的时钟频率
QueryPerformanceCounter(&litmp);
QPart1 = litmp.QuadPart;// 获得初始值

int icount = 0;
zhuhe *a = new zhuhe[TOTALKINDS];
int xiabiao = 0;
for (int i = 0
i<30
i++)
{
for (int j = i+1
j<31
j++)
{
for (int k = j+1
k<32
k++)
{
for (int l = k+1
l<33
l++)
{
for (int m = l+1
m<34
m++)
{
for (int n = m+1
n<35
n++)
{
for (int o= n+1
o<36
o++)
{
a[xiabiao].i1 = i;
a[xiabiao].i2 = j;
a[xiabiao].i3 = k;
a[xiabiao].i4 = l;
a[xiabiao].i5 = m;
a[xiabiao].i6 = n;
a[xiabiao].i7 = o;
xiabiao++;
icount++;
}
}
}
}
}
}
}
randomize();
int j=0;
for (int i = 0
i<100
i++)
{
j = random(TOTALKINDS);
Memo1->Lines->Add(IntToStr(a[j].i1)
+&quot;,&quot;+IntToStr(a[j].i2)
+&quot;,&quot;+IntToStr(a[j].i3)
+&quot;,&quot;+IntToStr(a[j].i4)
+&quot;,&quot;+IntToStr(a[j].i5)
+&quot;,&quot;+IntToStr(a[j].i6)
+&quot;,&quot;+IntToStr(a[j].i7));
}
delete a;

QueryPerformanceCounter(&amp;litmp);
QPart2 = litmp.QuadPart;//获得中止值
dfMinus = (double)(QPart2-QPart1);
dfTim = dfMinus / dfFreq;// 获得对应的时间值，单位为秒
Label1->Caption = (String)(dfTim);
Label2->Caption = (String)(icount);
}

我改回DELPHI代码再试试看

struct zhuhe
{
char i1;
char i2;
char i3;
char i4;
char i5;
char i6;
char i7;
char i8;

};
定义 char i8;是为了字节对齐可以提高0.03秒

你改回pascal语言行不行?

procedure TForm1.Button1Click(Sender: TObject);
type
TData = packed Record
data :array[0..6]of byte;
end;

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

begin
time := now;
ilength := 8347680;
SetLength(Data,iLength);
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
pData := @Data;
pData^.data[0]:= i1;
pData^.data[1]:= i2;
pData^.data[2]:= i3;
pData^.data[3]:= i4;
pData^.data[4]:= i5;
pData^.data[5]:= i6;
pData^.data[6]:= i7;
inc(i);
end;
time := now - time;
showmessage('用时：'+Format('%0.4f',[time*24*60*60]) + '秒')
end;

ＬＺ自己测结果吧。。。

将qqjm兄的最内层代码改成：
with Data 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(i);
速度可进一步提高（耗时减少为原来的60%左右 奔四 1.6G 约0.26秒）

for循环嵌套肯定比递归要快得多，另外，还没有字符串拼接

唔——看来，只有动态生成机器码才能在绝对速度上与别人一较高下了

qqjm兄的代码运行时间为:0.2340秒
经过creation-zy修改后的代码运行时间为:0.1870秒
比想象中的都快......

to creation-zy:
inc(i)应该在with里面吧?要不i就不进入循环了.
with Data do
begin
data[0]:= i1;
data[1]:= i2;
data[2]:= i3;
data[3]:= i4;
data[4]:= i5;
data[5]:= i6;
data[6]:= i7;
inc(i);
end;

两人的速度差不多,都是在0.1870-0.2040之间,刚才creation-zy的快了0.04,是因为i没有进行赋值.

procedure TForm1.Button1Click(Sender: TObject);
type
TData=packed record
Data:array[0..6]of Byte;
end;
var
iLength:integer;
i,i1,i2,i3,i4,i5,i6,i7: integer;
pData : ^TData;
t,t1:LongWord;
Data:array of TData;
begin
t1:=GetTickCount;
SetLength(Data,8347680);
t:=GetTickCount;
t1:=t-t1;
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
data[0]:= i1;
data[1]:= i2;
data[2]:= i3;
data[3]:= i4;
data[4]:= i5;
data[5]:= i6;
data[6]:= i7;
end;
Inc(i)
//位于最内层循环，没有错误
end;
t:=GetTickCount-t;
ShowMessage(Format('耗时: SetLength> %.3f 秒 for> %0.3f 秒',[t1*0.001,t*0.001]));
end;


Intel(R) Pentium(R) M processor 1400MHz [x86 Family 6 Model 9 Stepping 5] (L2 cache: 1024 KB) Ext.clock: 133 MHz
耗时: SetLength> 0.110 秒 for> 0.151 秒

不用With的结果
耗时: SetLength> 0.100 秒 for> 0.501 秒

在采用了With算子之后，运算速度提高了3倍多（注意到这里分配的空间非常大（有几十
M），必然会用不短的时间，我对SetLength的耗时也进行了监视）。

ps: with在Delphi中不仅仅是为了语法的简洁而引入的——它会将变量放在寄存器中，极大
的提高访问速度。你在循环内设定断点，然后在运行后用Ctrl+Alt+C看看Delphi生成的机器
码就知道了。

（已经修正）
呵呵，用with是比较快些。最好的记录是0.1720秒。
这个速度应该是极限了，但是用GetMemory申请内存，速度可以加快，在0.093-0.1100之间，，结果速度提升。
--－－－－－－－－－－－－－－－－
procedure TForm1.Button1Click(Sender: TObject);
type
TData = Record
data :array[0..6]of byte;
end;

var
iLength:integer;
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;
time := now - time;
showmessage('用时：'+Format('%0.4f',[time*24*60*60]) + '秒');
freeMem(p, iLength*sizeof(TData));
end;

在Delphi语言的层面上再次进行优化：

procedure TForm1.Button1Click(Sender: TObject);
type
TData=packed record
case Integer of
0: (
IntData:Integer
//前4个Byte可以用一个整数占位
Ext1,Ext2,Ext3:Byte //后面3个Byte
);
1: ( Data:array[0..6]of Byte )
end;
var
i,m:Integer;
i1,i2,i3,i4,i5,i6,i7:Byte;
t,t1:LongWord;
Data:array of TData;
begin
t1:=GetTickCount;
SetLength(Data,8347680);
t:=GetTickCount;
t1:=t-t1;
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
//将前4个数字存放在一个Integer中（位于外层循环，对效率几乎无影响）
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
//一次写入前4个Byte，提速
Ext1:=i5;
Ext2:=i6;
Ext3:=i7;
end;
Inc(i);
end;
end;
t:=GetTickCount-t;
ShowMessage(Format('耗时: SetLength> %.3f 秒 for> %0.3f 秒',[t1*0.001,t*0.001]));
SetLength(Data,0);
end;


耗时: SetLength> 0.100 秒 for> 0.130 秒

相对于单纯的with加速，效率提高了约10% 如果还要提速的话，不可避免的要到汇编
代码层面了（我相信，如果利用MMX扩展寄存器存放循环变量，速度还可以提高）。

to :creation-zy
加起来是0.23秒了，速度并没有加快啊！

to :creation-zy
为什么你的代码在我的机上运行不了的？
[Error] Unit1.pas(115): Operator not applicable to this operand type
这个错误指向Inc(i);后面的那个end;