20220513数据结构绿皮书读书笔记

20220513数据结构绿皮书读书笔记
效率分析
程序运行哪里耗时最长？显然不是输入，因为只有一次，输出一般来说也很快。大量的计算都是在update方法个neighborCount方法的调用上，在每代update都需要重新计算每个细胞的邻居，在一个常见的布局中，可能仅有5%的细胞是存活的，并且集中在一个区域。因此update会消耗大量的时间在计算死亡的细胞上，他们没有存货的邻居，也不可能复活。如果95%的细胞都死了，那么下一代的计算是相当没有效率的
但是这种性能下降重要吗？一般来说不重要，因为对用户来说计算可以很快的完成，看起来就是一瞬间的事情。反过来说，如果你在一个很垃圾的电脑上运行这个程序，或者是分时的系统上，你才可能需要找出程序的时间耗费在了哪里。但是一般来说，优化这个程序的运行时间是没有必要的，即使它的效率并不高

编程原则
除非必要，否则不要去优化你的代码
当你的程序没有完成且正确运行的情况下不要开始优化
大多数程序90%的时间会花费在10%的指令上。找到这10%，把你的精力花费在这上面

另外一个原因就是优化一个程序通常会产生很复杂的代码，当程序需要修改的时候这会变得更加困难

编程原则
保持你的算法尽可能的简单，当有疑问选择最简单的方式实现

为了修订程序添加的边界限制，需要使用我们还没写的数据结构，等到了9.9章的时候，我们会重新来看这个程序，在那时候我们会找出一个更加高效的算法，因此那个新的程序会更加的通用以及有更好的计算效率

编程原则
有时候推迟问题可以简化解决方案（凡事三思而后行：能不能不做？能不能别人做？能不能明天做？）

思考题
如何让矩阵的宽度也由用户输入？把常量改了呗，改成变量，推迟申请数组内存的时间
一个提高性能的办法是删掉周围一圈边界，这样计算边界的时候就不用算那些永远都是0的格子了。这种做法在这个联系里值得做么？显然不值，边界占比才多少- –

P1. 修改程序的初始化方法，接受连续的空字符和多个x作为存活的表示。代替现有的坐标输入方式
代码自己改吧，懒得写，就是换下读取函数而已

P2. 支持从文件读初始值，同样是改输入函数

P3.当程序结束的时候，输出最后一次的布局到文件里，给上一个问题用

P4. 在任意一代生成的时候，支持用户可以手动编辑插入新的存活细胞

P5. 在任意一代生成时，如果用户想看帮助，支持打印帮助

P6. 增加单步模式，解释每一个细胞的变化和原因
你看我说什么来着，肯定有新需求，你要是第一版没记，实际工作加这种需求就GG了

P7. 使用光标定位功能来让打印局部更新，而不是完整输出所有布局
关于命令行的光标定位功能本质上也是一系列的特殊字符，但是麻烦的是当你想局部更新的时候，需要计算要更新的坐标和当前光标的坐标才能知道输出什么控制字符
这个会很有意思，但是我懒得动hhhh 看看得了，我确认我写的出来的我就不写了

P8. 使用不同的颜色来表示每一代变化了和没变化的细胞
这个同样也是7里的控制字符，有的控制字符能修改后续字符的颜色，准备好打印之前修改对应字符的颜色就好了，难点是需要额外信息记录哪个变了

本章内容均为基础，看了下主要的部分，其中一些在后面会逐渐加深难度，其他的将会在其他课程中学习，还有一些需要在实践中学习

软件工程的实际周期
1.完整的分析需求，确认需求的合理性
2.构建原型和实验直到所有的需求都满足
3.设计算法和数据结构
4.验证算法的正确性，或者让算法足够简单来保证有足够的自信确认
5.分析算法来确定它的依赖并且确认满足需求
6.编码实现
7.用合适的测试数据来评估程序
8.重构程序使其足够的functional，不知道怎么翻译，意思应该是可重用
9.当必要的时候，优化代码来提高性能
10.维护程序，面对后续用户所需要的更改

问题分析
因用户说的和计算机科学天然有鸿沟，所以以下问题用户必须理解
1. What form will the input and output data take? How much data will there be?
格式可以让产品定义好，但必须满足第一范式。不满足则继续追问
多少数据产品有概率不知道，可能得自己算

2. Are there any special requirements for the processing? What special occurrences will require separate treatment?
特殊逻辑，也是产品给。没给就是没有

3. Will these requirements change? How? How fast will the demands on the
system grow?
需求会变不会变的产品自己都不知道。。。更不用提变得多快了，pass

4. What parts of the system are the most important? Which must run most efficiently?
拿部分都重要，出bug就得修。。。不被测试和用户发现的bug那能是bug么？那是feature
大部分都不需要啥效率，能跑就得了，但设计上还是要最佳的方案，免得有坑。

5. How should erroneous data be treated? What other error processing is needed?
错误的数据拒绝处理，但要保证系统能正常对其他数据运行。最坏情况下影响到个别人可以接受，但影响所有人不可以

6. What kinds of people will use the software? What kind of training will they have? What kind of user interface will be best?
非后台开发需要考虑的，丢给前端和产品

7. How portable must the software be, so that it can move to new kinds of equipment? With what other software and hardware systems must the project be
compatible?
后台来说不需要，linux能跑就行

8. What extensions or other maintenance are anticipated? What is the history of previous changes to software and hardware
设计时有犹豫的，就留出扩展。记录原始数据备用。历史上改的东西只有天知地知git知

mark 目前是41页第1.6.3，pdf是58页
明天和后天看心情更新

20220512数据结构绿皮书读书笔记

维护程序的第一步就是review、分析、评估。思考如下几个问题
1.程序是否按需求正确解决了问题？
2.程序在所有条件下都能正常的工作吗
3.程序是否有一个好的用户界面？用户能否方便简单的输入，输出是否有用简洁？程序是否提供了可选的特性供使用者选择？是否包含足够的指导和其他信息？
4.程序的逻辑是否使用使用方便和简短的函数来清晰的书写，数据结构能否准确的反映程序的需要
5.程序是否有良好的文档？命名是否意义准确？对困难和主要的代码是否有解释？
6.程序对空间和时间的利用是否高效？通过修改算法能否让程序的性能进一步提升？

