发表于

Java虚拟机内存空间是由哪些部分组成的？

jvm.png
ps:这张图在掘金上看到的,感觉很不错,来源: juejin.cn/post/684490…

ps:JDK1.8同JDK1.7相比:元空间(Metaspace)取代了永久代。元空间本质和永久代类似,都是对JVM规范中方法区的实现,不过元空间与永久代最大的区别是,元空间不存在于虚拟机中,而是使用了本地内存。

堆:

堆是什么？

堆是用来存放Java对象的地方,几乎所有的对象都存在于堆中。

堆的特点

  1. 线程共享的地方,每个线程都有权利访问堆区。
  2. 垃圾回收主要存在于堆区,因为java程序运行时也就是生成大部分java对象,从而垃圾回收也就是要回收不用的java的对象。
  3. 堆可以分为新生代和老年代,可以针对不同的区域使用不同的垃圾回收算法。(新生代:Eden,Survivor(from,to),老年代:old)。
  4. 堆的大小可以固定也可以扩展,但是堆已满的时候,内存无法扩展的时候,就会抛出OutOfMemoryError异常。

新生代与老年代

  1. 新生代是由 Eden + Survivor(S0) + Survivor(S1)构成的,默认比例 8:1:1。
  2. 老年代生命周期比年轻代生命周期长,也就是老年代对象存活时间长。
  3. 新生代与老年代默认比例,1:2 XX:NewRatio=2,新生代占堆空间的1/3。
  4. 所有的对象几乎都是在Eden区被new出来的,Eden放不了的大对象直接进入老年代。

对象分配的过程？

  1. 对象首先被new在Eden区,但是要看Eden区能否有足够的空间。
  2. 如果Eden空间不足,那么首先进行一次minorGC,进行一次年轻代回收,将年轻代不用的对象进行销毁,在把新的对象放入Eden区。
  3. 剩余的对象放入幸存者Survivor-S0区。
  4. 如果在进行垃圾回收的话,Survivor-S0区的对象如果没被回收掉的话,会被复制到S1区。
  5. 如果在进行垃圾回收的话,Survivor-S1区的对象如果没被回收掉的话,会被复制到S0区。（总之保证S0和S1只有一个区有对象）
  6. 默认是15次的循环,超过15次,则会将幸存者区存下来的对象转入老年代。

FullGC和MajorGC的触发条件？

  1. Full GC,完全GC,一般发生在老年代和方法区空间不够的情况下才会触发Full GC,同时对新老年代进行回收,STW-stop the-word停顿时间最长。
  2. Major GC,大型GC,一般是发生在老年代,但是老年代回收一般都要引起minor GC,年轻代GC。
  3. 参考文档:www.bookstack.cn/read/gc-han…

TLAB

  1. TLAB是Thread Local Allocation Buffer,即线程本地分配缓存区,是属于Eden区的,这是一个线程专用的内存分配区域,线程私有,默认开启的。
  2. 堆是全局共享的,在同一时间,可能会有多个线程在堆上申请空间,每次对象的分配都需要同步的进行,虚拟机通过CAS的方式保证更新操作的原子性。
  3. 通过TLAB来避免多线程冲突,在给对象分配内存的时候,每个线程使用自己的TLAB,这样可以使得线程同步,提高了对象分配的效率。
  4. -XX:+UseTLAB,-XX:+TLABSize设置TLAB的大小。

对象引用方式？

  1. 强引用:Squirrel s = new Squirrel(),此时的s就是Squirrel的引用变量,普通new出来的对象都是强引用,有引用变量指向的时候,jvm不会对其(forever)进行回收。
  2. 软引用:一个对象具有软引用,但是内存空间足够的时候,就不会去回收他,如果内存空间不够了,那么有可能会对其进行回收。Soft
  3. 弱引用:JVM进行垃圾回收的时候,都会对其进行回收 WeakReference
  4. 虚引用:任何时候都还会被垃圾回收器进行回收。

方法区:

方法区是什么？

  1. 方法区是堆的一个逻辑部分,但是他不存在于堆中,而是存在于本地内存中。

方法区中存放了什么？

  1. 被虚拟机加载的类信息
  2. 常量
  3. 静态变量
  4. 编译器编译后的代码

方法区的特点？

  1. 线程共享,和堆一样都是线程共享的。
  2. 方法区中的信息一般需要长期存在。
  3. 内存回收效率低,方法区中的信息一般需要长期存在,回收一遍之后可能只有少量信息无效,主要回收目标,常量池的回收,类型的卸载。

运行时常量池？

  1. 方法区中存放:类信息、常量、静态变量、即时编译器编译后的代码。常量就存放在运行时常量池中。
  2. 当类被虚拟机加载以后,.class文件中的常量就存放在方法区的运行时常量池中,而且在运行时期,可以向常量池中添加新的常量,如string的intern()可以在运行期向常量池添加字符串常量。

栈

栈.png

ps:来源：camo.githubusercontent.com/109d4eff5b6…

栈是什么？

栈是描述Java方法运行过程的内存模型。Java虚拟机会为每一个即将运行的Java方法创建一块叫做”栈针”的区域,用来存放该方法运行过程中的一些信息。局部变量表、操作数栈、动态链接、方法出口信息。

压栈出栈过程？

  1. 当方法运行过程中需要创建局部变量时,就将局部变量的值存入栈帧中的局部变量中。
  2. 虚拟机栈顶的栈帧是当前正在执行的活动栈,也就是当前正在执行的方法。PC寄存器也会指向这个地址。如果方法中仍然有方法,那么将其对应新的栈帧压入栈顶,变为当前的活动栈,方法结束后,当前活动栈的返回值变成新的活动栈帧的一个操作数。

局部变量表？

定义为一个数字数组，主要用于存储方法参数、定义在方法体内部的局部变量，数据类型包括各类基本数据类型，对象引用，以及 return address 类型。

操作数栈？

  1. 栈顶缓存技术：由于操作数是存储在内存中，频繁的进行内存读写操作影响执行速度，将栈顶元素全部缓存到物理 CPU 的寄存器中，以此降低对内存的读写次数，提升执行引擎的执行效率。
  2. 每一个操作数栈会拥有一个明确的栈深度，用于存储数值，最大深度在编译期就定义好。32bit 类型占用一个栈单位深度，64bit 类型占用两个栈单位深度操作数栈。
  3. 并非采用访问索引方式进行数据访问，而是只能通过标准的入栈、出栈操作完成一次数据访问。

动态链接？

如果被调用的方法无法再编译期被确定下来，只能在运行期将调用的方法的符号引用转为直接引用，这种引用转换过程具备动态性，因此被称为动态链接。

本地方法栈

本地方法栈是什么？

本地方法栈结构和虚拟机方法栈是一样的,只不过其实用C来实现的,这里就不过多介绍了。

程序计数器

什么是程序计数器？

程序计数器顾名思义:程序计数器存储的是当前线程正在执行的那条字节码指令的地址,若当前线程正在执行的是一个本地方法,那么此时计数器为undefined。

程序计数器的作用？

  1. 字节码解释器通过改变程序计数器来依次读取指令,从而实现代码的流程控制
  2. 在多线程情况下,程序计数器记录的是当前线程执行的位置,从而当线程切换回来的时候,就知道上次线程执行到哪了。

程序计数器的特点？

  1. 线程私有,每条线程都有自己的程序计数器。
  2. 生命周期,随着线程的创建而创建,随着线程的结束而销毁。
  3. 不会出现outOfMemoryError的内存区域。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

前言

为什么要讲讲synthetic和NBAC呢？其实在这之前，对Jdk中这两种机制并不了解，甚至没有听过，主要原因还是因为在阅读SkyWalking中Agent源码过程中，有这么一行，

1
2
3
4
java复制代码AgentBuilder agentBuilder = new AgentBuilder.Default(byteBuddy).ignore(
                nameStartsWith("net.bytebuddy.")
                        ...
                        .or(ElementMatchers.isSynthetic()));

而这段代码的作用就是通过ByteBuddy操作字节码时需要忽略synthetic修饰的代码。

什么是synthetic？

翻译一下，我们知道synthetic是意思是：合成的。那在Jdk中”合成的”又代表什么意思呢？

首先通过上面源码，能感觉它好像类似static、final这样的修饰关键词，但是写在代码中却没有办法识别，其实这是因为synthetic是属于编译器层面的一种关键词。

既然已经超出知识范围以外，那我们就得想办法查阅官方文档来找到它的定义，但是凭空去Jdk文档中搜synthetic或者肉眼翻阅，相信我你是绝对没有办法找到的（为什么我这么肯定，原因应该都懂），那就得需要一个锲机。

在平时开发的反射工具包中，通过下面代码你能看到，

1
2
3
4
5
6
7
8
9
java复制代码public class Test {
    
    public static void main(String[] args) {
        Field[] fields = Test.class.getDeclaredFields();
        for (Field field : fields) {
            field.isSynthetic();
        }
    }
}

Field有一个isSynthetic()方法，判断这个字段是否是合成的，那我们再来看看它的类图结构，

image-20211105172741413

发现isSynthetic()方法是Member接口中的实现，原来Method、Constructor都实现了这个方法，再通过方法上的注释，

1
2
3
4
5
6
7
8
9
10
java复制代码    /**
     * Returns {@code true} if this member was introduced by
     * the compiler; returns {@code false} otherwise.
     *
     * @return true if and only if this member was introduced by
     * the compiler.
     * @jls 13.1 The Form of a Binary
     * @since 1.5
     */
    public boolean isSynthetic();

已经描述的比较清楚了，该成员是由编译器引入，从1.5版本之后就出现了，那更详细的解释呢，注释中也提示了，到Java语言规范文档中 13.1 The Form of a Binary 章节查阅，于是在文档中看到这么一句话，

image-20211105173345433

翻译过来就是：如果 Java 编译器发出的构造与源代码中显式或隐式声明的构造不对应，则必须将其标记为合成的，除非发出的构造是类初始化方法（JVMS §2.9）。

到这里，synthetic代表的意思就大概清楚了，就是代码中本来并没有写的一些字段或方法代码，但是在编译时由编译器修改添加上去的，同时用synthetic来标识修饰。

作用和原理

那为什么会出现这样的情况呢？我们通过下面一些Demo来研究一下，这里我们使用Jdk1.8的版本，首先我们定义一个很简单的内部类，如下：

1
2
3
4
5
6
7
8
java复制代码public class FieldOut {

    public String outStr = "out";

    class FieldIn{
        private String inStr = outStr;
    }
}

实际开发经验告诉我们上面内部类的代码时没有任何错误且能正常允许的，但是我们先回顾一下Java语法规范中规定：一个类要是访问另一个类的public属性，必须先获取这个类的实例。也就是说按这种规范话，上面第6行代码应该是下面这样，

1
java复制代码private String inStr = new FieldOut().outStr;

咦，这样的话岂不是证明最上面代码应该报错吗？这时你会想到虽然语法规范有这么一条，但是在内部类的访问控制规范中也是允许这样的语法存在的。那我们通过反射看一下，为什么内部类中这么定义是没有问题的，

1
2
3
4
5
6
7
8
9
10
java复制代码public class Test {

    public static void main(String[] args) {

        Field[] fields = FieldOut.FieldIn.class.getDeclaredFields();
        for (Field field : fields) {
            System.out.println(field.getType() + " " + field.getName() + " : " + field.isSynthetic());
        }
    }
}

允许上面测试代码，控制台打印如下：

1
2
java复制代码class java.lang.String inStr : false
class com.example.demo.test.FieldOut this$0 : true

发现我们在上面代码中明明只定义了一个属性字段inStr，怎么通过反射遍历所有的字段还多了一个FieldOut类型的字段this$0，通过isSynthetic()方法我们能知道这个this$0就是由编译器合成的，好像有那么点意思了；那我们再看看类FieldIn通过javac编译生成的class文件，

image-20211108112935556

打开FieldOut$FieldIn.class文件，

1
2
3
4
5
6
7
8
9
10
java复制代码package com.example.demo.test;

class FieldOut$FieldIn {
    private String inStr;

    FieldOut$FieldIn(FieldOut var1) {
        this.this$0 = var1;
        this.inStr = this.this$0.outStr;
    }
}

你能看到这里添加了一些代码，通过有参构造器来定义初始化了字段FieldOut this$0，并将this$0.outStr赋值给了inStr，到这里恍然大悟，原来内部类中允许这么编写代码的原理是因为有编译器帮我们进行相应代码的生成添加。

我们还知道除了Filed，还有Method和Constrictor都实现了isSynthetic()方法，同理他们也应该会被编译器进行代码合成，

我们将上面的代码修改，

