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

香川群子 · 发表于 2012-10-4 19:21

本帖最后由香川群子于 2012-10-4 19:40 编辑

Dim sj, jg(), m%, k, h '定义公用变量
Sub kagawa_3() '递归组合求和-3 【倒序递归剪枝+末位计算提速】
tms = Timer
h = [b1] '获取目标和值
m = [a1].End(4).Row: ' sj0 = [a1].Resize(m) '获取原始数据个数m（A列最大行数）
[a1].Resize(m).Sort [a1], 1, , , 2 '如果原始数据乱序则先升序排序
sj = [a1].Resize(m, 2): ' [a1].Resize(m) = sj0 '排序处理后原始数据恢复原状
sj(1, 2) = sj(1, 1)
For i = 2 To m
sj(i, 2) = sj(i - 1, 2) + sj(i, 1)
Next
'以上为计算升序时的累计和值，以便剪枝时使用
ReDim jg(65536, 0) '定义输出结果的数组jg
k = 0 '符合条件个数k初始化
' Open "D:\Documents\Result.txt" For Output As #1
' Print #1, m & " / " & h
'直接输出结果到记事本文件时打开记事本文件的代码，如果不用则注释掉
Call dgH3(0, "", m + 1) '调用递归过程代码，注意到 i 参数为m+1开始
' Print #1, "Result: " & k & "/ Calc " & cnt & "/ Time: " & Format(Timer - tms, "0.000s")
' Close #1
'直接输出结果到记事本文件时关闭记事本文件用的代码，如果不用则注释掉
If k > 0 And k < 65536 Then [f:f] = "": [f1].Resize(k) = jg '输出结果数组jg中的值到F列
MsgBox "Result: " & k & "/ Calc " & cnt & " Time: " & Format(Timer - tms, "0.000s")
End Sub
Sub dgH3(r, s$, i%) '递归过程 r=和值累计、s=文本计算式结果、i=递归位置参数（对应第几个元素）
Dim j%
x = h - r '【目标和值h】-【当前和值r】的【差值x】
For j = 1 To i - 1 '只能用正序法检查1~i-1的元素范围中的值sj(j,1)正好等于差值x
If x = sj(j, 1) Then
If k < 65536 Then
jg(k, 0) = s & "+" & x '按计算顺序正向输出结果
' jg(k, 0) = "+" & x & s '按计算顺序反向输出结果
End If
k = k + 1
' Print #1, s & "+" & x '结果输出到记事本文件时用的输出代码，不用则注释掉
' Application.StatusBar = "kagawa: " & k & " / " & s & "+" & x '当前进度显示，调试时可用
Exit For '找到符合条件的末位值时即可退出，否则要循环到底。
End If
Next
'以上代码，即为末位计算法的实现，提速效果明显（大大降低了无效递归的循环次数。也可以算是一种剪枝）
For j = j - 1 To 1 Step -1 '从上面计算差值得到相等值的前一位置j-1开始倒序检查
If x >= sj(j, 1) Then 'If Not r + sj(j, 1) > h Then '如果本位置值sj(j,1)加上累计r值以后还是不大于目标和值h，则可进入递归，否则剪枝退出。
If x > sj(j, 2) Then 'If r + sj(j, 2) < h Then
Exit For '如果倒序递增到该位置的累计和值sj(j,2)加上累计r值以后还是不足目标和值h时就可提前退出。这也是剪枝提速的关键。
Else 'If Not r + sj(j, 2) < h Then
Call dgH3(r + sj(j, 1), s & "+" & sj(j, 1), j) '按计算顺序正向输出结果
' Call dgH3(r + sj(j, 1), "+" & sj(j, 1) & s, j) '按计算顺序反向输出结果
End If
End If
Next
End Sub

复制代码

香川群子 · 发表于 2012-10-4 20:31

本帖最后由香川群子于 2012-10-4 20:32 编辑

