[开_86] 比速度,看谁的程序更快.

东亚五金

为啥子要这个样子算呢，这是为什么呢{:soso_e113:}

五点水

带小数点怎么操作

梁ll

亲们  如果数据都是百万以上  有千万和亿的呢   怎么做呢？

awaw0913

请问一下，有小数点的情况应该怎么解决呢？谢谢！

香川群子

彭希仁 发表于 2006-8-26 14:56
QUOTE:以下是引用UNARTHUR在2006-7-3 16:04:35的发言：哪个答案是7秒算完的呀？贴出来了吗？我想看看。在本 ...

新的递归组合求和代码 研究出来啦。


一开始，用了正常递归代码，然后为了提高效率，
在每次递归循环之前，判断一下当前【求和结果】+【下一递归元素】之和，是否超出【目标值】。
如果超出则Exit For终止循环。
    For j = i + 1 To m
        If h - r < sj(j, 1) Then Exit For        
        Call dgH1(s & "+" & sj(j, 1), r + sj(j, 1), j, t + 1)
    Next j

但是这样仍然会产生很多次的多余循环，
而且对象元素越多，求和目标越大，冗余遍历计算次数越多。

比如：
1-100自然数求和值=100时，递归遍历总计 5272174次，比计算结果的 444793多了将近12倍。



………………
后来，为了完成彭版的题目，
想到了递归末位直接用计算法确定的思路。

经过代码研究、debug最后成功了。
目前的递归代码，完全没有冗余，因此效率达到了递归的极限。

经确认，比彭版42楼的7秒以内代码速度快50%（包括输出结果到记事本文件的时间）
而不含输出文件的速度比较，则比彭版算法要快2-3倍。

呵呵。总算完成了作业。

香川群子

公布递归代码以及附件：

1. 
   
2. Dim sj, jg(), m%, k, h% '设置公用变量
   
3. 
   
4. Sub kagawa_2() '递归组合求和-2
   
5.     tms = Timer
   
6.     m = [a1].End(4).Row
   
7.     h = [b1]
   
8. '    sj0 = [a1].Resize(m): [a1].Resize(m).Sort [a1], 1, , , 2 '如果原始数据乱序则先升序排序
   
9.     sj = [a1].Resize(m)
   
10. '    [a1].Resize(m) = sj0 '排序处理后原始数据恢复原状
    
11. '    ReDim jg(65536, 0)
    
12.     k = 0
    
13.    
    
14.     Open "D:\Result.txt" For Output As #1  '打开记事本文件用来保存输出结果，文件地址可以自己修改
    
15. '    Open "D:\Documents\Result.txt" For Output As #1
    
16. '    Open "D:\Backup\我的文档\Result.txt" For Output As #1
    
17.    
    
18.     Print #1, m & " / " & h '输出结果写入文件头信息
    
19.    
    
20.     Call dgH2("", 0, 0, 0)  '调用递归过程开始计算
    
21.    
    
22.     Print #1, "Result: " & k & "/ Time: " & Format(Timer - tms, "0.000s") '输出结果写入文件尾信息
    
23.     Close #1 '关闭记事本文件
    
24. 
    
25. '    If k < 65536 Then [d1].CurrentRegion = "": [d1].Resize(k) = jg
    
26.     MsgBox "Result: " & k & " Time: " & Format(Timer - tms, "0.000s")
    
27. End Sub
    
28. 
    
29. Sub dgH2(s$, r, i%, t%) '关键的递归过程代码
    
30.     Dim j%
    
31.    
    
32.     If h - r >= sj(i + 1, 1) Then
    
33.        '直接计算h-r即【目标值】-【当前结果】作为【计算末位值】，如果该末位值大于等于递归下一位置值则符合条件。      
    
34. '        If k < 65536 Then jg(k, 0) = s & "+" & h - r
    
35. '        Print #1, s & "+" & h - r '向记事本中写入本次递归计算结果。即【当前递归和r】+【计算末位值h-r】
    
36.         k = k + 1
    
37.     End If
    
38.    
    
39.     For j = i + 1 To m
    
40.         If h - r - sj(j, 1) < sj(j + 1, 1) Then
    