1
2
3
4
5
6
7
8
java复制代码public class FieldOut {

    private String outStr = "out";

    class FieldIn{
        private String inStr = outStr;
    }
}

其中将字段outStr的访问权限变为了private，上面代码依然没有问题且正常运行，但是这里又有疑问了，虽然编译器会帮我们生成字段this$0，使我们能够访问到outStr，但是根据Java面向对象的三个特性之一的封装，私有属性字段不能直接被外界访问，只能通过公共方法去get和set，所以我们在这里并没有编写字段outStr的get方法，FieldIn中又是怎么拿到的呢？

我们再写个测试方法，

1
2
3
4
5
6
7
8
9
10
11
java复制代码public class Test {

    public static void main(String[] args) throws InvocationTargetException, IllegalAccessException {

        Method[] methods = FieldOut.class.getDeclaredMethods();
        for (Method method : methods) {
            System.out.println(method.getReturnType() + " " + method.getName() + " : " + method.isSynthetic());
        }
        
    }
}

这次用来看看类FieldOut里面发生了什么变化，运行控制台打印如下：

1
java复制代码class java.lang.String access$000 : true

耶嘿，我们知道我们在类FieldOut中并没有定义任何方法，这个方法是哪来的，肯定和synthetic脱不开关系了，我们再来编译一下，然后看看编译后的FieldIn的class文件，

1
2
3
4
5
6
7
8
9
10
java复制代码package com.example.demo.test;

class FieldOut$FieldIn {
    private String inStr;

    FieldOut$FieldIn(FieldOut var1) {
        this.this$0 = var1;
        this.inStr = FieldOut.access$000(this.this$0);
    }
}

access$000()方法是不是很眼熟，原来编译器帮我们在类FieldOut生成了这个方法，然后在类FieldIn中就是通过这个方法获取到outStr的值的，它其实就是编译器帮我们生成的outStr的get方法。

那Constrictor呢，我门再将Demo改下，

1
2
3
4
5
6
7
8
9
java复制代码public class FieldOut {

    private FieldIn fieldIn = new FieldIn();

    class FieldIn{
        private FieldIn(){
        }
    }
}

反射遍历打印Constrictor出现什么呢？同样class文件里面生成的代码又是什么样的呢？相信我们已经知道了答案（感兴趣可以动手测试下），同时经过上面的文档和示例，对synchetic的作用以及原理也已经掌握了。

产生的问题

在上面我们知道synchetic其实就是通过编译器来帮我们解决了内部类中对其外部类的字段或方法访问控制的问题，但是在某些情况下会出现问题，我们来看一看。

基于上面的Demo修改下，Jdk版本依然是1.8，

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
java复制代码public class FieldOut {

    public void handle1(){
        new FieldIn().test();
    }

    public void handle2() throws Exception {
        new FieldIn().reflectTest(new FieldOut());
    }

    class FieldIn{

        private void test(){
            hello();
        }

        public void reflectTest(FieldOut fieldOut) throws Exception {
            Method method = fieldOut.getClass().getDeclaredMethod("hello");
            method.invoke(fieldOut);
        }
    }

    private void hello(){
        System.out.println("hello");
    }
}

这里主要在类FieldIn中定义了两个方法：test()方法是正常调用外部类FieldOut私有的hello()方法，reflectTest()方法是通过反射进行调用。我们再写个main函数测试下，

1
2
3
4
5
6
7
8
arduino复制代码public class Test {

    public static void main(String[] args) throws Exception {

        new FieldOut().handle1();
        new FieldOut().handle2();
    }
}

允许代码，控制台打印如下，

1
2
3
4
5
6
7
8
9
10
java复制代码hello
Exception in thread "main" java.lang.IllegalAccessException: class com.example.demo.test.FieldOut$FieldIn cannot access a member of class com.example.demo.test.FieldOut with modifiers "private"
	at java.base/jdk.internal.reflect.Reflection.newIllegalAccessException(Reflection.java:361)
	at java.base/java.lang.reflect.AccessibleObject.checkAccess(AccessibleObject.java:591)
	at java.base/java.lang.reflect.Method.invoke(Method.java:558)
	at com.example.demo.test.FieldOut$FieldIn.reflectTest(FieldOut.java:27)
	at com.example.demo.test.FieldOut.handle2(FieldOut.java:16)
	at com.example.demo.test.Test.main(Test.java:32)

Process finished with exit code 1

发现handle1()方法没有问题，但是handle2()却异常报错了，可能你会想到这里的反射调用并没有添加method.setAccessible(true)来允许访问，加了之后肯定运行没问题。确实如此，但是仔细想想，handle1()方法是可以直接调用外部类的私有方法，那反射是不是也应该可以直接访问，如果必须通过设置允许访问才能访问，那他们就不在一个起跑线了，那不是典型的”双标”嘛。

所以这里其实就有个逻辑上的问题：同是方法调用，但是却出现两种不同的结果，

  • 直接调用：正常运行
  • 反射调用：异常报错

什么是NBAC？

了解上面的问题之后，我们再来看看什么是NBAC，它的全称是Nested Based Access Controll，翻译过来就是基于嵌套的访问控制，这种机制是Jdk 1.11版本才出现的，而它其实在某些方面来说是对Jdk中synthetic的一种完善补充，在编译时也会对之前synthetic的代码合成产生一些影响。

同样是上面问题的Demo，如果你将Jdk的编译版本切换到1.11的话，再运行测试的main方法，handle1()和handle2()方法都是正常打印的。

相应的一些Java API是由Class类定义实现的，源码如下，

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
48
49
50
51
52
53
54
55
56
57
58
59
java复制代码    private native Class<?> getNestHost0();

    @CallerSensitive
    public Class<?> getNestHost() {
        if (!this.isPrimitive() && !this.isArray()) {
            Class host;
            try {
                host = this.getNestHost0();
            } catch (LinkageError var3) {
                return this;
            }

            if (host != null && host != this) {
                SecurityManager sm = System.getSecurityManager();
                if (sm != null) {
                    this.checkPackageAccess(sm, ClassLoader.getClassLoader(Reflection.getCallerClass()), true);
                }

                return host;
            } else {
                return this;
            }
        } else {
            return this;
        }
    }

    public boolean isNestmateOf(Class<?> c) {
        if (this == c) {
            return true;
        } else if (!this.isPrimitive() && !this.isArray() && !c.isPrimitive() && !c.isArray()) {
            try {
                return this.getNestHost0() == c.getNestHost0();
            } catch (LinkageError var3) {
                return false;
            }
        } else {
            return false;
        }
    }

    private native Class<?>[] getNestMembers0();

    @CallerSensitive
    public Class<?>[] getNestMembers() {
        if (!this.isPrimitive() && !this.isArray()) {
            Class<?>[] members = this.getNestMembers0();
            if (members.length > 1) {
                SecurityManager sm = System.getSecurityManager();
                if (sm != null) {
                    this.checkPackageAccess(sm, ClassLoader.getClassLoader(Reflection.getCallerClass()), true);
                }
            }

            return members;
        } else {
            return new Class[]{this};
        }
    }

其中有一些是native方法，调用的是底层C++的接口；而每个方法的作用在Jdk 11的API文档中可以查阅，同时在文档中也提到了这是由Java虚拟机规范中的5.4.4 访问控制定义的。它的主要作用就是：通过NestHost属性保存类的宿主类以及嵌套成员类的引用，这样去访问成员类的属性和方法是，就可以直接通过保存的对象引用去访问，某些情况下可以替代synthetic合成代码的方式来进行访问。感兴趣的可以基于上面synchetic中Demo里面的类用Jdk 11重新编译生成class文件，然后进行对比看看，相信结果更加一目了然。

身未动，心已远。

把一件事做到极致就是天分！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第4天，活动详情查看：2021最后一次更文挑战」

引言

谈到并发编程，就不得不谈ReentrantLock，谈到ReentrantLock就会问实现原理，谈到原理就引出AQS(AbstractQueuedSynchronized)，然后就被按在地上无情的摩擦。这篇文章主要讲解加锁过程，下一篇写释放锁过程。

ReentrantLock使用

1
2
3
4
5
6
7
8
9
10
11
java复制代码Lock lock = new ReentrantLock();
Condition condition = lock.newCondition();
lock.lock();
try {
  while(条件判断表达式) {
      condition.wait();
  }
 // 处理逻辑
} finally {
    lock.unlock();
}

lock.lock()显示的获取锁，并在finally块中显示的释放锁，目的是保证在获取到锁之后，最终能够被释放。

lock()方法调用过程（默认非公平锁）

非公平锁调用lock方法的源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
java复制代码static final class NonfairSync extends Sync {
	private static final long serialVersionUID = 7316153563782823691L;

	final void lock() {
		// 表示当前没有占有锁的线程，将锁的拥有者设置为当前线程
		if (compareAndSetState(0, 1))
			setExclusiveOwnerThread(Thread.currentThread());
		// 获取锁
		else
			acquire(1);
	}

	protected final boolean tryAcquire(int acquires) {
		return nonfairTryAcquire(acquires);
	}
}

下图是ReentrantLock.lock的调用过程图。
Untitled-2021-11-08-0921.png

AQS加锁实现

AQS(AbstractQueuedSynchronizer)：是JDK提供的同步框架，内部维护了一个FIFO双向队列（即CLH同步队列）。通过此队列实现同步状态的管理（volatile修饰的state状态，用于标志是否持有锁）。

Node

先了解AQS维护的队列节点结构，下面是队列节点Node的源码：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
java复制代码static final class Node {
	/** 共享节点 */
	static final Node SHARED = new Node();

	/** 独占节点 */
	static final Node EXCLUSIVE = null;

	/** 因为超时或者中断，节点会被设置成取消状态，被取消的节点不会参与到竞争中，
	     会一直是取消状态不会改变 */
	static final int CANCELLED =  1;

	/** 后继节点处于等待状态，如果当前节点释放了同步状态或者被取消，
	     会通知后继节点，使其得以运行 */
	static final int SIGNAL    = -1;

	/** 节点在等待条件队列中，节点线程等待在condition上，当其他线程对condition
	     调用了signal后，该节点将会从等待队列中进入同步队列中，获取同步状态 */
	static final int CONDITION = -2;

	/**
	 * 下一次共享式同步状态获取会无条件的传播下去
	 */
	static final int PROPAGATE = -3;

	/** 等待状态 */
	volatile int waitStatus;

	/** 前驱节点 */        
	volatile Node prev;

	/** 后继节点 */
	volatile Node next;

	/** 获取同步状态的线程 */
	volatile Thread thread;

	/**
	 * 下一个条件队列等待节点
	 */
	Node nextWaiter;

	final boolean isShared() {
		return nextWaiter == SHARED;
	}

	final Node predecessor() throws NullPointerException {
		Node p = prev;
		if (p == null)
			throw new NullPointerException();
		else
			return p;
	}

	Node() {    // Used to establish initial head or SHARED marker
	}

	Node(Thread thread, Node mode) {     // Used by addWaiter
		this.nextWaiter = mode;
		this.thread = thread;
	}

	Node(Thread thread, int waitStatus) { // Used by Condition
		this.waitStatus = waitStatus;
		this.thread = thread;
	}
}

FIFO队列(CLH队列)

队列用head，tail和state三个变量来维护，源码如下：

1
2
3
4
5
6
7
8
java复制代码/** 头节点 */
private transient volatile Node head;

/** 尾节点 */
private transient volatile Node tail;

/** 同步状态 */
private volatile int state;

结构示意图如下：
FIFO-2021-11-08-1427.png

compareAndSetState调用

首先尝试获取锁，调用compareAndSetState方法，期待值为0，新值为1。使用unsafe的compareAndSwapInt方法，通过一次CAS操作来修改state属性。

CAS操作即内存拿到volatile修饰的state属性值，与期望值0对比，如果取到的值为0，则执行+1操作，将state修改为1。其中还涉及知识点volatile修饰变量保证线程间可见，以及CAS操作的经典ABA问题。

源码如下：

1
2
3
4
5
6
7
8
9
10
11
java复制代码/**
 * 如果当前状态值等于预期值，则自动将同步状态设置为给定的更新值。
 * 这个操作具有volatile读和写的内存语义。
 * @param expect 期望值
 * @param update 新值
 * @return false返回表示实际值不等于预期值，true表示成功
 */
protected final boolean compareAndSetState(int expect, int update) {
	// See below for intrinsics setup to support this
	return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}

如果此方法执行成功，则调用setExclusiveOwnerThread方法将让线程占有锁，此时state已经置为1。

acquire调用

进入此方法说明，当前已经有其他线程占有锁了。由于此种加锁方式是非公平锁，进入方法后，首先尝试获取锁，如果获取不到锁，那么再将当前线程置于队列中，让当前线程中断执行。