review整个程序
首先是问题的定义：
如果我们回去看问题定义的规则，会发现我们并没有完全遵守，规则没提到gird矩阵有边界，但我们定义了最大值。在程序中超出边界的细胞被我们忽略了。
虽然任意的计算机模拟都肯定会有边界，但我们定义了20 60这种数字太过随意，其实可以做到不限定矩阵大小，但在此之前我们需要实现几种特殊的数据结构。

编程原则
确认你完全理解了你的问题，如果你必须修改问题描述，清晰的解释你改了什么

然后是程序的正确性：
因为程序测试无法证明错误不存在，我们需要其他的方式来二次证明程序的正确性，构造符号来证明程序的正确性通常是困难的，但有的时候是可以做到的。
Life模拟这个程序只有update会修改数据，只有neighborCount会统计邻居，我们关注这两个
对于neighborCount，只有有限的几个邻居和状态，使用白盒测试构造几个case即可完整测试
对于update，每个单元格的邻居数量只有几种情况，分别测试输出即可

接着是用户交互界面：
对于初始化状态通过坐标输入其实是比较反人类的，部分布局非常复杂，人工计算容易出问题。所以最好是支持用户输入一整行的数据，空行代表都是死亡比较方便。或者是支持从文件读入。另一个选项就是允许用户通过任意方式自己编辑初始值。

输出也有提升空间，如果直接我们不是每次都重新打印，只再原来的输出上修改变化的部分，看起来会更好一些。（命令行里，这其实是可以做到的）

帮助信息，可以用弹框或其他形式，更加直观

一般来说，设计一个程序必须要慎重考虑用户的使用体验，大型程序很重要的一点就是提供用户界面，通常设计界面的精力要比其他所有地方加起来都要多

效率分析，下次更新，不一定是明天，明天放假了hhhh 可能是下周再说了
mark 目前是37页第6点，pdf是54页

20220511数据结构绿书读书笔记

20220511
Life类的定义
每个Life对象都需要包含一个矩形数组，用1表示存活的细胞，0表示死亡的细胞。这样表示的好处是，如果要计算一个特定细胞的邻居，我们只需要把相邻的加起来就行了。因为每代的更新中都需要重复的计算每个细胞的邻居数量，所以Life类应当包含一个成员方法neighborCount来做这个任务。因为client的代码不需要知道这个方法，所以设置成private

计算邻居
可以预见（这说法特别像数学证明里的显然可得，然而初学者设计程序并不会有这种经验，只能是踩过坑才知道），如果需要边界细胞的邻居需要更多的判断条件，我们可以做一些优化，让数组的实际大小比定义的大一些，周围留出一圈，这样既避免了从0开始数的麻烦，也避免掉了多余的判断，让所有单元格计算邻居的时候可以用相同的代码

更新矩阵
更新的动作是相当明确的，我们首先计算一个新的矩阵用于记录更新后的数据，然后完整的把新的数据复制回原地即可（直接用新的不好吗？）
更新过程的算法比较容易，我们遍历非边界的地方，然后判断存活邻居的个数，实际上只需要判断2个和3个就行，其他的无论如何都是死亡。
这里需要注意下，如果需求让你打印死亡或存活的原因，就不能这么更新了。这也是很多搞算法的同学容易忽略的，算法题往往只需要一个正确的结果，记录这个结果一个bit位或者一个int就能搞定，而真实的需求往往会要求记录更多的信息。在这个例子里，可能的需求就是记录下每个细胞存活和死亡的代数和原因，后面可能还有可能查出相同复活和死亡原因的细胞分布，或者统计每个细胞存活的代数。什么？你没记？你怎么能不记呢？不记到时候加需求你怎么做啊？hhhhhh
程序的运行应当尽可能的留痕以供人工查阅或后期处理，记录尽可能原始的数据，而不是像AI神经网络一样输出一个莫名其妙大概率正确的结果而不知道为什么
如果考虑实际需求，那么数组的类型就不能是int了，还得再套个对象，记录当前细胞每代更新对自己的影响结果这种原始数据备用，可以用于计算它的出生代数、死亡代数、存活实际等其他数据，以防产品后面加需求。这是一个来自刚工作几年没少踩坑的开发的经验之谈，信不信由你

输入和输出
程序一般设计上是给很多人使用的，输入和输出的方法通常是最长的，输入的程序需要完整检查用户出入的正确性和一致性，输出要合理的格式化，要好好考虑什么应该输出什么不应该

编程原则：
保持你的输出和输出再不同的方法里，来让他们可以被轻易的修改，让你的系统有一定的custom tailored

提示语打印程序是一个非常简单的程序，只负责打印提示

测试用例drivers
可以写一小段程序给一个方法提供一些特定的输入，单独测试一个方法的运行是否正常

程序跟踪和debug
一个很常用的工具就是打印语句，详细的打印程序执行时所处的位置和相关变量的状态，生产环境一般用日志框架来处理，有的公司会有完整的日志收集、搜索、监控平台来做这件事情，自己写着玩直接print就好
脚手架代码也可以在debug的时候提供额外的帮助，用过之后记得删掉就好。当你的程序出现奇怪的错误时，脚手架代码可以放在1个或2个主程序的关键位置，用于快速确认问题出现的具体行数。

程序测试原则
测试数据的质量远比测试数据的数量要重要
程序测试可以证明bug的存在型，但无法证明bug不存在

程序测试方法
黑盒测试
使用普通数据、特殊的正常数据、边界附近的数据、非法的数据（参考测试工程师进酒吧）

白盒测试
分析程序的的每个分支，对每个执行路径都进行测试，大型程序种这种测试并不现实，一般选择性测试主要的执行路径