彭希仁发表于 2006-2-20 15:26
完全可以在1分钟之内运行完的，接着优化一下吧兄弟。

[此贴子已经被作者于2006-2-20 15:37:41编辑过]

   题目                         彭版数组倒序剪枝          香川正序递归+末位剪枝    香川倒序递归剪枝+末位剪枝
1-20自然数求和=88    计算 0.41s 含输出 0.63s 计算 0.36s 含输出 0.57s    计算 0.09s 含输出 0.30s
1-99奇数求和=150    计算 1.63s 含输出 2.14s 计算 0.53s 含输出 0.87s    计算 0.34s 含输出 0.68s
1-100自然数求和=100 计算 19.5s 不含输出       计算 3.6s 不含输出          计算 2.7s 不含输出

速度大为提高。

香川群子 · 发表于 2012-10-6 11:07

单纯显示计算速度和结果数的递归过程代码，看上去也很简单。

Sub dgH33(r, s$, i%)
Dim j%

x = h - r
For j = 1 To i - 1
If x = sj(j, 1) Then k = k + 1: Exit For
Next

For j = j - 1 To 1 Step -1
If x >= sj(j, 1) Then If x > sj(j, 2) Then Exit For Else Call dgH33(r + sj(j, 1), s & "+" & sj(j, 1), j)
Next
End Sub

香川群子 · 发表于 2012-10-6 11:34

Dim sj, jg(), k
'递归组合求和代码-4，原理是把每次计算的不足值r传递下去。
Sub kagawa_4()
tms = Timer
h = [b1]
m = [a1].End(4).Row: ' sj0 = [a1].Resize(m)
[a1].Resize(m).Sort [a1], 1, , , 2 '如果原始数据乱序则先升序排序
sj = [a1].Resize(m, 2): ' [a1].Resize(m) = sj0 '排序处理后原始数据恢复原状
sj(1, 2) = sj(1, 1)
For i = 2 To m
sj(i, 2) = sj(i - 1, 2) + sj(i, 1)
Next
ReDim jg(65536, 0)
k = 0: tms = Timer
Open "D:\Backup\我的文档\Rslt3.txt" For Output As #1 '打开输出用记事本文件
Print #1, m & " / " & h
Call dgH4(h, "", m + 1) '调用递归求和代码，输入[目标值]、[计算过程结果文本表达式]、[起始位置代码]
Print #1, "Result: " & k & "/ Time: " & Format(Timer - tms, "0.000s")
Close #1
If k > 0 And k < 65536 Then [f:f] = "": [f1].Resize(k) = jg
MsgBox "Result: " & k & " / Time: " & Format(Timer - tms, "0.000s")
End Sub
'下面是递归求和代码
Sub dgH4(r, s$, i%) '参数为：[目标值]、[计算过程结果文本表达式]、[起始位置代码]
Dim j%
For j = 1 To i - 1
If r = sj(j, 1) Then
If k < 65536 Then jg(k, 0) = s & "+" & r
k = k + 1
Print #1, s & "+" & r
Exit For
End If
Next
For j = i - 1 To 2 Step -1
If r > sj(j, 1) Then
If r > sj(j, 2) Then
Exit For
Else
Call dgH4(r - sj(j, 1), s & "+" & sj(j, 1), j)
End If
End If
Next
End Sub

复制代码

这个dgH4的递归计算过程，和我前面的dgH3的递归过程是极其相似的。
主要差别是：
dgH3 每次【从0开始】起，用【加法】计算累计和值r，并传递到下一层递归，
然后查找本次递归的【累计和值r】和【目标值h】之间的【差值x】是否在原始数组元素中存在。

dgH4 从【目标值开始】起，用【减法】计算当前不足值r，并传递到下一层递归，
然后直接查找本次递归的【累计余额值r】是否在原始数组元素中存在。

本来dgH4代码因为减少了数学计算次数，应该速度略有提高，
但结果发现速度反而有所降低。原因是：
由于算法的微小差异，造成循环次数略有不同。（dgH4的检查循环次数略微多一些）