非公平锁在此方法中首先展示不公平，这种不公平是对在队列中的线程来说的。就像我们去银行办业务，如果我是VIP用户，我可以越过等待的用户先办理，这对于其他等待用户不公平。

1
2
3
4
5
java复制代码public final void acquire(int arg) {
	if (!tryAcquire(arg) &&
		acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
		selfInterrupt();
}

tryAcquire

调用此方法来尝试获取锁。源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
java复制代码final boolean nonfairTryAcquire(int acquires) {
	final Thread current = Thread.currentThread();
	int c = getState();
        /** 首先获取state状态，此时第一个判断c==0后的操作是因为，
            有可能在执行过程中，其他线程释放了锁，那么state为0，则直接让当前线程持有锁
            */
	if (c == 0) {
		if (compareAndSetState(0, acquires)) {
			setExclusiveOwnerThread(current);
			return true;
		}
	}
        /** 如果当前线程就是持有锁的线程，那么state+1，
		 此处提现了可重入锁的概念，每次线程重入该锁就重复此操作*/
	else if (current == getExclusiveOwnerThread()) {
		int nextc = c + acquires;
		if (nextc < 0) // overflow
			throw new Error("Maximum lock count exceeded");
		setState(nextc);
		return true;
	}
	return false;
}

此处setState(nextc)，只是单纯让state+1，而没有用CAS操作。

addWaiter

负责把当前无法获得锁的线程包装为一个Node添加到队尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
java复制代码private Node addWaiter(Node mode) {
	Node node = new Node(Thread.currentThread(), mode);
	// Try the fast path of enq; backup to full enq on failure
	Node pred = tail;
	if (pred != null) {
		node.prev = pred;
		if (compareAndSetTail(pred, node)) {
			pred.next = node;
			return node;
		}
	}
	enq(node);
	return node;
}

其中参数mode是独占锁还是共享锁，默认为null，独占锁。追加到队尾的动作分两步：

1.如果当前队尾已经存在(tail!=null)，则使用CAS把当前线程追加到队尾。

2.如果当前Tail为null或则线程调用CAS设置队尾失败，则通过enq方法继续追加。

enq

通过for循环和CAS操作自旋过程，将当前线程加入队列中，源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
java复制代码private Node enq(final Node node) {
	for (;;) {
		Node t = tail;
                // 如果队尾是null，则说明队列空了，将当前线程设置为头尾节点
		if (t == null) {
			if (compareAndSetHead(new Node()))
				tail = head;
		} else {
                // 队尾非空，通过CAS将当前线程加入队尾。
			node.prev = t;
			if (compareAndSetTail(t, node)) {
				t.next = node;
				return t;
			}
		}
	}
}

acquireQueued

此方法是对addWaiter的补充，将加入队列的线程中断执行，源码如下：

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
java复制代码final boolean acquireQueued(final Node node, int arg) {
	// 操作失败标志
	boolean failed = true;
	try {
		// 线程中断标志
		boolean interrupted = false;
		for (;;) {
			// 当前节点的prev节点
			final Node p = node.predecessor();
			// 如果前一节点是头结点，并且尝试获取同步状态成功
			if (p == head && tryAcquire(arg)) {
				// 将当前当前线程设置成头结点
				setHead(node);
				// 将prev移除队列
				p.next = null; // help GC
				failed = false;
				return interrupted;
			}
			// 判断当前线程是否需要阻塞 && 阻塞当前线程并且检验线程中断状态
			if (shouldParkAfterFailedAcquire(p, node) &&
				parkAndCheckInterrupt())
				interrupted = true;
		}
	} finally {
		// 取消获取同步状态
		if (failed)
			cancelAcquire(node);
	}
}

p == head && tryAcquire(arg)，这里的判断也显示了非公平的意义。队里中有等待线程还要尝试获取锁。

shouldParkAfterFailedAcquire

此方法是阻塞线程前最后的检查操作，通过prev节点的等待状态判断当前线程是否应该被阻塞，

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
java复制代码private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
	// 拿到prev节点的等待状态
	int ws = pred.waitStatus;
	
	if (ws == Node.SIGNAL)
		/*
		 * 如果prev的status是signal，表示prev处于等待状态，可以阻塞当前线程，
           * 当prev释放了同步状态或者取消了，会通知当前节点。
		 */
		return true;
	if (ws > 0) {
		/*
		 * status > 0，表示为取消状态，需要将取消状态的节点从队列中移除
		 * 直到找到一个状态不是取消的节点为止
		 */
		do {
			node.prev = pred = pred.prev;
		} while (pred.waitStatus > 0);
		pred.next = node;
	} else {
		/*
		 * 除了以上情况，通过CAS将prev的status设置成signal
		 */
		compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
	}
	return false;
}

parkAndCheckInterrupt

如果程序走到这个位置，那么就说明已经将当前线程加入队列中，可以让线程中断了。线程阻塞通过调用LockSupport.park()完成，而LockSupport.park()则调用sun.misc.Unsafe.park()本地方法，再进一步，HotSpot在Linux中中通过调用pthread_mutex_lock函数把线程交给系统内核进行阻塞。

1
2
3
4
java复制代码private final boolean parkAndCheckInterrupt() {
	LockSupport.park(this);
	return Thread.interrupted();
}

至此加锁过程完成。

总结

ReentrantLock加锁是通过AQS实现，AQS中维护了一个FIFO的队列，当存在锁竞争时构建队列，构建过程中使用CAS和自旋，保证线程能够进入队列。已经进入队列的线程需要阻塞，使用LockSupport.park()方法完成，阻塞线程能够让CPU更专注于执行持有锁的线程，而不是将资源浪费在尝试获取锁的自旋过程中。

以上是对ReentrantLock加锁的过程分析，希望大佬多提意见。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于
  1. 背景

当前容器已经成为企业上云的主流选择，经过2019年下半年的深度研发和推广，2020年OPPO基本实现了基于kubernetes的容器的大规模使用和全业务上云。容器的优势是敏捷和高性能，然而由于需要共享宿主机内核，隔离不彻底等原因，当用户需要修改很多定制的内核参数或者在低版本的 Linux 宿主机上运行高版本的 Linux 容器，或者只是需要隔离性更高时，在容器上都是难以实现的。而由于历史原因，公司内部也仍然有一些业务需要使用强隔离的虚拟机，因此提供虚拟机服务，势在必行。

经过调研，我们发现对于已经建设有容器平台的公司，虚拟机的管理方案大部分是维护一套OpenStack或者类似的系统。然而OpenStack庞大且繁重，维护成本较高，且底层资源不能够统一管理，将会为混合调度带来很多不便。因此我们将统一的控制面管理，实现容器与虚拟机的统一调度和管理，作为选型的主要方向。

  1. 方案选型 Kubevirt or Virtlet

虚拟机与容器通过k8s平台进行混合管理，业界比较好的项目有kubevirt和virtlet等。

Kubevirt是Redhat开源的以容器方式运行虚拟机的项目，以k8s add-on方式，利用k8s CRD增加资源类型VirtualMachineInstance（VMI）， 使用容器的image registry去创建虚拟机并提供VM生命周期管理。

Virtlet是一个Kubernetes（Container Runtime Interface）的实现，能够在Kubernetes上运行基于虚机的Pods。（CRI能够令Kubernetes运行非docker的容器，例如Rkt）。

下面这张图是我们2020年初做选型时做的一个Kubevirt和Virtlet的对比图的部分。可以看到，Virtlet使用同一种资源类型Pod描述容器和虚拟机，因此如果使用原生的方式，虚拟机也只能有Running和删除两种状态，无法支持pause/unpause， start/stop等虚拟机专属状态，显然这是无法满足用户需求的。如果想要支持这些状态，又得深度定制kubelet，会导致虚拟机管理和容器管理耦合太重；另外考虑到当时virtlet社区不如kubevirt社区活跃，因此我们最终选择的方案是Kubevirt。

640.png

  1. Kubevirt介绍

3.1 VmiCRD/Pod/Domain对应关系

640 (1).png

3.2 组件介绍

kubevirt的各组件服务是部署在k8s上的，其中virt-api和virt-controller是deployment，可以多副本高可用部署，virt-api是无状态的，可以任意扩展；virt-controller是通过选举的方式选出一个主台提供服务；virt-handler以daemonset的方式部署，每一台虚拟机节点都运行一个virt-handler；而一个virt-launcher服务则对应一个虚拟机，每当创建一个虚拟机，都会创建一个对应的virt-launcher pod。

virt-api

  • kubevirt API服务，kubevirt是以CRD的方式工作的，virt-api提供了自定义的api请求处理，可以通过virtctl命令执行同步命令 virtctl vnc/pause/unpause/stop/start vm等。
  • virt-controller*
  • 与k8s api-server通讯监控VMI资源创建删除等事件，并触发相应操作
  • 根据VMI定义创建virt-launcher pod，该pod中将会运行虚拟机
  • 监控pod状态，并随之更新VMI状态
  • virt-handler*
  • 运行在kubelet的node上，定期更新heartbeat，并标记”kubevirt.io/schedulable”
  • 监听在k8s apiserver当发现VMI被标记的nodeName与自身node匹配时，负责虚拟机的生命周期管理
  • virt-launcher*
  • 以pod形式运行
  • 根据VMI定义生成虚拟机模板，通过libvirt API创建虚拟机
  • 每个虚拟机会对应独立的libvirtd
  • 与libvirt通讯提供虚拟机生命周期管理
  1. Kubevirt架构改造

4.1 原生架构

640 (3).png
原生架构中管理面与数据面耦合。在virt-launcher pod中运行虚拟机，当由于不确定原因（比如说docker的原因或物理机原因或者virt-launcher本身的挂掉升级等原因），造成virt-launcher容器退出后，会导致虚拟机也退出，从而会影响用户使用，增加了虚拟机的稳定性风险。因此我们在原有架构的基础上做了改造。

改造点：

  1. 将数据面kvm及libvirtd等进程移出管理面的virt-laucher容器，物理机上的libvirtd进程管理此物理机上的所有虚拟机。
  2. 新增virt-start-hook组件用以对接网络组件、存储组件及xml的路径变动等。
  3. 重构虚拟机镜像制作和分发方式，借助于OCS的对象存储管理，实现镜像的快速分发。

除了实现管理面与数据面的分离，我们还在稳定性增强等方面做了很多工作。比如实现了kubevirt的每个组件不管在任何时间任何情况下失效、故障、异常了，都不会影响到正常虚拟机的运行，并且要求测试覆盖到这些组件异常情况下的测试；物理机重启后虚拟机可以正常恢复生命周期管理等生产级要求，进一步保障了整个虚拟机管理系统的稳定性。

4.2 改造后架构

640 (4).png

4.3 架构改造后创建虚拟机流程

  1. 用户创建vmi crd，kubectl create -f vmi.yaml
  2. virt-controller watch到新的vmi对象，为vmi创建对应的virt-launcher pod
  3. virt-launcher pod创建好后，k8s的调度器kube-scheduler会将其调度到符合条件的kubevirt node节点上
  4. 然后virt-controller会将virt-launcher pod的nodeName更新到vmi对象上
  5. kubevirt node节点watch到vmi调度到本节点后，会将虚拟机的基础镜像mount到指定位置，然后调用virt-launcher的syncVMI接口创建domain
  6. virt-launcher接受到创建请求后，将vmi对象转变为domain对象，然后调用virt-start-hook，根据backingFile创建qcow2虚拟机增量镜像磁盘，将domain xml中的相关路径转变为物理机上路径，请求网络，配置xml，然后将最终配置好的xml返回virt-launcher
  7. virt-launcher收到virt-start-hook的返回后，调用物理机上的libvirtd来define domain xml和create domain

640 (5).png

4.4 架构改造后删除虚拟机流程

  1. 用户执行删除vmi命令，kubectl delete -f vmi.yaml
  2. virt-handler watch到vmi的update事件，并且vmi的deletionTimeStamp不为空，调用virt-launcher shutdownDomain，virt-launcher调用virt-start-hook释放网络然后调用libvirtd关机
  3. domain shutdown的消息由virt-launcher watch到并发送给virt-handler，virt-handler根据vmi和domain已停机的状态调用virt-launcher deleteDomain，virt-launcher调用virt-start-hook删除网络然后调用libvirtd undefineDomain
  4. domain undefine的消息由virt-launcher watch到并发送给virt-handler，virt-handler根据vmi和domain已删除的状态更新vmi添加domain已删除的condition，然后清理该domain的垃圾文件及路径
  5. virt-controller watch到vmi状态deleteTimeStamp不为空，并且vmi的condition DomainDeleted为True，则删除virt-launcher pod，然后等pod删除后，清理vmi的finalizer，使vmi自动删除

