- 類型：編程輔助大�。�1.8M語言：英文 評(píng)分：6.0
- 標(biāo)簽：
一直想寫這篇關(guān)于算法的文章，但是由于看到園子里眾多研究算法的高手讓我一直沒有決心寫下來，但高手歸高手，不是高手也可以寫出來讓高手們拍磚，所以今天就在這里獻(xiàn)丑了。相親數(shù)和完全數(shù)作為數(shù)學(xué)問題的確是頂級(jí)難題，可是拿來做娛樂就不同了，從剛接觸編程時(shí)C語言書上的課后習(xí)題到兩年前的Intel多核編程大賽，這個(gè)題目一直伴隨著我們，讓我們來娛樂一下吧。
簡單說一下概念，相親數(shù)是指兩個(gè)正整數(shù)中，彼此的全部約數(shù)之和（本身除外）與另一方相等。舉例來說：
220的全部約數(shù)(除掉本身)相加是：1+2+4+5+10+11+20+22+44+55+110=284
284的全部約數(shù)(除掉本身)相加的和是：1+2+4+71+142=220
所以220和284就是一對(duì)相親數(shù)。
那什么是完全數(shù)呢？即它所有的真因子（即除了自身以外的約數(shù)）的和恰好等于它本身。例如：
第一個(gè)完全數(shù)是6，它有約數(shù)1、2、3、6，除去它本身6外，其余3個(gè)數(shù)相加，1+2+3=6
第二個(gè)完全數(shù)是28，它有約數(shù)1、2、4、7、14、28，除去它本身28外，其余5個(gè)數(shù)相加，1+2+4+7+14=28
概念不多說了，直接上算法。
算法一：直接計(jì)算約數(shù)之和
這是最直接的方式了，循環(huán)計(jì)算所有可能成為約數(shù)的數(shù)字然后加和，直接到不用做過多的解釋，只要會(huì)寫程序，用任何語言都能實(shí)現(xiàn)！
1: /// <summary>
2: /// 直接計(jì)算約數(shù)之和(串行)
3: /// </summary>
4: public class Algorithm1
5: {
6: private int GetSum(int num)
7: {
8: int sum = 1;
9: int limit = (int)Math.Sqrt(num);
10: for (int i = 2; i <= limit; i++)
11: if (num % i == 0) sum += i + num / i;
12: return sum;
13: }
14:
15: public void Run(int from, int to)
16: {
17: int perfertCount = 0;
18: int amicablePairCount = 0;
19: for (int num = from; num <= to; num++)
20: {
21: int sum1 = this.GetSum(num);
22: if (sum1 == num)
23: {
24: Console.WriteLine("{0}是完全數(shù)", num);
25: perfertCount++;
26: }
27: if (sum1 > num)
28: {
29: int sum2 = this.GetSum(sum1);
30: if (sum2 == num)
31: {
32: Console.WriteLine("{0}和{1}是一對(duì)相親數(shù)", sum1, sum2);
33: amicablePairCount++;
34: }
35: }
36: }
37: Console.WriteLine("在{0}到{1}中共有{2}個(gè)完全數(shù)和{3}對(duì)相親數(shù)", from, to, perfertCount, amicablePairCount);
38: }
39: } 測(cè)試代碼，從2計(jì)算到5000000：
1: static void Main(string[] args)
2: {
3: var stopwatch = Stopwatch.StartNew();
4: Algorithm1 algorithm = new Algorithm1();
5: algorithm.Run(2, 5000000);
6: stopwatch.Stop();
7: Console.WriteLine("計(jì)算完成共花費(fèi){0}秒", stopwatch.Elapsed.TotalSeconds);
8: Console.ReadKey();
9: } 在我的ThinkPad R400上測(cè)試運(yùn)行時(shí)間大概在51秒左右，速度能不能再提高呢，讓我們看看.Net4.0為我們帶來的并行計(jì)算的新特性表現(xiàn)如何。
1: /// <summary>
2: /// 直接計(jì)算約數(shù)之和(并行)
3: /// </summary>
4: public class Algorithm2
5: {
6: private int GetSum(int num)
7: {
8: int sum = 1;
9: int limit = (int)Math.Sqrt(num);
10: for (int i = 2; i <= limit; i++)
11: if (num % i == 0) sum += i + num / i;
12: return sum;
13: }
14:
15: public void Run(int from, int to)
16: {
17: int perfertCount = 0;
18: int amicablePairCount = 0;
19: Parallel.For(from, to, num =>
20: {
21: int sum1 = this.GetSum(num);
22: if (sum1 == num)
23: {
24: Console.WriteLine("{0}是完全數(shù)", num);
25: perfertCount++;
26: }
27: if (sum1 > num)
28: {
29: int sum2 = this.GetSum(sum1);
30: if (sum2 == num)
31: {
32: Console.WriteLine("{0}和{1}是一對(duì)相親數(shù)", sum1, sum2);
33: amicablePairCount++;
34: }
35: }
36: });
37: Console.WriteLine("在{0}到{1}中共有{2}個(gè)完全數(shù)和{3}對(duì)相親數(shù)", from, to, perfertCount, amicablePairCount);
38: }
39: } 注意第19行，我們使用System.Threading.Tasks下的Parallel類取代傳統(tǒng)的for循環(huán)，由于在該算法中每一次計(jì)算都是獨(dú)立的，所以很適合并行，廢話不多說，直接運(yùn)行看結(jié)果，運(yùn)行時(shí)間在26秒左右，由于我的機(jī)器是雙核，所以同樣是從2計(jì)算到5000000，并行的時(shí)間差不多是之前的(51秒)一半，看來Parallel真是不錯(cuò)的新工具��！當(dāng)然，這個(gè)是從技術(shù)上達(dá)到了速度的提升，算法本質(zhì)還沒有變，那能不能從算法本身提高計(jì)算效率呢？答案當(dāng)然是肯定的！
算法二：通過計(jì)算所有質(zhì)因數(shù)來計(jì)算約數(shù)之和
先說一下原理：記得小學(xué)的奧賽有一個(gè)題型是計(jì)算一個(gè)自然數(shù)的約數(shù)的個(gè)數(shù)(現(xiàn)在還有沒有不清楚)，截法很簡單，先分解質(zhì)因數(shù)，然后把所有質(zhì)因子的冪加一再相乘就是約數(shù)的個(gè)數(shù)，例如數(shù)字36=2^2×3^2，那么36就有(2+1)×(2+1)=9個(gè)約數(shù)(1,2,3,4,6,9,12,18,36)。其實(shí)能算出有9個(gè)約數(shù)，自然可以計(jì)算9個(gè)約數(shù)是什么，是2個(gè)2和2個(gè)3排列組合的結(jié)果，剩下的就不用我廢話了，該算法的思路就是先分解質(zhì)因數(shù)然后在逐個(gè)計(jì)算約數(shù)并加和，上代碼：
1: /// <summary>
2: /// 通過計(jì)算所有質(zhì)因數(shù)來計(jì)算約數(shù)之和（串行）
3: /// </summary>
4: public class Algorithm3
5: {
6: private int GetNextFactor(int num)
7: {
8: int limit = (int)(Math.Sqrt(num));
9: for (int i = 2; i <= limit; i++)
10: if (num % i == 0)
11: return i;
12: return num;
13: }
14: private List<int> Decomposition(int num)
15: {
16: var factors = new List<int>();
17: while (true)
18: {
19: var divisor = GetNextFactor(num);
20: factors.Add(divisor);
21: if (divisor == num) break;
22: num = num / divisor;
23: }
24: return factors;
25: }
26: private int Sum(List<int> divisors)
27: {
28: int sum = 0;
29: for (int i = 0, count = divisors.Count - 1; i < count; i++)
30: sum += divisors[i];
31: return sum;
32: }
33: private int GetSum(List<int> factors)
34: {
35: if (factors.Count == 1) return 1;//質(zhì)數(shù)
36: var divisors = new List<int>() { 1 };
37: var factorPows = new List<List<int>>() { new List<int>() { factors[0] } };
38: for (int i = 1, count = factors.Count; i < count; i++)
39: {
40: var length = factorPows.Count;
41: if (factors[i] == factorPows[length - 1][0])
42: factorPows[length - 1].Add(Convert.ToInt32(Math.Pow(Convert.ToDouble(factors[i]), Convert.ToDouble(factorPows[length - 1].Count + 1))));
43: else
44: factorPows.Add(new List<int>() { factors[i] });
45: }
46: for (int f = 0, fCount = factorPows.Count; f < fCount; f++)
47: for (int d = 0, dCount = divisors.Count; d < dCount; d++)
48: for (int p = 0, pCount = factorPows[f].Count; p < pCount; p++)
49: divisors.Add(divisors[d] * factorPows[f][p]);
50: return Sum(divisors);
51: }
52: public void Run(int from, int to)
53: {
54: int perfertCount = 0;
55: int amicablePairCount = 0;
56: for (var num = from; num < to; num++)
57: {
58: int sum1 = this.GetSum(Decomposition(num));
59: if (sum1 == num)
60: {
61: Console.WriteLine("{0}是完全數(shù)", num);
62: perfertCount++;
63: }
64: if (sum1 > num)
65: {
66: int sum2 = this.GetSum(Decomposition(sum1));
67: if (sum2 == num)
68: {
69: Console.WriteLine("{0}和{1}是一對(duì)相親數(shù)", sum1, sum2);
70: amicablePairCount++;
71: }
72: }
73: }
74: Console.WriteLine("在{0}到{1}中共有{2}個(gè)完全數(shù)和{3}對(duì)相親數(shù)", from, to, perfertCount, amicablePairCount);
75: }
76: } 先看速度如何，是否比算法一更快，從2計(jì)算到5000000花費(fèi)近27秒，幾乎與算法一的并行版本接近，果然快很多，那么快在哪里了呢？算法一做了大量的取模和除法操作，相比于加、減、乘等操作這些操作都是很耗時(shí)的，而算法二先計(jì)算質(zhì)因數(shù)，減少了很多取模和除法操作，取而代之的是很多乘法和指數(shù)運(yùn)算，性能自然得到提升，但還算細(xì)心的我并沒有就此下結(jié)論，我把計(jì)算范圍縮小到2到100000，此時(shí)，算法一花費(fèi)時(shí)間是0.18秒而算法而則是0.36秒，算法一反而取勝了，其實(shí)道理很簡單，隨著數(shù)字的增大，算法一計(jì)算取模和除法的操作增加也不斷增加，而算法二隨著數(shù)字增大計(jì)算次數(shù)卻增加不明顯，因?yàn)榉纸赓|(zhì)因數(shù)其實(shí)是找質(zhì)數(shù)的過程，但找到第一個(gè)質(zhì)因數(shù)后，數(shù)字就變小了，計(jì)算量并沒增加多少，相反，找到的質(zhì)因數(shù)越多，計(jì)算約數(shù)的計(jì)算量就越大，所以在數(shù)字不大(相對(duì)不大)的領(lǐng)域里，試商次數(shù)不多所以算法一很快完成了計(jì)算，而算法二相對(duì)于算法一的卻沒什么太大優(yōu)勢(shì)，但隨著數(shù)字的變大，算法二的優(yōu)勢(shì)會(huì)越來越明顯！例如我從5000000計(jì)算到5500000，算法一就豪無優(yōu)勢(shì)了，落后算法二一半都不止，這讓我想起了一個(gè)古老的但卻眾所周知的梵塔問題，算法一就是這樣一個(gè)梵塔……
當(dāng)然我也沒忘記把這個(gè)算法改成并行版本，我就不貼代碼了，只要改第56行的for就可以了，從2計(jì)算到5000000花費(fèi)在16秒左右，這樣我們已經(jīng)從最初的51秒降低到16秒，還能更快嗎？我絞盡腦汁暫時(shí)還沒什么結(jié)果，因?yàn)槲野l(fā)現(xiàn)最后所花的時(shí)間都是在尋找質(zhì)數(shù)上了，難怪?jǐn)?shù)學(xué)界的頂級(jí)難題都跟質(zhì)數(shù)有關(guān)或者圍繞質(zhì)數(shù)展開，還有我們程序員熟悉的加密算法RSA，也是基于大整數(shù)難以分解的“特性”上，如果不幸被我找到了快速分解算法我就不用在這寫博客啦，扯遠(yuǎn)了，還是回歸娛樂吧，我們還有沒有辦法讓它再快點(diǎn)呢？
算法二SP1：之所以叫SP1是因?yàn)樗]有本質(zhì)上的更改，只是在外圍讓它顯得更快。話說算法界有兩大秘籍，九陰真經(jīng)和九陽神功——都不是，開個(gè)玩笑，其實(shí)沒什么秘籍，而是方法論，無非就是時(shí)間換空間和空間換時(shí)間，根據(jù)我們的需要，時(shí)間和空間在我們的代碼中轉(zhuǎn)換來轉(zhuǎn)換去，既然我追求的是速度，那自然是用空間來換時(shí)間嘍。
算法一我還沒想到哪里可以用空間來換取速度，倒是在對(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)槲覍懖磺宄o大家舉個(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拍磚。
喜歡 
頂
難過
囧
圍觀
無聊
