驳 GarbageMan 的《一个超复杂的简介递归》——对延迟计算的实验和思考

2023-05-16

这是一篇因骂战而起的博文，GarbageMan 在该文章回复中不仅对我进行了侮辱，还涉及了我的母校，特写此文用理性的分析和实验予以回击。

在此也劝告 GarbageMan，没什么本事就别在那叫嚣了，还写什么《C语言初学者代码中的常见错误与瑕疵》，误人子弟。

完整的实验代码点这里下载。使用方法见实验环境一节。

本文需要一些基本的数论知识。本人对于数论没有详细而深入的研究，部分表述有可能不严谨或不正确，如有发现，还请指正。

预备知识

素数，又称质数，指除了 1 和该整数自身外，无法被其他正整数整除的正整数。

素数定理表明，从不大于 n 的自然数随机选一个，它是素数的概率大约是 1/ln n 。

Eratosthenes 筛法。给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。

试除法。尝试从到的整数是否整除。

问题描述

GarbageMan 给出的问题原题在这里。在此对问题的本质进行简述：

任意给定一个正整数 n，求与 n 的差的绝对值最小的素数。若 n 是一个素数，则输出 n 自身；若有两个素数符合条件，则输出其中较大的一个。

根据我和 GarbageMan 在留言中的讨论，还要补充以下几点：

该题有两种模式，一种是只考虑一次问答的情况，另一种是考虑连续问答。
题目中会事先给定 n 的取值范围。

GarbageMan 所用算法分析

GarbageMan 在这篇文章中所用的算法本质上是试除法的一个变种，其改变有两点：

维持一个从到的素数表，在验证一个正整数是否是素数时，只需用素数表中的数进行验证即可，而无需使用从到的所有整数。
延迟计算。实现并不计算素数表，而是在用到的时候，按需进行计算。这样在单次问答中就不需要准备整张素数表，而只需要计算需要的部分即可。

首先肯定一下，GarbageMan 的思路是正确的：在给定的 n 附近由近及远的进行素数判定，直到找到一个素数为止。

那么我为什么会和 GarbageMan 在留言中吵起来，以至于 GarbageMan 对我进行人身攻击呢？这是因为 GarbageMan 在这个算法中使用延迟计算的方法，将素数表的计算推迟到提问之后按需进行计算。这一优化本来无可厚非，但是问题就出在他这篇文章的副标题是“C语言初学者代码中的常见错误与瑕疵”。我认为，这样的优化意义不大，并且凭空增加了许多代码复杂性。另一方面，尽管作者声明了“本文讨论的并不是初学者代码中的常见错误与瑕疵，而是对我自己代码的改进和优化”，但是顶着这样的标题写这样的内容，也有些欠妥。下面分两种情况讨论更好、更常见、代码更简洁易懂的方案。

改进方案分析

该问题有两种模式，一种是只考虑一次问答的情况，另一种是考虑连续问答。两种截然不同的模式会导致不同的算法设计。

如果只考虑一次问答的情况，Rabin-Miller 素数测试会成为一个更好的方案。因为 Rabin-Miller 素数测试可以被用于测试一个非常非常大的整数是否是一个素数，并且还不需要计算素数表，所以对于较大规模的数据，Rabin-Miller 素数测试比朴素的试除法效率更高。

如果考虑多次问答的情况，考虑平均情况，延迟计算最终也会计算出大部分的素数表。与其动态的不断补充素数表，还不如用更有效率的方法直接计算出整张素数表，所以对于这种情况，GarbageMan 的优化是毫无意义的。

下面将分别讨论上面提到的几种算法。

Rabin-Miller 素数测试

Rabin-Miller 素数测试，是一种素数判定法则，利用随机化算法判断一个数是合数还是可能是素数。

听起来像是一个不靠谱的算法，但是该算法可以以任意给定的准确率给出可能正确的答案。当这个准确率足够大时，我们可以近似的认为这个算法给出的答案正确。（这一点遭到了 GarbageMan 的疯狂嘲讽，我猜他不知道为什么无穷大的倒数等于 0）对此算法仍然不放心的话，已经有结论表明，如果 n < 4,759,123,141 的话，只需验证 a = 2, 7, and 61 的情况，就可以确定性的给出 n 是否是一个素数。该算法的伪代码如下：

Input: n > 3, an odd integer to be tested for primality;
Input: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2^s·d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
   pick a random integer a in the range [2, n − 2]
   x ← a^d mod n
   if x = 1 or x = n − 1 then do next WitnessLoop
   repeat s − 1 times:
      x ← x² mod n
      if x = 1 then return composite
      if x = n − 1 then do next WitnessLoop
   return composite
return probably prime

有关 Rabin-Miller 素数测试是否真的比通过试除法检验素数快，我们暂且将这一问题留待实验结果说明。下面我们讨论多次问答情况下的算法设计。

积极计算

GarbageMan 自鸣得意的一个优化就是延迟计算素数表。在我看来，这是一个完全没有必要的，并且极大地增加了代码复杂度的优化。在多次问答的情况下，最坏情况下如论如何都需要计算整张素数表用于之后的试除法检验素数。这样，延迟计算所节省的计算量，完全抵不过复杂代码所带来的负面效果。

