越来越难?这届开发者学不会的计算机理论

CSDN 2021-11-26 15:22

作者 | 马超   责编 | 张红月     
出品 | CSDN(ID:CSDNnews)

知其然然后知其所以然。对于软件开发者人员来说,入门的必备知识不是安装操作系统、不是快速编写软件项目,而是学习实实在在的理论知识,它们很可能会决定你职业生涯的高度。

最近外网的一篇《When did Computer Science Theory Get so Hard》引发了全网众多讨论,也有不少朋友向我推荐这篇博客,在仔细阅读过原文后,对于其中的一些细节,我倒并不能完全认同,但是文章整体的叙述与脉络非常清晰,尤其是计算机理论越来越难的现象也的确值得我们反思


计算机科学理论什么时候变得这么难?


与理论发展缓慢的态势不同,目前计算机领域的应用侧发展可谓日新月异,像GPT-3及其衍生的AI模型,各类大数据模型、超大规模云平台等方面的进展不胜枚举,相关成果也都举世瞩目,但这些计算机应用发展的本质,都是硬件价格不断快速下降所带来的衍生红利,而这种现象早在50年前就被摩尔定律所明确预言了,凡是能靠算力解决的问题,目前都不再是问题。

不过计算机理论要解决的问题都是非线性的,简单依靠硬件堆砌解决不了指数级上升的复杂度,因此计算机理论没有吃到硬件价格快速下降这波红利的,由于目前理论发展到了一个相对乏味的平台期,这也使计算机相关的理论只能向广度扩展,变得越来越高深、复杂,而且迟迟无法突破。可以说目前计算机领域像极了《三体》中所描述的场景,人类底层科学被锁死,但是应用实践却极大繁荣


Quake3的0x5f3759df 来自于应用界的最后尊严


虽然原文作者没有直接提到,但笔者这里还是要补充一下属于计算机应用界的光荣时刻。与现在流行的算力规模理念不同,之前在应用界尤其是游戏方面,各种神操作层也不穷,像80后对《Quake》也就是《雷神之锤》这款游戏一定会记忆深刻,这款3D游戏可以在几十兆内存的环境下跑得飞起,和目前动辄要求几十G内存的所谓3A大作形成鲜明对比,效果上两者最多差10倍,但是所消耗的资源却是天壤之别。

下面要举的这个《Quake 3》的例子,目前已经开源了,比如树莓派的版本地址如下:https://github.com/raspberrypi/quake3/,而以下这段代码中出现著名的魔法数0x5f3759df,这是对于开方的快速算法所引入的常量,在今天看来依旧是传奇。具体代码的地址:

https://github.com/raspberrypi/quake3/blob/8d89a2a3c1707bf0f75b2ea26645b872e97c0b95/code/qcommon/q_math.c

代码如下:

float Q_rsqrt( float number ){        floatint_tt;        floatx2, y;        constfloat threehalfs = 1.5F;        x2= number * 0.5F;        t.f  = number;        t.i  = 0x5f3759df - ( t.i >> 1 );               // what the fuck?        y  = t.f;        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration//     y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed         returny;}

Quake3使用的0x5f3759df属于一个魔法数字。它来自平方根倒数速算法,在《Quake 3》建模引擎中引用这个魔法之后,其速度要比标准的牛顿迭代法快上4倍。

没人知道《Quake 3》的作者卡马克是怎么发现这个数字的,估计卡马克本人可能也不知道,因为直到现在的开源版本中,还留着作者本人亲自加上的”what the *?“这样的注释。

i = 0x5f3759df - ( i >> 1 ); // what the fuck?

后来普度大学Lomont教授也对这个魔法数字产生了好奇,决定好好探究一下卡马克弄出来的这个魔法数到底奥秘何在。Lomont也是位大神,在精心研究之后他从理论上也推导出一个最佳猜测值0x5f37642f,和卡马克的数字非常接近 。

故事到这里并没有完结。Lomont拿自己计算出的魔法值和卡马克的进行回测比较,想看看谁的数字能够更快更精确地求得平方根。结果却是卡马克的0x5f3759df精度更高,这也让Lomont十分恼火,最后Lomont被逼无奈,为了找回面子,直接采用暴力方法一个数字一个数字试过来,终于找到一个比卡马克数字要好上那么一点点的数字,虽然实际上这两个数字所产生的结果非常近似,这个暴力得出的数字是0x5f375a86。

不过这个0x5f375a86的传奇可能是应用界最后的尊严时刻了,在硬件性能不断提升,而且价格不断下降的今天,应用界所奉行的信条都是“大就得了”,由于头部大玩家所掌握的算力往往是一般用户的几千甚至上万倍,因此大厂的精英基本也没人再为0x5f3759df这种4倍速度的优化费心了。应用界已经很久没出现什么惊天地,泣鬼神的神级代码了。


理论界要解决P=NP的问题,这就只能越来越难了


虽然靠着硬件性能的提升,线性优化策略可以不管,但是指数级别的复杂度却不能坐视不理。在前文《元宇宙是否会成为IPv6的拐点》中曾经介绍过一个SPF最短路径优先的动态规划算法Dijkstra,这种求地图两点之间最短路径的问题,相对来说时间复杂度可以接受的,我们不必穷举所有可能路线,通过贪心加动态规划的方法就能找到最优解。

但是其派生的兄弟问题旅行商路线规划,却是个典型的P对NP问题。旅行商路线规划要找到一条回路,将地图图上的所有顶点,不重复的走一遍,并最终回到起点,而且要保证总体路径最短。举个例子,假如一个旅行商,要在尽量短的时间内走完中国现有23个省,5个自治区,4个直辖市,2个特别行政区,对于这些地区的名胜景点,他的选择一共有34的阶乘那么多,这个数字大概有1000000000000000000000000000....000(一共38个0)。而能否有一个算法,在不逐一遍历所有路径的情况下找到最优解,也就是P/NP问题,将旅行商路线规划带入到P/NP理论的解释如下:NP代表所有解的集合也就是10^38次方种走法,而P代表其中一部分走法,能否是仅遍历P就把NP问题解决掉,这也就简化成P与NP是否等效的P=NP问题。

旅行商问题和图论中著名的哈密尔顿回路比较类似,只是给边加上了权重,而且它们和团问题、顶点覆盖问题等一样都属于NP完全问题,也就是只要你解决了其中一个,就相当于把其余的问题也解决了。

之前互联网的规模还不够大,因此所谓哈密尔顿图、旅行商问题等都还没有迫切的解决需要,不过现在不同了,互联网终端的规模越来越大,尤其是随着元宇宙等概念的发展还会快速膨胀,我们虽然可以在应用端采用分治策略把互联网分成若干个自治区(AS)来尽量避免直面这种NP的难题。但是像GMP(Graph Minor Theorem)等理论的发展几乎完全和P/NP问题深度绑定了,P/NP不动,计算机理论也动不了。

不过虽然P/NP问题如此重要,但人们All in去解决掉它的动力却不足,根据哥德尔不完备定理,在目前数学的研究领域,肯定会存在我们既无法证真也无法证伪的问题,P对NP问题也许就是一个根本不值得去研究的问题,因为最关键的是人类可能永远也无法得到P对NP问题的解,甚至不知道这个问题到底有没有解。

短期来看,还是靠规模,靠堆算力来得效果直接,但是P对NP这个问题又是如此重要,在得不到明确的解答之前,计算机理论只能向所谓的复杂方面发展。这其实又回归到之前大家一再争论的元宇宙哲学问题,人类的终极目标到底是星辰大海,还是眼前唾手可得的虚拟世界,我们是直接在现有认知基础上发展元宇宙,还是不计成本地去探索P/NP这种可能永远得不到答案的数学难题,以上问题的答案只能留给读者自己去思考了。

作者简介:马超,金融科技专家,人民大学高礼金融研究院校外双聘导师,阿里云MVP,华为2020年十大开发者之星,CSDN约稿专栏作者,著名的金融科技的布道者。众多国产开源项目的推动者及贡献人。

参考链接:http://blog.computationalcomplexity.org/2021/11/when-did-computer-science-theory-get-so.html

腾讯回应“腾讯云数据库泄露”传闻;特斯拉将推出13万元刹车套件;PHP 8.1.0正式发布 | 极客头条

做开源数据库,九章云极DataCanvas是认真的!

技术“摸鱼” 5 年,国外小哥白拿 45 万工资!

推荐阅读