Ticking-Box测试
不知道怎么翻译，翻译成随缘测试吧hhh
写完了让用户自己去用吧，出了问题一定是你不会用，才不是bug呢


import java.util.Scanner;

import javax.print.attribute.standard.PrinterLocation;

public class Main0510_1 {
    /**
     * 前置条件：用户指定了初始布局
     * 预期结果：根据规则打印所有存活的细胞
     * 依赖：Life类和成员方法initialize、print、update
     */
    public static void main(String[] args) {
        Life conf = new Life();
        instructions();
        conf.initialize();
        conf.print();
        System.out.println(&quot;是否继续下一代？&quot;);
        while (userSaysYes()) {
            conf.update();
            conf.print();
            System.out.println(&quot;是否继续下一代？&quot;);
        }
    }

    private static void instructions() {
        System.out.println(&quot;欢迎来到xxx游戏&quot;);
        System.out.println(&quot;这个游戏使用的布局大小是&quot; + Life.MAX_ROW + &quot;x&quot; + Life.MAX_COL);
        System.out.println(&quot;每个细胞都可以是活的也可以是死的&quot;);
        System.out.println(&quot;它们将一代代的根据邻居的存活数量不断迭代&quot;);
    }

    public static boolean userSaysYes() {
        try {
            Scanner in = new Scanner(System.in);
            boolean userInput = in.nextBoolean();
            return userInput;
        } catch (Exception e) {
            return userSaysYes();
        }
    }
}

class Life {
    public static final int MAX_ROW = 20;
    public static final int MAX_COL = 60;
    private int gird[][] = new int[MAX_ROW + 2][MAX_COL + 2];
    // 多两行两列用于方便计数，省的判断边界

    private int neighborCount(int row, int col) {
        int count = 0;
        for (int i = row - 1; i &lt; row + 1; i++) {
            for (int j = col - 1; j &lt; col + 1; j++) {
                count += gird[i][j];// 把存活的邻居记录上
            }
        }
        count -= gird[row][col];// 减去掉自己，因为自己不是自己的邻居
        return count;
    }

    public void initialize() {
        System.out.println(&quot;请输入存活细胞的坐标，以(-1,-1)结束，&quot;);
        System.out.println(&quot;格式为行&lt;空格&gt;列，从1开始数：&quot;);
        Scanner in = new Scanner(System.in);
        while (true) {
            int row = in.nextInt();
            int col = in.nextInt();
            // 正常程序建议in.nextLine()读入整行后trim
            // 然后先正则判断下格式对不对，避免脑残乱输入
            if (row == -1 || col == -1) {
                break;
            }
            boolean rowCorrect = row &gt;= 1 &amp;&amp; row &lt;= MAX_ROW;
            boolean colCorrect = col &gt;= 1 &amp;&amp; col &lt;= MAX_COL;
            if (!rowCorrect || !colCorrect) {
                System.out.println(&quot;行或列输入错误，MDZZ，再试一次吧&quot;);
                continue;
            }
            gird[row][col] = 1;
        }
    }

    public void print() {
        for (int row = 1; row &lt;= MAX_ROW; row++) {
            for (int col = 1; col &lt;= MAX_COL; col++) {
                int cell = gird[row][col];
                System.out.print(cell);
            }
            System.out.println();
        }
    }

    public void update() {
        int newGird[][] = new int[MAX_ROW + 2][MAX_COL + 2];
        for (int row = 1; row &lt;= MAX_ROW; row++) {
            for (int col = 1; col &lt;= MAX_COL; col++) {
                int neighborCount = neighborCount(row, col);
                if (neighborCount == 2) {
                    newGird[row][col] = gird[row][col];
                } else if (neighborCount == 3) {
                    newGird[row][col] = 1;
                } else {
                    newGird[row][col] = 0;
                }
            }
            gird = newGird;
        }
    }

}

100

101

102

103

104

105

106

107

108

109

110

import java.util.Scanner;

import javax.print.attribute.standard.PrinterLocation;