640 (6).png

  1. 存储方案

5.1 原生镜像存储方案

kubevirt中虚拟机的原始镜像文件会ADD到docker基础镜像的/disk路径下，并推送到镜像中心，供创建虚拟机时使用。

创建虚拟机时，会创建一个vmi crd，vmi中会记录需要使用的虚拟机镜像名称，vmi创建好后virt-controller会为vmi创建对应的virt-launcher pod，virt-launcher pod中有两个container，一个是运行virt-launcher进程的容器compute，另一个是负责存放虚拟机镜像的容器container-disk，container-disk容器的imageName就是vmi中记录的虚拟机镜像名称。virt-launcher pod创建后，kubelet会下载container-disk的镜像，然后启动container-disk容器。container-disk启动好后会一直监听在—copy-path下的disk_0.sock文件，而sock文件会通过hostPath的方式映射到物理机上的路径/var/run/kubevirt/container-disk/vmiUUID/ 中。

virt-handler pod会使用HostPid，这样virt-handler 容器内就可以看到物理机的pid和挂载信息。在创建虚拟机时，virt-handler会根据vmi的disk_0.sock文件找到container-disk进程的pid，标记为Cpid，然后根据/proc/Cpid/mountInfo找到container-disk容器根盘的磁盘号，然后根据container-disk根盘的磁盘号和物理机的挂载信息(/proc/1/mountInfo)找到container-disk根盘在物理机上的位置，再拼装上虚拟机镜像文件的路径/disk/xxx.qcow2，拿到虚拟机原始镜像在物理机上的实际存储位置sourceFile，然后将sourceFile mount 到targetFile上，供后面创建虚拟机时作为backingFile使用。

640 (7).png

5.2 本地盘存储

原生kubevirt中根据基础镜像backingFile创建的增量镜像文件xxx.qcow2只支持放到emptydir中，而我们的容器的数据盘一般使用的是lvm的方式，如果保存两种使用方式的话，在虚拟机容器混合部署的场景中，不利于物理机磁盘的统一规划统一调度，因此我们在原生的基础上也支持了虚拟机增量镜像文件存放到由virt-launcher容器申请的lvm盘中，从而保持了虚拟机与容器磁盘使用方式的一致性。此外我们还支持了为虚拟机单独创建一个qcow2空盘挂载为数据盘使用，也存放在virt-launcher容器申请的另外的lvm盘中。

640 (8).png

5.3 云盘存储

我们为虚拟机的系统盘和数据盘对接了云存储，方便用户在迁移或者某些其他场景下使用。

5.3.1 系统盘接入云盘

系统盘对接云存储，首先需要将虚拟机的基础镜像上传到basic ns下的pvc中，然后根据此pvc创建volumesnapshot。而在某个namespace下创建虚拟机时，需要从basic ns下拷贝基础镜像的volumesnapshot到自己的namespace下，然后依据拷贝的volumesnapshot创建出新的pvc给虚拟机使用。其中上传虚拟机基础镜像到basic namespace下的pvc及做snapshot的步骤，我们做了一个上传镜像的工具来统一管理；而创建虚拟机时需要的系统盘pvc及将pvc挂载到 vmi中的一系列操作，我们则是通过一个新定义的crd，及新的crd controller来实现统一的自动化管理。

640 (9).png

5.3.2 数据盘接入云盘

数据盘对接云存储，则是先在虚拟机所在namespace下创建pvc，然后将pvc配置到vmi的yaml中，virt-controller在创建vmi对应的virt-launcher pod时，会根据vmi中pvc的配置，将pvc volume配置到virt-launcher pod中，然后存储组件会挂载一个带有pvc信息的目录给pod，之后virt-start-hook会根据virt-launcher pod中pvc目录中的信息将云盘配置到domain的xml，供虚拟机使用。

640 (10).png

  1. 扩展功能

6.1 支持虚拟机停机/启动/重启

原生kubevirt提供了一些同步接口，比如pause和unpause，分别的作用是将虚拟机挂起和唤醒。原生的stop和start需要操作vm crd会导致虚拟机销毁再重建，这无法满足我们的需求。另外由于原本的架构不支持虚拟机的shutdown和start，因此也并未提供直接stop和start及reboot本虚拟机的接口（stop即对应shutdown）。而我们的用户有这个需求，由于经过架构改造后的kubevirt支持了虚拟机的shutdown和start，因此我们也在pause/unpause vmi的基础上定义开发了虚拟机的stop/start/reboot等接口，并增加了stopping，starting，rebooting等中间状态，方便用户查看使用。

6.2 支持虚拟机静态扩容缩容CPU/内存/本地盘

停机扩容缩容CPU/Mem/本地盘，提供的也是同步接口。此功能在扩容时，最终修改虚拟机的xml配置之前，需要先动态扩容virt-launcher pod的相关资源以便于检查虚拟机所在节点上是否有足够的资源进行扩容，如果所在节点资源不足需要拦截本次扩容请求，并回滚对于vmi及pod等相关配置的相关修改。而动态扩容pod配置，原生kubernetes是不支持的，这是我们在内部的k8s中提供的另外一套解决方案。

6.3 支持虚拟机Cpu绑核及大页内存

cpu绑核功能主要是结合了kubelet的cpuset功能来实现的，需要kubelet配置—cpu-manager-policy=static开启容器的绑核功能。流程大概是这样的，vmi配置上cpu的相关绑核配置dedicatedCpuPlacement=”true”等，然后创建guarantee的virt-launcher pod，virt-launcher pod调度到开启了绑核配置的kubelet节点上，kubelet为virt-launcher pod分配指定的cpu核，然后virt-launcher进程从自己的container中查看自己有哪些核，再将这些核配置到虚拟机xml中，从而通过kubelet管理cpu的方式实现了虚拟机和容器的cpuquota和cpuset的分配方式的统一管理。而虚拟机大页内存也是与k8s资源管理结合的思路，即通过使用k8s中已存在的大页内存资源，通过pod占用再分配给虚拟机的方式实现的。

6.4 其他功能

除了以上介绍的扩展功能外，我们还实现了支持虚拟机静态和动态增加或减少云盘、重置密码、查看虚拟机xml、支持云盘只读限制、支持直通GPU、直通物理机磁盘、virtionet支持多队列、IP显示优化等其他需求，供用户使用。

总结

当前我们已在多个集群中，同时提供了虚拟机和容器服务，实现了混合集群管理。基于此方案生产的虚拟机在我们的私有云领域已经提供给了众多业务使用，在稳定性及性能等方面都提供了强有力的保障。下一步主要的工作在于将容器和虚拟机在节点上能够实现混合部署，这样不仅在控制面上能够进行统一调度，在数据面上也能够进行混合管理。

另外除了本文介绍的工作之外，我们也实现了虚拟机快照，镜像制作和分发，静态迁移等方案，后续我们团队也会继续发文分享。

作者简介

Weiwei OPPO高级后端工程师

主要从事调度、容器化、混合云等相关方向的工作。

获取更多精彩内容，扫码关注[OPPO数智技术]公众号

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第1天，活动详情查看：2021最后一次更文挑战」。

前言

立冬啦！正式步入冬天，不过长沙的天气在这两天时好时坏，但是在今天出太阳啦晒晒太阳，突然想到之前画了个樱花的视频，然后趁着心情好就把它解析出来，嘿嘿是真的还蛮好看的，而且一个代码可以随机画出多种样式的，一起来看看叭

完成目标

通过Python绘制樱花树

B11D9ARN2MO6FAX4BLW.png

视频展现：

樱花动图.gif

因为一种樱花树要画比较久，我也就稍微展示一下啦，当然还有很多种就没有一一录屏了，可以自行去研究哦，嘻嘻嘻

工具准备

开发工具：pycharm

开发环境：python3.7， Windows11

使用工具包：turtle

项目解析思路

项目思路分为3部分：

  • 绘制樱花的落叶花瓣，掉落的花瓣
  • 给樱花树添加树枝
  • 给樱花树添加绘画背景
  • 颜色的绘制选取各种样式的颜色

绘制掉落花瓣功能

确定花瓣掉落的数量，掉落的花瓣数根据樱花树枝来判断，和树枝数乘15，树画的越大掉的就越多哈

设定花瓣的坐标花瓣的大小设置为（10,10）控制画笔移动到指定区域提笔，向前y，左转90，走x，落笔，画出花瓣形状，绘画完所以的花瓣数量就ok，在将画的形状指定颜色，在勾勒出圆形，回到起点提笔，后退x，右转90,后退y，落笔

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
scss复制代码def draw_petal(turtle_obj, flower):
    # 绘制掉落的花瓣
    for i in range(int(flower)):
        # 有正有负就可以让画笔往二个方向走
        x = flower - 4 * flower * random()

        # 花瓣整体宽度(-10, 10)
        y = 10 - 20 * random()

        # 提笔，向前y，左转90，走x，落笔
        turtle_obj.penup()
        turtle_obj.forward(y)
        turtle_obj.left(90)
        turtle_obj.forward(x)
        turtle_obj.pendown()

        # 珊瑚色
        turtle_obj.pencolor("lightcoral")
        # 画圆
        turtle_obj.circle(1)

        # 回到起点
        # 提笔，后退x，右转90,后退y，落笔
        turtle_obj.penup()
        turtle_obj.backward(x)
        turtle_obj.right(90)
        turtle_obj.backward(y)
        turtle_obj.pendown()

画树枝部分

确定树枝数量，颜色的色号选择，先默认设定最小的树枝分支长度个树枝两边设定颜色能看起来更加的好看，左边为白色，右边为珊瑚色，分支的概率设定在0.5，树枝可以设定成随机生长，通过随机数设定

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
48
49
50
51
52
53
54
55
56
57
58
python复制代码# 画树枝部分
def draw_tree(turtle_obj, branch, tree_color):
    # 设置一个最小分支长度
    min_branch = 4

    if branch > min_branch:
        if branch < 8:
            # 以0.5的概率，向左、右分支
            if randint(0, 1) == 0:
                # 左为白色
                turtle_obj.pencolor("snow")
            else:
                # 右为珊瑚色
                turtle_obj.pencolor("lightcoral")
            # 枝干
            turtle_obj.pensize(branch / 2)
        elif 8 <= branch <= 16:
            # 以0.33的概率，分为左、中、右分支
            if randint(0, 2) == 0:
                # 左为白色
                turtle_obj.pencolor("snow")
            else:
                # 中、右为珊瑚色
                turtle_obj.pencolor("lightcoral")
            # 树枝
            turtle_obj.pensize(branch / 4)
        else:
            # 褐色
            turtle_obj.pencolor(tree_color)
            # 细枝
            turtle_obj.pensize(branch / 10)

        # 最开始的树干长度
        turtle_obj.forward(branch)

        # 随机度数因子
        a = 1.5 * random()
        # 顺时针旋转随机角度（0～30度）
        turtle_obj.right(20 * a)

        # 随机长度因子
        b = 1.5 * random()
        # 往右画，直到画不动为止
        draw_tree(turtle_obj, branch - 10 * b, tree_color)

        # 左转随机角度
        turtle_obj.left(40 * a)
        # 往左画，直到画不动位置
        draw_tree(turtle_obj, branch - 10 * b, tree_color)

        # 右转一定角度
        turtle_obj.right(20 * a)
        # 提笔
        turtle_obj.penup()

        # 递归结束回到起点
        turtle_obj.backward(branch)
        turtle_obj.pendown()

创建画布，将数据颜色进行添加，设置好运行的加速倍数

1
2
3
4
5
6
7
8
9
10
arduino复制代码def get_screen(width, height, color, speed):
    # 创建画幕
    screen_obj = turtle.Screen()
    # 画布大小：(width, height)，颜色：color
    screen_obj.screensize(width, height, bg=color)
    screen_obj.setup(1.0, 1.0)
    # speed倍加速
    screen_obj.tracer(speed)

    return screen_obj

颜色画布画笔的选择：

  • 树干的颜色
  • 画笔的大小
  • 前进的相素格
  • 创建画笔
  • 画笔的粗细调整
  • 提笔落笔的选择
  • 画笔的颜色配置
  • 设置常量参数 枝干的粗细 落花数 第几颗数
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
ini复制代码def trees(tree_num):
    # 颜色
    color = ['brown', 'tan', 'black']

    for j in range(tree_num):
        # 树干颜色
        tree_color = color[randint(0, len(color) - 1)]

        # 画笔大小
        pensize = randint(2, 5)
        # 前进像素
        forward = ((-1) ** pensize) * pensize * randint(20, 50)
        # 后退像素
        if pensize <= 3:
            backward = ((-1) ** pensize) * (5 - pensize) * randint(10, 15)
        else:
            backward = pensize * randint(45, 50)

        # 创建画笔
        turtle_obj = turtle.Turtle()
        # 画笔粗细
        turtle_obj.pensize(pensize)
        # 提笔，向前forward，左转90，backward，落笔
        turtle_obj.penup()
        turtle_obj.forward(forward)
        turtle_obj.left(90)
        turtle_obj.backward(backward)
        turtle_obj.pendown()
        # 画笔颜色：褐色
        turtle_obj.pencolor(tree_color)

        # 枝干粗细
        branch = pensize * 15
        # 落花数
        flowers = branch
        # 第j棵树
        draw_tree(turtle_obj, branch, tree_color)
        # 花瓣
        draw_petal(turtle_obj, flowers)

