- 類型：編程輔助大小：1.8M語言：英文 評(píng)分：6.0
- 標(biāo)簽：
算法一我還沒想到哪里可以用空間來換取速度，倒是在對(duì)算法二的研究過程中我意識(shí)到大量的重復(fù)計(jì)算，最典型的是計(jì)算質(zhì)數(shù)，如果緩存這些質(zhì)數(shù)速度會(huì)不會(huì)快一些呢，其實(shí)是廢話當(dāng)然會(huì)快，花了空間速度還沒提升的事情誰會(huì)愿意做呢，但僅僅緩存質(zhì)數(shù)遠(yuǎn)遠(yuǎn)不夠，因?yàn)樽畲罅康挠?jì)算根本不在這里，如果連續(xù)的看待分解的過程，你就會(huì)發(fā)現(xiàn)它是一個(gè)遞歸的過程，之前的計(jì)算結(jié)果對(duì)后面很有用，比如我們已經(jīng)分解了36=2^2×3^2。那么當(dāng)我們分解72的時(shí)候是怎樣的過程呢，先找到了第一個(gè)因子2，然后得到36，繼續(xù)分解，36的分解過程又做一次，重復(fù)量可想而知，有人說，你把2^2×3^2記錄下來，在計(jì)算72的時(shí)候直接利用36的計(jì)算結(jié)果，說的沒錯(cuò)，但我記錄的信息是不是太大了，空間也不是這么揮霍的啊，于是我權(quán)衡再三，采用了下面的算法，先看代碼：
1: /// <summary>
2: /// 通過計(jì)算所有質(zhì)因數(shù)來計(jì)算約數(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}是一對(duì)相親數(shù)", result, num);
83: amicablePairCount++;
84: }
85: }
86: Console.WriteLine("在{0}到{1}中至少有{2}個(gè)完全數(shù)和{3}對(duì)相親數(shù)", 2, limit, perfertCount, amicablePairCount);
87: }
88: } 我緩存了質(zhì)數(shù)，每個(gè)數(shù)字的第一個(gè)因子和剩余因子的乘積以及每個(gè)數(shù)字的約數(shù)和，代碼之所以沒有注釋是因?yàn)槲覍懖磺宄�，給大家舉個(gè)例子，大家再對(duì)照代碼看就好：比如分解72，先找到它的第一個(gè)因子2，和剩余因子的乘積36(其實(shí)就是72/2)，然后緩存2和36做為72對(duì)應(yīng)的緩存變量，然后在緩存列表中找到36的第一個(gè)因子(因?yàn)橹耙呀?jīng)計(jì)算過)，也是2，然后看看36剩余因子的乘積是18有找到了18的第一個(gè)因子9……就這樣利用了原來的結(jié)果，把取模和除法變成了查(緩存)表，這樣無疑有個(gè)弊端，我們不能從中間開始算了，必須從2開始計(jì)算，先不管了，看看速度再說，從2計(jì)算到5000000花費(fèi)了13秒左右，注意這里計(jì)算次數(shù)跟之前不一樣，之前的算法是算到5000000，但可以超過5000000，而現(xiàn)在是只算到5000000，不管怎樣，速度比并行版本的算法二還要快一些(前提是從2開始計(jì)算)，緩存的效果不錯(cuò)哦，不過內(nèi)存也被吃去大片，空間換時(shí)間的代價(jià)……
算法二SP2：本來以上就是我要記錄的全部內(nèi)容，但由于遲遲未成文，所以最近我又發(fā)現(xiàn)一個(gè)“超級(jí)”快速的空間換時(shí)間的算法，比SP1快很多，請(qǐng)?jiān)试S我先賣一個(gè)關(guān)子，先公布結(jié)果，從2計(jì)算到5000000只需要2.8秒，具體實(shí)現(xiàn)且聽下回分解……(無恥的淫笑)
后記：鄭重聲明，本貼純屬娛樂帖，很多代碼并沒有在細(xì)節(jié)性能上過多糾纏(比如Math.Sqrt的性能還有提升空間，List申請(qǐng)空間處的性能提升等等……)，另外賣關(guān)子不是吊胃口，而是要說明這個(gè)SP2算法所花費(fèi)的篇幅可能比較長，實(shí)在寫不動(dòng)了，就賣了一個(gè)關(guān)子，小弟會(huì)盡快完成下一篇，敬請(qǐng)期待！不過通過把這篇文章寫出來(很多代碼多年前就寫好了)還是感觸頗深的，我們面對(duì)一個(gè)問題，可以從多個(gè)角度去分析優(yōu)化解決，可以從根本上想辦法(算法本身)，也可以找工具(并行)，還可以在外圍和結(jié)構(gòu)等方面想辦法(緩存……)，只要我們不停的思考，從多個(gè)角度想辦法，總會(huì)有些手段給我們利用。最后，不知大家是不是也研究過此類問題，或許您有更好的算法，無論是出于興趣還是其它，歡迎一起討論and拍磚。
本文導(dǎo)航
- 第1頁: 首頁
- 第2頁: 通過計(jì)算所有質(zhì)因數(shù)來計(jì)算約數(shù)之和
- 第3頁: 我還沒想到哪里可以用空間來換取速度
喜歡 
頂
難過
囧
圍觀
無聊
