当前位置:91小说网>都市小说>这个学霸疑似巨额知识来源不明> 第106章 三十二个证人(2/6)
阅读设置(推荐配合 快捷键[F11] 进入全屏沉浸式阅读)

设置X

第106章 三十二个证人(2/6)

这个数字小到机器一瞬间就能跑完并验证。

这让江临难免就想起了那块砖。

做江氏砖的时候,刻进他骨头里的数学动作,就是把一个庞大到趋于无穷的边界状态空间,精妙地压缩成机器能穷举人能复核的有限状态形式。

一百二十确实不大。

可如果是频繁出现在高级数据库索引中的,排八个数,排十六个数呢?

8!

四万种,机器依然能够轻松秒杀。

但是到了十六个数。

16!

二十万亿级别。

对普通程序来说,这已经不是多跑一会儿的问题,而是足以把最笨的全排列验证拖进泥潭。

如果mpS框架建立在这种愚蠢的全排列穷举上,它将迅速死在起跑线上。

江临转了一下手中的圆珠笔,大脑的记忆宫殿开始高速检索。

很快,他放下了笔,在键盘上敲下了一行学术检索词。

zero-one principle sorting work

(排序网络:零一原理)

他其实早在废土时间里,在啃噬那些浩如烟海的计算机科学巨着时,就已经做了相关的知识储备。

只是在这之前,它仅仅只是停留在离散数学课本里一条定理这样的程度上,并没有迫切的用武之地。

而现在,江临认为这条优美的定理可以成为mpS-Kernel的第一块地基。

在理论计算机科学中,零一原理可以高傲地宣称——

一个由比较—交换操作固定地构成的比较网络,它是一个绝对正确的排序网络,当且仅当,它能够极其正确地将所有仅仅由数字0和数字1构成的有限输入序列,完全排好序。

这条定理的杀伤力在于,它无情地斩断了无限与有限的边界。

不会要求你去检验全部的120种排列,也不要求你往这段排序代码里喂进任何一个带有具体数值的实际输入。

它只要求你检验那些由0和1拼凑出来的二进制序列。

对于sort5(五个位置),根据零一原理,可以看做每个独立的位置上,要么是绝对的0,要么是绝对的1(非 0 即 1)。

于是,它的验证空间一下子就被不可思议地坍缩成了2?

=32。

只要你写出的这段代码网络,能够正确无误地把这三十二个全由0和1构成的序列排成单调递增的形状

那么,神奇且绝对的是,这段比较网络,对任何来自同一全序类型的五个输入都正确。

原本的微小的120,被再次降维压成了32。

如果是十六个数,原本极其恐怖的二十万亿,也能压缩成六万五千个。

一个微处理器闭着眼睛都能跑完的数字。

更重要的是,这三十二个简陋的0-1序列,还不是软件工程里充满玄学的抽样测试,也绝对不是测试工程师绞尽脑汁想出来的边界测试用例。

它在数学意义上,是不留死角的完备检查。

只要顺利地跑通这三十二个简单的序列,这段代码底层的绝对正确性,就被焊死在了真理的铁板上。

这种利用抽象的数学定理斩杀无限状态空间的快感,简直太美妙。

江临立刻在mpS-Kernel根目录下新建了一个python脚本文件。

verify_sort5_zero_one.

py

引入itertools.
本章未完,请翻下一页继续阅读.........