但是，如果计算目标的数值较大，不是100而是几千万数量级别时，
实际dgH4的代码计算速度会稍快于dgH3的代码计算速度。这个当然是由于计算方式不同带来的影响啦。

呵呵。

香川群子 · 发表于 2012-10-7 13:50

今天又做了些改进。

加入了抽取元素个数n的限制条件。

在[b2]单元格中写入n=0-m范围的整数，
如果n=0 则取数个数无限制 → 输出全部结果。
……
如果n=2 则仅仅计算返回【2个数相加=目标和值】的结果，

…… 以此类推。

呵呵。这么做的最大好处，应该是可以减少计算量。

彭版的数组方法是否可以这么去改……可能比较麻烦。
当然有一个偷懒的方法是对符合条件的结果进行抽取个数的比对检查……但是这样一来就无法缩短计算时间了。

灰袍法师 · 发表于 2012-10-7 17:52

本帖最后由灰袍法师于 2012-10-7 19:09 编辑

香川群子发表于 2012-10-7 13:50
今天又做了些改进。

加入了抽取元素个数n的限制条件。

不错不错。
不过应该增加输出多少个结果的选项，如果只需要一个结果，就没必要算几万个出来。
另外，剪枝法的弱点还是无法避免，以下的数据就要好长好长时间
28个100 + 2 个101
求和 =1501 需要很长时间
求和 =1502 瞬间求出结果

香川群子 · 发表于 2012-10-7 20:00

灰袍法师发表于 2012-10-7 17:52
不错不错。
不过应该增加输出多少个结果的选项，如果只需要一个结果，就没必要算几万个出来。
另外，剪 ...

那如果改用升序法代码，立即就能出结果啦。

灰袍法师 · 发表于 2012-10-7 20:38

本帖最后由灰袍法师于 2012-10-7 20:48 编辑

香川群子发表于 2012-10-7 20:00
那如果改用升序法代码，立即就能出结果啦。

那，又如果是
1
1
23个100
101
101
求和 = 1301
那么不管用升序还是降序，都很慢。中间多插一个100，耗时就x2
也就是说，如果可行解分布在数据的前段，后段，那么就没法迅速把这些数据找出来了。
貌似先随机排序，指定时间内找不到解就再次随机排序，这样可以部分解决这个问题。
但无法避免最坏情况下就是 2^n 时间复杂度，这可以说是无法解决的问题。
你的程序比彭希仁的快得多，而且适用范围更广，一般来说，实际的数据很少碰到正反序都倒霉的情况，呵呵。

彭希仁 · 发表于 2012-10-8 11:38

香川群子发表于 2012-10-4 20:31
题目彭版数组倒序剪枝香川正序递归+末位剪枝香川 ...

1~100的组合=100的组合,测试只需要3.48秒啊

香川群子 · 发表于 2012-10-8 12:50

彭希仁发表于 2012-10-8 11:38
1~100的组合=100的组合,测试只需要3.48秒啊

你这个是用的42楼附件代码吧。

速度确实比较快了，但程序有bug，只能处理自然数序列。
如果是随机整数，或间隔>1的等差数列，就不能计算得到正确结果了……程序有错误。

例如，间隔=2的奇数序列：1,3,5,7,9,11,13,15,17,19,21
求目标和值=20时，正确结果仅 7个：
9+7+3+1
11+5+3+1
11+9
13+7
15+5
17+3
19+1

但你42楼程序计算结果返回了 9个……多了两个错误的结果：
9+7+3+1
11+5+3+1
11+7+3 = 21
11+9
13+5+3 = 21
13+7
15+5
17+3
19+1

因此，我并没有采用你42楼的代码来比较，而是用了你顶楼的正确代码作为比较。
而顶楼的代码，相比较速度就慢了。

呵呵。

		自动登录	找回密码
密码			免费注册

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

评分

评分

点评