我是白又白i，一名喜欢分享知识的程序媛❤️

感兴趣的可以关注我的公众号：白又白学Python【非常感谢你的点赞、收藏、关注、评论，一键三连支持】

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第8天，活动详情查看：2021最后一次更文挑战

image.png

根据这棵二叉树 我们先手动来模拟一下深度优先遍历算法，先访问a,a访问b 在b访问后 我们接着访问c 在c访问发现c没有孩子我们就回溯到b点再访问e点 ，e访问后再访问h ，发现h没有孩子就回溯到e点，发现e点孩子都访问完了又回溯到b点发现b点的孩子有访问了 则又回溯到a点再访问c点这样访问+回缩最后这棵树的顺序则为：abdehcfg 在这个过程中就会有一个（递归思想在里面）
若我们对树进行先序遍历，遍历的结果是：abdehcfg

因此根据上面模拟的过程再一次来梳理思想：
首先访问某一个起始顶点v，然后接着会访问v的未被访问的任一邻接点w1，再访问w1未被访问的任一邻接点w2..不断往下面访问，当不能再往下访问时，就回溯到最近刚被访问的顶点，若这个顶点还有邻接点未访问就继续上面的过程 最后倒所有结点都访问完就结束这次遍历

结合上面的思想来看一下他的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
scss复制代码bool visited[MaxNum]; //标记数组 用于标记结点是否被访问过
void DFSTraverse(Graph G){
  for(int i=0;i<G.vexnum;i++){ //初始化数组
    visited[i] = false;
  }
  
  for(int i;i<G.vexnum;i++){
    if(visited[i]){
      DFS(G,i);
    }
  }
}

void DFS(Graph G,int v){
   visit(v);
   visited[v] = true; //修改标记数组
   for(w=FirstNeighbor(G,v); W>=0; w= NextNeighbor(G,v,w)){  //检查顶点的所有邻接点
     if(!visited[w]){  
       DFS(G,w);
     }
   }

}

算法性能分析：

时间复杂度：

邻接矩阵： O(|V|2)

邻接表： O(|V|+|E|)

空间复杂度：O(|V|)（需要一个递归工作栈）

  • 总结
    图的遍历算法，在昨天和今天分享的广度优先遍历算法和深度优先遍历算法，广度优先遍历借助队列的先进先出特点来辅助，深度优先借助的就是一个递归栈来辅助实现的

而这两种遍历算法可以用来测试图的连通性，对于无向图来说，从任一个结点出发，遍历一次就能访问所有结点，所以不能一次访问完所有结点就可知该图为非连通图，对于有向图来说，从初始点到每一个点都有路径，则能够访问完所有结点 反之就不能访问。所以对于无向图，调用BFS(G,i)、DFS(G,i)的次数就是该图的连通分量数，而对于有向图，非强连通图是无法访问所有结点的。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

DispatcherServlet:

前端控制器，不需要工程师开发，由框架提供。
作用：统一处理请求和响应，整个流程控制的中心，由它调用其他组件处理用户的请求

HandlerMapping:

处理器映射器，不需要工程师开发，由框架提供。
作用：根据请求的url、method等信息查找Handler,即控制器方法

Handler：

处理器，需要工程师开发
作用：在Dispatcher的控制下Handler对具体的用户请求进行处理

HandlerAdapter：

处理器适配器，不需要工程师开发，由框架提供。
作用：通过HandlerAdapter对处理器（控制器方法）进行执行

ViewResolver:

视图解析器，不需要工程师开发，由框架提供。
作用：进行视图解析，得到相应的视图，例如：ThymeleafView、InternalResourceView、RedirectView

View:

视图。
作用：将模型数据通过页面展示给用户

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

说起「边玩边赚」的游戏，必然要提到 Axie Infinity。这款游戏开创了一种前所未有的游戏类型，可以让玩家边玩边赚。

在游戏玩法上，Axie Infinity 与 Pokémon 相似：玩家饲养、繁殖他们的 Axies，然后让 Axies 参与战斗。Axies 是一种看起来像蝾螈的卡通人物，不同之处在于，赢家不是通过胜利获得积分，而是获得该游戏的原生代币——Smooth Love Potion (SLP)。玩家可以直接在游戏里赚钱，人在家中坐，钱从网上来。

微信截图_20211108152832.png

现在，区块链技术似乎颠覆了传统的电子游戏市场。区块链技术将真正所有权的概念带入了数字游戏世界。由于这个和许多其他功能，区块链可以带来完全沉浸的感觉，并采取游戏的经验，到一个全新的水平。玩家可以在一个游戏中购买游戏元素，并将其顺利转移到另一个游戏中。这意味着区块链生态系统中玩家拥有的所有资产现在都有了真正的价值。这些资产第一次成为游戏玩家的财产，而不是游戏公司的财产。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第8天，活动详情查看：2021最后一次更文挑战

1.业务背景

如果有有错误消息，如果手动nack同时将消息放回到队列中，那么这条消息会反复消费，留在队列中 。

如果nack后将消息丢弃，那么如果碰到网络抖动，消息也会丢失 。所以 通过建立死信队列避免消息丢失。​

2.实现

文件目录如下：
在这里插入图片描述

1.原理

我们额外建立一条队列。当消息进入进入业务队列后，如果收到nack那么就将这条消息放入这条条队列中 。

2.修改pom文件

1
2
3
4
js复制代码       <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-amqp</artifactId>
        </dependency>

3.修改配置文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
js复制代码server:
  port: 8088
spring:
  rabbitmq:
    host: 192.168.*.*
    port: 5672
    username: root
    password: root
    virtual-host: /
    listener:
      simple:
        acknowledge-mode: manual  #手动应答
        prefetch: 1 # 每次只处理一个信息
    publisher-confirms: true #开启消息确认机制
    publisher-returns: true #支持消息发送失败返回队列

4.rabbitmq的配置

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
js复制代码@Configuration
public class RabbitMqConfig {

    /**
     * 连接工厂
     */
    @Autowired
    private ConnectionFactory connectionFactory;

    /**
     * 定制化amqp模版
     *
     * ConfirmCallback接口用于实现消息发送到RabbitMQ交换器后接收ack回调 即消息发送到exchange ack
     * ReturnCallback接口用于实现消息发送到RabbitMQ 交换器，但无相应队列与交换器绑定时的回调 即消息发送不到任何一个队列中 ack
     */
    @Bean
    public RabbitTemplate rabbitTemplate() {
        Logger logger = LoggerFactory.getLogger(RabbitTemplate.class);
        RabbitTemplate rabbitTemplate = new RabbitTemplate(connectionFactory);
        // 消息发送失败返回到队列中, yml需要配置 publisher-returns: true
        rabbitTemplate.setMandatory(true);
        // 发送消息确认, yml需要配置 publisher-confirms: true
        rabbitTemplate.setConfirmCallback(msgSendConfirmCallBack());
        // 消息返回, yml需要配置 publisher-returns: true
        rabbitTemplate.setReturnCallback((message, replyCode, replyText, exchange, routingKey) -> {
            String correlationId = message.getMessageProperties().getCorrelationId().toString();
            logger.debug("消息：{} 发送失败, 应答码：{} 原因：{} 交换机: {}  路由键: {}", correlationId, replyCode, replyText, exchange,
                routingKey);
        });
        return rabbitTemplate;
    }

    /**
     * 确认发送消息是否成功(调用util方法)
     *
     * @return
     */
    @Bean
    public MsgSendConfirmCallBack msgSendConfirmCallBack() {
        return new MsgSendConfirmCallBack();
    }
}

5.util类

发送是否成功的回调方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
js复制代码public class MsgSendConfirmCallBack implements RabbitTemplate.ConfirmCallback {

    /**
     * 回调方法
     * @param correlationData
     * @param ack
     * @param cause
     */
    @Override
    public void confirm(CorrelationData correlationData, boolean ack, String cause) {
        System.out.println("MsgSendConfirmCallBack  , 回调id:" + correlationData);
        if (ack) {
            System.out.println("消息发送成功");
        } else {
            //可以将消息写入本地，使用定时任务重新发送
            System.out.println("消息发送失败:" + cause + "\n重新发送");
        }
    }

}

这里有一个点，如果想做实现消息失败重新发送，在注释处可以实现。需要将消息写入本地，如果失败从本地读取，然后发送，如果成功删除本地信息。

6.业务队列(如：订单业务)

这里声明了一个业务队列 ，关键点在于x-dead-letter-exchange，x-dead-letter-routing-key 两个参数。

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
js复制代码@Configuration
public class BusinessConfig {

    /**
     * 业务1模块direct交换机的名字
     */
    public static final String YEWU1_EXCHANGE = "yewu1_direct_exchange";

    /**
     * 业务1 demo业务的队列名称
     */
    public static final String YEWU1_DEMO_QUEUE = "yewu1_demo_queue";

    /**
     * 业务1 demo业务的routekey
     */
    public static final String YEWU1_DEMO_ROUTINGKEY = "yewu1_demo_key";

    
    @Bean
    public Queue yewu1DemoDeadQueue() {
        // 将普通队列绑定到死信队列交换机上
        Map<String, Object> args = new HashMap<>(2);
        args.put(RetryConfig.RETRY_LETTER_QUEUE_KEY, DeadConfig.FAIL_EXCHANGE_NAME);
        args.put(RetryConfig.RETRY_LETTER_ROUTING_KEY, DeadConfig.FAIL_ROUTING_KEY);
        return new Queue("yewu1_demo_dead_queue", true, false, false, args);
    }

    /**
     * 将消息队列和交换机进行绑定
     */
    @Bean
    public Binding binding_one() {
        return BindingBuilder.bind(yewu1DemoDeadQueue()).to(yewu1Exchange())
            .with("yewu1_demo_dead_key");
    }
}

这里有一个点如果想持久化消息到磁盘，需要新建队列时，new Queue将第二个参数输入为true，但是面对大并发时效率会变低 。

7.死信队列

这里声明死信队列与绑定关系。

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
48
49
js复制代码@Configuration
public class DeadConfig {

    /**
     * 死信队列
     */
    public final static String FAIL_QUEUE_NAME = "fail_queue";

    /**
     * 死信交换机
     */
    public final static String FAIL_EXCHANGE_NAME = "fail_exchange";

    /**
     * 死信routing
     */
    public final static String FAIL_ROUTING_KEY = "fail_routing";

    /**
     * 创建配置死信队列
     *
     */
    @Bean
    public Queue deadQueue() {
        return new Queue(FAIL_QUEUE_NAME, true, false, false);
    }

    /**
     * 死信交换机
     *
     * @return
     */
    @Bean
    public DirectExchange deadExchange() {
        DirectExchange directExchange = new DirectExchange(FAIL_EXCHANGE_NAME, true, false);
        return directExchange;
    }

    /**
     * 绑定关系
     * 
     * @return
     */
    @Bean
    public Binding failBinding() {
        return BindingBuilder.bind(deadQueue()).to(deadExchange()).with(FAIL_ROUTING_KEY);
    }

}

8.生产者消费者

