计算机程序 等价于 状态机

· 1249 words · 3 minute read

计算机的本质 🔗

软件、程序可以很复杂。但是计算机的本质还是冯诺伊曼定义的：程序存储，指令驱动执行。
程序存储在内存，程序里的指令驱动改变程序的状态机变化，变到下一个状态或者终止状态。

每个人都在刷题、刷算法题，那这种自发的内卷和外部环境带来的外卷的意义是什么？
除了这题我遇到过，做过，这题我会做以外，能得出个什么信息和结论？

为什么明明程序只有几行代码，确写错或者写不出来？
因为程序虽然只有几行，但是程序执行过程中的状态机中状态挺多的。

如何证明程序写得就是对的，或者如何模拟执行程序？
可以列出状态机，证明程序是work。
以快速排序为例，将程序描述为表格状态机，以状态机的视角解析程序执行的过程。 表格的每一行可以认为是程序对应的等价状态机当前处于的一个状态描述。

软件中的大局观 🔗

软件是取、舍的平衡艺术。

空间和时间的取舍 🔗

性能优化：空间和时间的互换。
索引，缓存： 空间换时间
hash表， 二叉搜索树，avl树，红黑树，降低树的深度，变成多叉树（B树， B+树，LSM树，Trie树），跳表skiplist， 倒排索引
压缩： 时间换空间

func quick_sort(arr []int) {
    if len(arr) < 2 {                                 //1
        return                                        //2
    }                                                 //     
    var start, index int = 0, 0                       //3
    for i := 1; i < len(arr); i++ {                   //4
        if arr[i] < arr[start] {                      //5
            index++                                   //6
            arr[i], arr[index] = arr[index], arr[i]   //7
        }                                             //
    }                                                 //
    arr[start], arr[index] = arr[index], arr[start]   //8
    quick_sort(arr[start:index])                      //9
    quick_sort(arr[index+1:])                         //10
}

假设arr=[8, 5, 2, 6, 9, 3, 1, 4, 0, 7]

step i index start arr
1#inc1 undef undef undef [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
2#inc3 undef 0 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
3#inc4 1 0 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
4#inc5 1 0 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
5#inc6 1 1 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
6#inc7 1 1 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
7#inc4 2 1 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
8#inc5 2 1 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
9#inc6 2 2 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
10#inc7 2 2 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
11#inc4 3 2 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
12#inc5 3 2 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
13#inc6 3 3 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
14#inc7 3 3 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
15#inc4 4 3 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
16#inc5 4 3 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
17#inc4 5 3 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
18#inc5 5 3 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
19#inc6 5 4 0 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
20#inc7 5 4 0 [8, 5, 2, 6, 3, 9, 1, 4, 0, 7]
21#inc4 6 4 0 [8, 5, 2, 6, 3, 9, 1, 4, 0, 7]
22#inc5 6 4 0 [8, 5, 2, 6, 3, 9, 1, 4, 0, 7]
23#inc6 6 5 0 [8, 5, 2, 6, 3, 9, 1, 4, 0, 7]
24#inc7 6 5 0 [8, 5, 2, 6, 3, 1, 9, 4, 0, 7]
25#inc4 7 5 0 [8, 5, 2, 6, 3, 1, 9, 4, 0, 7]
26#inc5 7 5 0 [8, 5, 2, 6, 3, 1, 9, 4, 0, 7]
27#inc6 7 6 0 [8, 5, 2, 6, 3, 1, 9, 4, 0, 7]
28#inc7 7 6 0 [8, 5, 2, 6, 3, 1, 4, 9, 0, 7]
29#inc4 8 6 0 [8, 5, 2, 6, 3, 1, 4, 9, 0, 7]
30#inc5 8 6 0 [8, 5, 2, 6, 3, 1, 4, 9, 0, 7]
31#inc6 8 7 0 [8, 5, 2, 6, 3, 1, 4, 9, 0, 7]
32#inc7 8 7 0 [8, 5, 2, 6, 3, 1, 4, 0, 9, 7]
33#inc4 9 7 0 [8, 5, 2, 6, 3, 1, 4, 0, 9, 7]
34#inc5 9 7 0 [8, 5, 2, 6, 3, 1, 4, 0, 9, 7]
35#inc6 9 8 0 [8, 5, 2, 6, 3, 1, 4, 0, 9, 7]
36#inc7 9 8 0 [8, 5, 2, 6, 3, 1, 4, 0, 7, 9]
37#inc4 10 8 0 [8, 5, 2, 6, 3, 1, 4, 0, 7, 9]
38#inc8 undef 8 0 [7, 5, 2, 6, 3, 1, 4, 0, 8, 9]
39#inc1 ... ... ... ...
... ... ... ... ...

简单8位二进制CPU的设计与实现 🔗

半导体 -〉逻辑门 -〉模块 -〉 CPU

一位二进制的加法器 🔗

真值表 -〉 真值表达式 -〉 与或非的门电路
真值表:

A B C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

只需要关心真值表中等于1的行
真值表达式:
$$ \begin{aligned} S = & \overline{A}B + A\overline{B} \ C = & AB \end{aligned} $$

全加器（两位以上） 🔗

减法（补码） 🔗

减一个数X == 利用加一个数（- X）的补码。

R-S触发器 🔗

。。。

linux