我的建议是，使用初始化方法预先计算从 [2, log MAX_N] 之间的素数，然后再用 GarbageMan 的 get_nearest 方法进行计算。在问答量比较大时，这种方法甚至会比 GarbageMan 优化过的算法还要快。

素数筛法

素数筛法是用于计算素数表的快速方法，其效率比朴素的通过试除法发现素数然后再添加到素数表中，要快得多。素数筛法已经十分先进了，甚至有亚线性时间复杂度的算法，因此，在实现生成素数表的情况下，没有理由不选择素数筛法。

由于这样一个事实——素数的个数随着数量级的增大而变得越来越稀疏（参考预备知识中的素数定理），当题目中给定的 n 非常大时，在 n 的附近寻找一个素数将变得越来越没有效率。对此，我建议在计算素数表的时候，直接计算到比 n 的上限还要大的一个素数之后再停止生成素数表，然后通过二分查找，直接确定给定的 n 在素数表中的位置，从而找到距离 n 最近的素数。

算法的思路至此介绍完毕，下面将设计实验来验证我的想法是否正确。

实验设计

由于题目分为两种情况，我的算法设计也分别针对这两种情况，因此在做实验进行对比的时候，也将分别设计实验。

实验的思路如下：

生成在 [1, MAX_N] 上均匀分布的若干随机数，并记录下来备用；
将这些随机数使用 GarbageMan 的方法进行计算，收集答案，并且统计用时；
将这些随机数使用我上面提出的几种方法进行计算，收集答案，并且统计用时；
验证这些不同算法答案是否相同，即确保算法的正确性；
比对不同算法的用时。

严密的验证需要多次重复试验不同的数据规模，并且排除其他因素的干扰。由于实验环境的限制，我将只进行一种中等数据规模的测试，得出的实验结果不严密，但是足以说明问题。

实验分别比较在单次问答模式下，GarbageMan 所用算法和 Rabin-Miller 算法的用时；在多次问答模式下，GarbageMan 所用算法和其他算法的用时。其中，在多次问答模式下，需要对 GarbageMan 所用的算法进行一些微调，以保证测试的公平性和正确性：

将 get_nearest 方法中的 Node * head = NULL; 语句挪到 get_nearest 方法外面，并加上 static 标识符；
删除掉 get_nearest 方法中的 my_free(head); 一句；
修改 get_remainder 方法中的 if 语句判断条件为 if ((x != p->prime) && (x % p->prime == 0))。

前两条修改意在重用已经计算好的素数表；第三条修改是在判断素数表中已有素数时，会产生错误的结果。

实验环境

CPU : Intel Core Duo P7450 2.13GHz
Windows 7 64bit
Visual Studio 2013

编译选项 /STACK:10485760,1048576 /O2

完整的实验代码点这里下载。

给出的测试代码依赖于 C++11 标准中提供的随机数生成函数，因此只能在 Visual Studio 2013 和较新版本的 g++，clang++ 上不需要修改的通过编译。使用较低版本的编译器编译时，可以结合 boost 库提供的支持，进行有限的修改后通过编译。如果使用 g++ 或者 clang++ 进行编译的话，请使用参数 -O2 -std=c++11。

实验结果

当设定 n 的范围在 [1, 10^6 - 10]，且生成 50,000 个随机数时，多次问答模式下的测试结果如下：

Elapsed : 3900005ms    // GarbageMan 的方法
Elapsed : 500001ms     // 积极计算的方法
Elapsed : 2890109ms    // Rabin-Miller 算法
Elapsed : 270015ms     // 素数筛法和二分查找

再测一次：

Elapsed : 3920017ms    // GarbageMan 的方法
Elapsed : 500001ms     // 积极计算的方法
Elapsed : 2800004ms    // Rabin-Miller 算法
Elapsed : 300001ms     // 素数筛法和二分查找

由大数定律可知，GarbageMan 的算法在平均情况下运行效率较低，并且低于积极计算的方法，可见不仅白优化了，还起到了负面效果。

由于实验结果显示，在多次问答模式下 GarbageMan 的算法运行效率仍然低于为单次问答模式所设计的 Rabin-Miller 算法，因此没有必要再进行单次问答模式的实验。

GarbageMan 多次对我进行人身攻击，并且侮辱我的母校。在此我要说一句，GarbageMan 你真是人如其名——渣男，人品渣，技术也渣。

结论

延迟计算是一个重要的概念，有着很多有趣的用法，尤其是 Haskell 语言中内建支持延迟计算，有很多利用这一特性的优美代码。

但是应该知道，延迟计算是有代价的，如果不能通过延迟计算节省足够的计算量，使用延迟计算在运行速度上就得不偿失。尤其是使用不“天然”支持延迟计算特性的语言时（比如说 C 语言），更加需要谨慎的使用延迟计算特性，否则不仅达不到优化的目的，反而使代码变得复杂难以理解，运行效率降低。

参考资料

维基百科——素数
维基百科——素数定理
互动百科——质数表
维基百科——Eratosthenes 筛法
维基百科——素性测试
维基百科——Rabin-Miller 素数测试
维基百科——大数定律
维基百科——Sieve of Atkin

转载于:https://www.cnblogs.com/HCOONa/p/lazy-evaluation-is-usually-slow.html

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)