生产者与消费者的代码实现。

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
js复制代码public enum RabbitEnum {

    /**
     * 处理成功
     */
    ACCEPT,

    /**
     * 可以重试的错误
     */
    RETRY,

    /**
     * 无需重试的错误
     */
    REJECT
@RequestMapping("/sendDirectDead")
        String sendDirectDead(@RequestBody String message) throws Exception {
        System.out.println("开始生产");
        CorrelationData data = new CorrelationData(UUID.randomUUID().toString());
        rabbitTemplate.convertAndSend(BusinessConfig.YEWU1_EXCHANGE, "yewu1_demo_dead_key",
                message, data);
        System.out.println("结束生产");
        System.out.println("发送id:" + data);
        return "OK,sendDirect:" + message;
    }
    @RabbitListener(queues = "yewu1_demo_dead_queue")
    protected void consumerDead(Message message, Channel channel) throws Exception {
        RabbitEnum ackSign = RabbitEnum.RETRY;
        try {
            int i = 10 / 0;
            channel.basicAck(message.getMessageProperties().getDeliveryTag(), false);
        } catch (Exception e) {
            ackSign = RabbitEnum.RETRY;
            throw e;
        } finally {
            // 通过finally块来保证Ack/Nack会且只会执行一次
            if (ackSign == RabbitEnum.ACCEPT) {
                channel.basicAck(message.getMessageProperties().getDeliveryTag(), false);
            } else if (ackSign == RabbitEnum.RETRY) {
                channel.basicNack(message.getMessageProperties().getDeliveryTag(), false, false);
            }
        }
    }

9.实验

当发送yewu1_demo_dead_queue队列时，如果抛出异常，会放入死信队列中。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

字符串匹配

BF算法

BF算法是最简单也是最暴力的一种方法，即模式串依次在主串的第i个位置开始进行比较，相同则继续比较，不同就移至下一位重新比较。

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
kotlin复制代码package algorithm.string_match;

/**
 * @author EnochStar
 * @title: BF
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/8 11:56
 */
public class BF {
    public boolean isMatching(String mainString,String sonString) {
        if (mainString == null || sonString == null) {
            return false;
        }
        for (int i = 0;i < mainString.length() - sonString.length() + 1;i++) {
            for (int j = 0;j < sonString.length();j++) {
                if (mainString.charAt(i + j) != sonString.charAt(j)) {
                    break;
                }
                if (j == sonString.length() - 1) return true;
            }
        }
        return false;
    }
}

极端情况下时间复杂度为O（n*m）（如：主串”aaaaaaaaaa…..“ 子串”aaaaaab“），尽管时间复杂度很高，但他是最常用的字符串匹配算法。原因如下：

1、在大多数情况下，主串和子串的长度不会特别长，同时子串在中途遇到不能匹配的字符时，就停止匹配了，所以不会完全遍历子串

2、该算法实现简单，当出现bug时也容易发现并修正。

RK算法

其思路是利用哈希算法，求得主串下的所有与模式串相同长度的子串的哈希值，这样只要比较哈希值即可确认主串中是否存在子串。关键就在于求主串下所有子串的哈希值所消耗的时间。

image.png
由图可知h[i]与h[i-1]存在一定的关系。

image.png

用数学表达可知，h[i] = 26h[i - 1] - 26^m(s[i - 1] - 'a') + s[i + m - 1] - 'a'.

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
arduino复制代码package algorithm.string_match;

import java.util.HashSet;
import java.util.Set;

/**
 * @author EnochStar
 * @title: RK
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/8 14:17
 */
public class RK {
    private Set<Long> set = new HashSet();

    public boolean matching(String mainString,String sonString) {
        int m = sonString.length();
        initSonOfMainHash(mainString,m);
        long base = initBase(sonString,m);

        return set.contains(base);
    }
    private void initSonOfMainHash(String mainString,int m){
        long base = initBase(mainString,m);
        set.add(base);
        for (int i = 1;i < mainString.length() - m + 1;i++) {
            base = (long) (26 * base - Math.pow(26,m) * (mainString.charAt(i - 1) - 'a')
            + (mainString.charAt(i + m - 1) - 'a'));
            set.add(base);
        }
    }
    private long initBase(String s,int m) {
        long base = 0;
        for (int i = 0;i < m;i++) {
            base += Math.pow(26,m - i - 1) * (s.charAt(i) - 'a');
        }
        return base;
    }

}

由关系表达式，只需要O(n)的时间复杂度即可求得主串下所有子串的哈希值，用set判断模式串的哈希值是否存在也只需要O(n)的时间复杂度，故该方法的时间复杂度为O(n)，但存在缺陷，如果模式串和主串的长度都非常的长，超过了数值的范围，那么这种方法就不可取了，这时候只能允许哈希冲突，当存在哈希值的时候再使用BK算法进行判断。

BM

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
ini复制代码package algorithm.string_match;

import java.util.Arrays;

/**
 * @author EnochStar
 * @title: BM
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/9 14:58
 */
public class BM {

    // 用于存储坏字符最后一次出现在模式串的位置
    private int[] table = new int[256];

    public int bm(char[] a,int n,char[] b,int m){
        initTable(b,m);
        int[] suffix = new int[m];
        boolean[] prefix = new boolean[m];
        initSuffixAndPrefix(b,m,suffix,prefix);
        int i = 0;
        while (i <= n - m) {
            int j;
            for (j = m - 1;j >= 0;j--) {
                if (a[i + j] != b[j]) break;
            }
            if (j < 0) return i;
            int moveBad =j - table[a[j + i]];
            int y = 0;
            if (j < m - 1) {
                y = moveGood(j,m,prefix,suffix);
            }
            i = i + Math.max(y,moveBad);
        }
        return -1;
    }
    private int moveGood(int j,int m,boolean[] prefix,int[] suffix) {
        int k = m - 1 - j;
        if (suffix[k] != -1) {
            return j - suffix[k] + 1;
        }
        for (int r = j + 2;r <= m - 1;r++) {
            if (prefix[m - r]) return r;
        }
        return m;
    }
    private void initTable(char[] b,int m) {
        Arrays.fill(table, -1);
        for (int i = 0;i < m;i++) {
            int ascii = (int)b[i];
            table[ascii] = i;
        }
    }
    private void initSuffixAndPrefix(char[] b,int m,int[] suffix,boolean[] prefix){
        Arrays.fill(suffix,-1);
        Arrays.fill(prefix,false);
        for (int i = 0;i < m - 1;i++) {
            int j = i;
            int k = 0;
            while (j >= 0 && b[j] == b[m - 1 - k]) {
                --j;
                k++;
                suffix[k] = j + 1;
            }
            if (j == -1) prefix[k] = true;
        }
    }
}

KMP算法

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
ini复制代码package algorithm.string_match;

/**
 * @author EnochStar
 * @title: KMP
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/10 15:38
 */
public class KMP {
    public int kmp(char[] a,int n,char[] b,int m) {
        int[] next = generateNext(b);
        int j = 0;
        for (int i = 0;i < n - m + 1;i++) {
            while (j > 0 && a[i] != b[j]) {
                j = next[j - 1] + 1;
            }
            if (a[i] == b[j]) j++;
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
    private int[] generateNext(char[] b) {
        int len = b.length;
        int[] next = new int[len];
        int k = -1;
        next[0] = -1;
        for (int i = 1;i < len;i++) {
            while (k != -1 && b[i] != b[k + 1]) {
                k = next[k];
            }
            if (b[i] == b[k + 1]) {
                k++;
            }
            next[i] = k;
        }
        return next;
    }
}

字典树(Trie)

不同于kmp、rk、bm等算法，模式串-主串。他是将所有字符串统一加入到字典中，后续判断字符串是否存在于字典树中。

实现字典树

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
48
49
50
51
ini复制代码package algorithm.string_match;

/**
 * @author EnochStar
 * @title: Trie
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/11 10:48
 */
public class Trie {

    TrieNode head = new TrieNode();

    public void insert(char[] string) {
        TrieNode root = head;
        for (int i = 0;i  < string.length;i++) {
            int index = string[i] - 'a';
            if (root.childrenNode[index] == null) {
                TrieNode node = new TrieNode(string[i]);
                root.childrenNode[index] = node;
            }
            root = root.childrenNode[index];
        }
        root.isEnd = true;
    }

    public boolean find(char[] string) {
        TrieNode root = head;
        for (int i = 0;i < string.length;i++) {
            int index = string[i] - 'a';
            if (root.childrenNode[index] == null) {
                return false;
            }
            root = root.childrenNode[index];
        }
        return root.isEnd;
    }
}
class TrieNode{
    private char data;
    public TrieNode[] childrenNode = new TrieNode[26];
    public boolean isEnd;

    public TrieNode() {

    }

    public TrieNode(char data) {
        this.data = data;
    }
}

字典树的优缺点

字典树是一种空间换时间的思路，其本质虽然是避免存储相同前缀的字符串，但重复前缀并不多的情况下，每一个节点都需要存储26个字符，如果需要存储中文字符、数字等，那么需要更多的存储空间。面对空间浪费的情况，可以选择舍弃一定的查询效率，选择红黑树、有序数组、跳表、散列表等。

总结：Trie树使用的场景

1、不适用于字符集特别大的情况

2、要求字符串的前缀重合比较多

3、Trie由于用到了指针，所以对cpu缓存不友好。

Trie树不适合精确查找，比较适合查找前缀匹配的字符。因此可以用于搜索关键字的提示。

贪心算法

贪心算法是一种算法思想。指在对问题求解时，总是做出在当前看来是最好的选择。典型应用于哈夫曼编码。

在给定限定值和期望值的情况下，要求在满足限定值时使期望值达到最大。这个时候可以使用贪心算法。

image.png
当背包容量一定时，要求背包内的价值最大，可以对各个豆子求单位容量下的价值，然后从大到小依次放入背包中。

但有时贪心算法得到的也不是最优值。

image.png

贪心算法的思路，先找到和S相连权的最小边，直到找到T，路径为S -》 A -》E -》 T ,而最短路径为S -》B -》 D -》 T。

实战题

435. 无重叠区间 - 力扣（LeetCode） (leetcode-cn.com)

402. 移掉 K 位数字 - 力扣（LeetCode） (leetcode-cn.com)

分治算法

分而治之，将原问题划分成n个规模较小，且结构与原问题相似的子问题，递归的解决这个子问题，再合并结果。

应用举例

求逆序对，暴力法为O（n^2）,可以采取分治法的思路，将原数组划分为A、B两个子数组，然后查询A数组内的逆序对和B数组内逆序对，以及A、B之间的逆序对。

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
ini复制代码class Solution {
    private int num;
    public int reversePairs(int[] nums) {
        num = 0;
        reverse(nums,0,nums.length - 1);
        return num;
    }
    public void reverse(int[] nums,int left,int right) {
        if(left >= right) {
            return;
        }
        int mid = ((right - left) >> 1) + left;
        reverse(nums,left,mid);
        reverse(nums,mid + 1,right);
        sort(nums,left,mid,right);
    }
    public void sort(int[] nums,int left,int mid,int right) {
        int l1 = left;
        int l2 = mid + 1;
        int[] tmp = new int[right - left + 1];
        int k = 0;
        while(l1 <= mid && l2 <= right) {
            if(nums[l1] <= nums[l2]) {
                tmp[k++] = nums[l1++];
            }else{
                num += (mid - l1 + 1);
                tmp[k++] = nums[l2++];
            }
        }
        while(l1 <= mid) {
            tmp[k++] = nums[l1++];
        }
        while(l2 <= right) {
            tmp[k++] = nums[l2++];
        }
        for(int i = 0;i < tmp.length;i++) {
            nums[i + left] = tmp[i];
        }
    }
}

剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode） (leetcode-cn.com)

回溯算法

回溯算法即枚举所有的解。

典型应用

八皇后

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
48
49
50
51
52
53
54
55
56
57
58
ini复制代码class Solution {
    private List<List<String>> res; 
    public List<List<String>> solveNQueens(int n) {
        res = new ArrayList();
        char[][] board = new char[n][n];
        init(board);
        tryPut(board,0,n);
        return res;
    }

    public void tryPut(char[][] board,int level,int n) {
        if(level == n) {
            res.add(convert(board));
            return;
        }
        for(int i = 0;i < n;i++) {
            board[level][i] = 'Q';
            if(isValid(board,level,i)) {
                tryPut(board,level + 1,n);
            }
            board[level][i] = '.';
        }
    }

    // 转化为String
    public List<String> convert(char[][] board) {
        List<String> tmp = new ArrayList();
        for(int i = 0;i < board.length;i++) {
            String s = new String(board[i]);
            tmp.add(s);
        }
        return tmp;
    }

    public boolean isValid(char[][] board,int level,int col) {
        for(int i = 0;i < level;i++) {
            if(board[i][col] == 'Q') return false;
        }
        for(int i = level - 1,j = col - 1;i >= 0 && j >= 0;) {
            if(board[i][j] == 'Q') return false;
            i--;
            j--;
        }
        for(int i = level - 1,j = col + 1;i >= 0 && j < board.length;) {
            if(board[i][j] == 'Q') return false;
            i--;
            j++;
        }
        return true;
    }

    // 初始化board
    public void init(char[][] board) {
        for(int i = 0;i < board.length;i++) {
            Arrays.fill(board[i],'.');
        }
    }
}

面试题 08.12. 八皇后 - 力扣（LeetCode） (leetcode-cn.com)

0-1背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
arduino复制代码public int maxW = Integer.MIN_VALUE; //存储背包中物品总重量的最大值
// cw表示当前已经装进去的物品的重量和；i表示考察到哪个物品了；
// w背包重量；items表示每个物品的重量；n表示物品个数
// 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数：
// f(0, 0, a, 10, 100)
    public void f(int i, int cw, int[] items, int n, int w) {
        if (cw == w || i == n) { // cw==w表示装满了;i==n表示已经考察完所有的物品
            if (cw > maxW) maxW = cw;
            return;
        }
        f(i + 1, cw, items, n, w);
        if (cw + items[i] <= w) {// 已经超过可以背包承受的重量的时候，就不要再装了
            f(i + 1, cw + items[i], items, n, w);
        }
    }

正则表达式

“*“匹配0个到多个任意字符，”.”匹配0个或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
typescript复制代码package algorithm;

/**
 * @author EnochStar
 * @title: Pattern
 * @projectName basic_use
 * @description: “*”表示匹配0个到多个 “。”表示匹配0或1个任意字符
 * @date 2021/11/15 16:35
 */
public class Pattern {
    private boolean isMatched = false;
    // s为待匹配 p为正则表达式
    public boolean match(String s,String p) {
        rMatch(s,0,p,0);
        return isMatched;
    }
    public void rMatch(String s,int sIndex,String p,int pIndex) {
        if (isMatched) return;
        if (pIndex == p.length()) {
            if (sIndex == s.length()) {
                isMatched = true;
            }
            return;
        }
        if (s.charAt(sIndex) == p.charAt(pIndex)) {
            rMatch(s,sIndex + 1,p,pIndex + 1);
        }else if (p.charAt(pIndex) == '.') {
            rMatch(s,sIndex + 1,p,pIndex + 1);
            rMatch(s,sIndex,p,pIndex + 1);
        }else if(p.charAt(pIndex) == '*') {
            for (int i = sIndex;i < s.length();i++) {
                rMatch(s,i,p,pIndex + 1);
            }
        }
    }
}

动态规划（一）

以0-1背包为例，用回溯法解决：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
arduino复制代码// 回溯算法实现。注意：我把输入的变量都定义成了成员变量。
private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
private int[] weight = {2, 2, 4, 6, 3}; // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量

public void f(int i, int cw) { // 调用f(0, 0)
    if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了
        if (cw > maxW) maxW = cw;
        return;
    }
    f(i + 1, cw); // 选择不装第i个物品
    if (cw + weight[i] <= w) {

        f(i + 1, cw + weight[i]); // 选择装第i个物品
    }
}

image.png
如图，有很多重复的计算，可以通过备忘录避免冗余计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ini复制代码private int maxW = Integer.MIN_VALUE; // 结果放到maxW中
private int[] weight = {2, 2, 4, 6, 3
}; // 物品重量
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量
private boolean[][] mem = new boolean[5][10]; // 备忘录，默认值false

public void f(int i, int cw) { // 调用f(0, 0)
    if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了
        if (cw > maxW) maxW = cw;
        return;
    }
    if (mem[i][cw]) return; // 重复状态
    mem[i][cw] = true; // 记录(i, cw)这个状态
    f(i + 1, cw); // 选择不装第i个物品
    if (cw + weight[i] <= w) {
        f(i + 1, cw + weight[i]); // 选择装第i个物品
    }
}

采用动规思路，可以将求解分为n个阶段，每个阶段会决策物品是否放入背包，决策（放入或者不放入背包）完之后，背包中的物品的重量会有多种情况，我们把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。我们可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过w个（w表示背包的承载重量）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ini复制代码// weight:物品重量，n:物品个数，w:背包可承载重量
public int knapsack(int[] weight, int n, int w) {
    boolean[][] states = new boolean[n][w+1]; // 默认值false
    states[0][0] = true; // 第一行的数据要特殊处理，可以利用哨兵优化
    states[0][weight[0]] = true;
    for (int i = 1; i < n; ++i) { // 动态规划状态转移
        for (int j = 0; j <= w; ++j) {// 不把第i个物品放入背包
            if (states[i-1][j] == true) states[i][j] = states[i-1][j];
        }
        for (int j = 0; j <= w-weight[i]; ++j) {//把第i个物品放入背包
            if (states[i-1][j]==true) states[i][j+weight[i]] = true;
        }
    }
    for (int i = w; i >= 0; --i) { // 输出结果
        if (states[n-1][i] == true) return i;
    }
    return 0;
}

回溯法的时间复杂度根据回溯树可知，为O（2 ^ n），而动规的时间复杂度为O（ｎ＊ｗ），可以对空间复杂度进行进一步的优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
arduino复制代码public static int knapsack2(int[] items, int n, int w) {
    boolean[] states = new boolean[w+1]; // 默认值false
    states[0] = true; // 第一行的数据要特殊处理，可以利用哨兵优化
    states[items[0]] = true;
    for (int i = 1; i < n; ++i) { // 动态规划
        for (int j = w-items[i]; j >= 0; --j) {//把第i个物品放入背包
            if (states[j]==true) states[j+items[i]] = true;
        }
    }
    for (int i = w; i >= 0; --i) { // 输出结果
        if (states[i] == true) return i;
    }
    return 0;
}

当要求满足最大价格限制前提下，使总价格最大：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ini复制代码private int maxV = Integer.MIN_VALUE; // 结果放到maxV中
private int[] weight = {2, 2, 4, 6, 3}; // 物品的重量
private int[] value = {3, 4, 8, 9, 6}; // 物品的价值
private int n = 5; // 物品个数
private int w = 9; // 背包承受的最大重量

public void f(int i, int cw, int cv) { // 调用f(0, 0, 0)
    if (cw == w || i == n) { // cw==w表示装满了，i==n表示物品都考察完了

        if (cv > maxV) maxV = cv;
        return;
    }
    f(i + 1, cw, cv); // 选择不装第i个物品
    if (cw + weight[i] <= w) {
        f(i + 1, cw + weight[i], cv + value[i]); // 选择装第i个物品
    }
}

image.png
由图可知，在（i，cw）相同的情况下，只需要考虑value最大的即可，此时回溯法无法用备忘录解决。
动规实现：

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
ini复制代码public static int knapsack3(int[] weight, int[] value, int n, int w) {
    int[][] states = new int[n][w+1];
    for (int i = 0; i < n; ++i) { // 初始化states
        for (int j = 0; j < w+1; ++j) {
            states[i][j] = -1;
        }
    }
    states[0][0] = 0;
    states[0][weight[0]] = value[0];
    for (int i = 1; i < n; ++i) { //动态规划，状态转移
        for (int j = 0; j <= w; ++j) { // 不选择第i个物品
            if (states[i-1][j] >= 0) states[i][j] = states[i-1][j];
        }
        for (int j = 0; j <= w-weight[i]; ++j) { // 选择第i个物品
            if (states[i-1][j] >= 0) {
                int v = states[i-1][j] + value[i];
                if (v > states[i][j+weight[i]]) {
                    states[i][j+weight[i]] = v;
                }
            }
        }
    }
    // 找出最大值
    int maxvalue = -1;
    for (int j = 0; j <= w; ++j) {
        if (states[n-1][j] > maxvalue) maxvalue = states[n-1][j];
    }
    return maxvalue;
}

思考

双十一想要薅羊毛，提供满200的优惠，现购物车有一系列商品，要求在能薅羊毛的前提下，使得商品价格最少，即大于200的最小值。

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
ini复制代码// items商品价格，n商品个数, w表示满减条件，比如200
public static void double11advance(int[] items, int n, int w) {
    boolean[][] states = new boolean[n][3*w+1];//超过3倍就没有薅羊毛的价值了
    states[0][0] = true; // 第一行的数据要特殊处理
    states[0][items[0]] = true;
    for (int i = 1; i < n; ++i) { // 动态规划
        for (int j = 0; j <= 3*w; ++j) {// 不购买第i个商品
            if (states[i-1][j] == true) states[i][j] = states[i-1][j];
        }
        for (int j = 0; j <= 3*w-items[i]; ++j) {//购买第i个商品
            if (states[i-1][j]==true) states[i][j+items[i]] = true;
        }
    }
    int j;
    for (j = w; j < 3*w+1; ++j) {
        if (states[n-1][j] == true) break; // 输出结果大于等于w的最小值
    }
    if (j == -1) return; // 没有可行解
    for (int i = n-1; i >= 1; --i) { // i表示二维数组中的行，j表示列
        if(j-items[i] >= 0 && states[i-1][j-items[i]] == true) {
            System.out.print(items[i] + " "); // 购买这个商品
            j = j - items[i];
        } // else 没有购买这个商品，j不变。
    }
    if (j != 0) System.out.print(items[0]);
}

练习

剑指 Offer II 100. 三角形中最小路径之和 - 力扣（LeetCode） (leetcode-cn.com)

动态规划（二）

一模型三特征

1、最优子结构。最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。

2、无后效性。第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。

3、重复子问题。不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态

解决动规的思路

1、状态转移表法。回溯算法实现-定义状态-画递归树-找重复子问题-画状态转移表-根据递推关系填表-将填表过程翻译成代码。

2、状态转移方程。找最优子结构-写状态转移方程-将状态 转移方程翻译成代码。

四种思想的比较

回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最 优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了。

尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重 复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划 之所以高效，就是因为回溯算法实现中存在大量的重复子问题。

贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（“贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。每一个阶段，我们都选择当前看起 来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。）

思考

322. 零钱兑换 - 力扣（LeetCode） (leetcode-cn.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ini复制代码class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int coin : coins) {
            for(int j = coin;j <= amount;j++) {
                if(dp[j - coin] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j],dp[j - coin] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

动态规划（三）

在搜索引擎中输入错误的单词时，搜索引擎提供一个拼音纠错功能。他是如何量化两个字符之间的相似程度的呢？

编辑距离是将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离就越 小，说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是0。

编辑距离有两种计算方式。一个是莱文斯坦距离，另一个是最长公共子串长度。莱文斯坦距离允许增加、删除、 替换字符这三个编辑操作，最长公共子串长度只允许增加、删除字符这两个编辑操作。分析相似度时，莱文斯坦距离的大小，表示两个字符串差异的大小；而最长公共子串的大小，表示两个字符串相似程度的大小。

莱文斯坦距离

如果a[i]与b[j]匹配，我们递归考察a[i+1]和b[j+1]。如果a[i]与b[j]不匹配，那我们有多种处理方式可选：

  • 可以删除a[i]，然后递归考察a[i+1]和b[j]；
  • 可以删除b[j]，然后递归考察a[i]和b[j+1]；
  • 可以在a[i]前面添加一个跟b[j]相同的字符，然后递归考察a[i]和b[j+1];
  • 可以在b[j]前面添加一个跟a[i]相同的字符，然后递归考察a[i+1]和b[j]；
  • 可以将a[i]替换成b[j]，或者将b[j]替换成a[i]，然后递归考察a[i+1]和b[j+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
ini复制代码package algorithm.edit_distance;

/**
 * @author EnochStar
 * @title: LaiWenSiTan
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/18 11:16
 */
public class LaiWenSiTan {
    private char[] a = "mitcmu".toCharArray();
    private char[] b = "mtacnu".toCharArray();
    private int n = 6;
    private int m = 6;
    private int minDist = Integer.MAX_VALUE; // 存储结果
    // 调用方式 lwstBT(0, 0, 0);
    public void lwstBT(int i, int j, int edist) {
        if (i == n || j == m) {
            if (i < n) edist += (n-i);
            if (j < m) edist += (m - j);
            if (edist < minDist) minDist = edist;
            return;
        }
        if (a[i] == b[j]) { // 两个字符匹配
            lwstBT(i+1, j+1, edist);
        } else { // 两个字符不匹配
            lwstBT(i + 1, j, edist + 1); // 删除a[i]或者b[j]前添加一个字符
            lwstBT(i, j + 1, edist + 1); // 删除b[j]或者a[i]前添加一个字符
            lwstBT(i + 1, j + 1, edist + 1); // 将a[i]和b[j]替换为相同字符
        }
    }
}

image.png
递归树可知，(i,j)相同时，保留更小的edist，由此推断出状态转移方程

如果：a[i]!=b[j]，那么：min_edist(i, j)就等于： min(min_edist(i-1,j)+1, min_edist(i,j-1)+1, min_edist(i-1,j-1)+1) 如果：a[i]==b[j]，那么：min_edist(i, j)就等于： min(min_edist(i-1,j)+1, min_edist(i,j-1)+1，min_edist(i-1,j-1)) 其中，min表示求三数中的最小值。

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
ini复制代码public int lwstDP(char[] a, int n, char[] b, int m) {
    int[][] minDist = new int[n][m];
    for (int j = 0; j < m; ++j) { // 初始化第0行:a[0..0]与b[0..j]的编辑距离
        if (a[0] == b[j]) minDist[0][j] = j;
        else if (j != 0) minDist[0][j] = minDist[0][j-1]+1;
        else minDist[0][j] = 1;
    }
    for (int i = 0; i < n; ++i) { // 初始化第0列:a[0..i]与b[0..0]的编辑距离
        if (a[i] == b[0]) minDist[i][0] = i;
        else if (i != 0) minDist[i][0] = minDist[i-1][0]+1;
        else minDist[i][0] = 1;
    }
    for (int i = 1; i < n; ++i) { // 按行填表
        for (int j = 1; j < m; ++j) {
            if (a[i] == b[j]) minDist[i][j] = min(
                    minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]);
            else minDist[i][j] = min(
                    minDist[i-1][j]+1, minDist[i][j-1]+1, minDist[i-1][j-1]+1);
        }
    }
    return minDist[n-1][m-1];
}
private int min(int x, int y, int z) {
    int minv = Integer.MAX_VALUE;
    if (x < minv) minv = x;
    if (y < minv) minv = y;
    if (z < minv) minv = z;
    return minv;
}

最长公共子串

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
ini复制代码package algorithm.edit_distance;

/**
 * @author EnochStar
 * @title: MaxLongSonString
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/18 11:22
 */
public class MaxLongSonString {
    public int lcs(char[] a, int n, char[] b, int m) {
        int[][] maxlcs = new int[n][m];
        for (int j = 0; j < m; ++j) {//初始化第0行：a[0..0]与b[0..j]的maxlcs
            if (a[0] == b[j]) maxlcs[0][j] = 1;
            else if (j != 0) maxlcs[0][j] = maxlcs[0][j-1];
            else maxlcs[0][j] = 0;
        }
        for (int i = 0; i < n; ++i) {//初始化第0列：a[0..i]与b[0..0]的maxlcs
            if (a[i] == b[0]) maxlcs[i][0] = 1;
            else if (i != 0) maxlcs[i][0] = maxlcs[i-1][0];
            else maxlcs[i][0] = 0;
        }
        for (int i = 1; i < n; ++i) { // 填表
            for (int j = 1; j < m; ++j) {
                if (a[i] == b[j]) maxlcs[i][j] = max(
                        maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]+1);
                else maxlcs[i][j] = max(
                        maxlcs[i-1][j], maxlcs[i][j-1], maxlcs[i-1][j-1]);
            }
        }
        return maxlcs[n-1][m-1];
    }
    private int max(int x, int y, int z) {
        int maxv = Integer.MIN_VALUE;
        if (x > maxv) maxv = x;
        if (y > maxv) maxv = y;
        if (z > maxv) maxv = z;
        return maxv;
    }
}

优化纠错功能

针对纠错效果不好的问题，我们有很多种优化思路，我这里介绍几种。

  • 我们并不仅仅取出编辑距离最小的那个单词，而是取出编辑距离最小的TOP 10，然后根据其他参数，决策选择哪个单词作为拼写纠错单词。
  • 比如使用搜索热门程度来决定哪个单词作为拼写纠错单词。 我们还可以用多种编辑距离计算方法，比如今天讲到的两种，然后分别编辑距离最小的TOP 10，然后求交集，用交集的结果，再继续优化处理。
  • 我们还可以通过统计用户的搜索日志，得到最常被拼错的单词列表，以及对应的拼写正确的单词。搜索引擎在拼写纠错的时候，首先在这个最长被拼错单词列表中查找。如果一旦找到，直接返回对应的正确的单词。 这样纠错的效果非常好。
  • 我们还有更加高级一点的做法，引入个性化因素。针对每个用户，维护这个用户特有的搜索喜好，也就是常用的搜索关键词。当用户输入错误的单词的时候，我们首先在这个用户常用的搜索关键词中，计算编辑距 离，查找编辑距离最小的单词。
    针对纠错性能方面，我们也有相应的优化方式。我讲两种分治的优化思路。
  • 如果纠错功能的TPS不高，我们可以部署多台机器，每台机器运行一个独立的纠错功能。当有一个纠错请求的时候，我们通过负载均衡，分配到其中一台机器，来计算编辑距离，得到纠错单词。
  • 如果纠错系统的响应时间太长，也就是，每个纠错请求处理时间过长，我们可以将纠错的词库，分割到很多台机器。当有一个纠错请求的时候，我们就将这个拼写错误的单词，同时发送到这多台机器，让多台机器并 行处理，分别得到编辑距离最小的单词，然后再比对合并，最终决定出一个最优的纠错单词.

最短距离

迪杰斯特拉算法

单源最短路径（一个顶点到另一个顶点） 时间复杂度O（ElogV）

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
ini复制代码package algorithm.shortest_road;

import java.util.LinkedList;
import java.util.Objects;
import java.util.PriorityQueue;

/**
 * @author EnochStar
 * @title: Graph
 * @projectName basic_use
 * @description:
 * v表示顶点数
 * adj表示第i个顶点的出度即两个顶点间的权值
 * Edge存储某一点到另一点及两点的权值
 * Vertex存储从最起始点，到某一点的权值
 * @date 2021/11/19 15:07
 */
public class Graph {
    private int v;
    private LinkedList<Edge> adj[];

    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0;i < v;i++) {
            adj[i] = new LinkedList<Edge>();
        }
    }
    public void addEdge(int s,int e,int c) {
        adj[s].add(new Edge(s,e,c));
    }
    private class Edge{
        private int begin;
        private int end;
        private int count;

        public Edge(int begin, int end, int count) {
            this.begin = begin;
            this.end = end;
            this.count = count;
        }
    }
    private class Vertex implements Comparable<Vertex> {
        private int did;
        private int dist;

        public Vertex(int did, int dist) {
            this.did = did;
            this.dist = dist;
        }

        @Override
        public int compareTo(Vertex o) {
            if (o.dist > this.dist) {
                return -1;
            }else{
                return 1;
            }
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vertex vertex = (Vertex) o;
            return did == vertex.did;
        }

        @Override
        public int hashCode() {
            return Objects.hash(did);
        }
    }

    /**
     * @param s s 起点
     * @param t t 终点
     *        isInQueue 用于判断某一点是否处于队列中，
     *        preRoad 用于输出两点间最短路径
     *        vertices 记录最值
     */
    public void disktra(int s,int t) {
        boolean[] isInQueue = new boolean[v];
        int[] preRoad = new int[v];
        Vertex[] vertices = new Vertex[v];
        PriorityQueue<Vertex> priorityQueue = new PriorityQueue<>();
        for (int i = 0;i < v;i++) {
            vertices[i] = new Vertex(i,Integer.MAX_VALUE);
        }
        vertices[s].dist = 0;
        isInQueue[s] = true;
        priorityQueue.add(vertices[s]);
        while (!priorityQueue.isEmpty()) {
            Vertex tmp = priorityQueue.poll();
            if (tmp.did == t) {
                break;
            }
            for (int i = 0;i < adj[tmp.did].size();i++) {
                Edge edge = adj[tmp.did].get(i);
                Vertex next = vertices[edge.end];
                if (tmp.dist + edge.count < next.dist) {
                    next.dist = tmp.dist + edge.count;
                    preRoad[next.did] = tmp.did;
                    if (!isInQueue[next.did]) {
                        isInQueue[next.did] = true;
                        priorityQueue.add(next);
                        // 更新优先队列
                    }else{
                        priorityQueue.remove(next);
                        priorityQueue.add(next);
                    }
                }
            }
        }
        System.out.println("输出路径");
        System.out.print(s);
        printRoad(s,t,preRoad);
    }
    public void printRoad(int s,int t,int[] preRoad) {
        if (s == t) return;
        printRoad(s,preRoad[t],preRoad);
        System.out.print("-->" + t);
    }

    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(2,3,1);
        graph.addEdge(3,4,1);
        graph.disktra(2,4);
    }
}