41.             Exit Sub '提前计算下一递归结果的【末位计算值h - r'】是否有效，无效则退出递归循环r'=r + sj(j, 1)
    
42.         Else
    
43.             Call dgH2(s & "+" & sj(j, 1), r + sj(j, 1), j, t + 1)
    
44.         End If
    
45.     Next j
    
46. End Sub
    

复制代码

从结果看，代码算法的改变不是特别复杂。但效果显著。

香川群子

附件代码中输出记事本语句被注释了，所以得到的只是纯粹的组合计算时间。

如果是 1-100求和=100，则彭版42楼代码平均计算耗时 3.8秒，而我的递归代码只要1.93秒 快1.9倍。

如果是 1-120求和=120，则彭版42楼代码平均计算耗时 18.4秒，而我的递归代码只要9.6秒 快1.9倍。


…………
进一步发现，如果原始数据不是自然数序列，而是间隔不均等元素对象的话，
彭版42楼代码立即就会产生计算错误。
彭版在顶楼的代码已经可以正确计算了，但时间就不对了。1-100求和=100，经计算就耗时 14秒了。


我现在的递归代码也有问题。明天再想办法，好像稍加改进应该就可以适应了。

香川群子

研究了一下彭版顶楼附件的代码，
是数组计算最大值递增剪枝处理方法。

和我的递归代码比，差异如下：

如果是求和目标值较小，比如1-100求总和100时，递归代码效率最高。

因为我的递归方法是从最小值开始递增计算的，
对于这样特定的题目，则每一次计算结果都是有效的。


但是，如果目标和值较大，即必须最大值参与进来时，
递归的方法就很慢了，因为必须计算所有的递归组合才能到达最大值部分。

而彭版的数组有效最大值递增组合方法，这时候的效率最高。


如附图，总的来说，还是彭版顶楼的数组方法最好。

香川群子

对于原始数据非自然递增序列时的bug改进代码如下：

仅仅加了一个循环，检查h-r值是否存在即可。基本不影响速度。

1. Dim sj, jg, m%, h, k, cnt
   
2. Sub 递归组合求和()
   
3.     tms = Timer
   
4.     m = [a1].End(4).Row: 'sj0 = [a1].Resize(m)
   
5.     [a1].Resize(m).Sort [a1], 1, , , 2
   
6.     sj = [a1].Resize(m): '[a1].Resize(m) = sj0
   
7.     h = [b1]: ReDim jg(65535, 0): k = 0: cnt = 0
   
8.     Open "D:\Documents\Result.txt" For Output As #1
   
9.    
   
10.     Call dgH(0, "", 0)
    
11.    
    
12.     Close #1
    
13.     [d1].CurrentRegion = "": [d1].Resize(k) = jg
    
14.     MsgBox k & " / " & cnt & Format(Timer - tms, " 0.000s")
    
15. End Sub
    
16. Sub dgH(r, s, i%)
    
17.     Dim j%
    
18.     cnt = cnt + 1
    
19.    
    
20.     x = h - r
    
21.     For j = i + 1 To m
    
22.         If x = sj(j, 1) Then
    
23.             jg(k, 0) = s & "+" & x
    
24.             Print #1, s & "+" & x
    
25.             k = k + 1
    
26.             Exit For
    
27.         ElseIf x < sj(j, 1) Then
    
28.             Exit For
    
29.         End If
    
30.     Next
    
31.    
    
32.     For j = i + 1 To m - 1
    
33.         If x - sj(j, 1) < sj(j + 1, 1) Then
    
34.             Exit Sub
    
35.         Else
    
36.             Call dgH(r + sj(j, 1), s & "+" & sj(j, 1), j)
    
37.         End If
    
38.     Next
    
39. End Sub

复制代码

香川群子

终于研究成功~！

参照【彭版】的【数组倒序剪枝法】思路，
结合我的末位计算搜寻法提速，并写成了递归方法的代码。

结果速度是到达了最快……纯计算部分比彭版的数组代码快大约 7倍。


呵呵。

上附件。


附图分别为：
我的【正序递归+末位计算】、
【彭版倒序数组剪枝】、
以及我的【倒序递归剪枝+末位计算】
这三种代码的内部循环次数比较。

显然我的【倒序递归剪枝+末位计算】法内部循环次数最少，所以速度也最快。