public class Main0510_1 {

/**

* 前置条件：用户指定了初始布局

* 预期结果：根据规则打印所有存活的细胞

* 依赖：Life类和成员方法initialize、print、update

public static void main(String[] args) {

Life conf = new Life();

instructions();

conf.initialize();

conf.print();

System.out.println("是否继续下一代？");

while (userSaysYes()) {

conf.update();

conf.print();

System.out.println("是否继续下一代？");

}

private static void instructions() {

System.out.println("欢迎来到xxx游戏");

System.out.println("这个游戏使用的布局大小是" + Life.MAX_ROW + "x" + Life.MAX_COL);

System.out.println("每个细胞都可以是活的也可以是死的");

System.out.println("它们将一代代的根据邻居的存活数量不断迭代");

}

public static boolean userSaysYes() {

try {

Scanner in = new Scanner(System.in);

boolean userInput = in.nextBoolean();

return userInput;

} catch (Exception e) {

return userSaysYes();

}

class Life {

public static final int MAX_ROW = 20;

public static final int MAX_COL = 60;

private int gird[][] = new int[MAX_ROW + 2][MAX_COL + 2];

// 多两行两列用于方便计数，省的判断边界

private int neighborCount(int row, int col) {

int count = 0;

for (int i = row - 1; i < row + 1; i++) {

for (int j = col - 1; j < col + 1; j++) {

count += gird[i][j];// 把存活的邻居记录上

}

count -= gird[row][col];// 减去掉自己，因为自己不是自己的邻居

return count;

}

public void initialize() {

System.out.println("请输入存活细胞的坐标，以(-1,-1)结束，");

System.out.println("格式为行<空格>列，从1开始数：");

Scanner in = new Scanner(System.in);

while (true) {

int row = in.nextInt();

int col = in.nextInt();

// 正常程序建议in.nextLine()读入整行后trim

// 然后先正则判断下格式对不对，避免脑残乱输入

if (row == -1 || col == -1) {

break;

}

boolean rowCorrect = row >= 1 && row <= MAX_ROW;

boolean colCorrect = col >= 1 && col <= MAX_COL;

if (!rowCorrect || !colCorrect) {

System.out.println("行或列输入错误，MDZZ，再试一次吧");

continue;

}

gird[row][col] = 1;

}

public void print() {

for (int row = 1; row <= MAX_ROW; row++) {

for (int col = 1; col <= MAX_COL; col++) {

int cell = gird[row][col];

System.out.print(cell);

}

System.out.println();

}

public void update() {

int newGird[][] = new int[MAX_ROW + 2][MAX_COL + 2];

for (int row = 1; row <= MAX_ROW; row++) {

for (int col = 1; col <= MAX_COL; col++) {

int neighborCount = neighborCount(row, col);

if (neighborCount == 2) {

newGird[row][col] = gird[row][col];

} else if (neighborCount == 3) {

newGird[row][col] = 1;

} else {

newGird[row][col] = 0;

}

gird = newGird;

}

20220511结束，耗时一个半小时，明天继续看程序的评估

20220510数据结构绿书读书笔记

20220510
解决方案：类、对象、方法
大概来说，一个程序运行上述游戏需要以下几个部分组成
1.算法
设置一个初始布局状态，打印这个布局状态，当用户想看下一代的时候根据规则更新布局状态并打印当前状态

2.类和对象
一个configuration布局实体/实例/对象，类型是Life，我们让这个对象使用Life的3个方法：initialize将会初始化一个最开始的状态，print打印当前布局，update让布局更新为下一代

一个Clients类，用于访问前面的对象，可以声明前面这些类的实例。一般可以叫做Main活着xxxTest之类的都ok

3.规范
当编写一个客户端程序的时候，一个很重要的点是我们不需要知道数据是如何存储的，也不需要知道这些方法是如何被编程的。这是自顶向下设计非常重要的一个转变，写代码多了就会熟悉这种思路。这通常被称为information hiding
当我们实现Life类的时候，我们才需要决定如何存储这些数据，以及如何实现这些方法，这些数据和方法对Life来说都是私有的，client程序不需要知道这些，只需要访问公开的方法即可


import java.util.Scanner;

public class Main0510_1 {
    /**
     * 前置条件：用户指定了初始布局
     * 预期结果：根据规则打印所有存活的细胞
     * 依赖：Life类和成员方法initialize、print、update
     */
    public static void main(String[] args) {
        Life conf = new Life();
        instructions();
        conf.initialize();
        conf.print();
        System.out.println(&quot;是否继续下一代？&quot;);
        while (userSaysYes()) {
            conf.update();
            conf.print();
            System.out.println(&quot;是否继续下一代？&quot;);
        }
    }

    private static void instructions() {
        System.out.println(&quot;打印使用指南&quot;);
    }

    public static boolean userSaysYes() {
        Scanner in = new Scanner(System.in);
        boolean userInput = in.nextBoolean();
        return userInput;
    }
}

import java.util.Scanner;

public class Main0510_1 {

/**

* 前置条件：用户指定了初始布局

* 预期结果：根据规则打印所有存活的细胞

* 依赖：Life类和成员方法initialize、print、update

public static void main(String[] args) {

Life conf = new Life();

instructions();

conf.initialize();

conf.print();

System.out.println("是否继续下一代？");

while (userSaysYes()) {

conf.update();

conf.print();

System.out.println("是否继续下一代？");

}

private static void instructions() {

System.out.println("打印使用指南");

}

public static boolean userSaysYes() {

Scanner in = new Scanner(System.in);

boolean userInput = in.nextBoolean();

return userInput;

}

编程中一个相当重要的道德行为就是命名规范，尽管数据和算法之前就存在了，但只有当给他们有意义的名字的时候，他们才能被正常的阅读。为了精确的理解每个变量和方法的作用，有时需要给类、变量、方法编写文档来说明。它们的名字应当简洁且清晰的精确表示他们的含义，寻找一个好的变量名并不总是一个简单的工作

使用小写字母l、大写字母O、数字0的时候需要额外的注意，底下是一个蛋疼的例子(吐槽下苹果上对于括号的渲染，也是个大坑)


l = 1; x = 1; x = l; x = O; O = 0;

l = 1; x = 1; x = l; x = O; O = 0;

注释要避免解释代码本身的动作，解释Why，而不是解释How


 count ++ //count自增1
 count ++ //增加xxx的计数，这里的xxx是上下文相关的，count的实际含义，虽然我一般会直接用xxxCount来避免这种注释

count ++ //count自增1

count ++ //增加xxx的计数，这里的xxx是上下文相关的，count的实际含义，虽然我一般会直接用xxxCount来避免这种注释

编程原则:

让程序的阅读起来更容易，因为一个程序的阅读时间要远多于编写时间
不要丢掉全局视野
用类来对基础概念进行建模
每个方法都应该只做一件事，但做到极致
每个类都应该隐藏一些东西
保持上下文简洁、如非必要，不要用全局变量
尽可能的避免边际效应，如果一定要用全局变量，写文档

编码&测试&重构
stub打桩技术，快速让主程序通过编译或为了方便测试，可以先搭架子


import java.util.Scanner;

public class Main0510_1 {
    /**
     * 前置条件：用户指定了初始布局
     * 预期结果：根据规则打印所有存活的细胞
     * 依赖：Life类和成员方法initialize、print、update
     */
    public static void main(String[] args) {
        Life conf = new Life();
        instructions();
        conf.initialize();
        conf.print();
        System.out.println(&quot;是否继续下一代？&quot;);
        while (userSaysYes()) {
            conf.update();
            conf.print();
            System.out.println(&quot;是否继续下一代？&quot;);
        }
    }

    private static void instructions() {
        System.out.println(&quot;打印使用指南&quot;);
    }

    public static boolean userSaysYes() {
        Scanner in = new Scanner(System.in);
        boolean userInput = in.nextBoolean();
        return userInput;
    }
}

class Life {

    public void initialize() {
    }

