背景

今天和大佬聊天的时候聊到了现在的项目架构让我感觉非常混乱，大佬给我看了一些理想的架构，以及一些理想的对应方法

参考资料

• clean architecture
• 关于repository的pattern

一些交流笔记

总体来说，可以分成三个部分

• interface部分，包括前段，form，controller，webBean等等的内容
• application的业务逻辑部分，包括各种interface，service（logic），repository interface，repository
• 更高层级的业务部分（domain，flow）等，在开发的时候可以不考虑

从根本上来说，所有的代码都可以写在一起，但是划分这么多层级的主要目的就是消减代码之间的依赖关系。比如如果把业务逻辑写在controller里面，那么修改逻辑的时候就必须要从controller里面再去寻找了。更严重的问题，比如在service层级里面有大量依存数据库的代码，那么更改数据库之后所有的地方都需要更改。

• 最理想的方式是service和repository里面都带有interface，这样不需要触碰更深一层的代码（但是太理想了现在的业务里做不到）
• repository的最大存在意义是处理很复杂的select逻辑->（所以如果特别简单的数据读取（比如index）可以考虑跳过repository，但是相当于增加了对数据库的依存）

repository pattern的阅读笔记

根本目的：和DAO相似的设计模式，用高度抽象的操作隐藏具体的数据库操作（也就像JPA里面只给我们看interface）。这样用repository的人不用考虑底层用的什么数据库（MySQL还是Redis），而是直接跟interface交涉

经常出现的一些反面教材

按照功能分开repository

对于一个entity，按照不同的功能分出来了好几个repository

• 光看一眼不知道用哪个功能，业务逻辑也被分散在不同的地方
• 因为太混乱，所以业务逻辑上更容易出问题
• 对策
  • 意识到repository只是对底层的对数据库的读写，不要加入进去太多的业务逻辑
  • 把这个功能整合到service里面

对于子table做很多个repository

比如用户对应的住所，联络方式等等多个表，每个表都有一个repository

• 如果联络方式有两个种类（自家电话，手机），同时注册用户的时候要求必须有一种联系方式。这样的话虽然是跟用户有关的操作但是必须放在联络方式的repository里面，变得更混乱了
• 对策
  • DDD集约，也就是跟这个entity（用户）有关系的必须都经过一个object
  • （但是不太适合太复杂的情况，太多了）

复杂的query

比如要找：没有退会+最近三个月登陆过+最近一个月买过10个以上商品的

• 问题：需要从id的到商品记录，在count买过的商品数。这种比较大的query会引起一些性能上的问题以及维护上的混乱
• 对策 CQS(Command Query Separation)
  • command和query分离的方法
  • 复杂的query不装在repository里面，而是直接装在业务逻辑里面（也就是service层）
• CQS
  • Query： 是得到一个method的return（不改变application的state）
  • Command：是让一个method有所行动（改变application的state）-> 可以在method名字前面加上！可以提醒用户这个会改变状态
  • 这样我call这个method的时候，我就会知道我这个行为会不会改变application的state
• 违反这个原则的，比如pop，又改变了stack的状态，又取得了内容

course link

• CSS Tutorial - Zero to Hero (Complete Course)

CSS

• cascading style sheet
• 添加方法：一般用link加到html的head里面
  • 测试方法，可以直接把background设置成别的颜色运行一下试试

参考资料

目的

虽然在很多模板上写了不少html和css，但是还是没有一个基础的概念。正好这次的工作要写前端的模板，所以顺势学习一下他们的基本概念

Java的imperative表达和Declarative表达

• 目标：创建一个person的class，打印出来里面所有的女性
• 前置工作:创建person这个class

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

  static class Person { private final String name; private final Gender gender; public Person(String name, Gender gender) { this.name = name; this.gender = gender; } @Override public String toString() { return "Person{" + "name='" + name + '\'' + ", gender=" + gender + '}'; } } enum Gender{ MALE,FEMALE }

Youtube三小时速成SQL

MySQL Tutorial for Beginners [Full Course]

什么是SQL

• DB里面，数据都按一定的顺序排放，大家通过DB的管理软件（database management）来访问数据库并得到结果
  • 有两种种类
    • ralational:table分成不同的表，之间是有关系的
      • 比如MySQL，Server SQL等等。MySQL是开源的，用的人最多
    • NoSQL：没有表，没有关系，和SQL的语法不共通

Java基础部分1

Step01VariableTest

Java字符串拼接

• 可以用+连接，当其中有一个string的时候，其他的数据类型也会直接变成string。
  • 注意这里其他种类都会被转换成string，即使是String s = null;也会在拼接之后变成“null”
• 如果都是string类型的话，可以用a.concat(b)。因为已经假设都是字符串了，所以相对的效率更高
• 可以考虑用StringBuffer.append()来拼接

  1 2 3 4 5 6 7

  StringBuffer buf=new StringBuffer() buf.append("a"); if(someCondition){ buf.append("b"); } buf.append("c"); String d=buf.toString();

再赋值

• 基础变量（primitive value）的再赋值不会改变之前的值，但是reference的再赋值改变的是reference，不是实际的值，所以会变
  • 一个variable只有两个可能，是reference或者是primitive value
• 注意赋值的时候，需要assign到位，比如sea = sea+1而不是sea+1（太久不写Java感觉脑子不转了）

###没有assign的时候的默认情况

