算法一我还没想到哪里可以用空间来换取速度，倒是在对算法二的研究过程中我意识到大量的重复计算，最典型的是计算质数，如果缓存这些质数速度会不会快一些呢，其实是废话当然会快，花了空间速度还没提升的事情谁会愿意做呢，但仅仅缓存质数远远不够，因为最大量的计算根本不在这里，如果连续的看待分解的过程，你就会发现它是一个递归的过程，之前的计算结果对后面很有用，比如我们已经分解了36=2^2×3^2。那么当我们分解72的时候是怎样的过程呢，先找到了第一个因子2，然后得到36，继续分解，36的分解过程又做一次，重复量可想而知，有人说，你把2^2×3^2记录下来，在计算72的时候直接利用36的计算结果，说的没错，但我记录的信息是不是太大了，空间也不是这么挥霍的啊，于是我权衡再三，采用了下面的算法，先看代码：
1: /// <summary>
2: /// 通过计算所有质因数来计算约数之和（空间算法）
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;//质数
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}是完全数", num);
78: perfertCount++;
79: }
80: else if (result < num && resultList[result] == num)
81: {
82: Console.WriteLine("{0}和{1}是一对相亲数", result, num);
83: amicablePairCount++;
84: }
85: }
86: Console.WriteLine("在{0}到{1}中至少有{2}个完全数和{3}对相亲数", 2, limit, perfertCount, amicablePairCount);
87: }
88: } 我缓存了质数，每个数字的第一个因子和剩余因子的乘积以及每个数字的约数和，代码之所以没有注释是因为我写不清楚，给大家举个例子，大家再对照代码看就好：比如分解72，先找到它的第一个因子2，和剩余因子的乘积36(其实就是72/2)，然后缓存2和36做为72对应的缓存变量，然后在缓存列表中找到36的第一个因子(因为之前已经计算过)，也是2，然后看看36剩余因子的乘积是18有找到了18的第一个因子9……就这样利用了原来的结果，把取模和除法变成了查(缓存)表，这样无疑有个弊端，我们不能从中间开始算了，必须从2开始计算，先不管了，看看速度再说，从2计算到5000000花费了13秒左右，注意这里计算次数跟之前不一样，之前的算法是算到5000000，但可以超过5000000，而现在是只算到5000000，不管怎样，速度比并行版本的算法二还要快一些(前提是从2开始计算)，缓存的效果不错哦，不过内存也被吃去大片，空间换时间的代价……
算法二SP2：本来以上就是我要记录的全部内容，但由于迟迟未成文，所以最近我又发现一个“超级”快速的空间换时间的算法，比SP1快很多，请允许我先卖一个关子，先公布结果，从2计算到5000000只需要2.8秒，具体实现且听下回分解……(无耻的淫笑)
后记：郑重声明，本贴纯属娱乐帖，很多代码并没有在细节性能上过多纠缠(比如Math.Sqrt的性能还有提升空间，List申请空间处的性能提升等等……)，另外卖关子不是吊胃口，而是要说明这个SP2算法所花费的篇幅可能比较长，实在写不动了，就卖了一个关子，小弟会尽快完成下一篇，敬请期待！不过通过把这篇文章写出来(很多代码多年前就写好了)还是感触颇深的，我们面对一个问题，可以从多个角度去分析优化解决，可以从根本上想办法(算法本身)，也可以找工具(并行)，还可以在外围和结构等方面想办法(缓存……)，只要我们不停的思考，从多个角度想办法，总会有些手段给我们利用。最后，不知大家是不是也研究过此类问题，或许您有更好的算法，无论是出于兴趣还是其它，欢迎一起讨论and拍砖。
本文导航
- 第1页: 首页
- 第2页: 通过计算所有质因数来计算约数之和
- 第3页: 我还没想到哪里可以用空间来换取速度