弗洛伊德算法

所有点到所有点 最短路径的算法。时间复杂度O（n^3）

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
ini复制代码package algorithm.shortest_road;

/**
 * @author EnochStar
 * @title: Floyd
 * @projectName basic_use
 * @description: TODO
 * @date 2021/11/19 19:06
 */
public class Floyd {
    private static int[][] distance;
    private static int[][] path;

    public static void floyd(int[][] graph) {
        distance = graph;
        int n = graph.length;
        path = new int[n][n];
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < n;j++) {
                path[i][j] = j;
            }
        }
        // 中转点
        for (int i = 0;i < n;i++) {
            // 入度
            for (int j = 0;j < n;j++) {
                // 出度
                for (int k = 0;k < distance[j].length;k++) {
                    if (distance[j][i] != -1 && distance[i][k] != -1) {
                        int newDistance = distance[j][i] + distance[i][k];
                        if (newDistance < distance[j][k] || distance[j][k] == -1) {
                            distance[j][k] = newDistance;
                            path[j][k] = i;
                        }
                    }
                }
            }
        }
    }
    public static void main(String[] args) {
        char[] vertices = new char[]{'A', 'B', 'C', 'D'};
        int[][] graph = new int[][]{
                {0, 2, -1, 6}
                , {2, 0, 3, 2}
                , {-1, 3, 0, 2}
                , {6, 2, 2, 0}};
        floyd(graph);
        System.out.println("====distance====");
        for (int[] ints : distance) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
        System.out.println("====path====");
        for (int[] ints : path) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }
}