    public void print() {
    }

    public void update() {
    }


}

import java.util.Scanner;

public class Main0510_1 {

/**

* 前置条件：用户指定了初始布局

* 预期结果：根据规则打印所有存活的细胞

* 依赖：Life类和成员方法initialize、print、update

public static void main(String[] args) {

Life conf = new Life();

instructions();

conf.initialize();

conf.print();

System.out.println("是否继续下一代？");

while (userSaysYes()) {

conf.update();

conf.print();

System.out.println("是否继续下一代？");

}

private static void instructions() {

System.out.println("打印使用指南");

}

public static boolean userSaysYes() {

Scanner in = new Scanner(System.in);

boolean userInput = in.nextBoolean();

return userInput;

}

class Life {

public void initialize() {

}

public void print() {

}

public void update() {

}

20220510结束，耗时1小时10分钟
顺带一提，vscode Code-runner跑代码乱码可以这样解决


    &quot;code-runner.executorMap&quot;: {
        &quot;java&quot;: &quot;cd $dir &amp;&amp; javac -encoding utf-8 $fileName &amp;&amp; java -Dfile.encoding=UTF-8 $fileNameWithoutExt&quot;
    }

"code-runner.executorMap": {

"java": "cd $dir && javac -encoding utf-8 $fileName && java -Dfile.encoding=UTF-8 $fileNameWithoutExt"

}

20220509数据结构绿书读书笔记

20220509
数据结构读书笔记
全书目录如下
1.编程原则
2.栈
3.队列
4.链栈&队列
5.回溯
6.列表和串
7.搜索
8.排序
9.表格与信息检索
10.二叉树
11.多叉树
12.图
13.波兰式

开坑！

第一章其实上学时候就看过，我很多的习惯都是因为这本书才养成的，但当时并没有记录- -，这次一并补上，看英文书的好处就是写的足够详细，什么时候读都能get到作者的意思，不好的地方就是太啰嗦了。但好在我是为了消磨时间才立的这个flag
编写一个large的程序往往有很多问题，这里的large可以理解为实现复杂或者规模庞大
问题1.精确的定义问题
拆分并逐渐分割成小问题，直到可以方便处理
问题2.程序设计
“先跑起来再慢慢优化”对小程序也许有用，但并不适合large的程序，大型程序的每个部分都需要良好的组织、清晰的实现、良好的可读性，否则它将难以复用或被他人阅读
问题3.选择合适的数据结构
同一个问题多种算法和数据结构都能解决，很难选择出一个最好的。在算法设计上一般来说选择的最好方法是看数据是如何存储的：
1.数据之间的关系是怎样的
2.那些数据保持在内存中
3.当需要的时候哪些数据已经被计算好了
4.哪些数据是存在文件里的？文件是如何被组织的
后面会先学列表、栈、队列，然后再学几个厉害的算法来对数据做处理，比如排序和搜索
问题4.算法分析
当有多种方法管理数据和设计算法的时候，就必须有一个标准来帮忙评判算法。
问题5.测试和验证程序的正确性
debug程序的难度会随着程序的规模而增加，可能是指数级
正确性：减少错误，让程序更加方便维护、方便我们验证算法是正确的、有方法可以测试我们的程序，让我们自信的说程序没有非预期行为

问题6.维护
当程序开始提供服务后，可能还会有新的需求

吹一波C++NB：
C++允许抽象数据、允许面向对象设计、允许自顶向下的设计方法、允许代码重用。。。。。

casestudy GameOfLife
cell不知道是翻译作细胞更好，还是叫单元格更好，反正前面都说grid的了，我就先当成细胞了
生存模拟，在一个无边界的矩阵中每个细胞都可以被有机物占用或不占用，被有机物占用的被称作“活着”，未被占用的称作“死的”
规则如下
1.给定1个细胞，它相邻的8个细胞都可以被接触，横竖斜都可以，称之为邻居
2.如果一个细胞活着，但同时邻居都没有存活，或仅剩1个存活，则在下一代将因孤独而死
3.如果一个细胞活着，但同时有4个或4个以上的邻居存活，则在下一代将因拥挤而死
4.如果一个存活的细胞有2个或3个邻居存活，则在下一代可以继续保持存活
5.如果一个细胞死了，但如果正好有3个活着的邻居，那么在下一代将被复活。所有死亡的其他细胞在下一代将保持死亡状态（这不是废话么hhh）
6.所有的生死均在一瞬间同时完成，所以正在死亡的细胞可以帮助其他细胞复活，但无法阻止其他细胞因拥挤导致的死亡。刚出生的细胞也无法复获或杀死上一代存活的细胞

一组特定排列的细胞叫做初始布局，上面的规则描述了一个布局如何在每代更替中变为下一个布局

多样性；有的布局会很快死干净、有的会从很小一点涨到巨大。。。难以人工预测
小目标：写一个程序模拟一个初始布局是如何一代代变化的
这个游戏被发明后不久，MARTIN GARDNER就在Scientific American的专栏里讨论过，被很多人所吸引

跳过面向对象基础部分，直接进入正题

本书的后续将严格区分method和function，中文翻译为方法和函数，方法是公开的，函数是私有的。（我写笔记会尽量遵守，但不保证hhhh

虽然书用的是C++，但并不影响我使用Java来表达相同的内容，代码将于我觉得可以的时机，公开在github和gitee上
耗时一个半小时，才读了8页hhhh，能读得完么= = 后面少记点笔记也许能读的快点
20220509结束

20220424树的布局算法

某群友需要绘制树形结构数据到excel中，拍脑袋想了下感觉不是很难，遂给出算法分析。

偷懒用了excel的column和row函数获取所在行列，直接能看到结果，目测也是算得出来结果的

因为要求是横着的，所以例子是横着的。但算法定义时候是竖着思考的，所以用的是宽度w和距离左侧的宽度l，算完了再横过来画就完了

首先这样定义子节点宽度：
当不存在子节点(即叶子节点)时，宽度为1
当存在子节点时，如果子节点为奇数n则宽度为n，如果为偶数n则宽度为n+1。说明：因为偶数的情况下父节点需要居中占一个，(n+1)/2的位置要空着给父节点
然后计算节点距离左侧长度l：取已知的层序i
如果是非叶子节点：取上一步宽度w, l=(w-1)/2，如果i>1再加上前面所有节点计算的宽度，如果当前层是偶数个子树则再+1
如果是叶子节点，取所在子树上一步计算的宽度，直接铺开排列。非首个子树加下前面的所有宽度，注意偶数子树情况下中间空1个。

偷懒没实现，谁有兴趣可以写下代码试试，允许使用任意数据结构存储相关信息

有个好的文章参考

https://llimllib.github.io/pymag-trees/

20211023.Web后端参数检查的通用代码生成设计与实现

Web后端参数检查的通用代码生成设计与实现

前言

本文章来自这里，主要讨论&设计常见接口实现逻辑中的参数校验部分，主要是实现到Controller实现逻辑的时候决定修改总计划，不再追求全流程代码生成，原因不再赘述。

需求价值

简化&替代实际业务场景下常见的参数校验代码编写，提高开发效率，减少浪费在Copy And Paste上的宝贵生命

目标

实现参数校验部分的meta-model&对应的代码生成器

需要支持自动生成常见的校验策略，包括字符串trim后非空、字符串长度、字符串分中英文字符长度限制、数字范围、数据库存在性校验、多字段直接人工定义的约束校验等

校验策略支持2种，打断or完整校验

校验结果分为校验成功和校验失败

支持选择是否生成校验上下文记录额外IO的结果

其中完整策略下校验失败时支持生成详细的校验结果用于程序判断原因

支持校验结果自定义处理，打断策略下默认抛一个异常让开发者自己处理

支持的组合如下

1.打断策略

1.1.校验成功

1.1.1.不生成上下文

返回值void，结束方法运行

1.1.2.生成上下文

返回值中包含所有额外IO的原始结果变量

1.2.校验失败

打断策略下遇到任何一个校验错误都会直接停止后续校验，抛出异常和错误信息，这个错误信息给人看的，不支持程序来判断原因。

1.2.1.不生成上下文

异常中不包含上下文信息

1.2.2.生成上下文

异常中包含所有额外IO的原始结果变量

2.完整策略

2.1.校验成功

2.1.1.不生成上下文

返回值void，结束方法运行

2.1.2.生成上下文

返回值中包含所有额外IO的原始结果变量

2.2.校验失败

2.2.1.不生成上下文

异常中不包含上下文信息

2.2.2.生成上下文

异常中包含所有额外IO的原始结果变量

2.2.3.不生成详细的校验结果

异常中不包含详细错误信息

2.2.4.生成详细的校验结果

异常中需要包含校验失败的字段以及错误信息

需求分析

spring内置了@Valid注解来完成单一对象下单独属性的检查，且支持扩展自定义逻辑。看上去很好，很强大。

虽然但是，实际如果你用了，就会发现在真实业务流程下，这种校验有多鸡肋。

spring理解的校验：通过代码或注解定义静态规则，且可以让开发者拿到过不去规则的原因

简单的校验大概都是getXXX 然后做基础的校验，这部分基础校验就是spring理解的校验，如果失败打断流程，成功要把继续往下执行。

复杂校验往往依赖前面校验的结果，或依赖其他字段的状态，或依赖数据库来做校验。比如queryDbByXXX 成功则取部分内容继续流程，失败则打断。

根据工作经验来看，实际业务的校验往往不是单纯的单一规则校验就能完成，同时为了性能考虑校验过程中查到的数据库的结果还需要给下一步操作来使用。

这时候会面临方案选择：1.简单校验使用spring注解，复杂校验手动编写逻辑。2.全部手动编写逻辑

如果是写新需求：

方案1和2往往都是找个相同类型已有的类似代码，改字段、注解、属性名。这个过程将会占用大量时间在Copy And Paste，且毫无编程体验，可以说真的是板砖，并且还是从乱七八糟的地方搬

如果是维护改造类任务：

无论方案1还是2你会发现校验逻辑会比较分散，可能出现在类的属性注解、Controller的参数注解、各个Service的不知道第几层嵌套里。如果有人还用了反射来实现，那更是轻易找不全逻辑。

这时候如果想服用已有代码的部分业务流程，你就得小心的从原有屎山代码中拆分校验逻辑和业务逻辑。

虽然方案1可以通过ThreadLocal或缓存等手段来跨方法传递保存Spring校验过程中产出的上下文信息(比如从数据库查出的对象)，但这样做无形中增加了代码后续的维护成本和理解难度。后续维护麻烦不说且容易改丢东西。所以实际开发中一般还是要手动写代码实现而不是仅简单的使用spring注解。

因此设想一种方案3，在代码之外尽可能简单的定义这些约束条件，通过代码生成器自动生成指定类实例(下文可能称之为对象，一个意思)的校验代码逻辑

概要设计

说了这么多其实可以类比数据关系约束对这完整性的描述(可能不够严谨，但意思大概对)：

1.实体完整性

对象中的每个字段，是否都满足自身的约束，如字符非空/字符长度/数字值范围/字符串枚举等

这些校验实现起来相对简单，无需额外IO，校验所依赖的数据输入仅是字段的值本身，按每个规则直接实现即可。如果有多个规则，则同时执行多条校验即可

2.参照完整性

情况1 对象中的每个字段如果是另一个对象的主属性

情况2 另一个对象通过引用形式嵌入到了当前对象中

对于情况1 这种校验往往仅靠CPU无法完成，需要额外IO操作，比如查mysql数据库、redis。额外IO操作的结果后续可能有用也可能没用，如果校验通过了，可能就要继续用，否则大概率是没用的

对于情况2 和关系型数据库定义不一样的是，当对象的字段是引用且必填时候，需要额外校验引用非空，同时递归校验该引用对象的完整性

3.用户定义完整性

除了1，2意外的规则都可以纳入用户定义完整性

例如:字段间的特殊关联约束（字段1=A时字段2必须=BCD）

这部分校验和业务逻辑会有部分重合，需要根据情况来慎重决定是应该算作校验还是业务逻辑，必要时需要慎重选择

个人建议当这个规则后续大概率在业务中永远需要校验时才算业务逻辑，否则均按校验逻辑处理，避免污染核心业务逻辑。

例如用户A仅能修改uid=A的数据行：在不需要管理后的时候，算业务逻辑。当管理后台有超管可随意修改时，算校验逻辑。

详细设计

校验流程依赖元模型提供校验规则信息，因此需要进行元模型设计

校验流程分为主流程方法签名、主流程实现、子流程方法签名、子流程实现四部分。主流程由多个子流程实现，子流程由多个子代码模板组合而成。

1.元模型设计

已有定义：请求参数(Payload)包含多个属性(Attr)，每个属性类型可能是字符串(Str)、整数(Int)、长整数(Long)、引用类型(ReferencedType)

1.1.类抽象结构设计

abstract Eclass AbstractCheckRule{// 约束的抽象父类使用EReference作为Payload和Attr的子节点

EString desc

}

abstract Eclass DomainEntityCheckRule extends AbstractCheckRule 实体完整性

Eclass ReferencedCheckRule extends AbstractCheckRule 参照完整性 {

EReference Dto;

}

abstract Eclass UserDefinedCheckRule extends AbstractCheckRule 用户定义完整性

Eclass CustomCheckRule extends UserDefinedCheckRule 留个自定义的类方便扩展任意校验操作

逻辑上第一种DomainEntityCheckRule和第二种ReferencedCheckRule 字段校验的规则附加在属性(Attr)上，第三种校验附加在Payload上

1.Payload的Attr来自于DomainEntity的Attr映射：~~优先使用DomainEntity的AbstractCheckRule 子节点，同名的checkRule覆盖DomainEntity的~~(表达式可能不好写，先不实现)

2.Payload的Attr不是来自于DomainEntity的Attr映射：使用自己的AbstractCheckRule 子节点

3.Payload来自于DomainEntity映射：~~优先使用DomainEntity的AbstractCheckRule 子节点，同名的checkRule覆盖DomainEntity的~~(表达式可能不好写，先不实现)

4.Payload不是来自于DomainEntity映射：使用自己的AbstractCheckRule 子节点

对有映射关系的Payload或Attr来说，暂时考虑实现为合并DomainEntity的AbstractCheckRule，同时Payload增加CheckRuleMixIn属性支持合并其他Payload的AbstractCheckRule(参考Python的MixIn设计模式可以灵活增加通用的规则，之所以不用继承是因为避免模型管理的困难，不便于后期搜索功能的实现)

1.2.常用校验规则设计

目前的数据类型分为基本数据类型PrimitiveType和引用类型ReferencedType

基本类型包括字符串str，整型int，布尔类型bool, 长整型long

引用目前类型包括Dto，RequestPayload，ResponseResult

继续声明常用具体的检测逻辑

abstract Eclass PrimitiveTypeCheckRule extends DomainEntityCheckRule

abstract Eclass ReferencedTypeCheckRule extends ReferencedCheckRule

Eclass MustNotNullCheckRule extends PrimitiveTypeCheckRule, ReferencedTypeCheckRule

Eclass MustNullCheckRule extends PrimitiveTypeCheckRule, ReferencedTypeCheckRule

1.2.1.字符串str

abstract Eclass StringTypeCheckRule extends PrimitiveTypeCheckRule

Eclass NotEmptyCheckRule extends StringTypeCheckRule

Eclass LengthCheckRule extends StringTypeCheckRule {

EInteger min

EInteger max

}

Eclass RegexCheckRule extends StringTypeCheckRule {

EString regex

}

1.2.2.数字int long

abstract Eclass NumberTypeCheckRule extends PrimitiveTypeCheckRule

abstract Eclass IntegerTypeCheckRule extends NumberTypeCheckRule

abstract Eclass LongTypeCheckRule extends NumberTypeCheckRule

Eclass IntegerRangeCheckRule extends IntegerTypeCheckRule {

EInteger min

EInteger max

}

Eclass LongRangeCheckRule extends LongTypeCheckRule{

ELong min

ELong max

}

1.2.3.布尔 bool

abstract Eclass BoolTypeCheckRule extends PrimitiveTypeCheckRule

Eclass TrueValueCheckRule extends BoolTypeCheckRule

Eclass FalseValueCheckRule extends BoolTypeCheckRule

1.2.4.引用类型

abstract Eclass DtoTypeCheckRule extends ReferencedTypeCheckRule

Eclass HasValueRefCheckRule extends DtoTypeCheckRule, MustNotNullCheckRule

2.模板设计

子模板需要提供方法签名模板、各数据类型校验流程模板

2.0.代码转写

进行元模型M2T设计，仅凭设计稿基本难以一次性写对，因此在这里开始代码人工转写。基本都是人工先转写一版，再照着转写的结果进行M2T代码的开发。

2.1.方法签名设计

根据目标描述，对校验行为分类，确定Java返回值和参数签名


class CheckContext {
    ExtIOVar var1;
    ExtIOVar var2; 
}
class CheckException {
    CheckContext context; 
    String msg;
}

class CheckContext {

ExtIOVar var1;

ExtIOVar var2;

}

class CheckException {

CheckContext context;

String msg;

}

1.1.1.打断策略、校验成功、不生成上下文|返回值void，结束方法运行

1.2.1.打断策略、校验失败、不生成上下文|返回异常，异常中不包含上下文信息


void check1(Payload aPayload) throws CheckException; //可以考虑和1.1.2 1.2.2合并，返回null即可

0 1	void check1(Payload aPayload) throws CheckException; //可以考虑和1.1.2 1.2.2合并，返回null即可

1.1.2.打断策略、校验成功、生成上下文|返回上下文，上下文中包含所有额外IO的原始结果变量

1.2.2.打断策略、校验失败、生成上下文|返回异常，异常中包含所有额外IO的原始结果变量


CheckContext check2(Payload aPayload) throws CheckException;

0 1	CheckContext check2(Payload aPayload) throws CheckException;

2.1.1.完整策略、校验成功、不生成上下文|返回值void，结束方法运行

2.1.2.完整策略、校验成功、生成上下文|返回上下文，上下文中包含所有额外IO的原始结果变量

2.2.1.完整策略、校验失败、不生成上下文|返回异常，异常中不包含上下文信息

2.2.2.完整策略、校验失败、生成上下文|返回异常，异常中包含所有额外IO的原始结果变量

2.2.3.完整策略、校验失败、不生成详细的校验结果|返回异常，异常中不包含详细错误信息

2.2.4.完整策略、校验失败、生成详细的校验结果|返回异常，异常中需要包含校验失败的字段以及错误信息


CheckResult check4(Payload aPayload);
class CheckResult {
    boolean result;
    CheckContext context;
    List<CheckException> exceptions;
    CheckResult referencedAttrResult1;
    CheckResult referencedAttrResult2;
    //.... other referencedAttrResultx
}

CheckResult check4(Payload aPayload);

class CheckResult {

boolean result;

CheckContext context;

List<CheckException> exceptions;

CheckResult referencedAttrResult1;

CheckResult referencedAttrResult2;

//.... other referencedAttrResultx

}

2.2.方法签名生成逻辑设计

[xxxx/]代表Acceleo中的元模板占位

Payload元模型节点定义

Payload.genClassName 生成类名

Payload.name Payload的名字

对Payload子类的实例对象aPayload做M2T转换规则设计如下：


class AAAPayload {
    private String a;
}
AAAPayload aaaPayload;
//预期生成代码签名为
CheckContext checkAAAPayload(AAAPayload aaaPayload) throws CheckException;
//MTL模板对应为
CheckContext check[aPayload.genClassName()/]([aPayload.genClassName()/] [aPayload.name/])

class AAAPayload {

private String a;

}

AAAPayload aaaPayload;

//预期生成代码签名为

CheckContext checkAAAPayload(AAAPayload aaaPayload) throws CheckException;

//MTL模板对应为

CheckContext check[aPayload.genClassName()/]([aPayload.genClassName()/] [aPayload.name/])

2.3.数据类型校验设计

对任意属性 checkAttr(anAttr:Attr)

做对anAttr的type做类似于instance of的类型判断如下：

对字符串 checkStr(v->predicate(v))

对数值 checkNumber(v->predicate(v))

对布尔checkBool(v->predicate)

对引用类型来说 checkRef(ref->predicate(ref)) && ref.attrs.forEach(attr->checkAttr(attr))

MustNotNullCheckRule


ValueUtils.notNull(payload.getUser(), "empty user");//代码

0 1	ValueUtils.notNull(payload.getUser(), "empty user");//代码


genMustNotNullCheckRule(varRef:EString, varRefName:EString)
ValueUtils.notNull(varRef, "empty [varRefName/]");//mtl模板

genMustNotNullCheckRule(varRef:EString, varRefName:EString)

ValueUtils.notNull(varRef, "empty [varRefName/]");//mtl模板

2.1.1.字符串 str

NotEmptyCheckRule


ValueUtils.notEmpty(user.getEmail(), "empty user.email");//代码

0 1	ValueUtils.notEmpty(user.getEmail(), "empty user.email");//代码


genNotEmptyCheckRule(varRef:EString, varRefName:EString)
ValueUtils.notEmpty(varRef, "[varRefName/] is empty");//mtl模板

genNotEmptyCheckRule(varRef:EString, varRefName:EString)

ValueUtils.notEmpty(varRef, "[varRefName/] is empty");//mtl模板

Eclass LengthCheckRule


ValueUtils.strLength(user.getEmail(), 1, 1, "user.email length error");//代码

0 1	ValueUtils.strLength(user.getEmail(), 1, 1, "user.email length error");//代码


genLengthCheckRule(varRef:EString, varRefName:EString, aRule:LengthCheckRule)
ValueUtils.checkLength(varRef,aRule.min, aRule.max, "[varRefName/] length error");//mtl模板

genLengthCheckRule(varRef:EString, varRefName:EString, aRule:LengthCheckRule)

ValueUtils.checkLength(varRef,aRule.min, aRule.max, "[varRefName/] length error");//mtl模板

RegexCheckRule


ValueUtils.checkRegex(user.getEmail(), ".*", "user.email length error");//代码

0 1	ValueUtils.checkRegex(user.getEmail(), ".*", "user.email length error");//代码


genRegexCheckRule(varRef:EString, varRefName:EString, aRule:RegexCheckRule)
ValueUtils.checkRegex(varRef, "[aRule.regex/]", "[varRefName/] regex check error");//mtl模板

genRegexCheckRule(varRef:EString, varRefName:EString, aRule:RegexCheckRule)

ValueUtils.checkRegex(varRef, "[aRule.regex/]", "[varRefName/] regex check error");//mtl模板

2.1.2.数字

代码结构设计 https://github.com/956237586/realworld-mdd/blob/master/src/main/java/cn/hylstudio/mdse/demo/realworld/util/ValueUtils.java#L69

模板设计参考 https://github.com/956237586/hyldesigner-codegen/blob/main/src/cn/hylstudio/mdse/demo/gen/abstractCheckRule.mtl#L41

2.4.主校验流程设计

因限定了参数校验的范围，因此主流程可以固定下来，不会陷入无限接近代码的怪圈。

按前面所说校验分为三类依次执行，其中2和3可能产生CheckContext。

对指定对象的每个属性，依次获取子节点下+引用源子节点下的所有规则，并根据规则执行生成逻辑

20220130目前只取了当前子节点下的，未获取源子节点下的，CheckContext因和数据库有关，因此推迟