★我設計的組合算法★20取10，0.39秒

灰袍法师 · 发表于 2010-10-30 00:59

其实楼主你的算法并没有比那一个更快，不过也没有更慢。

因为你的VBA是存储可选数值的阵列编号，即 Arr(1) = 1, Arr(2)=0, Arr(3)=1 Arr(4) = 1 ....

而彭希仁的VBA是存储可选数值的输出结果即 "1+3+4" ，如果去掉计算这一个string的语句，那么他的combin(20,10)只需0.08秒。

可见主要速度差别是计算数字会比计算一个string型快而已，

如果你最后还是要生成string的结果，那么其实速度差不多。

你和彭希仁的算法应该是一样的，都是每个选择的数字对应一个阵列的下标，然后只加减这个下标就可以取出不同的阵列组合，所以计算速度也不会有什么差别，最多就是相差数倍，排除输出结果的不同格式，可以认为是无差别。

不过你输出结果到excel worksheet的方法不对。

For X = 1 To 組合數
      For Y = 1 To 選數
         Cells(X, Y) = 組合陣列(Y, X)
      Next Y
Next X

这一段是非常慢的，应该直接计算出 range(cells(1,1), cells(X,Y) ).value = 組合陣列

最后，以后讨论问题应该上传附件，而不是贴代码，更不要用中文名字，你的中文代码在我的简体Excel里面全显示是红字。

彭希仁的代码计算combin(29,10) 不生成组合的string，20030010 个解! 耗时6.57秒
生成组合的string则是 20030010 个解! 耗时52.46秒

彭希仁的代码计算combin(30,10) 不生成组合的string，30045015 个解! 耗时9.81秒
生成组合的string则是 30045015 个解! 耗时77.03秒

你的代码计算combin(29,10)是 23.15088秒-共20030010筆

你的代码计算combin(30,10)会导致死机，原因是内存不够了。你应该把on error resume next去掉，或者增加内存不够时的错误处理，不然一旦组合数过多，就必定死机的啦。

可以考虑一下阵列用integer型，虽然计算慢一些，但是内存少用一半吖！而且根本没有人会去列举 combin(32767,2)的嘛

甚至byte也是可以考虑的。。。。。。combin(255,4)也已经是很大的数字了

[ 本帖最后由灰袍法师于 2010-10-30 06:47 编辑 ]

linyancheng · 发表于 2010-10-30 14:21

樓上的真是好心人，我發這帖也值得了，學到了不少，謝謝！

你說不更快，也不更慢，指的是算法，對吧？

可是後面的實驗，卻相差不少，是因為算法以外的其他因素，對嗎？和內存有關嗎？

你說會死機，我倒是沒試過這麼大的數值，那為什麼彭版主的不會死機？是因為
on error resume next這一句有關嗎？那他是如何做錯誤處理的？為什麼他的內存不會不夠？

灰袍法師做這個比較一定有更改彭版主的代碼為輸出成一個完整的數值陣列的型態，可不可以分享？因為我還看不太懂，沒辦法改。

不用中文，我自己看都很吃力，我可以轉成簡體字就沒問題。

如果把純數值譬如「1~20」換成有內容的「陣列(20)」來進行組合，肯定是比較耗時的。

linyancheng · 发表于 2010-10-30 14:40

續樓上，我又想一想，我猜想，
29取10的實驗的差別是不是因為，其實把彭版主的寫入txt功能略過，可是實際上並沒有存成一個完整陣列，所以自然沒有內存的問題，也沒有錯誤的問題，所以我的會有這些問題，而且這也導致速度變慢？

之前從來也沒遇過內存不足的問題，設定資料型態時也不會考慮內存的問題，真沒想到設計組合算法就遇到了。

本來只能算到27取10，
我把long改成integer，可以算到28取10
把integer改成byte，可以算到29取10
我的電腦算29取10，並記錄為完整陣列，共耗時57.92188秒。

最後聲明，做這個並不是要和別人比較、競賽，我只是看不懂別人的代碼，所以才自己想算法（當然別人看我的代碼也不一定懂），一開始很慢，才提出來討論、求教，謝謝！

[ 本帖最后由 linyancheng 于 2010-10-30 15:13 编辑 ]

hanter007 · 发表于 2010-10-30 15:26

楼主很好的钻研精神..学习一下..

灰袍法师 · 发表于 2010-10-30 20:06