区别： Dijkstra 算法：每次从「未求出最短路径」的点中 取出 最短路径的点，并通过这个点为「中转站」刷新剩下「未求出最短路径」的距离。

Dijkstra 的算法在图中的效果像是：以起点为中心像是一个涟漪一样在水面上铺开。

Floyd 算法在图中的效果像是：一个一个多点的小涟漪，最后小涟漪铺满整个水面。

练习：
网络延迟时间 - 网络延迟时间 - 力扣（LeetCode） (leetcode-cn.com)

位图

思考：如何实现网页爬虫的url去重问题？

对于这个问题，要实现的功能是，添加一个url以及查询一个url，同时要求复杂度尽可能的高。显然，散列表是率先想到的方法，无论添加还是查找都只需要O（1）的时间复杂度，然而对于查找操作，由于是url所以这会涉及到字符串匹配的问题，同时如果爬取的url很多，那么也会消耗极大的内存空间。对于后者，可以采用分治的思路，即利用哈希算法，多台机器存储url。

那么，如何在提高时间复杂度的前提下，尽可能使内存占用率小呢？

可以使用位图来解决这个方法，假设有一千万个数，每个数的范围是1到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
java复制代码package algorithm.bit;

/**
 * @author EnochStar
 * @title: BitMap
 * @projectName basic_use
 * @description: nbits表示数据的最大范围
 * @date 2021/11/22 10:53
 */
public class BitMap {
    private char[] bits;
    private int nbits;

    public BitMap(int nbits) {
        this.nbits = nbits;
        bits = new char[nbits / 8 + 1];
    }

    public void set(int num) {
        if (num > nbits) return;
        int byteIdx = num / 8;
        int bitIdx = num % 8;
        bits[byteIdx] |= (1 << bitIdx);
    }

    public boolean get(int num) {
        int byteIdx = num / 8;
        int bitIdx = num % 8;
        return (bits[byteIdx] & (1 << bitIdx)) != 0;
    }
}

如果是动态的添加数据，即未知数据量的大小，以及数据所在的范围呢？

那这时候就需要进行动态扩容，可以先初始化四个long类型数组，第一个数组不放数据，剩下的三个数组的操作和位图一致，假设添加的数字为67540，则对应的数组下标应该为1055，对应的位应该为20，此时就需要对原数组扩容，下标为4的数组和下标为0的数组一样仍然不存储数据，此时下标为4的值转化为2进制
110000011100，其中前32位表示后续连续存储数据的数组，后32位表示跨越的数组，此时数组中下标为5的位置就存储67540的值。当判断数据是否存在时，则可以通过解析存储跨度信息的下标，即从0开始解析，然后依次判断。

此处参考：漫画：Bitmap算法 整合版 (qq.com)

当允许存在精确误差时，可以使用布隆过滤器，布隆过滤器是基于位图实现的，其目的是在丢失部分精确性的前提下进一步节省内存空间。实现原理是，对于一个数字，通过多个哈希算法求得多个下标，并设置为1，当判断是否存在时，同样也是用多个哈希算法求得对应下标，判断是否为1.其产生误差的原因如图：

image.png

因此在允许误差的情况下，可以使用布隆过滤器对网页爬虫的url去重。

思考

假设我们有1亿个整数，数据范围是从1到10亿，如何快速并且省内存地给这1亿个数据从小到大排序？

答：可以使用位图，将数字添加到位图中，依次读取值为1的下标。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%