• String的初始默认值是null，如果用了String s = ""则是给初始赋值了空字符
• int等等数字类型的初始值都是0
• boolean的初始值是false
• Integer是java提供的封装类，所以它在未赋值的时候初始是null，这样可以分清楚是未赋值还是赋值0的区别。
  • 封装类：封装类里面会包含很多对基础数据类型的操作，比较方便。但是在效率上面会比primitive要低

++a 和 a++

• ++i先运算再赋值，显示出来的是计算之后的
• i++先赋值再运算，显示出来的是计算之前的

  1 2	System.out.println("a=i++===> "+(a=i++));//1 System.out.println("a=++i===> "+(a=++i));//2

###局部变量,全局变量,实例变量

• 定义在类里的是class variable，不需要初始化，会有默认值。静态变量（要加静态变量的static）。
  • 可以直接通过类名来调用
• 定义在方法里面的是局部变量（local variable），必须初始化，出了作用域就会被销毁
• 实例变量instance variable:非静态变量，位于method外面，class里面
• Java允许两种变量重名
  • 局部变量的范围会覆盖全局变量。如果想调用全局变量，需要用this关键字来找
  • {}代表一个作用域

###Java参数传递

• 值传递：调用时，参数把值传给形参，方法执行里面的primitive参数变化不会改变原本参数的值

  • 基础数据类型，包括string

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

    public class A { public static void change(int i, int j) { int temp = i; i = j; j = temp; } public static void main(String[] args) { int a = 3; int b = 4; change(a, b); System.out.println("a=" + a); //3 System.out.println("b=" + b); //4 } }

• 引用传递：调用的时候传递的是地址，所以会改变参数的值

  • String以外的剩余复合数据类型，包括数组，类等等
  • 比如如果用StringBuild()而不是String来初始化新的String，那么他就可以被传递了
  • 如果参数构造成了一个新的对象，就不是传递的那个对象了，那传递的对象就不变了

    1 2 3 4 5 6 7 8 9 10 11 12

    public class Test { public static void add(A a) { //a = new A(); //if not comment, output 0 a.i++; } public static void main(String args[]) { A a = new A(); add(a); System.out.println(a.i ); //output 1 } }

当primitive和其他数据类型同时出现在参数里面的时候，要注意谁会改变谁不会改变！！

Step02IfForTest

插入：List，Arraylist

• Array的大小固定，连续储存，删除速度很慢
• List继承Collection，有两个实现类，ArrayList和LinkedList
  • List是接口，不能直接构造list，需要List list = new ArrayList();
  • ArrayList可以看为可以随意增减的数组

for表达式

• 声明语句
  • 类型，必须和数组的数据类型匹配
  • 作用域就在for的括号里面
• 表达式：想要访问的数组名

  1 2 3 4

  for(声明语句 : 表达式（数组）) { //代码句子 }

foreach用法

• 特点：没有储存，函数式编程

• 循环map,list等等

  1	item.forEach(元素 -> 处理方法);

• 没有continue

  • 要用return跳入下一个循环。
• 没有break的功能
  • 可以自己设置一个flag来判断是不是要跳出循环
• 不可以在里面直接给变量赋值，要赋值必须使用method来处理
  • 比如不能直接给String赋值，但是可以改成StringBuilder里面的方法

Step03DataTypeTest

Java的符号优先级

• 括号
• 加减的优先级高于比大于小于
• 大于小于高于等于不等于
• 与 -> 或

强制类型转换

• float和double结尾可以是d/f也可以是D/F
• 超出范围的大数转小的会溢出，出现奇妙数字（具体变成什么要看bit上面的位）
  • short 4bit
  • int 8bit
  • float 8bit
  • double 16bit
• float转int（强制）的时候会舍去

##Step05ClassTest

Java里面写class

• public的class必须自己单独放在一个.java的文件里面
• class里面的

  1 2 3

  public 类名(构造函数的参数) { this.class_varibles = ...; }

final的用法

• 装饰类：final class A{}，这样被装饰的类不能被继承，final类里面的所有方法都会被认为是final的方法
• 装饰方法
  • 把方法锁定，避免其他继承类修改他的意义
  • 为了效率（现在好像已经不是很重要了）
  • private的方法会被认为是隐式的final方法
• 装饰变量
  • 如果变量是primitive，一旦初始化之后就不能被更改，可以被认为是常量
  • 如果是引用，那么初始化之后就不能指向另一个对象了
• 装饰变量详解：
  • 如果是类的变量，比如在定义或者构造器的时候初始化，初始化之后就不能再被赋值了
  • 注意：如果像下面第二个例子一样，final修饰的指向对象的时候，就不会被优化成常量
  • static可以不依赖具体的对象就可以被调用

    1 2 3 4 5 6 7 8 9 10 11

    public class Test { public static void main(String[] args) { String a = "hello2"; final String b = "hello"; String d = "hello"; String c = b + 2; String e = d + 2; System.out.println((a == c)); //true -> final的变量就直接被认为是常量了 System.out.println((a == e)); //false } }

1
2
3
4
5
6
7
8
9
10
11
12
13

public class Test {
    public static void main(String[] args)  {
        String a = "hello2"; 
        final String b = getHello();
        String c = b + 2; 
        System.out.println((a == c));  //false -> 
 
    }
     
    public static String getHello() {
        return "hello";  //这个是可变的
    }
}

插入：java判断两个字符串是否相等

• 不能用==来判断是够相同，因为String是对象类型，两个对象不一样，比较的是内存地址，所以不一样
• a.equals(b)

Java创建字典

• 关键字：HashMap<Integer,String> map=new HashMap<Integer,String>();
• 添加元素 map.put(1,"a");
• 注意：Java的map里面不能用primitive的数据类型，要改成封装类型来做

Step06ObjectOrientedTest

protected和private

• 如果希望被外部访问，那么一定要用public
• 如果希望被不同包下的子类访问，可以用protected或者public
• 如果要被本包下的其他类访问，可以不装饰，或者用上面两个
• 如果不想被任何外部类访问，那么必须用private
• default可以被类内部+同一包内访问（比protected少一个子类）

###抽象类（abstract）作为方法的参数和返回值

• 作为方法的参数传递：必须传递一个子类的对象
• 作为返回值传递：必须返回子类的对象

关于继承

• 当子类继承父类的时候，就获得了父类里面的属性和方法，子类中就不存在重复的代码，提高代码复用性
• Java不能一个子类继承多个父类，但是可以多重继承（A继承B继承C）-> 和c++的区别

  1 2 3 4 5

  class 父类 { } class 子类 extends 父类 { }

继承的特性

• 子类可以拥有父类的非private的属性和方法
• 子类可以对父类的方法进行扩展
• 子类可以用自己的方式来实现父类的方法

关键字

• implements可以变相的实现继承多个接口

  1 2 3 4 5 6 7 8 9 10 11

  public interface A {。//接口不能有自己的实例，对类的行为进行约束 public void eat(); public void sleep(); } public interface B { public void show(); } public class C implements A,B { //中间用逗号分隔开 }

• super可以实现对父类成员的访问（引用当前对象的父类）。this指向自己的引用。可以有和父类名字相同的函数

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

  class Animal { void eat() { System.out.println("animal : eat"); } } class Dog extends Animal { void eat() { System.out.println("dog : eat"); } void eatTest() { this.eat(); // this 调用自己的方法 super.eat(); // super 调用父类方法 } } public class Test { public static void main(String[] args) { Animal a = new Animal(); a.eat(); Dog d = new Dog(); d.eatTest(); } }

1
2
3

animal : eat
dog : eat
animal : eat

• 构造器
  • 子类是不能继承父类的构造器（构造方法/构造函数），只是调用
  • 如果父类构造器带参数，子类必须用super关键字来调用
  • 如果父类构造器不带参数，子类会自动调用父类的构造器
• 父类new子类
  • 父类 = new 子类，初始化为子类
  • 调用的是子类的方法，但是子类有父类里面没有的方法不能调用

override

@override：子类对父类进行重新编写

• 参数必须完全相同
• 返回值可以不同，但必须是父类的派生
• 如果父类里面是public，子类里面不能比public更低
• final不能重写
• static不能重写，但是可以被再次声明
• 如果子类和父类在一个包，子类可以重写所有父类的方法，除了private和final
• 如果不在一个包，那么只能重写public和protected
• 构造方法不能被重写

Interface

• 抽象方法的集合，一个class可以通过继承interface来继承接口的抽象方法

  • 不能实例化
  • 没有构造方法
  • 必须是抽象方法
  • 不包含成员变量，除了final和static
  • 接口不是被类继承了，是被类实现了
  • 接口可以继承接口，一个接口也可以继承多个借口

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

    [可见度] interface 接口名称 [extends 其他的接口名] { // 声明变量 // 抽象方法 } /* 文件名 : Animal.java */ interface Animal { public void eat(); public void travel(); } /* 文件名 : MammalInt.java */ public class MammalInt implements Animal{ public void eat(){ System.out.println("Mammal eats"); } public void travel(){ System.out.println("Mammal travels"); } public int noOfLegs(){ return 0; } public static void main(String args[]){ MammalInt m = new MammalInt(); m.eat(); m.travel(); } }

• interface存在的意义：把使用接口的人和实现接口的人分开，这样用的人不用关心是怎么实现的，实现的人也不用关心影不影响别人用

• interface和class的类型转换：因为接口不可以实例化，但是可以将接口初始化为类

  1 2 3

  public class B implements A{} A a = new B(); //引用变量a被定义为A接口类型,引用了B实例 A a = new A(); //错误,接口不允许实例化

• instanceof二元操作符，测试左边是不是右边类的实例

  1 2	子类 instanceof 父类 == true 父类 instanceof 子类 == false

抽象类和interface

• 抽象类也不能被实例化
• 抽象类里面可以写非抽象的实现方法，这样可以避免在子类里面复用
• 和普通的class相比，抽象类仅仅作为parent来使用

Step07ExceptionTest

Exception的层次

• 所有异常都是从Exception继承的子类
• Exception是Throwable的子类，除了Exception之外，还有一个子类是Error。Error表示的是运行环境发生的错误
• Exception包括两个主要子类，IOException和RuntimeException

返回异常的信息种类

• getMessage:返回详细的错误信息
• getCause：返回代表异常的原因。如果是多层的会显示最底层的？
• toString：返回串类的名字
• printStackTrace：打印错误输出流
• getStackTrace：返回包含堆栈的数组
• fillInStackTrace

例子：捕捉IO的异常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public void test_exception_checkedException_basic() {
        FileWriter fw = null;  //需要在外面声明，不然finally里面没有反应
        try {
            fw = new FileWriter("/ssa/demo.txt"); //错误的路径
            fw.write("abcdefg");
        }
        catch (IOException e){
            log(e.getMessage());
        }
        finally { //考虑到可能在打开之后出现exception，所以最后一定要关上
            try{
                if(fw!= null){
                    fw.close();  //创建不成功的时候，就不能关闭了，也要捕捉这个地方的异常
                }
            }
            catch (IOException e){
                log(e.getMessage());
            }
        }

    }

###异常处理
在处理异常的时候有两种不同的方法

• 抛出异常
  • 系统自动抛出异常
  • throw
  • throws
• 捕捉异常

throws/throw关键字

• throw e，一般用于程序员主动抛出的特定种类的异常，throw new e
  • 执行throw一定是抛出了某种异常
  • e.getMessage()可以得到这个异常里面的信息
  • throw new RuntimeException("",e) 把异常包在一个异常里面跑出，由上方解决
• throws在声明方法的时候抛出的异常，出现在函数头
  • 表示运行这个函数可能会出现异常的一种可能，并不一定会发生

    1 2 3 4 5 6 7 8 9 10 11 12 13

    public static void function() throws NumberFormatException{ String s = "abc"; System.out.println(Double.parseDouble(s)); //尝试转换 } public static void main(String[] args) { try { function(); } catch (NumberFormatException e) { System.err.println("非数据类型不能转换。"); //e.printStackTrace(); } }

Java里面try和catch的用法

• 用处：可以捕获异常，放在异常容易发生的地方，保护代码
  • catch不能独立于try
  • finally不是强制的
  • 中间不能掺杂其他部分的代码
  • try后面catch和finally必须有一个

• 当在try的里面出现了会出现的异常的时候，catch语句会抓住上面的异常的名字（e1），并且运行catch里面的语句，比如print出来语句

  1 2 3 4 5 6 7

  try { // 程序代码，尝试运行的程序 }catch(ExceptionName e1) { //Catch 块，对名字为e的异常的处理方法 }

• 也可以用多个catch来抓住不同的异常名字，使用不同的处理方法

  • 可以在最后加上finally的分支，无论是否发生异常，finally的部分都会被执行

    1 2 3 4 5 6 7 8 9 10 11

    try{ // 程序代码 }catch(异常类型1 异常的变量名1){ // 程序代码 }catch(异常类型2 异常的变量名2){ // 程序代码 }catch(异常类型3 异常的变量名3){ // 程序代码 }finally{ // 程序代码 }

####异常需要注意的点

• throw只是消极的抛出了异常，并没有处理，如果可以一定要用try来处理异常
• try抓到了异常之后，一定要用catch进行处理，至少print出来
• 如果是IO的异常，要在最后的finally里面关闭输入输出流
• 如果在函数体内抛出了异常，最好在函数名加上throws，交给上层函数来处理

得到错误的行号

1
2
3
4
5
6

try {
            //一些操作
        } catch (exception的种类 e) {
            StackTraceElement stackTraceElement= e.getStackTrace()[0]; //得到首歌错误的信息
            log(stackTraceElement.getLineNumber()); //打印行号
        }

多层exception的异常传递

• 需要把异常一层一层传递上去
• 当class一层套一层的时候，很需要每一层都把exception传递上去，不然的话会很难判断哪里出了问题
• 传递的时候需要在throw里面带着Throwable的参数e，不然的话不会把状况传递下去的（注意在自己定义exception class的时候也需要加上这样的方法）
  • 自己写的可以从系统的except里面继承，然后直接super父类的方法

logger

• 目的：在写代码的时候，需要print出来很多需要的语句，代码改好了又要删除，logger的存在就是为了取代System.out.println()
  • 可以设置输出样式
  • 可以设置输出级别，比如只输出错误日志
  • 可以被定向到文件

    1 2	private static final Logger logger = LoggerFactory.getLogger(St7BasicExceptionThrower.class); logger.debug("park");

Step08Java8FunctionTest

• Java8的特性，允许把函数作为方法的参数

  1 2 3

  (parameters) -> expression 或 (parameters) ->{ statements; }

• 可选类型声明，可以不声明参数的类型

• 一个参数不需要定义圆括号，多个参数需要
• 如果函数体只有一个参数，不需要大括号
• 如果主体只有一个表达式，会自动返回返回值

1
2
3
4
5
6
7
8
9
10
11

//1.
() -> System.out.println("Hello Lambda");
//2.
number1 -> int a = number1 * 2;
//3.
(number1, number2) -> int a = number1 + number2;
//4.
(number1, number2) -> {
 int a = number1 + number2;
 System.out.println(a);
}

变量作用域

• 只能用标记了final外层局部变量-> 不能在lambda的函数里修改作用域之外的变量，会造成编译错误
• 不允许声明一个和局部变量重名的参数

函数式接口（functional interface）

• 有且只有一个抽象的方法的接口，和lambda配合使用，必须保证只有一个抽象方法
• 当目前的条件不想被锁死的时候，可以改成lambda，这样可以在使用的时候直接修改
• 四个最基础的函数接口
  • Supplier:数据提供器
    • 提供T类型对象，没有构造器，只有get方法（相当于得到你输入参数的值，也就是得到你写在parameter里面的函数）
    • 不接受任何参数（指前面的括号里是空的），返回一个结果
  • Function：数据转换器，接收T返回R，提供了apply/compose/andThen/identity的方法
    • apply：把function的对象运用在输入的参数上，返回计算的结果（相当于apply里给的是真正的参数，lambda里面是如何运行这个参数）
  • Consumer：数据消费器
    • 接收T，没有返回值，通常根据T进行处理，提供accept和andThen
    • accept：override之后里面包括的就是实现的方法。可以不override直接定义consumer的内容Consumer<String> consumer1 = (s) -> System.out.println(s);//lambda表达式返回的就是一个Consumer接口
  • Predicate：条件测试器，接收T，返回boolean

参考链接

• Python - lru_cache和singledispatch装饰器
• 官方文档

今天写算法题dp的自上而下的算法的时候，看到有人用了``@functools.lru_cache这个函数。最神奇的是没用之前我的算法是超时的，用了之后居然就跑出来了

这个函数是什么？

根据官方文档，这个函数的定义如下：

1

@functools.lru_cache(maxsize=128, typed=False)

1
2
3
4
5
6
7
8
9
10
11

一个为函数提供缓存功能的装饰器，缓存 maxsize 组传入参数，在下次以相同参数调用时直接返回上一次的结果。用以节约高开销或I/O函数的调用时间。

由于使用了字典存储缓存，所以该函数的固定参数和关键字参数必须是可哈希的。

不同模式的参数可能被视为不同从而产生多个缓存项，例如, f(a=1, b=2) 和 f(b=2, a=1) 因其参数顺序不同，可能会被缓存两次。

如果指定了 user_function，它必须是一个可调用对象。 这允许 lru_cache 装饰器被直接应用于一个用户自定义函数，让 maxsize 保持其默认值 128:

如果 maxsize 设置为 None ，LRU功能将被禁用且缓存数量无上限。 maxsize 设置为2的幂时可获得最佳性能。

如果 typed 设置为true，不同类型的函数参数将被分别缓存。例如， f(3) 和 f(3.0) 将被视为不同而分别缓存。

• 取这个函数名的意义在于，LRU叫做最久未使用算法，是一种缓存文件的置换方法。这些种方法会使用最久没有被访问的对象作为置换进去的对象。于此相对的方法还有，最近最少使用，非最近使用，先进先出等等算法。
• 也就是说，这个函数默认会储存128个调用结果。这个函数实现了备忘功能，会避免在传入相同函数的重复计算。超过这个条目的缓存，会根据LRU规则被丢弃掉。可以使cache_clear()来清除缓存

实现场景

• 比如在一些使用recursion的场景下，会重复调用很多相同参数的函数（我的雅虎网测也是因此没有通过）。使用这种方法可以很好的减少计算量
• 比如斐波那契的计算，计算31的时候调用函数的次数已经差出了几千倍，时间也差很多
• 使用的时候记得import functools

  1 2 3 4 5

  @functools.lru_cache(None) def fib_with_cache(n): if n < 2: return n return fib_with_cache(n - 2) + fib_with_cache(n - 1)

什么是装饰器

既然说到了这种装饰器，我就突然发现自己还不知道什么是装饰器。

参考链接

• 如何理解python装饰器
• Python 函数装饰器

核心思想：python万物皆对象，包括函数本身

装饰器（decorators）

• 整体来说，装饰器的作用就是在不影响以前的函数的情况下，提供我们需要的效果。本质上来说，装饰器也是一个python的函数，他可以让其他函数实现额外的功能，而不修改本身的代码。可以用装饰器实现大量复用的功能
• 装饰器返回的也是函数对象。

一个例子

如果现在有一个函数

1
2

def foo():
    print('i am foo')

但是我想要一个需求，就是记录下来执行日志

1
2
3

def foo():
    print('i am foo')
    logging.info("foo is running")

但是如果在很多个函数中都想要实现这个功能，那么我们需要修改每个函数的内容，加上log的代码。如果这个log的功能只是测试的时候用一下，那么修改的时候还需要把所有的代码再删掉。这时候最开始的想法是写一个新的函数包括这些功能，比如

1
2
3
4
5
6
7
8

def foo():
	print("THIS is foo")

def decotator(func):
	print("start...%s"%func)
	func()

decotator(foo)

但是写成这样挺丑的，而且调用这个函数的时候就变成了不是调用这个函数本身，这时候就需要装饰器来工作。

• 面函数里面的wrapper是一个函数对象，因为修饰器的参数是函数，wrapper是来解决这个函数还有参数的问题。

• 这个效果也就等同于foo = Log(foo)，然后调用的时候调用foo(arg)的效果。把这个方法自动化之后就是加上@让他自动变成装饰器了

  1 2 3 4 5 6 7 8 9

  def Log(func): def wrapper(*args, **kwargs): logging.warn("%s is running"%func.__name__) return func(*args) return wrapper @Log def foo(): print("this is foo")

• 在装饰器调用的时候，用@来表示，避免再一次的赋值操作（本来应该是 foo = Log(foo) foo()的这种调用方法。
  在实现带参数的装饰器的时候，可以给装饰器再套一层。注意函数名带括号和不带括号的区别

  1 2 3 4 5 6 7 8

  def Log(level): def decorator(func): def wrapper(*args,**kwargs): if level == "1": logging.warn("start %s"%func.__name__) return func(*args) return wrapper return decorator

其他的一些

• 类装饰器：如果装饰器的参数是个类，可以给类写装饰器，可以实现更多的功能
• 装饰器的顺序，离这个函数越近的越是

可变参数

参考
上面的参数里面有加了星标的，这个突然发现自己有一点理解不准确，而且这么久了感觉也没怎么用到过。就一起写在这里了
总得来说，可变参数就是可以处理不同数量的参数

*args

1
2
3
4
5
6
7

def argsFunc(a, *args):
	print a
	print args
	
>>> argsFunc(1, 2, 3, 4)
1
(2, 3, 4)

**kwargs

• 参数名字前面加两个星号，表示参数会被存放在dict里面，这时候调用这个函数的时候需要输入arg1 = value1, arg2 = value2这种形式
• 这种的一般会在调用sql的时候用到

994 腐烂的橘子

2020.3.4
链接

在给定的网格中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 - 1。

基本思路

• 刚开始看到这道题感觉像是DP，因为要求的是最短时间，乍一看感觉是找一天最快的路径。但是仔细看了一下发现因为每次传播的时候，都同时向四个方向传播，每个的传播时间也相同，所以不存在最优路径的问题。这么想来的话应该是用BFS
• 基本流程如下：
  • 在所有橘子腐烂之前，把上波新被传染的橘子放进Queue
  • 遍历Queue里面的橘子，向这个橘子周围一周传染，判断是否有格子，传染结束之后从Queue里面移除
  • 如果所有没有新的橘子可被感染，那么循环结束
• 实现中的判断如下：
  • 首先遍历所有格子，得到有多少橘子和有多少腐烂的橘子。如果腐烂的橘子总数 == 橘子数，则说明所有的都被感染。反之，循环结束的时候如果没有都被感染，返回 - 1
  • 判断跳出循环条件：没有新的橘子被感染，设定一个counter计算被新感染的橘子数，如果等于0则说明结束了
• 注意点
  • 如果想从queue里面移除元素，可以用pop。如果用remove的话，需要在for的时候复制一个新的queue，否则报错

基本代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

def orangesRotting(self, grid: List[List[int]]) -> int:
    if not grid:
        return -1

    m, n = len(grid), len(grid[0])
    rotten = []
    org_num = 0  # 总数
    counter = 0  # 坏了的数量
    timer = 0

    # 第一次遍历找到坏了的
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 2:
                rotten.append((i, j))
                org_num += 1
                counter += 1
            elif grid[i][j] == 1:
                org_num += 1
    # 开始扩散
    while rotten:
        # print(rotten)
        this_counter = 0
        for r in rotten[:]:
            candidate = [(r[0] - 1, r[1]), (r[0] + 1, r[1]),
                         (r[0], r[1] - 1), (r[0], r[1] + 1)]
            for a in candidate[:]:
                if a[0] < 0 or a[0] >= m:
                    candidate.remove(a)
                elif a[1] < 0 or a[1] >= n:
                    candidate.remove(a)
            for a in candidate:
                if grid[a[0]][a[1]] == 1:
                    grid[a[0]][a[1]] = 2
                    rotten.append((a[0], a[1]))
                    counter += 1
                    this_counter += 1
            rotten.remove(r)
        if this_counter > 0:
            timer += 1
        # print(rotten,timer)
    if counter == org_num:
        return timer
    else:
        return -1

希望改进的地方

• remove的用法感觉有点丑陋，counter的用法也有点丑陋
  • 可以不用while里面的那个counter，直接用queue是否为空来判断
  • 使用pop -> 但是这个不是一个一个判断而是每次会有好几个腐烂的橘子，所以pop不太好用
• 判断在不在格子里感觉也有点丑陋，能不能在这个格子周围加一圈？
  • 设定一个四个元素的list来表示这个格子的四周
• 最后的判断方法也优点丑陋
  • 其实可以直接判断最后的结果里面有没有1，但是这样的话需要增加一次对整个矩阵的循环。但用个数判断也无可厚非

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

def orangesRotting(self, grid: List[List[int]]) -> int:
    if not grid:
        return -1

    m, n = len(grid), len(grid[0])
    rotten = []
    org_num = 0  # 总数
    counter = 0  # 坏了的数量
    timer = 0

    D = [[1, 0], [-1, 0], [0, 1], [0, -1]]  # 找到周围的点

    # 第一次遍历找到坏了的
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 2:
                rotten.append((i, j))
                org_num += 1
                counter += 1
            elif grid[i][j] == 1:
                org_num += 1
    # 开始扩散
    while rotten:
        this_counter = 0
        for r in rotten[:]:
            i, j = r[0], r[1]
            for d in D:
                mat_i, mat_j = i + d[0], j + d[1]
                if 0 <= mat_i < m and 0 <= mat_j < n and grid[mat_i][mat_j] == 1:
                    grid[mat_i][mat_j] = 2
                    rotten.append((mat_i, mat_j))
                    counter += 1
                    this_counter += 1
            rotten.remove(r)
        if this_counter > 0:
            timer += 1
    if counter == org_num:
        return timer
    else:
        return -1

最近在当数据结构和算法的TA，记录一下老师考试的重点

时间复杂度

pass

经典排序

看经典排序哪章，主要是merge排序和quick排序
插入平常用的比较多，插入排序是前面的已经是排好序的了，后面的插入到前面里面。
注意在实现排序的时候，尽量选择交换的方法来实现排序，而不是用创建新的数组的方法

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def SelectionSort(nums):
    for i in range(len(nums)):
        Min = float("inf")
        index = None
        for j in range(i, len(nums)):
            if nums[j] < Min:
                index = j
                Min = nums[j]
        if index != i:
            temp = nums[i]
            nums[i] = nums[index]
            nums[index] = temp
    return nums

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13

def InsertSort(nums):
    n = len(nums)
    for i in range(1, n):
        temp = nums[i]
        j = i
        while j > 0 and temp < nums[j - 1]:
            nums[j] = nums[j - 1]
            j -= 1
        if j != i:
            nums[j] = temp
    return nums

merge排序（这种实现的空间复杂度是n）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def Merge(L, R):
    M = []
    while L and R:
        if L[0] <= R[0]:
            M.append(L.pop(0))
        else:
            M.append(R.pop(0))
    while L:
        M.append(L.pop(0))
    while R:
        M.append(R.pop(0))
    return M


def MergeSort(nums):
    if len(nums) < 2:
        return nums
    mid = int(len(nums) / 2)
    L, R = nums[:mid], nums[mid:]
    Merge(L, R)

快速排序(不占空间版本)

• 重点：最后才把piv和最前或者最后的交换，先设置一个虚拟的piv的坐标

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  def partition(nums, l, r): piv = nums[r] i = l - 1 # 相当于piv的坐标 for j in range(l, r): # 相当于把比piv小的都换到piv（i）的前面去 if nums[j] <= piv: i += 1 nums[i], nums[j] = nums[j], nums[i] # i的虚拟坐标和i的真实坐标right交换，也就是把piv换到最中间 nums[i + 1], nums[r] = nums[r], nums[i + 1] return i + 1 def QuickSort(nums, l, r): if l < r: q = partition(nums, l, r) QuickSort(nums, l, q - 1) QuickSort(nums, q + 1, r)

Heap

其实也就是堆排序，子节点的数值总是小于（或者大于父节点的数值）。通过list来操作，父节点为i的时候，子节点的坐标是 2i + 1 和 2i + 2，子节点为i的时候，父节点的坐标是 floor（（i - 1）/ 2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def HeapSort(nums):
    for start in range(len((nums) - 2) // 2, -1, -1):
        MinHeap(nums, start, len(nums) - 1)
    for i in range(len(nums) - 1, -1, -1):
        nums[0], nums[i] = nums[i], nums[0]
        MinHeap(nums, 0, i - 1)


def MinHeap(nums, start, end):
    dad = start
    child = dad * 2 + 1
    while child <= end:
        if child + 1 <= end and nums[child] > nums[child + 1]:
            child += 1
        if nums[dad] > nums[child]:
            nums[dad], nums[child] = nums[child], nums[dad]
            dad = child
            child = child * 2 + 1

Hash

DFS BFS

KMP，BM(shift table)

BM：
从最末尾开始匹配，如果最后一个没匹配上，最后一个就是坏字符。

• 如果单词里没有坏字符，那么直接移动到坏字符后一个
• 如果单词里有，移动到他们俩对着的（搜索词里面出现的最后一次）

  1 2	后移位数 = 坏字符的位置(在搜索词的哪一位) - 搜索词中的上一次出现位置 如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1。

如果后面几位可以匹配上，最后几位就是好后缀。(good suffix)

1
2
3

　　后移位数 = 好后缀的位置(算到最后一位) - 搜索词中的上一次出现位置
如果只出现了一次，那么这个位置是-1
如果有多个好后缀，除了最长的那个，其他的必须出现在头部

在上面两个移动方法中取最大的一个

因为好后缀比较难实现，所以大也可以光用坏字符法则

生成表

最牛逼的是，坏字符和好后缀都只和单词有关，和被搜索的东西无关，所以可以实现生成一张表来表示，然后再用的时候直接查

路径规划（prim，dij，krus）

把所有的点都设置成未访问的，并且距离是无穷大。只有起始点是访问的，并且距离是0.

• visited记录已经访问过得点
• distance记录这个点和起点的距离
  每次找不在visited里面，并且距离起点distance最小的点。放入已访问，并且relax所有和这个点连接的点（更新distance）
  重复这个步骤

python里面直接用字典来记录所有的数据类型就行了

在寻找未得到最优值的点中最小的值时，采用堆优化，其复杂度为O(1)，可以将整个算法的复杂度降为nlog(n) -> 用堆实现的也就是优先队列

• 上面能够优化的时间复杂度是在“找到不在集合中的离 ss 最近的点”（每个点必须要进入集合才算更新结束，所以大循环的 O(n)O(n) 是无法减小的），我们能否通过一些排序操作，使得能够快速地找到这个点 xx 呢？
  这里就可以用到一个“小顶堆”的数据结构，它能够在 O(logn)O(log⁡n)（其中 nn 为堆中的元素数量）的时间复杂度内完成插入、删除最小值的操作，在 O(1)O(1) 的时间复杂度内完成取堆内最小值的操作。于是我们可以将上面的查找这一步操作放入到堆中，时间复杂度就能下降到 O(nlogn)

树（最大最小，字母树）

C++和python的特点

Python:面向对象，解释，通用。标准库比较多。

• 语法简单，数据结构不需要定义
• 解释性语言，跨平台的
• 高级语言，屏蔽了很多底层实现。比如可以自动管理内存

缺点

• 运行速度慢解释性语言的通病

编译语言和解释语言

编译型语言

源代码 -> 编译器 -> 最终可执行文件(.exe) -> OS -> CPU

• 一次编译之后可以无限运行
• 不能跨平台
  • 可执行程序不能跨平台，同平台可能不兼容
  • 源代码可能也不能跨平台。比如字节长度等问题

解释型语言

源代码 -> 解释器 -> OS -> CPU

• 执行效率低。一般计算机的底层功能都会用C或者C++实现，应用层面才会使用解释性语言
• 解释器可以把源代码转换成不同的机器码，所以源代码本身是可以跨平台的。解释器不能跨平台

##C++和python

• C++更接近于底层，可以直接操作内存。大规模的计算
• C++不仅面向对象，也面向过程

python： 快速开发应用程序
java： 健壮的大型软件
C++： 需求效率的软件
C： 操作系统及驱动

面向对象编程的特征

面向过程：就是分析出解决问题所需要的步骤，然后用函数把这些步骤一步一步实现，使用的时候一个一个依次调用就可以了。

封装 カプセル化 encapsulation

隐藏了某一方法的具体运行步骤，取而代之的是通过消息传递机制发送消息给它。封装是通过限制只有特定类的对象可以访问这一特定类的成员，而它们通常利用接口实现消息的传入传出。

不用知道是怎么实现的也可以用。私有成员不会被访问。

1
2
3
4
5
6
7
8
9

/* 一个面向过程的程序会这样写： */
定义莱丝
莱丝.设置音调(5)
莱丝.吸气()
莱丝.吐气()

/* 而当狗的吠叫被封装到类中，任何人都可以简单地使用： */
定义莱丝是狗
莱丝.吠叫()

继承 inheritance

在某种情况下，一个类会有“子类”。子类比原本的类（称为父类）要更加具体化
私有成员不会被继承，protected的成员会被继承
python的私有成员前面加两个下划线。保护乘员前面加一个下划线。前后都加下划线的是系统定义的名字

1
2
3
4

类牧羊犬 : 继承狗

定义莱丝是牧羊犬
莱丝.吠叫()    /* 注意这里调用的是狗这个类的吠叫方法。*/

当一个类从多个父类继承时，我们称之为“多重继承”。如一只狗既是吉娃娃犬又是牧羊犬（虽然事实上并不合逻辑）。多重继承并不总是被支持的，因为它很难理解，又很难被好好使用。

多态 polymorphism

指允许不同类的对象对同一消息做出响应。即同一消息可以根据发送对象的不同而采用多种不同的行为方式。很好的解决了应用程序函数同名问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

类狗
开始
    公有成员:
        叫()
        开始
            吠叫()
        结束
结束

类鸡
开始
    公有成员:
        叫()
        开始
            啼叫()
        结束
结束

定义莱丝是狗
定义鲁斯特是鸡
莱丝.叫()
鲁斯特.叫()

overload

首先说重载（overload），是发生在同一类中。与什么父类子类、继承毫无关系。
标识一个函数除了函数名外，还有函数的参数（个数和类型）。也就是说，一个类中可以有两个或更多的函数，叫同一个名字而他们的参数不同。
他们之间毫无关系，是不同的函数，只是可能他们的功能类似，所以才命名一样，增加可读性，仅此而已！

override

覆盖(override),是发生在子类中！也就是说必须有继承的情况下才有覆盖发生。
我们知道继承一个类，也就有了父类了全部方法，如果你感到哪个方法不爽，功能要变，那就把那个函数在子类中重新实现一遍。

机器学习和深度学习

机器学习直接来源于早期的人工智能领域，传统的算法包括决策树、聚类、贝叶斯分类、支持向量机、EM、Adaboost等等。从学习方法上来分，机器学习算法可以分为监督学习（如分类问题）、无监督学习（如聚类问题）、半监督学习、集成学习、深度学习和强化学习。

最初的深度学习是利用深度神经网络来解决特征表达的一种学习过程。深度神经网络本身并不是一个全新的概念，可大致理解为包含多个隐含层的神经网络结构。为了提高深层神经网络的训练效果，人们对神经元的连接方法和激活函数等方面做出相应的调整。其实有不少想法早年间也曾有过，但由于当时训练数据量不足、计算能力落后，因此最终的效果不尽如人意。

深度学习需要大量的样本才能很好的解决问题，如果样本数量不够的时候，使用机器学习的方法可以更好的解决问题

机器学习的主要障碍

由于以下原因，使用低功率/简单模型是优于使用高功率/复杂模型：

• 在我们拥有强大的处理能力之前，训练高功率模型将需要很长的时间。 在我们拥有大量数据之前，训练高功率模型会导致过度拟合问题（因为高功率模型具有丰富的参数并且可以适应广泛的数据形状，所以我们最终可能训练一个适合于特定到当前的训练数据，而不是推广到足以对未来的数据做好预测）。
• 然而，选择一个低功率的模型会遇到所谓的“欠拟合”的问题，模型结构太简单，如果它复杂，就无法适应训练数据。（想象一下，基础数据有一个二次方关系：y = 5 x ^ 2;你无法适应线性回归：y = a x + b，不管我们选择什么样的a和b。
• 为了缓解“不适合的问题”，数据科学家通常会运用他们的“领域知识”来提出“输入特征”，这与输出关系更为直接。（例如，返回二次关系y = 5 square（x），如果创建了一个特征z = x ^ 2，则可以拟合线性回归：y = a z + b，通过选择a = 5和b = 0）。
• 机器学习的主要障碍是特征工程这个步骤，这需要领域专家在进入训练过程之前就要找到非常重要的特征。特征工程步骤是要靠手动完成的，而且需要大量领域专业知识，因此它成为当今大多数机器学习任务的主要瓶颈。

深度学习的优点

DNN的主要区别在于，你可以将原始信号（例如RGB像素值）直接输入DNN，而不需要创建任何域特定的输入功能。通过多层神经元（这就是为什么它被称为“深度”神经网络），DNN可以“自动”通过每一层产生适当的特征，最后提供一个非常好的预测。这极大地消除了寻找“特征工程”的麻烦，这是数据科学家们最喜欢看到的。