可是後面的實驗，卻相差不少，是因為算法以外的其他因素，對嗎？和內存有關嗎？
29取10的實驗的差別是不是因為，其實把彭版主的寫入txt功能略過，可是實際上並沒有存成一個完整陣列，所以自然沒有內存的問題，也沒有錯誤的問題，所以我的會有這些問題，而且這也導致速度變慢？
===============================================================================
是的，我说程式速度一样，是指算法的复杂度一样，实际运行时间相差几倍这是可以忽略不计的。

只要随着combin(X,N)的增加，程式的时间还是一样地按比例增加，那么就可以认为是一样的速度。

因为速度的差异仅仅是代码的不同，也许是for...next 跟 do...loop的不同，也许是用数字存储还是用string存储的不同，甚至只是用了long型还是byte型的不同，这些都是可以忽视的。

彭版主的程式并没有存储完整阵列，很可能他也是考虑到内存会不足，所以选择写入硬碟

其实写入硬碟也没有好多少，组合数的增加是很快的，数字再多一些填满硬碟也很容易，最好的做法是

先计算一下总的组合数是多少，高于一定数值例如1000万，就干脆不要算了。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝
你說會死機，我倒是沒試過這麼大的數值，那為什麼彭版主的不會死機？是因為
on error resume next這一句有關嗎？那他是如何做錯誤處理的？為什麼他的內存不會不夠？
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
你的程式死机是因为 redim 组合阵列 (Y,N) 这一句出错，出错是因为不够内存

但是你有 on error resume next，所以程式会从出错的地方继续执行，也就是再执行 redim 组合阵列(Y,N)，结果就无限死循环了。彭版主的程式不存储完整阵列，所以内存不会不够，但是用硬碟存储，硬碟会不够，哈哈哈。

我也没有把彭版主的程式改为输出完整阵列，因为这个是毫无意义的，如果真的要逐一处理每个组合，那么在生成这个组合的时候，就调用处理代码好了，先存起来，然后另一个程式去处理，必定会碰到组合数太大的问题（除非你之前设定组合数超过1千万就不处理之类。）

最后，附件是楼主和彭希仁的组合生成算法，我略有修改，主要是把彭希仁版主的代码改了变量类型，这样可以避免不同类型数据混合计算减慢速度，另外取消输出到文档，改为模拟输出到阵列

结果就跟楼主的程式一样快了，这也证明了我之前说的话，楼主的程式跟彭版主的程式，速度是一样的。

其实只要用的算法一样，程式的速度就肯定会一样，实际代码的数倍差异是可以不考虑的。

[ 本帖最后由灰袍法师于 2010-10-30 20:08 编辑 ]

linyancheng · 发表于 2010-10-30 23:53

灰袍法師真是很用心，令人感動，我想受益的除了我，很多人都因此受益，功能無量！

的確，我最後覺得組合的結果動輒幾十幾百萬，應用起來十分頭痛，可能要改變程式架構，把組合數降低才行。

如果真的要儲存起來，再讓後續代碼應用，那存成陣列會比存成文字檔，讀取上效率較高，但較有內存問題，所以邊生成組合邊進行後續代碼，在某些情況的確是可以考慮的方式。

[ 本帖最后由 linyancheng 于 2010-10-31 00:03 编辑 ]

lbch123 · 发表于 2010-10-31 07:44

跟随大师们学习！

sunsoncheng · 发表于 2010-10-31 08:39

ReDim Preserve 会慢吗?
还真没有试过

看来我的程序也得重新思考过才行

这样的讨论很好!

linyancheng · 发表于 2010-10-31 12:36

我再把：
If 組合陣列(X, N) + 1 <= 總數 + 1 - X Then
改成：
If 組合陣列(X, N) < 總數 + 1 - X Then
又快了一些。
這算是不小心未優化到的部分。

結果在10樓。

灰袍法师 · 发表于 2010-10-31 17:21

原帖由 linyancheng 于 2010-10-31 12:36 发表
我再把：
If 組合陣列(X, N) + 1

那为什么不写成 If 組合陣列(X, N) <= 总数 - X

或者把总数 - X 放入一个阵列，直接拿出来比较，不需要每次都计算，变成
If 組合陣列(X, N) <= 上限(X)
注意组合阵列() 和上限() 最好是同一数据类型

当然，这些小优化其实意义不大，你还不如给代码加上注释，对用户的帮助会更大

[ 本帖最后由灰袍法师于 2010-10-31 17:28 编辑 ]

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

[讨论] ★我設計的組合算法★20取10，0.39秒