趣味編程之計算相親數(shù)(上)

第 3 頁 我還沒想到哪里可以用空間來換取速度
算法一我還沒想到哪里可以用空間來換取速度，倒是在對算法二的研究過程中我意識到大量的重復計算，最典型的是計算質(zhì)數(shù)，如果緩存這些質(zhì)數(shù)速度會不會快一些呢，其實是廢話當然會快，花了空間速度還沒提升的事情誰會愿意做呢，但僅僅緩存質(zhì)數(shù)遠遠不夠，因為最大量的計算根本不在這里，如果連續(xù)的看待分解的過程，你就會發(fā)現(xiàn)它是一個遞歸的過程，之前的計算結果對后面很有用，比如我們已經(jīng)分解了36=2^2×3^2。那么當我們分解72的時候是怎樣的過程呢，先找到了第一個因子2，然后得到36，繼續(xù)分解，36的分解過程又做一次，重復量可想而知，有人說，你把2^2×3^2記錄下來，在計算72的時候直接利用36的計算結果，說的沒錯，但我記錄的信息是不是太大了，空間也不是這么揮霍的啊，于是我權衡再三，采用了下面的算法，先看代碼：

1: /// <summary>
2: /// 通過計算所有質(zhì)因數(shù)來計算約數(shù)之和（空間算法）
3: /// </summary>
4: public class Algorithm5
5: {
6: public List<int> primeList = new List<int>();
7: public int[] firstFactorList;
8: public int[] remainingList;
9: public int[] resultList;
10: public int GetNextFactor(int num)
11: {
12: var max = (int)Math.Sqrt(num);
13: for (int i = 0; i < primeList.Count; i++)
14: {
15: var p = primeList[i];
16: if (p > max) break;
17: if (num % p == 0)
18: return p;
19: }
20: primeList.Add(num);
21: return num;
22: }
23: public List<int> Decomposition(int num)
24: {
25: var divisors = new List<int>();
26: var factor = firstFactorList[num] = GetNextFactor(num);
27: if (factor == num)
28: remainingList[num] = 1;
29: else
30: remainingList[num] = num / firstFactorList[num];
31: while (true)
32: {
33: divisors.Add(firstFactorList[num]);
34: if (remainingList[num] == 1) break;
35: num = remainingList[num];
36: }
37: return divisors;
38: }
39: private int Sum(List<int> divisors)
40: {
41: int sum = 0;
42: for (int i = 0, count = divisors.Count - 1; i < count; i++)
43: sum += divisors[i];
44: return sum;
45: }
46: public int GetSum(List<int> factors)
47: {
48: if (factors.Count == 1) return 1;//質(zhì)數(shù)
49: var divisors = new List<int>() { 1 };
50: var factorPows = new List<List<int>>() { new List<int>() { factors[0] } };
51: for (int i = 1, count = factors.Count; i < count; i++)
52: {
53: var length = factorPows.Count;
54: if (factors[i] == factorPows[length - 1][0])
55: factorPows[length - 1].Add(Convert.ToInt32(Math.Pow(Convert.ToDouble(factors[i]), Convert.ToDouble(factorPows[length - 1].Count + 1))));
56: else
57: factorPows.Add(new List<int>() { factors[i] });
58: }
59: for (int f = 0, fCount = factorPows.Count; f < fCount; f++)
60: for (int d = 0, dCount = divisors.Count; d < dCount; d++)
61: for (int p = 0, pCount = factorPows[f].Count; p < pCount; p++)
62: divisors.Add(divisors[d] * factorPows[f][p]);
63: return Sum(divisors);
64: }
65: public void Run(int limit)
66: {
67: firstFactorList = new int[limit];
68: remainingList = new int[limit];
69: resultList = new int[limit];
70: int perfertCount = 0;
71: int amicablePairCount = 0;
72: for (var num = 2; num < limit; num++)
73: {
74: var result = resultList[num] = this.GetSum(Decomposition(num));
75: if (result == num)
76: {
77: Console.WriteLine("{0}是完全數(shù)", num);
78: perfertCount++;
79: }
80: else if (result < num && resultList[result] == num)
81: {
82: Console.WriteLine("{0}和{1}是一對相親數(shù)", result, num);
83: amicablePairCount++;
84: }
85: }
86: Console.WriteLine("在{0}到{1}中至少有{2}個完全數(shù)和{3}對相親數(shù)", 2, limit, perfertCount, amicablePairCount);
87: }
88: } 我緩存了質(zhì)數(shù)，每個數(shù)字的第一個因子和剩余因子的乘積以及每個數(shù)字的約數(shù)和，代碼之所以沒有注釋是因為我寫不清楚，給大家舉個例子，大家再對照代碼看就好：比如分解72，先找到它的第一個因子2，和剩余因子的乘積36(其實就是72/2)，然后緩存2和36做為72對應的緩存變量，然后在緩存列表中找到36的第一個因子(因為之前已經(jīng)計算過)，也是2，然后看看36剩余因子的乘積是18有找到了18的第一個因子9……就這樣利用了原來的結果，把取模和除法變成了查(緩存)表，這樣無疑有個弊端，我們不能從中間開始算了，必須從2開始計算，先不管了，看看速度再說，從2計算到5000000花費了13秒左右，注意這里計算次數(shù)跟之前不一樣，之前的算法是算到5000000，但可以超過5000000，而現(xiàn)在是只算到5000000，不管怎樣，速度比并行版本的算法二還要快一些(前提是從2開始計算)，緩存的效果不錯哦，不過內(nèi)存也被吃去大片，空間換時間的代價……

算法二SP2：本來以上就是我要記錄的全部內(nèi)容，但由于遲遲未成文，所以最近我又發(fā)現(xiàn)一個“超級”快速的空間換時間的算法，比SP1快很多，請允許我先賣一個關子，先公布結果，從2計算到5000000只需要2.8秒，具體實現(xiàn)且聽下回分解……(無恥的淫笑)

后記：鄭重聲明，本貼純屬娛樂帖，很多代碼并沒有在細節(jié)性能上過多糾纏(比如Math.Sqrt的性能還有提升空間，List申請空間處的性能提升等等……)，另外賣關子不是吊胃口，而是要說明這個SP2算法所花費的篇幅可能比較長，實在寫不動了，就賣了一個關子，小弟會盡快完成下一篇，敬請期待！不過通過把這篇文章寫出來(很多代碼多年前就寫好了)還是感觸頗深的，我們面對一個問題，可以從多個角度去分析優(yōu)化解決，可以從根本上想辦法(算法本身)，也可以找工具(并行)，還可以在外圍和結構等方面想辦法(緩存……)，只要我們不停的思考，從多個角度想辦法，總會有些手段給我們利用。最后，不知大家是不是也研究過此類問題，或許您有更好的算法，無論是出于興趣還是其它，歡迎一起討論and拍磚。