第107章 三十二个证人（3 / 7）
不会要求你去检验全部的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.product，暴力地生成全部確定的三十二个0-1序列。
对每一个独立的序列，机械地跑一遍外部掛载的候选排序网络代码。
严格地检查输出序列是否满足单调不减。
三十二个严苛的证人，只要全部通过，程序就会返回绿色的【proven valid】（证明有效）。
而只要有任何一个微小的序列无法通过，程序就会將那个反例直接吐出来，无情地枪毙这段代码。
三十二个全过，返回已证明。
任何一个不过，把那个反例吐出来。
江临敲下回车键，拿陈启明团队提供的那份原始的 /baseline/sort5_pure.c 暴力地跑了一遍夹具。
绿色。
三十二个0-1证人，在严密的数学法庭上，没有一个翻供。
正確性的地基，有了。
接下来的是神仙打架的活：在所有正確的排序网络里，找出最好的那一个。
江临开始把他在铺砌几何中经过千锤百炼的mps搜索骨架，巧妙地往这个代码问题上套。
做砖时，状態是一块局部铺砌，动作是放下一块新砖，胜利条件是排除所有拓扑逃逸。
现在呢？ ↑返回顶部↑
它只要求你检验那些由0和1拼凑出来的二进位序列。
对於sort5（五个位置），根据零一原理，可以看做每个独立的位置上，要么是绝对的0，要么是绝对的1（非 0 即 1）。
於是，它的验证空间一下子就被不可思议地坍缩成了2?=32。
只要你写出的这段代码网络，能够正確无误地把这三十二个全由0和1构成的序列排成单调递增的形状
那么，神奇且绝对的是，这段比较网络，对任何来自同一全序类型的五个输入都正確。
原本的微小的120，被再次降维压成了32。
如果是十六个数，原本极其恐怖的二十万亿，也能压缩成六万五千个。
一个微处理器闭著眼睛都能跑完的数字。
更重要的是，这三十二个简陋的0-1序列，还不是软体工程里充满玄学的抽样测试，也绝对不是测试工程师绞尽脑汁想出来的边界测试用例。
它在数学意义上，是不留死角的完备检查。
只要顺利地跑通这三十二个简单的序列，这段代码底层的绝对正確性，就被焊死在了真理的铁板上。
这种利用抽象的数学定理斩杀无限状態空间的快感，简直太美妙。
江临立刻在mps-kernel根目录下新建了一个python脚本文件。
verify_sort5_zero_one.py
引入itertools.product，暴力地生成全部確定的三十二个0-1序列。
对每一个独立的序列，机械地跑一遍外部掛载的候选排序网络代码。
严格地检查输出序列是否满足单调不减。
三十二个严苛的证人，只要全部通过，程序就会返回绿色的【proven valid】（证明有效）。
而只要有任何一个微小的序列无法通过，程序就会將那个反例直接吐出来，无情地枪毙这段代码。
三十二个全过，返回已证明。
任何一个不过，把那个反例吐出来。
江临敲下回车键，拿陈启明团队提供的那份原始的 /baseline/sort5_pure.c 暴力地跑了一遍夹具。
绿色。
三十二个0-1证人，在严密的数学法庭上，没有一个翻供。
正確性的地基，有了。
接下来的是神仙打架的活：在所有正確的排序网络里，找出最好的那一个。
江临开始把他在铺砌几何中经过千锤百炼的mps搜索骨架，巧妙地往这个代码问题上套。
做砖时，状態是一块局部铺砌，动作是放下一块新砖，胜利条件是排除所有拓扑逃逸。
现在呢？ ↑返回顶部↑