精华内容
下载资源
问答
  • 深入理解Java对象的创建过程:类的初始化与实例化
    万次阅读 多人点赞
    2017-05-18 14:17:45

    摘要:

      在Java中,一个对象在可以被使用之前必须要被正确地初始化,这一点是Java规范规定的。在实例化一个对象时,JVM首先会检查相关类型是否已经加载并初始化,如果没有,则JVM立即进行加载并调用类构造器完成类的初始化。在类初始化过程中或初始化完毕后,根据具体情况才会去对类进行实例化。本文试图对JVM执行类初始化和实例化的过程做一个详细深入地介绍,以便从Java虚拟机的角度清晰解剖一个Java对象的创建过程。


    版权声明:

    本文原创作者:书呆子Rico
    作者博客地址:http://blog.csdn.net/justloveyou_/


    友情提示:

      一个Java对象的创建过程往往包括 类初始化 类实例化 两个阶段。本文的姊妹篇《 JVM类加载机制概述:加载时机与加载过程》主要介绍了类的初始化时机和初始化过程,本文在此基础上,进一步阐述了一个Java对象创建的真实过程。


    一、Java对象创建时机

      我们知道,一个对象在可以被使用之前必须要被正确地实例化。在Java代码中,有很多行为可以引起对象的创建,最为直观的一种就是使用new关键字来调用一个类的构造函数显式地创建对象,这种方式在Java规范中被称为 : 由执行类实例创建表达式而引起的对象创建。除此之外,我们还可以使用反射机制(Class类的newInstance方法、使用Constructor类的newInstance方法)、使用Clone方法、使用反序列化等方式创建对象。下面笔者分别对此进行一一介绍:


    1). 使用new关键字创建对象

      这是我们最常见的也是最简单的创建对象的方式,通过这种方式我们可以调用任意的构造函数(无参的和有参的)去创建对象。比如:

      Student student = new Student();

    2). 使用Class类的newInstance方法(反射机制)

      我们也可以通过Java的反射机制使用Class类的newInstance方法来创建对象,事实上,这个newInstance方法调用无参的构造器创建对象,比如:

      Student student2 = (Student)Class.forName("Student类全限定名").newInstance(); 
    或者:
      Student stu = Student.class.newInstance();

    3). 使用Constructor类的newInstance方法(反射机制)

      java.lang.relect.Constructor类里也有一个newInstance方法可以创建对象,该方法和Class类中的newInstance方法很像,但是相比之下,Constructor类的newInstance方法更加强大些,我们可以通过这个newInstance方法调用有参数的和私有的构造函数,比如:

    public class Student {
    
        private int id;
    
        public Student(Integer id) {
            this.id = id;
        }
    
        public static void main(String[] args) throws Exception {
    
            Constructor<Student> constructor = Student.class
                    .getConstructor(Integer.class);
            Student stu3 = constructor.newInstance(123);
        }
    }

      使用newInstance方法的这两种方式创建对象使用的就是Java的反射机制,事实上Class的newInstance方法内部调用的也是Constructor的newInstance方法。


    4). 使用Clone方法创建对象

      无论何时我们调用一个对象的clone方法,JVM都会帮我们创建一个新的、一样的对象,特别需要说明的是,用clone方法创建对象的过程中并不会调用任何构造函数。关于如何使用clone方法以及浅克隆/深克隆机制,笔者已经在博文《 Java String 综述(下篇)》做了详细的说明。简单而言,要想使用clone方法,我们就必须先实现Cloneable接口并实现其定义的clone方法,这也是原型模式的应用。比如:

    public class Student implements Cloneable{
    
        private int id;
    
        public Student(Integer id) {
            this.id = id;
        }
    
        @Override
        protected Object clone() throws CloneNotSupportedException {
            // TODO Auto-generated method stub
            return super.clone();
        }
    
        public static void main(String[] args) throws Exception {
    
            Constructor<Student> constructor = Student.class
                    .getConstructor(Integer.class);
            Student stu3 = constructor.newInstance(123);
            Student stu4 = (Student) stu3.clone();
        }
    }

    5). 使用(反)序列化机制创建对象

      当我们反序列化一个对象时,JVM会给我们创建一个单独的对象,在此过程中,JVM并不会调用任何构造函数。为了反序列化一个对象,我们需要让我们的类实现Serializable接口,比如:

    public class Student implements Cloneable, Serializable {
    
        private int id;
    
        public Student(Integer id) {
            this.id = id;
        }
    
        @Override
        public String toString() {
            return "Student [id=" + id + "]";
        }
    
        public static void main(String[] args) throws Exception {
    
            Constructor<Student> constructor = Student.class
                    .getConstructor(Integer.class);
            Student stu3 = constructor.newInstance(123);
    
            // 写对象
            ObjectOutputStream output = new ObjectOutputStream(
                    new FileOutputStream("student.bin"));
            output.writeObject(stu3);
            output.close();
    
            // 读对象
            ObjectInputStream input = new ObjectInputStream(new FileInputStream(
                    "student.bin"));
            Student stu5 = (Student) input.readObject();
            System.out.println(stu5);
        }
    }

    6). 完整实例

    public class Student implements Cloneable, Serializable {
    
        private int id;
    
        public Student() {
    
        }
    
        public Student(Integer id) {
            this.id = id;
        }
    
        @Override
        protected Object clone() throws CloneNotSupportedException {
            // TODO Auto-generated method stub
            return super.clone();
        }
    
        @Override
        public String toString() {
            return "Student [id=" + id + "]";
        }
    
        public static void main(String[] args) throws Exception {
    
            System.out.println("使用new关键字创建对象:");
            Student stu1 = new Student(123);
            System.out.println(stu1);
            System.out.println("\n---------------------------\n");
    
    
            System.out.println("使用Class类的newInstance方法创建对象:");
            Student stu2 = Student.class.newInstance();    //对应类必须具有无参构造方法,且只有这一种创建方式
            System.out.println(stu2);
            System.out.println("\n---------------------------\n");
    
            System.out.println("使用Constructor类的newInstance方法创建对象:");
            Constructor<Student> constructor = Student.class
                    .getConstructor(Integer.class);   // 调用有参构造方法
            Student stu3 = constructor.newInstance(123);   
            System.out.println(stu3);
            System.out.println("\n---------------------------\n");
    
            System.out.println("使用Clone方法创建对象:");
            Student stu4 = (Student) stu3.clone();
            System.out.println(stu4);
            System.out.println("\n---------------------------\n");
    
            System.out.println("使用(反)序列化机制创建对象:");
            // 写对象
            ObjectOutputStream output = new ObjectOutputStream(
                    new FileOutputStream("student.bin"));
            output.writeObject(stu4);
            output.close();
    
            // 读取对象
            ObjectInputStream input = new ObjectInputStream(new FileInputStream(
                    "student.bin"));
            Student stu5 = (Student) input.readObject();
            System.out.println(stu5);
    
        }
    }/* Output: 
            使用new关键字创建对象:
            Student [id=123]
    
            ---------------------------
    
            使用Class类的newInstance方法创建对象:
            Student [id=0]
    
            ---------------------------
    
            使用Constructor类的newInstance方法创建对象:
            Student [id=123]
    
            ---------------------------
    
            使用Clone方法创建对象:
            Student [id=123]
    
            ---------------------------
    
            使用(反)序列化机制创建对象:
            Student [id=123]
    *///:~

      从Java虚拟机层面看,除了使用new关键字创建对象的方式外,其他方式全部都是通过转变为invokevirtual指令直接创建对象的。


    二. Java 对象的创建过程

      当一个对象被创建时,虚拟机就会为其分配内存来存放对象自己的实例变量及其从父类继承过来的实例变量(即使这些从超类继承过来的实例变量有可能被隐藏也会被分配空间)。在为这些实例变量分配内存的同时,这些实例变量也会被赋予默认值(零值)。在内存分配完成之后,Java虚拟机就会开始对新创建的对象按照程序猿的意志进行初始化。在Java对象初始化过程中,主要涉及三种执行对象初始化的结构,分别是 实例变量初始化实例代码块初始化 以及 构造函数初始化


    1、实例变量初始化与实例代码块初始化

      我们在定义(声明)实例变量的同时,还可以直接对实例变量进行赋值或者使用实例代码块对其进行赋值。如果我们以这两种方式为实例变量进行初始化,那么它们将在构造函数执行之前完成这些初始化操作。实际上,如果我们对实例变量直接赋值或者使用实例代码块赋值,那么编译器会将其中的代码放到类的构造函数中去,并且这些代码会被放在对超类构造函数的调用语句之后(还记得吗?Java要求构造函数的第一条语句必须是超类构造函数的调用语句),构造函数本身的代码之前。例如:

    public class InstanceVariableInitializer {  
    
        private int i = 1;  
        private int j = i + 1;  
    
        public InstanceVariableInitializer(int var){
            System.out.println(i);
            System.out.println(j);
            this.i = var;
            System.out.println(i);
            System.out.println(j);
        }
    
        {               // 实例代码块
            j += 3; 
    
        }
    
        public static void main(String[] args) {
            new InstanceVariableInitializer(8);
        }
    }/* Output: 
                1
                5
                8
                5
     *///:~

      上面的例子正好印证了上面的结论。特别需要注意的是,Java是按照编程顺序来执行实例变量初始化器和实例初始化器中的代码的,并且不允许顺序靠前的实例代码块初始化在其后面定义的实例变量,比如:

    public class InstanceInitializer {  
        {  
            j = i;  
        }  
    
        private int i = 1;  
        private int j;  
    }  
    
    public class InstanceInitializer {  
        private int j = i;  
        private int i = 1;  
    }  

      上面的这些代码都是无法通过编译的,编译器会抱怨说我们使用了一个未经定义的变量。之所以要这么做是为了保证一个变量在被使用之前已经被正确地初始化。但是我们仍然有办法绕过这种检查,比如:

    public class InstanceInitializer {  
        private int j = getI();  
        private int i = 1;  
    
        public InstanceInitializer() {  
            i = 2;  
        }  
    
        private int getI() {  
            return i;  
        }  
    
        public static void main(String[] args) {  
            InstanceInitializer ii = new InstanceInitializer();  
            System.out.println(ii.j);  
        }  
    }  

      如果我们执行上面这段代码,那么会发现打印的结果是0。因此我们可以确信,变量j被赋予了i的默认值0,这一动作发生在实例变量i初始化之前和构造函数调用之前。


    2、构造函数初始化

      我们可以从上文知道,实例变量初始化与实例代码块初始化总是发生在构造函数初始化之前,那么我们下面着重看看构造函数初始化过程。众所周知,每一个Java中的对象都至少会有一个构造函数,如果我们没有显式定义构造函数,那么它将会有一个默认无参的构造函数。在编译生成的字节码中,这些构造函数会被命名成<init>()方法,参数列表与Java语言书写的构造函数的参数列表相同。

      我们知道,Java要求在实例化类之前,必须先实例化其超类,以保证所创建实例的完整性。事实上,这一点是在构造函数中保证的:Java强制要求Object对象(Object是Java的顶层对象,没有超类)之外的所有对象构造函数的第一条语句必须是超类构造函数的调用语句或者是类中定义的其他的构造函数,如果我们既没有调用其他的构造函数,也没有显式调用超类的构造函数,那么编译器会为我们自动生成一个对超类构造函数的调用,比如:

    public class ConstructorExample {  
    
    } 

      对于上面代码中定义的类,我们观察编译之后的字节码,我们会发现编译器为我们生成一个构造函数,如下,

    aload_0  
    invokespecial   #8; //Method java/lang/Object."<init>":()V  
    return  

      上面代码的第二行就是调用Object类的默认构造函数的指令。也就是说,如果我们显式调用超类的构造函数,那么该调用必须放在构造函数所有代码的最前面,也就是必须是构造函数的第一条指令。正因为如此,Java才可以使得一个对象在初始化之前其所有的超类都被初始化完成,并保证创建一个完整的对象出来。


      特别地,如果我们在一个构造函数中调用另外一个构造函数,如下所示,

    public class ConstructorExample {  
        private int i;  
    
        ConstructorExample() {  
            this(1);  
            ....  
        }  
    
        ConstructorExample(int i) {  
            ....  
            this.i = i;  
            ....  
        }  
    }  

      对于这种情况,Java只允许在ConstructorExample(int i)内调用超类的构造函数,也就是说,下面两种情形的代码编译是无法通过的:

    public class ConstructorExample {  
        private int i;  
    
        ConstructorExample() {  
            super();  
            this(1);  // Error:Constructor call must be the first statement in a constructor
            ....  
        }  
    
        ConstructorExample(int i) {  
            ....  
            this.i = i;  
            ....  
        }  
    }  

    或者,

    public class ConstructorExample {  
        private int i;  
    
        ConstructorExample() {  
            this(1);  
            super();  //Error: Constructor call must be the first statement in a constructor
            ....  
        }  
    
        ConstructorExample(int i) {  
            this.i = i;  
        }  
    }   

      Java通过对构造函数作出这种限制以便保证一个类的实例能够在被使用之前正确地初始化。


    3、 小结

      总而言之,实例化一个类的对象的过程是一个典型的递归过程,如下图所示。进一步地说,在实例化一个类的对象时,具体过程是这样的:

      在准备实例化一个类的对象前,首先准备实例化该类的父类,如果该类的父类还有父类,那么准备实例化该类的父类的父类,依次递归直到递归到Object类。此时,首先实例化Object类,再依次对以下各类进行实例化,直到完成对目标类的实例化。具体而言,在实例化每个类时,都遵循如下顺序:先依次执行实例变量初始化和实例代码块初始化,再执行构造函数初始化。也就是说,编译器会将实例变量初始化和实例代码块初始化相关代码放到类的构造函数中去,并且这些代码会被放在对超类构造函数的调用语句之后,构造函数本身的代码之前。

                 这里写图片描述

                    
      Ps: 关于递归的思想与内涵的介绍,请参见我的博文《 算法设计方法:递归的内涵与经典应用》


    4、实例变量初始化、实例代码块初始化以及构造函数初始化综合实例

      笔者在《 JVM类加载机制概述:加载时机与加载过程》一文中详细阐述了类初始化时机和初始化过程,并在文章的最后留了一个悬念给各位,这里来揭开这个悬念。建议读者先看完《 JVM类加载机制概述:加载时机与加载过程》这篇再来看这个,印象会比较深刻,如若不然,也没什么关系~~
      

    //父类
    class Foo {
        int i = 1;
    
        Foo() {
            System.out.println(i);             -----------(1)
            int x = getValue();
            System.out.println(x);             -----------(2)
        }
    
        {
            i = 2;
        }
    
        protected int getValue() {
            return i;
        }
    }
    
    //子类
    class Bar extends Foo {
        int j = 1;
    
        Bar() {
            j = 2;
        }
    
        {
            j = 3;
        }
    
        @Override
        protected int getValue() {
            return j;
        }
    }
    
    public class ConstructorExample {
        public static void main(String... args) {
            Bar bar = new Bar();
            System.out.println(bar.getValue());             -----------(3)
        }
    }/* Output: 
                2
                0
                2
     *///:~

      根据上文所述的类实例化过程,我们可以将Foo类的构造函数和Bar类的构造函数等价地分别变为如下形式:

        //Foo类构造函数的等价变换:
        Foo() {
            i = 1;
            i = 2;
            System.out.println(i);
            int x = getValue();
            System.out.println(x);
        }
        //Bar类构造函数的等价变换
        Bar() {
            Foo();
            j = 1;
            j = 3;
            j = 2
        }

      这样程序就好看多了,我们一眼就可以观察出程序的输出结果。在通过使用Bar类的构造方法new一个Bar类的实例时,首先会调用Foo类构造函数,因此(1)处输出是2,这从Foo类构造函数的等价变换中可以直接看出。(2)处输出是0,为什么呢?因为在执行Foo的构造函数的过程中,由于Bar重载了Foo中的getValue方法,所以根据Java的多态特性可以知道,其调用的getValue方法是被Bar重载的那个getValue方法。但由于这时Bar的构造函数还没有被执行,因此此时j的值还是默认值0,因此(2)处输出是0。最后,在执行(3)处的代码时,由于bar对象已经创建完成,所以此时再访问j的值时,就得到了其初始化后的值2,这一点可以从Bar类构造函数的等价变换中直接看出。


    三. 类的初始化时机与过程

      关于类的初始化时机,笔者在博文《 JVM类加载机制概述:加载时机与加载过程》已经介绍的很清楚了,此处不再赘述。简单地说,在类加载过程中,准备阶段是正式为类变量(static 成员变量)分配内存并设置类变量初始值(零值)的阶段,而初始化阶段是真正开始执行类中定义的java程序代码(字节码)并按程序猿的意图去初始化类变量的过程。更直接地说,初始化阶段就是执行类构造器<clinit>()方法的过程。<clinit>()方法是由编译器自动收集类中的所有类变量的赋值动作和静态代码块static{}中的语句合并产生的,其中编译器收集的顺序是由语句在源文件中出现的顺序所决定。

      类构造器<clinit>()与实例构造器<init>()不同,它不需要程序员进行显式调用,虚拟机会保证在子类类构造器<clinit>()执行之前,父类的类构造<clinit>()执行完毕。由于父类的构造器<clinit>()先执行,也就意味着父类中定义的静态代码块/静态变量的初始化要优先于子类的静态代码块/静态变量的初始化执行。特别地,类构造器<clinit>()对于类或者接口来说并不是必需的,如果一个类中没有静态代码块,也没有对类变量的赋值操作,那么编译器可以不为这个类生产类构造器<clinit>()。此外,在同一个类加载器下,一个类只会被初始化一次,但是一个类可以任意地实例化对象。也就是说,在一个类的生命周期中,类构造器<clinit>()最多会被虚拟机调用一次,而实例构造器<init>()则会被虚拟机调用多次,只要程序员还在创建对象。

      注意,这里所谓的实例构造器<init>()是指收集类中的所有实例变量的赋值动作、实例代码块和构造函数合并产生的,类似于上文对Foo类的构造函数和Bar类的构造函数做的等价变换。


    四. 总结

      1、一个实例变量在对象初始化的过程中会被赋值几次?

      我们知道,JVM在为一个对象分配完内存之后,会给每一个实例变量赋予默认值,这个时候实例变量被第一次赋值,这个赋值过程是没有办法避免的。如果我们在声明实例变量x的同时对其进行了赋值操作,那么这个时候,这个实例变量就被第二次赋值了。如果我们在实例代码块中,又对变量x做了初始化操作,那么这个时候,这个实例变量就被第三次赋值了。如果我们在构造函数中,也对变量x做了初始化操作,那么这个时候,变量x就被第四次赋值。也就是说,在Java的对象初始化过程中,一个实例变量最多可以被初始化4次。


      2、类的初始化过程与类的实例化过程的异同?

      类的初始化是指类加载过程中的初始化阶段对类变量按照程序猿的意图进行赋值的过程;而类的实例化是指在类完全加载到内存中后创建对象的过程。


      3、假如一个类还未加载到内存中,那么在创建一个该类的实例时,具体过程是怎样的?

      我们知道,要想创建一个类的实例,必须先将该类加载到内存并进行初始化,也就是说,类初始化操作是在类实例化操作之前进行的,但并不意味着:只有类初始化操作结束后才能进行类实例化操作。例如,笔者在博文《 JVM类加载机制概述:加载时机与加载过程》中所提到的下面这个经典案例:

    public class StaticTest {
        public static void main(String[] args) {
            staticFunction();
        }
    
        static StaticTest st = new StaticTest();
    
        static {   //静态代码块
            System.out.println("1");
        }
    
        {       // 实例代码块
            System.out.println("2");
        }
    
        StaticTest() {    // 实例构造器
            System.out.println("3");
            System.out.println("a=" + a + ",b=" + b);
        }
    
        public static void staticFunction() {   // 静态方法
            System.out.println("4");
        }
    
        int a = 110;    // 实例变量
        static int b = 112;     // 静态变量
    }/* Output: 
            2
            3
            a=110,b=0
            1
            4
     *///:~

      大家能得到正确答案吗?笔者已经在博文《 JVM类加载机制概述:加载时机与加载过程》中解释过这个问题了,此不赘述。
      
      总的来说,类实例化的一般过程是:父类的类构造器<clinit>() -> 子类的类构造器<clinit>() -> 父类的成员变量和实例代码块 -> 父类的构造函数 -> 子类的成员变量和实例代码块 -> 子类的构造函数。


    五. 更多

      更多关于类初始化时机和初始化过程的介绍,请参见我的博文《 JVM类加载机制概述:加载时机与加载过程》

      更多关于类加载器等方面的内容,包括JVM预定义的类加载器、双亲委派模型等知识点,请参见我的转载博文《深入理解Java类加载器(一):Java类加载原理解析》

      关于递归的思想与内涵的介绍,请参见我的博文《 算法设计方法:递归的内涵与经典应用》


    引用:

    Java对象初始化详解
    Java中创建对象的几种方式

    更多相关内容
  • 内存分配的基本单位为1KB,同时要求支持至少两种分配策略,并进行测试和对不同分配策略的性能展开比较评估。 最佳适应算法(Best Fit): 它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区,这种方法...
  • 超硬核!小白读了这篇文章,就能在算法圈混了

    万次阅读 多人点赞 2021-03-29 10:21:58
    这些神级算法送给你 目录 第一节 1.1bogo排序 1.2位运算 1.3打擂台 1.4morris遍历 第二节 2.1睡眠排序 2.2会死的兔子 2.3矩阵快速幂 2.4摔手机/摔鸡蛋 时空复杂度目录 二分 尝试较优的策略 ...

     作为一只超级硬核的兔子,从来不给你说废话,只有最有用的干货!这些神级算法送给你

     

    目录

    第一节

    1.1bogo排序

    1.2位运算

    1.3打擂台

     

    1.4morris遍历

    第二节

    2.1睡眠排序

    2.2会死的兔子

    2.3矩阵快速幂

    2.4摔手机/摔鸡蛋

    时空复杂度目录

    二分

    尝试较优的策略

    归纳表达式

    写出暴力递归

    改为动态规划

    压缩空间

    四边形不等式优化

    换一种思路

    最优解

    测试:

    第三节

    3.1斐波那契之美

    3.2桶排序

    3.3快速排序

    3.4BFPRT

    第四节

    4.1防止新手错误的神级代码

    4.2不用额外空间交换两个变量

    4.3八皇后问题神操作

    4.4马拉车——字符串神级算法

    4.4一、分析枚举的效率

    4.4二、初步优化

    4.4三、Manacher原理

    假设遍历到位置i,如何操作呢

    4.4四、代码及复杂度分析


    第一节

    1.1bogo排序

    Bogo排序(Bogo-sort),又被称为猴子排序,是一种恶搞排序算法。

    将元素随机打乱,然后检查其是否符合排列顺序,若否,则继续进行随机打乱,继续检查结果,直到符合排列顺序。
    Bogo排序的最坏时间复杂度为O(∞),一辈子也不能输出排序结果,平均时间复杂度为O(n·n!)。

    这让我想到了另一个理论:猴子理论,只要让一只猴子一直敲打计算机,理论上会有一天,它能敲出一本圣经出来,但是这个概率小到宇宙毁灭也很难敲出来。。

    真的不知道这个排序应该叫做天才还是垃圾哈哈哈,但是闲的没事的我就把他实现出来了。

    public class Main {
    
    	public static void main(String[] args) {
    		int[] arr = { 9,8,7,6,5,4,3,2,1};
    		System.out.println("排序次数" + bogo(arr));
    		for (int i : arr) {
    			System.out.print(i + " ");
    		}
    	}
    	
    	public static int bogo(int[] arr) {
    		int count = 0;
    		while (!isOrdered(arr)) {
    			shuffle(arr);
    			count++;
    		}
    		return count;
    	}
    
    	// 判断是否有序方法
    	public static boolean isOrdered(int[] arr) {
    		for (int i = 1; i < arr.length; i++) {
    			if (arr[i - 1] > arr[i]) {
    				return false;
    			}
    		}
    		return true;
    	}
    
    	// 随机排序方法
    	public static void shuffle(int[] arr) {
    		int temp;
    		for (int i = 0; i < arr.length; i++) {
    			int j = (int) (Math.random() * arr.length);
    			temp = arr[i];
    			arr[i] = arr[j];
    			arr[j] = temp;
    		}
    	}
    
    }
    

    9是中国最大的数字嘛,我就把数组长度设为9,结果平均排序次数要60万次,不知道我的运气怎么样哈哈,你们也试试吧?

     

    然而,有个看似笑话的方法声称可以用O(n)实现Bogo排序,依照量子理论的平行宇宙解释,使用量子随机性随机地重新排列元素,不同的可能性将在不同的宇宙中展开,总有一种可能猴子得到了正确的顺序,量子计算机找到了这个宇宙后,就开始毁灭其他排序不成功的宇宙,剩下一个观察者可以看到的正确顺序的宇宙。

    如果想要迈出这个看似荒诞,但令人无比兴奋的"高效算法"的第一步,请先证明"平行宇宙解释"的正确性。

    1.2位运算

    关于位运算有很多天秀的技巧,这里举一个例子。

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

    说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

    示例 1:

    输入: [2,2,1]输出: 1
    示例 2:

    输入: [4,1,2,1,2]输出: 4

    思路:拿map,set,都不符合要求,那怎么办呢?

    我们知道什么数字和自己异或,都等于0.

    什么数字和0异或,都等于它本身,

    异或又符合交换律

    所以全部异或一遍,答案就是那个出现一次的数字。

    class Solution {
        public int singleNumber(int[] nums) {
            int ans = 0;
            for(int i :nums)ans ^= i;
            return ans;
        }
    }

    有没有被秒了?

     

    1.3打擂台

    给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

    你可以假设数组是非空的,并且给定的数组总是存在多数元素。

    把狂野般的思绪收一收,咱们来看看最优解。

    class Solution {
        public int majorityElement(int[] nums) {
            int count = 0;//当前答案出现的次数
            Integer candidate = null;//答案
    
            for (int num : nums) {
                if (count == 0) candidate = num;
                count += (num == candidate) ? 1 : -1;
            }
    
            return candidate;
        }
    }

    我来解释一下策略:记录当前的答案candidate ,记录count。这时,我们遍历了一个新的数字,如果和candidate 一样,我们就让count+1,否则让count-1.如果count变成了0,那candidate 就下擂台,换新的擂主(数字)上,也就是说把candidate 更新成新的数字,count也更新成1.

    最后在擂台上的一定是答案。

    肯定有人怀疑这个做法的正确性吧?我就来说一下它为啥对?

    首先,我们想像一下对最终隐藏答案ans最不利的情况:每个其他数字全部都打擂这个答案ans,那ans的count最后也会剩1,不会被打下来。

    正常情况呢?其他数字还会互相打擂,这些数字如此“内耗”,又怎么能斗得过最终答案ans呢?对不对?

     

    1.4morris遍历

    通常,实现二叉树的前序(preorder)、中序(inorder)、后序(postorder)遍历有两个常用的方法:一是递归(recursive),二是使用栈实现的迭代版本(stack+iterative)。这两种方法都是O(n)的空间复杂度(递归本身占用stack空间或者用户自定义的stack),我分别给出一个例子

    递归:

    void PreorderTraversal( BinTree BT )
    {
        if(BT==NULL)return ;
        printf(" %c", BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }

    非递归:

    *p=root;
    while(p || !st.empty())
    {
        if(p)//非空
        {
            //visit(p);进行操作
            st.push(p);//入栈
            p = p->lchild;左
        } 
        else//空
        {
            p = st.top();//取出
            st.pop();
            p = p->rchild;//右
        }
    }

    为啥这个O(n)的空间就是省不掉呢?因为我们需要空间来记录之前的位置,好在遍历完了可以回到父节点。所以这个空间是必须的!如下图:

    比如我们遍历2,想遍历4,这时候我们要保证遍历完4以后,还能回到2,我们好去继续遍历5等等结点,所以必须花空间记录。

     

    但是,还就有这么一种算法,能实现空间O(1)的遍历,服不服。

    你们可能会问,你刚说的,必须有空间来记录路径,怎么又可以不用空间了呢?

    这就是morris遍历,它其实是利用了叶子节点大量的空余空间来实现的,只要把他们利用起来,我们就可以省掉额外空间啦。

    我们不说先序中序后序,先说morris遍历的原则:

    1、如果没有左孩子,继续遍历右子树,比如:

    这个2就没有左孩子,这时直接遍历右孩子即可。

    2、如果有左孩子,找到左子树最右节点。

    比如上图,6就是2的最右节点。

        1)如果最右节点的右指针为空(说明第一次遇到),把它指向当前节点,当前节点向左继续处理。

    修改后:

        2)如果最右节点的右指针不为空(说明它指向之前结点),把右指针设为空,当前节点向右继续处理。

     

    这就是morris遍历。

    请手动模拟深度至少为4的树的morris遍历来熟悉流程。

    下面给出实现:

    定义结点:

    	public static class Node {
    		public int value;
    		Node left;
    		Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}

    先序:(完全按规则写就好。)

    //打印时机(第一次遇到):发现左子树最右的孩子右指针指向空,或无左子树。
    	public static void morrisPre(Node head) {
    		if (head == null) {
    			return;
    		}
    		Node cur1 = head;
    		Node cur2 = null;
    		while (cur1 != null) {
    			cur2 = cur1.left;
    			if (cur2 != null) {
    				while (cur2.right != null && cur2.right != cur1) {
    					cur2 = cur2.right;
    				}
    				if (cur2.right == null) {
    					cur2.right = cur1;
    					System.out.print(cur1.value + " ");
    					cur1 = cur1.left;
    					continue;
    				} else {
    					cur2.right = null;
    				}
    			} else {
    				System.out.print(cur1.value + " ");
    			}
    			cur1 = cur1.right;
    		}
    		System.out.println();
    	}

    morris在发表文章时只写出了中序遍历。而先序遍历只是打印时机不同而已,所以后人改进出了先序遍历。至于后序,是通过打印所有的右边界来实现的:对每个有边界逆序,打印,再逆序回去。注意要原地逆序,否则我们morris遍历的意义也就没有了。

    完整代码: 

    public class MorrisTraversal {
    	public static void process(Node head) {
    		if(head == null) {
    			return;
    		}
    		// 1
    		//System.out.println(head.value);
    		process(head.left);
    		
    		// 2
    		//System.out.println(head.value);
    		process(head.right);
    		
    		// 3
    		//System.out.println(head.value);
    	}
    	
    	
    	public static class Node {
    		public int value;
    		Node left;
    		Node right;
    		public Node(int data) {
    			this.value = data;
    		}
    	}
    
    //打印时机:向右走之前
    	public static void morrisIn(Node head) {
    		if (head == null) {
    			return;
    		}
    		Node cur1 = head;//当前节点
    		Node cur2 = null;//最右
    		while (cur1 != null) {
    			cur2 = cur1.left;
    			//左孩子不为空
    			if (cur2 != null) {
    				while (cur2.right != null && cur2.right != cur1) {
    					cur2 = cur2.right;
    				}//找到最右
    				//右指针为空,指向cur1,cur1向左继续
    				if (cur2.right == null) {
    					cur2.right = cur1;
    					cur1 = cur1.left;
    					continue;
    				} else {
    					cur2.right = null;
    				}//右指针不为空,设为空
    			}
    			System.out.print(cur1.value + " ");
    			cur1 = cur1.right;
    		}
    		System.out.println();
    	}
    
    //打印时机(第一次遇到):发现左子树最右的孩子右指针指向空,或无左子树。
    	public static void morrisPre(Node head) {
    		if (head == null) {
    			return;
    		}
    		Node cur1 = head;
    		Node cur2 = null;
    		while (cur1 != null) {
    			cur2 = cur1.left;
    			if (cur2 != null) {
    				while (cur2.right != null && cur2.right != cur1) {
    					cur2 = cur2.right;
    				}
    				if (cur2.right == null) {
    					cur2.right = cur1;
    					System.out.print(cur1.value + " ");
    					cur1 = cur1.left;
    					continue;
    				} else {
    					cur2.right = null;
    				}
    			} else {
    				System.out.print(cur1.value + " ");
    			}
    			cur1 = cur1.right;
    		}
    		System.out.println();
    	}
    
    //逆序打印所有右边界
    	public static void morrisPos(Node head) {
    		if (head == null) {
    			return;
    		}
    		Node cur1 = head;
    		Node cur2 = null;
    		while (cur1 != null) {
    			cur2 = cur1.left;
    			if (cur2 != null) {
    				while (cur2.right != null && cur2.right != cur1) {
    					cur2 = cur2.right;
    				}
    				if (cur2.right == null) {
    					cur2.right = cur1;
    					cur1 = cur1.left;
    					continue;
    				} else {
    					cur2.right = null;
    					printEdge(cur1.left);
    				}
    			}
    			cur1 = cur1.right;
    		}
    		printEdge(head);
    		System.out.println();
    	}
    //逆序打印
    	public static void printEdge(Node head) {
    		Node tail = reverseEdge(head);
    		Node cur = tail;
    		while (cur != null) {
    			System.out.print(cur.value + " ");
    			cur = cur.right;
    		}
    		reverseEdge(tail);
    	}
    //逆序(类似链表逆序)
    	public static Node reverseEdge(Node from) {
    		Node pre = null;
    		Node next = null;
    		while (from != null) {
    			next = from.right;
    			from.right = pre;
    			pre = from;
    			from = next;
    		}
    		return pre;
    	}
    	public static void main(String[] args) {
    		Node head = new Node(4);
    		head.left = new Node(2);
    		head.right = new Node(6);
    		head.left.left = new Node(1);
    		head.left.right = new Node(3);
    		head.right.left = new Node(5);
    		head.right.right = new Node(7);
    
    		morrisIn(head);
    		morrisPre(head);
    		morrisPos(head);
    	}
    
    }

    第二节

    2.1睡眠排序

    这是那个员工写的睡眠排序,写完就被开除了哈哈哈哈。

    它的基本思想是:

    主要是根据CPU的调度算法实现的,对一组数据进行排序,不能存在负数值,这个数是多大,那么就在线程里睡眠它的10倍再加10,不是睡眠和它的数值一样大的原因是,当数值太小时,误差太大,睡眠的时间不比输出的时间少,那么就会存在不正确的输出结果。

    按道理,他的程序也没问题啊,老板为什么要开除他?应用程序中出 BUG 不是很正常的事吗?但他这种排序思维,能写出这样的隐藏 BUG 也是绝了,创造性的发明了 "休眠排序" 算法,系统里面还不知道有多少这样的坑,不开除他开除谁啊?

    如果非要说一个原因,我感觉,这哥们是故意这么写的,造成查询速度较慢,之后下个迭代优化,查询速度瞬间提上来了,这可是为公司做出大贡献了,年底了,奖励个优秀个人奖.....

     

    2.2会死的兔子

    斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。

    这个例子是:刚开始,有一只兔子,这只兔子长到两岁的时候可以生一只小兔子,以后每年都可以生一只小兔子,而且兔子不会死。求第n年有几只兔子?

    我们这么想:

    今年的总数=去年的总数+今年的新出生的兔子,

    而今年新出生的兔子=今年成熟了的兔子数量(每只成熟的兔子生一只小兔),

    那今年成熟了的兔子数量又是什么呢?其实就是前年的兔子总数,因为前年的兔子,不管几岁,到今年一定成熟,可以生新兔子了。而去年的没有成熟,不能生兔子。

    所以今年的总数=去年的总数+前年的总数。

    F(n)=F(n-1)+F(n-2)。

    这个数列就是1、1、2、3、5、8、13、21、34、……

    在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。

    解题也非常容易

    解法一:完全抄定义

    def f(n):
    	if n==1 or n==2:
       		return 1
    	return f(n-1)+f(n-2)

    分析一下,为什么说递归效率很低呢?咱们来试着运行一下就知道了:

    比如想求f(10),计算机里怎么运行的?

    https://img-blog.csdn.net/20180412131244538

    想算出f(10),就要先算出F(9),

    想算出f(9),就要先算出F(8),

    想算出f(8),就要先算出F(7),

    想算出f(7),就要先算出F(6)……

    兜了一圈,我们发现,有相当多的计算都重复了,比如红框部分:

    那如何解决这个问题呢?问题的原因就在于,我们算出来某个结果,并没有记录下来,导致了重复计算。那很容易想到如果我们把计算的结果全都保存下来,按照一定的顺序推出n项,就可以提升效率

    解法2:

    def f1(n):
        if n==1 or n==2:
            return 1
        l=[0]*n                #保存结果
        l[0],l[1]=1,1            #赋初值
        for i in range(2,n):
            l[i]=l[i-1]+l[i-2]     #直接利用之前结果
        return l[-1]

    可以看出,时间o(n),空间o(n)。

    继续思考,既然只求第n项,而斐波那契又严格依赖前两项,那我们何必记录那么多值浪费空间呢?只记录前两项就可以了。

    解法3:

    def f2(n):
        a,b=1,1
        for i in range(n-1):
            a,b=b,a+b
        return a

    但是就有这么一个问题:兔子也会死

    出生到死亡只有三年,即n年出生,n+3年死去。

    出生一年以后可以生育,也就是n+1年开始生育,一年可以生一只宝宝。

    如果你硬要推今年的总数,你会发现相当困难。

    这时我们换一个思路:

    定义f(n)为第n年新出生的动物个数,则f(n)=f(n-1)+f(n-2),前两项为1,而每年的总数也就是三项求和而已。

    每年出生的数量为1,1,2,3,5,8,13,21

    每年总数就是1,2,4,10,16,26,42

    发现依旧是前两项加起来。

    所以当我们按老思路解不出新的变形题,这时不妨换个思路,可能会有奇效,你想到了吗?

     

    2.3矩阵快速幂

    还是上面的斐波那契数列问题(兔子不会死),这种递推的题,一般无法突破O(N)时间的魔咒,但是我们可以利用矩阵快速幂的方法写出O(logN)的方法,是不是很神奇?

    	public static int[][] matrixPower(int[][] m, int p) {
    		int[][] res = new int[m.length][m[0].length];
    		for (int i = 0; i < res.length; i++) {
    			res[i][i] = 1;
    		}
    		int[][] tmp = m;
    		for (; p != 0; p >>= 1) {
    			if ((p & 1) != 0) {
    				res = muliMatrix(res, tmp);
    			}
    			tmp = muliMatrix(tmp, tmp);
    		}
    		return res;
    	}
    
    	public static int[][] muliMatrix(int[][] m1, int[][] m2) {
    		int[][] res = new int[m1.length][m2[0].length];
    		for (int i = 0; i < m1.length; i++) {
    			for (int j = 0; j < m2[0].length; j++) {
    				for (int k = 0; k < m2.length; k++) {
    					res[i][j] += m1[i][k] * m2[k][j];
    				}
    			}
    		}
    		return res;
    	}
    	public static int f3(int n) {
    		if (n < 1) {
    			return 0;
    		}
    		if (n == 1 || n == 2) {
    			return 1;
    		}
    		int[][] base = { { 1, 1 }, { 1, 0 } };
    		int[][] res = matrixPower(base, n - 2);
    		return res[0][0] + res[1][0];
    	}

    值得思考的是,当我们一项一项的一维计算到达维度极限时,提高一个维度的计算就突破了时间极限,那么是否有三维的计算的解法?

     

    2.4摔手机/摔鸡蛋

    如果对算法感兴趣的朋友,可能会知道下面这道题:

    leetcode的hard难度(我认为应该出一个顶级难度):

    你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N  共有 N 层楼的建筑。

    每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。

    你知道存在楼层 F ,满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎,从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

    每次移动,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层 X 扔下(满足 1 <= X <= N)。

    你的目标是确切地知道 F 的值是多少。

    无论 F 的初始值如何,你确定 F 的值的最小移动次数是多少?

    示例 1:

    输入:K = 1, N = 2
    输出:2
    解释:鸡蛋从 1 楼掉落。如果它碎了,我们肯定知道 F = 0 。
    否则,鸡蛋从 2 楼掉落。如果它碎了,我们肯定知道 F = 1 。
    如果它没碎,那么我们肯定知道 F = 2 。
    因此,在最坏的情况下我们需要移动 2 次以确定 F 是多少。

    蓝桥杯:

      x星球的居民脾气不太好,但好在他们生气的时候唯一的异常举动是:摔手机。
    各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试,并且评定出一个耐摔指数来,之后才允许上市流通。
            x星球有很多高耸入云的高塔,刚好可以用来做耐摔测试。塔的每一层高度都是一样的,与地球上稍有不同的是,他们的第一层不是地面,而是相当于我们的2楼。
            如果手机从第7层扔下去没摔坏,但第8层摔坏了,则手机耐摔指数=7。

    特别地,如果手机从第1层扔下去就坏了,则耐摔指数=0。如果到了塔的最高层第n层扔没摔坏,则耐摔指数=n

            为了减少测试次数,从每个厂家抽样3部手机参加测试。
            某次测试的塔高为1000层,如果我们总是采用最佳策略,在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢?
            请填写这个最多测试次数。

            注意:需要填写的是一个整数,不要填写任何多余内容

    答案19
    问法不同,但是实际上是一个问题。

    读完题后,我们追求的不是要写出得数(至少对于本博客是不够的),而是用代码实现方法,并思考是否可以优化。

    其实本题的方法是非常多种多样的。非常适合锻炼思维。

    我们把问题扩展到n个手机来思考。

    手机k个,楼n层,最终结果M次。

    时空复杂度目录

    暴力:                        O(N!)

    DP:                            O(N*N*K)  O(N*K)

    压空间:                    O(N*N*K)  O(N)

    四边形不等式优化     O(N*N)       

    换思路:                    O(K*M)

    最优:                         O(K*M)    O(N)

    文末有测试,大家可以去直观感受一下各方法运行的效率

    二分

     

    容易想到二分思路:不断二分范围,取中点,测验是否会摔坏,然后缩小一半范围,继续尝试,很显然,答案为logN(2为底)

    但是,二分得出的答案是不对的。注意:我们要保证在都手机摔完之前,能确定耐摔指数到底是多少。

    举例:

    我们在500楼摔坏了,在250楼摔,又坏了。接下来,我们只能从1楼开始一层一层试

    因为如果我们在125层摔坏了,就没有手机可以用,也就是永远都测不出来,而这是不被允许的。其实我们连测第2层都不敢测,因为在第2层摔坏了,我们就无法知道手机在第一层能否被摔坏。所以只有一部手机时,我们只敢从第一层开始摔。

     

    尝试较优的策略

     

    既然二分是不对的,我们继续分析:摔手机的最优策略到底是如何的。

    只有一部手机时,我们只敢从第一层开始摔。

    有两部手机的时候,我们就敢隔层摔了,因为一部手机坏了,我们还有另一部来继续试。

    这时就有点意思了,我们分析情况:

    情况1)假设我们第一部手机在i层摔坏了,然后最坏情况还要试多少次?这时我们还剩一部手机,所以只敢一层一层试,最坏情况要试到i-1层,共试了i次。

    情况2)假设我们第一部手机在i层试了,但是没摔坏,然后最坏情况还要试多少次?(这时发现算情况2时依旧是相似的问题,确定了可以用递归来解。)

     

    最优解(最小值)是决策后两种情况的最差情况(最大值),我们的本能感觉应该就是让最差情况好一点,让最好情况差一点,这样比较接近正确答案。比如两部手机,一百层,我们可以在50层摔,没坏,这一次就很赚,我们没摔坏手机还把范围缩小了50层。如果坏了,就比较坑了,我们要从1试到50。虽然可能缩小一半,但是最坏情况次数太多,所以肯定要从某个低于五十的层开始尝试。

    (以上几行是为了让读者理解决策,下面正文分析)

     

    归纳表达式

     

    假设我们的楼一共n层,我们的i可以取1-n任意值,有很多种可能的决策,我们的最小值设为f(n,k),n代表楼高(范围为1-100或101-200其实都一样),k代表手机数.

    我们假设的决策是在第i楼扔

    对于情况一,手机少了一部,并且我们确定了范围,一定在第i楼以下,所以手机-1,层数为i-1,这时f(n,k)=f(i-1,k-1).+1

    对于情况二,手机没少,并且我们确定了范围,一定在第i楼之上,所以手机数不变,而层数-i层,这时f(n,k)=f(n-i,k).+1

    归纳出

    f(n,k)=min(  max(f(i-1,k-1) ,f(n-i,k) ) i取1-n任意数    )+1

    简单总结:怎么确定第一个手机在哪扔?每层都试试,哪层的最坏情况(max)最好(min),就去哪层扔。

     

    写出暴力递归

    按照分析出来的表达式,我们可以写出暴力递归:

    	public static int solution1(int nLevel, int kChess) {
    		if (nLevel == 0) {
    			return 0;
    		}//范围缩小至0
    		if (kChess == 1) {
    			return nLevel;
    		}//每层依次试
    		int min = Integer.MAX_VALUE;//取不影响结果的数
    		for (int i = 1; i != nLevel + 1; i++) {
                          //尝试所有决策,取最优
    			min = Math.min(
    					min,
    					Math.max(Process1(i - 1, kChess - 1),Process1(nLevel - i, kChess)));
    		}
    		return min + 1;//别忘了加上本次
    	}

     

    改为动态规划

     

    具体思路如下

    https://blog.csdn.net/hebtu666/article/details/79912328

    	public static int solution2(int nLevel, int kChess) {
    		if (kChess == 1) {
    			return nLevel;
    		}
    		int[][] dp = new int[nLevel + 1][kChess + 1];
    		for (int i = 1; i != dp.length; i++) {
    			dp[i][1] = i;
    		}
    		for (int i = 1; i != dp.length; i++) {
    			for (int j = 2; j != dp[0].length; j++) {
    				int min = Integer.MAX_VALUE;
    				for (int k = 1; k != i + 1; k++) {
    					min = Math.min(min,
    							Math.max(dp[k - 1][j - 1], dp[i - k][j]));
    				}
    				dp[i][j] = min + 1;
    			}
    		}
    		return dp[nLevel][kChess];
    	}

     

    压缩空间

     

    我们发现,对于状态转移方程,只和上一盘排的dp表和左边的dp表有关,所以我们不需要把值全部记录,用两个长度为n的数组不断更新即可(具体对dp压缩空间的思路,也是很重要的,我在其它文章中有提过,在这里就不写了)

    	public static int solution3(int nLevel, int kChess) {
    		if (kChess == 1) {
    			return nLevel;
    		}
    		int[] preArr = new int[nLevel + 1];
    		int[] curArr = new int[nLevel + 1];
    		for (int i = 1; i != curArr.length; i++) {
    			curArr[i] = i;
    		}//初始化
    		for (int i = 1; i != kChess; i++) {
                      //先交换
    			int[] tmp = preArr;
    			preArr = curArr;
    			curArr = tmp;
                      //然后打新的一行
    			for (int j = 1; j != curArr.length; j++) {
    				int min = Integer.MAX_VALUE;
    				for (int k = 1; k != j + 1; k++) {
    					min = Math.min(min, Math.max(preArr[k - 1], curArr[j - k]));
    				}
    				curArr[j] = min + 1;
    			}
    		}
    		return curArr[curArr.length - 1];
    	}

     

    四边形不等式优化

     

    四边形不等式是一种比较常见的优化动态规划的方法

    定义:如果对于任意的a1≤a2<b1≤b2,有m[a1,b1]+m[a2,b2]≤m[a1,b2]+m[a2,b1],那么m[i,j]满足四边形不等式。

    对s[i,j-1]≤s[i,j]≤s[i+1,j]的证明:

    设mk[i,j]=m[i,k]+m[k,j],s[i,j]=d

    对于任意k<d,有mk[i,j]≥md[i,j](这里以m[i,j]=min{m[i,k]+m[k,j]}为例,max的类似),接下来只要证明mk[i+1,j]≥md[i+1,j],那么只有当s[i+1,j]≥s[i,j]时才有可能有mk[i+1,j]≥md[i+1,j]

    (mk[i+1,j]-md[i+1,j])-(mk[i,j]-md[i,j])

    =(mk[i+1,j]+md[i,j])-(md[i+1,j]+mk[i,j])

    =(m[i+1,k]+m[k,j]+m[i,d]+m[d,j])-(m[i+1,d]+m[d,j]+m[i,k]+m[k,j])

    =(m[i+1,k]+m[i,d])-(m[i+1,d]+m[i,k])

    ∵m满足四边形不等式,∴对于i<i+1≤k<d有m[i+1,k]+m[i,d]≥m[i+1,d]+m[i,k]

    ∴(mk[i+1,j]-md[i+1,j])≥(mk[i,j]-md[i,j])≥0

    ∴s[i,j]≤s[i+1,j],同理可证s[i,j-1]≤s[i,j]

    证毕

     

    通俗来说,

    优化策略1)我们在求k+1手机n层楼时,最后发现,第一个手机在m层扔导致了最优解的产生。那我们在求k个手机n层楼时,第一个手机的策略就不用尝试m层以上的楼了。

    优化策略2)我们在求k个手机n层楼时,最后发现,第一个手机在m层扔导致了最优解的产生。那我们在求k个手机n+1层楼时,就不用尝试m层以下的楼了。

    	public static int solution4(int nLevel, int kChess) {
    		if (kChess == 1) {
    			return nLevel;
    		}
    		int[][] dp = new int[nLevel + 1][kChess + 1];
    		for (int i = 1; i != dp.length; i++) {
    			dp[i][1] = i;
    		}
    		int[] cands = new int[kChess + 1];
    		for (int i = 1; i != dp[0].length; i++) {
    			dp[1][i] = 1;
    			cands[i] = 1;
    		}
    		for (int i = 2; i < nLevel + 1; i++) {
    			for (int j = kChess; j > 1; j--) {
    				int min = Integer.MAX_VALUE;
    				int minEnum = cands[j];
    				int maxEnum = j == kChess ? i / 2 + 1 : cands[j + 1];
                                  //优化策略
    				for (int k = minEnum; k < maxEnum + 1; k++) {
    					int cur = Math.max(dp[k - 1][j - 1], dp[i - k][j]);
    					if (cur <= min) {
    						min = cur;
    						cands[j] = k;//最优解记录层数
    					}
    				}
    				dp[i][j] = min + 1;
    			}
    		}
    		return dp[nLevel][kChess];
    	}

    注:对于四边形不等式的题目,比赛时不需要严格证明

    通常的做法是打表出来之后找规律,然后大胆猜测,显然可得。(手动滑稽)

     

    换一种思路

     

    有时,最优解并不是优化来的。

    当你对着某个题冥思苦想了好久,无论如何也不知道怎么把时间优化到合理范围,可能这个题的最优解就不是这种思路,这时,试着换一种思路思考,可能会有奇效。

    (比如训练时一道贪心我死活往dp想,肝了两个小时以后,不主攻这个方向的队友三分钟就有贪心思路了,泪目,不要把简单问题复杂化

     

    我们换一种思路想问题:

    原问题:n层楼,k个手机,最多测试次数

    反过来看问题:k个手机,扔m次,最多能确定多少层楼?

    我们定义dp[i][j]:i个手机扔j次能确定的楼数。

    分析情况:依旧是看第一部手机在哪层扔的决策,同样,我们的决策首先要保证能确定从1层某一段,而不能出现次数用完了还没确定好的情况。以这个为前提,保证了每次扔的楼层都是最优的,就能求出结果。

    依旧是取最坏情况:min(情况1,情况2)

    情况1)第一个手机碎了,我们就需要用剩下的i-1个手机和j-1次测试次数往下去测,dp[i-1][j-1]。那我们能确定的层数是无限的,因为本层以上的无限层楼都不会被摔坏。dp[i-1][j-1]+无穷=无穷

    情况2)第一个手机没碎,那我们就看i个手机扔j-1次能确定的楼数(向上试)+当前楼高h

    归纳表达式,要取最差情况,所以就是只有情况2:dp[i][j]=dp[i-1][j-1]+h

    那这个h到底是什么呢?取决于我敢从哪层扔。因为次数减了一次,我们还是要考虑i个球和j-1次的最坏情况能确定多少层,我才敢在层数+1的地方扔。(这是重点)

    也就是dp[i][j-1]的向上一层:h=dp[i][j-1]+1

     

    总:min(情况1,情况2)=min(无穷,dp[i-1][j-1]+dp[i][j-1]+1)=dp[i-1][j-1]+dp[i][j-1]+1

    这是解决k个手机,扔m次,最多能确定多少层楼?

    原问题是n层楼,k个手机,最多测试次数。

    所以我们在求的过程中,何时能确定的层数大于n,输出扔的次数即可

     

    最优解

    我们知道完全用二分扔需要logN+1次,这也绝对是手机足够情况下的最优解,我们做的这么多努力都是因为手机不够摔啊。。。。所以当我们的手机足够用二分来摔时,直接求出logN+1即可。

     

    当然,我们求dp需要左边的值和左上的值:

    依旧可以压缩空间,从左往右更新,previous记录左上的值。

    求自己时也要注意记录,否则更新过后,后面的要用没更新过的值(左上方)就找不到了。

    记录之后,求出当前数值,把记录的temp值给了previous即可。

    	public static int solution5(int nLevel, int kChess) {
    		int bsTimes = log2N(nLevel) + 1;
    		if (kChess >= bsTimes) {
    			return bsTimes;
    		}
    		int[] dp = new int[kChess];
    		int res = 0;
    		while (true) {
    			res++;//压缩空间记得记录次数
    			int previous = 0;
    			for (int i = 0; i < dp.length; i++) {
    				int tmp = dp[i];
    				dp[i] = dp[i] + previous + 1;
    				previous = tmp;
    				if (dp[i] >= nLevel) {
    					return res;
    				}
    			}
    		}
    	}
    
    	public static int log2N(int n) {
    		int res = -1;
    		while (n != 0) {
    			res++;
    			n >>>= 1;
    		}
    		return res;
    	}

    测试:

    暴力:                        O(N!)

    DP:                            O(N*N*K)  O(N*K)

    压空间:                    O(N*N*K)  O(N)

    四边形不等式优化     O(N*N)       

    最优:                         O(K*M)    O(N)

    		long start = System.currentTimeMillis();
    		solution1(30, 2);
    		long end = System.currentTimeMillis();
    		System.out.println("cost time: " + (end - start) + " ms");
    		start = System.currentTimeMillis();
    		solution2(30, 2);
    		end = System.currentTimeMillis();
    		System.out.println("cost time: " + (end - start) + " ms");
    		start = System.currentTimeMillis();
    		solution3(30, 2);
    		end = System.currentTimeMillis();
    		System.out.println("cost time: " + (end - start) + " ms");
    		start = System.currentTimeMillis();
    		solution4(30, 2);
    		end = System.currentTimeMillis();
    		System.out.println("cost time: " + (end - start) + " ms");
    		start = System.currentTimeMillis();
    		solution5(30, 2);
    		end = System.currentTimeMillis();
    		System.out.println("cost time: " + (end - start) + " ms");
    /*
    结果:
    cost time: 7043 ms
    cost time: 0 ms
    cost time: 0 ms
    cost time: 0 ms
    cost time: 0 ms
    */

    暴力时间实在是太久了,只测一个30,2

     

    后四种方法测的大一些(差点把电脑测炸了,cpu100内存100):

    solution(100000, 10):

    solution2 cost time: 202525 ms
    solution3 cost time: 38131 ms
    solution4 cost time: 11295 ms
    solution5 cost time: 0 ms

     

    感受最优解的强大:

    solution5(1000 000 000,100):0 ms

    solution5(1000 000 000,10):0 ms

    最优解永远都是0 ms,我也是服了。。

     

    对比方法,在时间复杂度相同的条件下,空间复杂度一样会影响时间,因为空间太大的话,申请空间是相当浪费时间的。并且空间太大电脑会炸,所以不要认为空间不重要。

    第三节

    3.1斐波那契之美

    斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。

    这个数列就是1、1、2、3、5、8、13、21、34、……

    在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。

    但是斐波那契的知识不止于此,它还有很多惊艳到我的地方,下面我们就一起了解一下:

    1. 随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值0.6180339887..
    2. 从第二项开始,每个奇数项的平方都比前后两项之积多1,每个偶数项的平方都比前后两项之积少1。(注:奇数项和偶数项是指项数的奇偶,而并不是指数列的数字本身的奇偶,比如第五项的平方比前后两项之积多1,第四项的平方比前后两项之积少1)
    3. 斐波那契数列的第n项同时也代表了集合{1,2,…,n}中所有不包含相邻正整数的子集个数。
    4. f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1
    5. f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)
    6. f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1
    7. [f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1)
    8. f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1
    9. f(m+n)=f(m-1)·f(n-1)+f(m)·f(n) (利用这一点,可以用程序编出时间复杂度仅为O(log n)的程序。)

    真的不禁感叹:真是一个神奇的数列啊

    3.2桶排序

    我们都知道,基于比较的排序,时间的极限就是O(NlogN),从来没有哪个排序可以突破这个界限,如速度最快的快速排序,想法新颖的堆排序,分治的归并排序。

    但是,如果我们的排序根本就不基于比较,那就可能突破这个时间。

    桶排序不是基于比较的排序方法,只需对号入座。将相应的数字放进相应编号的桶即可。

    当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间o(n)

    对于海量有范围数据十分适合,比如全国高考成绩排序,公司年龄排序等等。

    l=list(map(int,input().split(" ")))
    n=max(l)-min(l)
    p=[0]*(n+1)#为了省空间
    for i in l:
        p[i-min(l)]=1#去重排序,做标记即可
    for i in range(n):
        if p[i]==1:#判断是否出现过
            print(i+min(l),end=" ")

    当然,基数排序是桶排序的改良版,也是非常好的排序方法,具体操作是:把数字的每一位都按桶排序排一次,因为桶排序是稳定的排序,因此从个位进行桶排序,然后十位进行桶排序。。。直到最高位,排序结束。

    这样极大的弱化了桶排序范围有限的弱点,比如范围1-100000需要准备100000个铜,而基数排序只要10个铜就够了(因为一共就十个数字。)。

    想出这个排序的人也是个天才啊。。。选择合适的场合使用觉得有很好的效果。

    3.3快速排序

    快速排序(Quicksort)是对冒泡排序的一种改进。

    快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
    分三区优化1:

    在使用partition-exchange排序算法时,如快速排序算法,我们会遇到一些问题,比如重复元素太多,降低了效率,在每次递归中,左边部分是空的(没有元素比关键元素小),而右边部分只能一个一个递减移动。结果导致耗费了二次方时间来排序相等元素。这时我们可以多分一个区,即,小于区,等于区,大于区。(传统快排为小于区和大于区)

    下面我们通过一个经典例题来练习这种思想。

    荷兰国旗问题

    ”荷兰国旗难题“是计算机科学中的一个程序难题,它是由Edsger Dijkstra提出的。荷兰国旗是由红、白、蓝三色组成的。

    现在有若干个红、白、蓝三种颜色的球随机排列成一条直线。现在我们的任务是把这些球按照红、白、蓝排序。

    样例输入

    3
    BBRRWBWRRR
    RRRWWRWRB
    RBRW
    样例输出

    RRRRRWWBBB
    RRRRRWWWB
    RRWB
    思路:

    现在我们的思路就是把未排序时前部和后部分别排在数组的前面和后面,那么中部自然就排好了。

    设置两个标志位head指向数组开头,tail指向数组末尾,now从头开始遍历:

    (1)如果遍历到的位置为1,那么它一定是属于前部,于是就和head交换值,然后head++,now++;

    (2)如果遍历到的位置为2,说明属于中部,now++;

    (3)如果遍历到的位置为3,说明属于后部,于是就和tail交换值,然而,如果此时交换后now指向的值属于前部,那么就执行(1),tail--;

    废话不多说,上代码。

    #include<iostream>
    #include<algorithm>
    using namespace std;
     
    const int maxn = 100 + 5;
     
    int n;
    string str;
    int main(){
        cin>>n;
        while(n--){
            cin>>str;
            int len=str.size();
            int now=0,ans=0;
            int head=0,tail=len-1;
            while(now<=tail){
                if(str[now]=='R'){
                    swap(str[head],str[now]);
                    head++;
                    now++;
                }
                else if(str[now]=='W'){
                    now++;
                }
                else{
                    swap(str[now],str[tail]);
                    tail--;
                }
            }
            cout<<str<<endl;
        }return 0;
    }

    快排分三区以后降低了递归规模,避免了最差情况,性能得到改进。
    但是还是存在退化情况:

    随机化快排优化2:
    快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。比如1 2 3 4 5,每次取第一个元素,就退化为了O(N^2)。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。

    这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。
     

    def gg(a,b):
        global l
        if a>=b:#注意停止条件,我以前没加>卡了半小时
            return
        x,y=a,b
        import random#为了避免遇到基本有序序列退化,随机选点
        g=random.randint(a,b)
        l[g],l[y]=l[y],l[g]#交换选中元素和末尾元素
        while a<b:
            if l[a]>l[y]:#比目标元素大
                l[a],l[b-1]=l[b-1],l[a]#交换
                b=b-1#大于区扩大
                #注意:换过以后a不要加,因为新换过来的元素并没有判断过
            else:a=a+1#小于区扩大
        l[y],l[a]=l[a],l[y]#这时a=b
        #现在解释a和b:a的意义是小于区下一个元素
        #b是大于区的第一个元素
        gg(x,a-1)#左右分别递归
        gg(a+1,y)
     
    l=list(map(int,input().split(" ")))
    gg(0,len(l)-1)
    print(l)

    3.4BFPRT

    我们以前写过快排的改进求前k大或前k小,但是快排不可避免地存在退化问题,即使我们用了随机数等优化,最差情况不可避免的退化到了O(N^2),而BFPRT就解决了这个问题,主要的思想精华就是怎么选取划分值。

    我们知道,经典快排是选第一个数进行划分。而改进快排是随机选取一个数进行划分,从概率上避免了基本有序情况的退化。而BFPRT算法选划分值的规则比较特殊,保证了递归最小的缩减规模也会比较大,而不是每次缩小一个数。

    这个划分值如何划分就是重点。

    如何让选取的点无论如何都不会太差。

    1、将n个元素划分为n/5个组,每组5个元素
    2、对每组排序,找到n/5个组中每一组的中位数; 
    3、对于找到的所有中位数,调用BFPRT算法求出它们的中位数,作为划分值。

    下面说明为什么这样找划分值。

    我们先把数每五个分为一组。

    同一列为一组。

    排序之后,第三行就是各组的中位数。

    我们把第三行的数构成一个数列,递归找,找到中位数。

    这个黑色框为什么找的很好。

    因为他一定比A3、B3大,而A3、B3、C3又在自己的组内比两个数要大。

    我们看最差情况:求算其它的数都比c3大,我们也能在25个数中缩小九个数的规模。大约3/10.

    我们就做到了最差情况固定递减规模,而不是可能缩小的很少。

    下面代码实现:

    public class BFPRT {
    //前k小
    	public static int[] getMinKNumsByBFPRT(int[] arr, int k) {
    		if (k < 1 || k > arr.length) {
    			return arr;
    		}
    		int minKth = getMinKthByBFPRT(arr, k);
    		int[] res = new int[k];
    		int index = 0;
    		for (int i = 0; i != arr.length; i++) {
    			if (arr[i] < minKth) {
    				res[index++] = arr[i];
    			}
    		}
    		for (; index != res.length; index++) {
    			res[index] = minKth;
    		}
    		return res;
    	}
    //第k小
    	public static int getMinKthByBFPRT(int[] arr, int K) {
    		int[] copyArr = copyArray(arr);
    		return select(copyArr, 0, copyArr.length - 1, K - 1);
    	}
    
    	public static int[] copyArray(int[] arr) {
    		int[] res = new int[arr.length];
    		for (int i = 0; i != res.length; i++) {
    			res[i] = arr[i];
    		}
    		return res;
    	}
    //给定一个数组和范围,求第i小的数
    	public static int select(int[] arr, int begin, int end, int i) {
    		if (begin == end) {
    			return arr[begin];
    		}
    		int pivot = medianOfMedians(arr, begin, end);//划分值
    		int[] pivotRange = partition(arr, begin, end, pivot);
    		if (i >= pivotRange[0] && i <= pivotRange[1]) {
    			return arr[i];
    		} else if (i < pivotRange[0]) {
    			return select(arr, begin, pivotRange[0] - 1, i);
    		} else {
    			return select(arr, pivotRange[1] + 1, end, i);
    		}
    	}
    //在begin end范围内进行操作
    	public static int medianOfMedians(int[] arr, int begin, int end) {
    		int num = end - begin + 1;
    		int offset = num % 5 == 0 ? 0 : 1;//最后一组的情况
    		int[] mArr = new int[num / 5 + offset];//中位数组成的数组
    		for (int i = 0; i < mArr.length; i++) {
    			int beginI = begin + i * 5;
    			int endI = beginI + 4;
    			mArr[i] = getMedian(arr, beginI, Math.min(end, endI));
    		}
    		return select(mArr, 0, mArr.length - 1, mArr.length / 2);
            //只不过i等于长度一半,用来求中位数
    	}
    //经典partition过程
    	public static int[] partition(int[] arr, int begin, int end, int pivotValue) {
    		int small = begin - 1;
    		int cur = begin;
    		int big = end + 1;
    		while (cur != big) {
    			if (arr[cur] < pivotValue) {
    				swap(arr, ++small, cur++);
    			} else if (arr[cur] > pivotValue) {
    				swap(arr, cur, --big);
    			} else {
    				cur++;
    			}
    		}
    		int[] range = new int[2];
    		range[0] = small + 1;
    		range[1] = big - 1;
    		return range;
    	}
    //五个数排序,返回中位数
    	public static int getMedian(int[] arr, int begin, int end) {
    		insertionSort(arr, begin, end);
    		int sum = end + begin;
    		int mid = (sum / 2) + (sum % 2);
    		return arr[mid];
    	}
    //手写排序
    	public static void insertionSort(int[] arr, int begin, int end) {
    		for (int i = begin + 1; i != end + 1; i++) {
    			for (int j = i; j != begin; j--) {
    				if (arr[j - 1] > arr[j]) {
    					swap(arr, j - 1, j);
    				} else {
    					break;
    				}
    			}
    		}
    	}
    //交换值
    	public static void swap(int[] arr, int index1, int index2) {
    		int tmp = arr[index1];
    		arr[index1] = arr[index2];
    		arr[index2] = tmp;
    	}
    //打印
    	public static void printArray(int[] arr) {
    		for (int i = 0; i != arr.length; i++) {
    			System.out.print(arr[i] + " ");
    		}
    		System.out.println();
    	}
    
    	public static void main(String[] args) {
    		int[] arr = { 6, 9, 1, 3, 1, 2, 2, 5, 6, 1, 3, 5, 9, 7, 2, 5, 6, 1, 9 };
    		// sorted : { 1, 1, 1, 1, 2, 2, 2, 3, 3, 5, 5, 5, 6, 6, 6, 7, 9, 9, 9 }
    		printArray(getMinKNumsByBFPRT(arr, 10));
    
    	}
    }

    这个办法解决了最差的退化情况,在一大堆数中求其前k大或前k小的问题,简称TOP-K问题。目前解决TOP-K问题最有效的算法即是BFPRT算法,其又称为中位数的中位数算法,该算法由Blum、Floyd、Pratt、Rivest、Tarjan提出 ,让我们永远记住这群伟大的人。

    第四节

    4.1防止新手错误的神级代码

    #define ture true

    #define flase false

    #difine viod void

    #define mian main

    #define ; ;

    以后有新手问题就把这几行代码给他就好啦。

     

    4.2不用额外空间交换两个变量

    a = 5
    b = 8

    #计算a和b两个点到原点的距离之和,并且赋值给a
    a = a+b

    #使用距离之和减去b到原点的距离
    #a-b 其实就是a的原值(a到原点的距离),现在赋值给了b
    b = a-b

    #再使用距离之和减去b (a到原点的距离)
    #得到的是b的原值(b到原点的距离),现在赋值给了a
    a = a-b

    4.3八皇后问题神操作

    是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2。而且仅当 n2 ≥ 1 或 n1 ≥ 4 时问题有解。

    皇后问题是非常著名的问题,作为一个棋盘类问题,毫无疑问,用暴力搜索的方法来做是一定可以得到正确答案的,但在有限的运行时间内,我们很难写出速度可以忍受的搜索,部分棋盘问题的最优解不是搜索,而是动态规划,某些棋盘问题也很适合作为状态压缩思想的解释例题。

    进一步说,皇后问题可以用人工智能相关算法和遗传算法求解,可以用多线程技术缩短运行时间。本文不做讨论。

    (本文不展开讲状态压缩,以后再说)

    一般思路:

    N*N的二维数组,在每一个位置进行尝试,在当前位置上判断是否满足放置皇后的条件(这一点的行、列、对角线上,没有皇后)。

    优化1:

    既然知道多个皇后不能在同一行,我们何必要在同一行的不同位置放多个来尝试呢?

    我们生成一维数组record,record[i]表示第i行的皇后放在了第几列。对于每一行,确定当前record值即可,因为每行只能且必须放一个皇后,放了一个就无需继续尝试。那么对于当前的record[i],查看record[0...i-1]的值,是否有j = record[k](同列)、|record[k] - j| = | k-i |(同一斜线)的情况。由于我们的策略,无需检查行(每行只放一个)。

    public class NQueens {
    	public static int num1(int n) {
    		if (n < 1) {
    			return 0;
    		}
    		int[] record = new int[n];
    		return process1(0, record, n);
    	}
    	public static int process1(int i, int[] record, int n) {
    		if (i == n) {
    			return 1;
    		}
    		int res = 0;
    		for (int j = 0; j < n; j++) {
    			if (isValid(record, i, j)) {
    				record[i] = j;
    				res += process1(i + 1, record, n);
    			}
    		}//对于当前行,依次尝试每列
    		return res;
    	}
    //判断当前位置是否可以放置
    	public static boolean isValid(int[] record, int i, int j) {
    		for (int k = 0; k < i; k++) {
    			if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
    				return false;
    			}
    		}
    		return true;
    	}
    	public static void main(String[] args) {
    		int n = 8;
    		System.out.println(num1(n));
    	}
    }
    

    位运算优化2:

    分析:棋子对后续过程的影响范围:本行、本列、左右斜线。

    黑色棋子影响区域为红色

    1)本行影响不提,根据优化一已经避免

    2)本列影响,一直影响D列,直到第一行在D放棋子的所有情况结束。

    3)左斜线:每向下一行,实际上对当前行的影响区域就向左移动

    比如:

    尝试第二行时,黑色棋子影响的是我们的第三列;

    尝试第三行时,黑色棋子影响的是我们的第二列;

    尝试第四行时,黑色棋子影响的是我们的第一列;

    尝试第五行及以后几行,黑色棋子对我们并无影响。

    4)右斜线则相反:

    随着行序号增加,影响的列序号也增加,直到影响的列序号大于8就不再影响。

     

    我们对于之前棋子影响的区域,可以用二进制数字来表示,比如:

    每一位,用01代表是否影响。

    比如上图,对于第一行,就是00010000

    尝试第二行时,数字变为00100000

    第三行:01000000

    第四行:10000000

     

    对于右斜线的数字,同理:

    第一行00010000,之后向右移:00001000,00000100,00000010,00000001,直到全0不影响。

     

    同理,我们对于多行数据,也同样可以记录了

    比如在第一行我们放在了第四列:

    第二行放在了G列,这时左斜线记录为00100000(第一个棋子的影响)+00000010(当前棋子的影响)=00100010。

    到第三行数字继续左移:01000100,然后继续加上我们的选择,如此反复。

     

    这样,我们对于当前位置的判断,其实可以通过左斜线变量、右斜线变量、列变量,按位或运算求出(每一位中,三个数有一个是1就不能再放)。

    具体看代码:

    注:怎么排版就炸了呢。。。贴一张图吧

    public class NQueens {
    	public static int num2(int n) {
    		// 因为本方法中位运算的载体是int型变量,所以该方法只能算1~32皇后问题
    		// 如果想计算更多的皇后问题,需使用包含更多位的变量
    		if (n < 1 || n > 32) {
    			return 0;
    		}
    		int upperLim = n == 32 ? -1 : (1 << n) - 1;
            //upperLim的作用为棋盘大小,比如8皇后为00000000 00000000 00000000 11111111
            //32皇后为11111111 11111111 11111111 11111111
    		return process2(upperLim, 0, 0, 0);
    	}
    
    	public static int process2(int upperLim, int colLim, int leftDiaLim,
    			int rightDiaLim) {
    		if (colLim == upperLim) {
    			return 1;
    		}
    		int pos = 0;            //pos:所有的合法位置
    		int mostRightOne = 0;   //所有合法位置的最右位置
    
            //所有记录按位或之后取反,并与全1按位与,得出所有合法位置
    		pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
    		int res = 0;//计数
    		while (pos != 0) {
    			mostRightOne = pos & (~pos + 1);//取最右的合法位置
    			pos = pos - mostRightOne;       //去掉本位置并尝试
    			res += process2(
                         upperLim,                             //全局
                         colLim | mostRightOne,                //列记录
                         //之前列+本位置
    					(leftDiaLim | mostRightOne) << 1,      //左斜线记录
                         //(左斜线变量+本位置)左移             
    					(rightDiaLim | mostRightOne) >>> 1);   //右斜线记录
                         //(右斜线变量+本位置)右移(高位补零)
    		}
    		return res;
    	}
    
    	public static void main(String[] args) {
    		int n = 8;
    		System.out.println(num2(n));
    	}
    }
    

    完整测试代码:

    32皇后:结果/时间

    暴力搜:时间就太长了,懒得测。。。

    public class NQueens {
    
    	public static int num1(int n) {
    		if (n < 1) {
    			return 0;
    		}
    		int[] record = new int[n];
    		return process1(0, record, n);
    	}
    
    	public static int process1(int i, int[] record, int n) {
    		if (i == n) {
    			return 1;
    		}
    		int res = 0;
    		for (int j = 0; j < n; j++) {
    			if (isValid(record, i, j)) {
    				record[i] = j;
    				res += process1(i + 1, record, n);
    			}
    		}
    		return res;
    	}
    
    	public static boolean isValid(int[] record, int i, int j) {
    		for (int k = 0; k < i; k++) {
    			if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
    				return false;
    			}
    		}
    		return true;
    	}
    
    	public static int num2(int n) {
    		if (n < 1 || n > 32) {
    			return 0;
    		}
    		int upperLim = n == 32 ? -1 : (1 << n) - 1;
    		return process2(upperLim, 0, 0, 0);
    	}
    
    	public static int process2(int upperLim, int colLim, int leftDiaLim,
    			int rightDiaLim) {
    		if (colLim == upperLim) {
    			return 1;
    		}
    		int pos = 0;
    		int mostRightOne = 0;
    		pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
    		int res = 0;
    		while (pos != 0) {
    			mostRightOne = pos & (~pos + 1);
    			pos = pos - mostRightOne;
    			res += process2(upperLim, colLim | mostRightOne,
    					(leftDiaLim | mostRightOne) << 1,
    					(rightDiaLim | mostRightOne) >>> 1);
    		}
    		return res;
    	}
    
    	public static void main(String[] args) {
    		int n = 32;
    
    		long start = System.currentTimeMillis();
    		System.out.println(num2(n));
    		long end = System.currentTimeMillis();
    		System.out.println("cost time: " + (end - start) + "ms");
    
    		start = System.currentTimeMillis();
    		System.out.println(num1(n));
    		end = System.currentTimeMillis();
    		System.out.println("cost time: " + (end - start) + "ms");
    	}
    }
    

    4.4马拉车——字符串神级算法

    Manacher's Algorithm 马拉车算法操作及原理 

    package advanced_001;
    
    public class Code_Manacher {
    
    	public static char[] manacherString(String str) {
    		char[] charArr = str.toCharArray();
    		char[] res = new char[str.length() * 2 + 1];
    		int index = 0;
    		for (int i = 0; i != res.length; i++) {
    			res[i] = (i & 1) == 0 ? '#' : charArr[index++];
    		}
    		return res;
    	}
    
    	public static int maxLcpsLength(String str) {
    		if (str == null || str.length() == 0) {
    			return 0;
    		}
    		char[] charArr = manacherString(str);
    		int[] pArr = new int[charArr.length];
    		int C = -1;
    		int R = -1;
    		int max = Integer.MIN_VALUE;
    		for (int i = 0; i != charArr.length; i++) {
    			pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
    			while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
    				if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
    					pArr[i]++;
    				else {
    					break;
    				}
    			}
    			if (i + pArr[i] > R) {
    				R = i + pArr[i];
    				C = i;
    			}
    			max = Math.max(max, pArr[i]);
    		}
    		return max - 1;
    	}
    
    	public static void main(String[] args) {
    		String str1 = "abc1234321ab";
    		System.out.println(maxLcpsLength(str1));
    	}
    
    }
    

     问题:查找一个字符串的  最长回文子串

    首先叙述什么是回文子串:回文:就是对称的字符串,或者说是正反一样的

    小问题一:请问,子串和子序列一样么?请思考一下再往下看

     当然,不一样。子序列可以不连续,子串必须连续。

    举个例子,”123”的子串包括1,2,3,12,23,123(一个字符串本身是自己的最长子串),而它的子序列是任意选出元素组成,他的子序列有1,2,3,12,13,23,123,””,空其实也算,但是本文主要是想叙述回文,没意义。

    小问题二:长度为n的字符串有多少个子串?多少个子序列?

     子序列,每个元素都可以选或者不选,所以有2的n次方个子序列(包括空)

    子串:以一位置开头,有n个子串,以二位置开头,有n-1个子串,以此类推,我们发现,这是一个等差数列,而等差序列求和,有n*(n+1)/2个子串(不包括空)。

    (这里有一个思想需要注意,遇到等差数列求和,基本都是o(n^2)级别的)

    4.4一、分析枚举的效率

    好,我们来分析一下暴力枚举的时间复杂度,上文已经提到过,一个字符串的所有子串,数量是o(n^2)级别,所以光是枚举出所有情况时间就是o(n^2),每一种情况,你要判断他是不是回文的话,还需要o(n),情况数和每种情况的时间,应该乘起来,也就是说,枚举时间要o(n^3),效率太低。

    4.4二、初步优化

    思路:我们知道,回文全是对称的,每个回文串都会有自己的对称轴,而两边都对称。我们如果从对称轴开始, 向两边阔,如果总相等,就是回文,扩到两边不相等的时候,以这个对称轴向两边扩的最长回文串就找到了。

    举例:1 2 1 2 1 2 1 1 1

    我们用每一个元素作为对称轴,向两边扩

    0位置,左边没东西,只有自己;

    1位置,判断左边右边是否相等,1=1所以接着扩,然后左边没了,所以以1位置为对称轴的最长回文长度就是3;

    2位置,左右都是2,相等,继续,左右都是1,继续,左边没了,所以最长为5

    3位置,左右开始扩,1=1,2=2,1=1,左边没了,所以长度是7

    如此把每个对称轴扩一遍,最长的就是答案,对么?

    你要是点头了。。。自己扇自己两下。

    还有偶回文呢,,比如1221,123321.这是什么情况呢?这个对称轴不是一个具体的数,因为人家是偶回文。

    问题三:怎么用对称轴向两边扩的方法找到偶回文?(容易操作的)

    我们可以在元素间加上一些符号,比如/1/2/1/2/1/2/1/1/1/,这样我们再以每个元素为对称轴扩就没问题了,每个你加进去的符号都是一个可能的偶数回文对称轴,此题可解。。。因为我们没有错过任何一个可能的对称轴,不管是奇数回文还是偶数回文。

    那么请问,加进去的符号,有什么要求么?是不是必须在原字符中没出现过?请思考

     

    其实不需要的,大家想一下,不管怎么扩,原来的永远和原来的比较,加进去的永远和加进去的比较。(不举例子说明了,自己思考一下)

    好,分析一波时间效率吧,对称轴数量为o(n)级别,每个对称轴向两边能扩多少?最多也就o(n)级别,一共长度才n; 所以n*n是o(n^2)   (最大能扩的位置其实也是两个等差数列,这么理解也是o(n^2),用到刚讲的知识)

     

    小结:

    这种方法把原来的暴力枚举o(n^3)变成了o(n^2),大家想一想为什么这样更快呢?

    我在kmp一文中就提到过,我们写出暴力枚举方法后应想一想自己做出了哪些重复计算,错过了哪些信息,然后进行优化。

    看我们的暴力方法,如果按一般的顺序枚举,012345,012判断完,接着判断0123,我是没想到可以利用前面信息的方法,因为对称轴不一样啊,右边加了一个元素,左边没加。所以刚开始,老是想找一种方法,左右都加一个元素,这样就可以对上一次的信息加以利用了。

    暴力为什么效率低?永远是因为重复计算,举个例子:12121211,下标从0开始,判断1212121是否为回文串的时候,其实21212和121等串也就判断出来了,但是我们并没有记下结果,当枚举到21212或者121时,我们依旧是重新尝试了一遍。(假设主串长度为n,对称轴越在中间,长度越小的子串,被重复尝试的越多。中间那些点甚至重复了n次左右,本来一次搞定的事)

    还是这个例子,我换一个角度叙述一下,比较直观,如果从3号开始向两边扩,121,21212,最后扩到1212121,时间复杂度o(n),用枚举的方法要多少时间?如果主串长度为n,枚举尝试的子串长度为,3,5,7....n,等差数列,大家读到这里应该都知道了,等差数列求和,o(n^2)。

    4.4三、Manacher原理

    首先告诉大家,这个算法时间可以做到o(n),空间o(n).

    好的,开始讲解这个神奇的算法。

    首先明白两个概念:

    最右回文边界R:挺好理解,就是目前发现的回文串能延伸到的最右端的位置(一个变量解决)

    中心c:第一个取得最右回文边界的那个中心对称轴;举个例子:12121,二号元素可以扩到12121,三号元素 可以扩到121,右边界一样,我们的中心是二号元素,因为它第一个到达最右边界

    当然,我们还需要一个数组p来记录每一个可能的对称轴最后扩到了哪里。

    有了这么几个东西,我们就可以开始这个神奇的算法了。

    为了容易理解,我分了四种情况,依次讲解:

     

    假设遍历到位置i,如何操作呢

    1)i>R:也就是说,i以及i右边,我们根本不知道是什么,因为从来没扩到那里。那没有任何优化,直接往右暴力 扩呗。

    (下面我们做i关于c的对称点,i’)

    2)i<R:,

    三种情况:

    i’的回文左边界在c回文左边界的里面

    i’回文左边界在整体回文的外面

     i’左边界和c左边界是一个元素

    (怕你忘了概念,c是对称中心,c它当初扩到了R,R是目前扩到的最右的地方,现在咱们想以i为中心,看能扩到哪里。)

    按原来o(n^2)的方法,直接向两边暴力扩。好的,魔性的优化来了。咱们为了好理解,分情况说。首先,大家应该知道的是,i’其实有人家自己的回文长度,我们用数组p记录了每个位置的情况,所以我们可以知道以i’为中心的回文串有多长。 

    2-1)i’的回文左边界在c回文的里面:看图

    我用这两个括号括起来的就是这两个点向两边扩到的位置,也就是i和i’的回文串,为什么敢确定i回文只有这么长?和i’一样?我们看c,其实这个图整体是一个回文串啊。

    串内完全对称(1是括号左边相邻的元素,2是右括号右边相邻的元素,34同理),

     由此得出结论1:

    由整体回文可知,点2=点3,点1=点4

     

    当初i’为什么没有继续扩下去?因为点1!=点2。

    由此得出结论2:点1!=点2 

     

    因为前面两个结论,所以3!=4,所以i也就到这里就扩不动了。而34中间肯定是回文,因为整体回文,和12中间对称。

     

    2-2)i回文左边界在整体回文的外面了:看图

     这时,我们也可以直接确定i能扩到哪里,请听分析:

    当初c的大回文,扩到R为什么就停了?因为点2!=点4----------结论1;

    2’为2关于i’的对称点,当初i’左右为什么能继续扩呢?说明点2=点2’---------结论2;

    由c回文可知2’=3,由结论2可知点2=点2’,所以2=3;

    但是由结论一可知,点2!=点4,所以推出3!=4,所以i扩到34为止了,34不等。

    而34中间那一部分,因为c回文,和i’在内部的部分一样,是回文,所以34中间部分是回文。 

     

    2-3)最后一种当然是i左边界和c左边界是一个元素

     点1!=点2,点2=点3,就只能推出这些,只知道34中间肯定是回文,外边的呢?不知道啊,因为不知道3和4相不相等,所以我们得出结论:点3点4内肯定是,继续暴力扩。

    原理及操作叙述完毕,不知道我讲没讲明白。。。

    4.4四、代码及复杂度分析

     看代码大家是不是觉得不像o(n)?其实确实是的,来分析一波。。

    首先,我们的i依次往下遍历,而R(最右边界)从来没有回退过吧?其实当我们的R到了最右边,就可以结束了。再不济i自己也能把R一个一个怼到最右

    我们看情况一和四,R都是以此判断就向右一个,移动一次需要o(1)

    我们看情况二和三,直接确定了p[i],根本不用扩,直接遍历下一个元素去了,每个元素o(1).

    综上,由于i依次向右走,而R也没有回退过,最差也就是i和R都到了最右边,而让它们移动一次的代价都是o(1)的,所以总体o(n)

    可能大家看代码依旧有点懵,其实就是code整合了一下,我们对于情况23,虽然知道了它肯定扩不动,但是我们还是给它一个起码是回文的范围,反正它扩一下就没扩动,不影响时间效率的。而情况四也一样,给它一个起码是回文,不用验证的区域,然后接着扩,四和二三的区别就是。二三我们已经心中有B树,它肯定扩不动了,而四确实需要接着尝试。

    (要是写四种情况当然也可以。。但是我懒的写,太多了。便于理解分了四种情况解释,code整合后就是这样子)    

     

    我真的想象不到当初发明这个算法的人是怎么想到的,向他致敬。

    展开全文
  • IPVS和Nginx两种WRR负载均衡算法详解

    千次阅读 热门讨论 2018-04-28 05:23:40
      忆起与人交流一个负载均衡问题时,偶然聊到了WRR算法,就必然要记下些什么,以表示曾经聊过这个话题,作此文以记之! 简介 在负载均衡场景中,我们经常需要对一组服务器做加权轮询均衡调用,即适配一个...

    动机

    五一临近,四月也接近尾声,五一节乃小长假的最后一天。今天是最后一天工作日,竟然感冒了,半夜里翻来覆去无法安睡,加上窗外大飞机屋里小飞机(也就是蚊子)的骚扰,实在是必须起来做点有意义的事了!

      忆起与人交流一个负载均衡问题时,偶然聊到了WRR算法,就必然要记下些什么,以表示曾经聊过这个话题,作此文以记之!

    简介

    在负载均衡场景中,我们经常需要对一组服务器做加权轮询均衡调用,即适配一个叫做WRR(Weighted Round-Robin Scheduling)的算法。本文的主要内容就是分析常见的两种WRR算法,即Linux IPVS的WRR算法和Nginx的WRR算法,并试图做出二者的比较。

      当然了,负载均衡的算法非常多,但很难在一篇技术随笔中盖以全貌,与其说不透,不如干脆不说,因此本文的内容仅仅包含两种常见的WRR算法。

    Linux内核IPVS使用的WRR算法

    这里接不介绍IPVS了,直接切入算法本身,详见net/netfilter/ipvs/ip_vs_wrr.c中的结构体:

    static struct ip_vs_scheduler ip_vs_wrr_scheduler = {
        .name =         "wrr",
        .refcnt =       ATOMIC_INIT(0),
        .module =       THIS_MODULE,
        .n_list =       LIST_HEAD_INIT(ip_vs_wrr_scheduler.n_list),
        .init_service =     ip_vs_wrr_init_svc,
        .done_service =     ip_vs_wrr_done_svc,
        .add_dest =     ip_vs_wrr_dest_changed,
        .del_dest =     ip_vs_wrr_dest_changed,
        .upd_dest =     ip_vs_wrr_dest_changed,
        .schedule =     ip_vs_wrr_schedule,
    };

    这里重点关注schedule 回调函数ip_vs_wrr_schedule。

      为了让事情更加直观,不至于陷入到Linux内核源码IPVS复杂业务逻辑的深渊,这里给出其Wiki上上的写法,摘自:http://kb.linuxvirtualserver.org/wiki/Weighted_Round-Robin_Scheduling

    Supposing that there is a server set S = {S0, S1, …, Sn-1};
    W(Si) indicates the weight of Si;
    i indicates the server selected last time, and i is initialized with -1;
    cw is the current weight in scheduling, and cw is initialized with zero; 
    max(S) is the maximum weight of all the servers in S;
    gcd(S) is the greatest common divisor of all server weights in S;
    
    while (true) {
        i = (i + 1) mod n;
        if (i == 0) {
            cw = cw - gcd(S); 
            if (cw <= 0) {
                cw = max(S);
                if (cw == 0)
                return NULL;
            }
        } 
        if (W(Si) >= cw) 
            return Si;
    }

    如果你还是没有一个直观上的感受,下面是我写的一个简单的能run的程序,直接编译运行即可:

    #include <stdio.h>
    #include <stdlib.h>
    
    struct entry {
            int weight;
    };
    
    struct entry *g_entry = NULL;
    int max_weight = 0;
    int curr_weight = 0;
    int divisor = 0;
    int iter = -1;
    
    
    int gcd(int a, int b)  
    {  
            if (a == 0) {
                    return b;
            }
            return gcd(b%a, a);  
    } 
    
    struct entry *next(int size) 
    {
    
            struct entry *ent;
            while (1) {
                    iter = (iter + 1) % size;
                    if (iter == 0) {
                            curr_weight = curr_weight - divisor; 
                            if (curr_weight <= 0) {
                                    curr_weight = max_weight;
                            }
                    } 
                    ent = &g_entry[iter];
                    if (ent->weight >= curr_weight) {
                            return ent;
                    }
            }
    }
    
    int main(int argc, char **argv)
    {
            int size = atoi(argv[1]);
            int i = 0;
            int total = 0;
    
            g_entry = (struct entry *)calloc(size, sizeof(struct entry));
            for (i = 0; i < size; i++) {
                    struct entry *ent = &g_entry[i];
                    ent->weight = atoi(argv[i+2]);
                    total += ent->weight;
                    if (ent->weight > max_weight) {
                            max_weight = ent->weight;
                    }
                    divisor = gcd(divisor, ent->weight);
            }
    
            for (i = 0; i < total; i++) {
                    struct entry *ent = next(size);
                    printf("[LAST]: %d\n", ent->weight);
            }
    
    }

    你可以这样使用这个程序:

    # 这里生成一个3(第一个参数)个元素的集合,其权值分别为5,1,1(后面的参数)
    ./a.out 3 5 1 1

    简单的证明和分析

    这个算法给出的结果总是正确的吗?回答这个问题我觉得非常简单直观,请看下图:
    这里写图片描述

    按照上图中的规则,取元素的顺序则是:

    这里写图片描述


    在数学上证明算法的正确性似乎也不难,设一个元素的权值为 Wi W i ,那么它在锚点一轮轮询中被选中的次数就是 Widiv W i d i v ,可见,对于一个固定的序列,其 div d i v 一定,一个元素被选中的次数与其权值成正比,这便符合了算法的要求。

    问题

    观察上面的图,如果一个集合中最大权值的元素和次大权值的元素相隔太远,那么这个算法在选元素的时候是不会把权值大的元素打散的,比如:

    root@debian:/home/zhaoya# ./a.out 2 5 1
    [LAST]: 5
    [LAST]: 5
    [LAST]: 5
    [LAST]: 5
    [LAST]: 5
    [LAST]: 1

    映射回负载均衡的真实场景,这显然会对某些大权值的服务器造成很大的压力,因此对这个算法的改进或者说换另外一个算法是一件必须要做的事。接下来我们就开始分析一个结果序列更加平均的WRR算法,即Nginx服务器中使用的WRR算法。


    Nginx使用的WRR算法

    关于这个算法,具体的描述详见:
    https://github.com/phusion/nginx/commit/27e94984486058d73157038f7950a0a36ecc6e35

    和分析IPVS之WRR算法的做法一样,我依然给出一个能run的代码,其运行方法与上述IPVS的算法完全一致:

    #include <stdio.h>
    #include <stdlib.h>
    
    struct entry {
            int weight;
            int curr_weight;
    };
    
    struct entry *curr_entry = NULL;
    struct entry *g_entry = NULL;
    
    struct entry *next(struct entry *entrys, int size) 
    {
    
            struct entry *ent;
            int i = 0, total = 0;
            for (i = 0; i < size; i++) {
                    ent = &entrys[i];
                    ent->curr_weight += ent->weight;
                    total += ent->weight;
                    if (curr_entry == NULL || ent->curr_weight > curr_entry->curr_weight) {
                            curr_entry = ent;
                    }
            }
            curr_entry->curr_weight -= total;
            for (i = 0; i < size; i++) {
                    ent = &entrys[i];
            }
            return curr_entry;
    }
    
    int main(int argc, char **argv)
    {
            int size = atoi(argv[1]);
            int i = 0;
            int total = 0;
    
            g_entry = (struct entry *)calloc(size, sizeof(struct entry));
            for (i = 0; i < size; i++) {
                    struct entry *ent = &g_entry[i];
                    ent->weight = atoi(argv[i+2]);
                    total += ent->weight;
            }
    
    
            for (i = 0; i < total; i++) {
                    struct entry *ent = next(g_entry, size);
                    printf("[LAST]: %d\n", ent->weight);
            }
    
    }

    以上就是Nginx所采用的WRR算法的代码描述,在大多数情况下,采用这种算法是一个不错的选择。即满足了固定的加权平均,又使得元素的选择尽可能地分散开来,非常精妙!

      该算法与IPVS的WRR按照某种规则和组织静态遍历完全不同,它完全是一个动态的过程,因此除非用动画,否则一张图无法展示全貌。我用简单的3个元素加权来描述一下这个算法。假设有3个具有不同权值的 {A:a,B:b,C:c} { A : a , B : b , C : c } 元素供选择,在一轮轮询中,3个元素分别被递加其权值的递增量为:

    元素 A A 递增a的量: a×(a+b+c) a × ( a + b + c )
    元素 B B 递增b选中的量: b×(a+b+c) b × ( a + b + c )
    元素 C C 递增c选中的量: c×(a+b+c) c × ( a + b + c )

    每选中一个元素,将会从其递增量中减去 (a+b+c) ( a + b + c ) ,那么很显然,问题部分地被转化为求出每个元素递增量中包含多少个递减量便是该元素会被选中的次数。最终,我们承认下面的解是一个正确的解:

    元素 A A 被选中的次数:a×(a+b+c)a+b+c
    元素 B B 被选中的次数:b×(a+b+c)a+b+c
    元素 C C 被选中的次数:c×(a+b+c)a+b+c

      然而,这个解是唯一的解吗?如何证明这是唯一解?这便是一个数学问题。理解并使用该算法是完全没有问题的,coders深谙此道,然而想要彻底理解它,则必须要证明在算法的操作下,最终得到的解是唯一解,接下来我就简单用反证法来证明一下。

    算法的描述

    这个算法很有意思,所有集合一开始各就各位初始化自己的 Wcurri W c u r r i 为自己的权值,然后谁获胜(即其 Wcurri W c u r r i 最大),谁就要减掉所有元素的权值之和 (a+b+c) ( a + b + c ) ,接下来继续推进一步,每一个元素再加上自己的权值…最终我们发现,每一步推进过程,每一个元素各自增加自身的权值,然后获胜者把所有元素增加的权值一次性做减法,这意味着,任何时候,在选择元素前:

    ΣWcurri=a+b+c Σ W c u r r i = a + b + c

    而选择了 Wcurri W c u r r i 最大的元素后:

    ΣWcurri=0 Σ W c u r r i = 0

    这像不像古代军队弓箭手放乱箭的过程,简直太像了!同时,这是一种非积累即时消费的模型,即获胜者一次性消费掉其它选手在本轮中获取的配额这种非积累特性抹掉了很多潜在的记忆阻止了幂律产生作用,让结果散列地更均匀


    算法正确性证明

    假设在集合 {A:a,B:b,C:c} { A : a , B : b , C : c } 尚未取够 (a+b+c) ( a + b + c ) 个元素的时候,权重为 a a 的元素A已经取满了 a a 个,此时:

    Wcurra=N×a(a1)(a+b+c)
    Wcurrb=N×bmb1(a+b+c) W c u r r b = N × b − m b 1 ( a + b + c )
    Wcurrc=N×cmc1(a+b+c) W c u r r c = N × c − m c 1 ( a + b + c )

    由算法基本逻辑,我们知道上面 3 3 式子相加等于(a+b+c)

    ΣWcurri=N×(a+b+c)(a1+mb1+mc1)(a+b+c)=(a+b+c) Σ W c u r r i = N × ( a + b + c ) − ( a − 1 + m b 1 + m c 1 ) ( a + b + c ) = ( a + b + c )

    化简得到:

    N=a+mb1+mc1 N = a + m b 1 + m c 1    (1) ( 1 )

    现在假设,在取到第 T T (N<T<a+b+c)个的时候,又取了一个权重为 a a 的元素A,则此时根据算法逻辑计算 Wcurri W c u r r i

    Wcurra=T×a(a+mT1)(a+b+c) W c u r r a = T × a − ( a + m T − 1 ) ( a + b + c )    mT m T 为此间取到 A A 的次数
    Wcurrb=T×bmb2(a+b+c)
    Wcurrc=T×cmc2(a+b+c) W c u r r c = T × c − m c 2 ( a + b + c )

    又因为取到权值为 a a 的元素A的条件是此时其 Wcurr W c u r r 最大,则有:

    T×a(a+mT1)(a+b+c)>T×bmb2(a+b+c) T × a − ( a + m T − 1 ) ( a + b + c ) > T × b − m b 2 ( a + b + c )
    T×a(a+mT1)(a+b+c)>T×cmc2(a+b+c) T × a − ( a + m T − 1 ) ( a + b + c ) > T × c − m c 2 ( a + b + c )

    化简上面式子:

    T×(ab)>(a+mT1mb2)(a+b+c) T × ( a − b ) > ( a + m T − 1 − m b 2 ) ( a + b + c )
    T×(ac)>(a+mT1mc2)(a+b+c) T × ( a − c ) > ( a + m T − 1 − m c 2 ) ( a + b + c )

    根据条件 N<T<a+b+c N < T < a + b + c 代入,则有:

    T×(ab)>(a+mT1mb2)×T T × ( a − b ) > ( a + m T − 1 − m b 2 ) × T
    T×(ac)>(a+mT1mc2)×T T × ( a − c ) > ( a + m T − 1 − m c 2 ) × T

    最终,我们得到两个不等式:

    mb2b>mT1 m b 2 − b > m T − 1
    mc2c>mT1 m c 2 − c > m T − 1

    由于我们是在第 T T 次取的第a+1个权值为 a a 的元素A,所以这里的 m m 等于1,则有:

    mb2b>0 m b 2 − b > 0
    mc2c>0 m c 2 − c > 0

    现在谜底要揭开了!由于我们假设在集合 {A:a,B:b,C:c} { A : a , B : b , C : c } 取完 a+b+c a + b + c 个元素之后,权值为 a a 的元素A的取量多于 a a 个,那么权值为b c c 的元素B C C 取量必然至少有一个要少于自己权重数值,而上面的不等式表明,若需要满足权值为a的元素 A A 的取量多于a个,权值为 b b c的元素 B B C取量也必须同时多于它们的权值!这显然最终会造成一个矛盾:

    ma+mb+mc>a+b+c m a + m b + m c > a + b + c

    因此,假设是错误的!即:

    权值为 a a 的元素A在一轮轮询之后的取量不可能多于 a a

    那么,能不能少于a个呢?这个问题很简单!既然 A A 元素少于a个,那么在总量 a+b+c a + b + c 一定的情况下,一定有别的元素的取量多于自己的权值,因此问题还是会转化为上面我们反证的问题,这实际上是同一个问题!


    好了,本节我们证明了Nginx里面的这个WRR算法是正确的,即通过算法指示的操作,算法轮询结束后,会严格按照元素的权值比例分配被轮询的次数

    为什么比IPVS的WRR要好?

    这个问题其实很难回答,因为很难有一个确定的标准。我咨询过很多大师大神,得到的答案几乎都是从概率,global state的变更频率以及最大熵的角度来分析,然而这些对于回到这个问题有点复杂了。因为我知道Nginx的WRR算法也远不是最好的,其序列分布也不满足最大熵…

      所以,我把问题化简,我只要能求出一个权值最大的元素在序列一开始时连续分布的最大上界就基本OK了,如果我求出的这个上界小于其权值 Wi W i ,那就可以说明不可能所有的最大权值的元素完全连续分布,但确实要连续分布一点点,这便打散了整个分布,这已经比IPVS的WRR算法最终的序列分布要好了。

      现在让我们开始。


    假设元素 A A 的权值最大,为a,设其连续分布 x x 次,则有:

    x×a(x1)(a+b+c)>0

    上面式子的含义是,选最后一次 A A 的时候,其配额依然是正的。现在化简:

    x<a+b+cb+c

    这就是上界!

      好吧,我现在用一个更加极端的例子来展示一下:

    root@debian:/home/zhaoya# ./a.out 2 18 1
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18
    [LAST]: 1
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18
    [LAST]: 18

    很显然, 18 18 连续了 9 9 次,按照上界公式算出来18连续分布应该不超过19次,显然9没有超过19,这是正确的。那么如何解释中间插入的那个1呢?显然,这就是算法的精妙之所在。

      按照算法描述,每选中一个最大值Wcurri元素,其 Wcurri W c u r r i 便需要减去配额 (a+b+c) ( a + b + c ) ,与此同时,其它落选的元素其 Wcurri W c u r r i 是单调递增的,这是一个小学四年级就学过的相遇问题,这从根本上阻止了任意元素的连续分布!

      依然以3个元素的集合为例,假设元素 A A 的权值最大,为a,元素 B B 的权值次大(我们需要次大的元素与最大的元素的Wcurri相遇),为 b b ,按照相遇问题的解法,我们有:

    ax×(b+c)=x×b

    化简为:

    x=a2b+c x = a 2 b + c

    在下面的例子中代入上式:

    root@debian:/home/zhaoya# ./a.out 2 18 1

    我们得到 x=9 x = 9

      当然,在这里我有意把问题简化了,因此这不是一个普通的相遇问题,因此上面式子中的等号 = = 是不恰当的,但无论如何,我展示了一个极端情况下Nginx WRR算法的表现。

    算法的O(n)问题

    很多人对本文中所描述的两种WRR算法并不是很满意,因为在寻找next元素的时候,其时间复杂度是O(n)的,人们一般很讨厌看到这个 O(n) O ( n )

      但是实际上,这并无所谓,虽然是 O(n) O ( n ) ,但是还有一件利器,即cache的思路,或者说网络上转控分离思路来解决这个 O(n) O ( n ) 的问题。

      在不考虑权值动态更新的前提下,事实上,给定一个集合,按照权值的WRR分布是一个固定的序列,我们不妨在第一次获取到这个序列的时候就将其保存起来,随便用什么基于定位而非查找的数据结构都可以,比如数组,bitmap这种,总之就是在后续的操作中,用 O(1) O ( 1 ) 的时间复杂度来定位集合中的next元素!

      这类似将WRR做了一个预处理,事先生成了序列。

    CFS/FQ/PQ调度与WRR负载均衡

    最后来比较一下WRR和FQ队列。

      FQ队列以及PQ队列以及队列领域的WRR算法注重于在时间上调度上的公平性,即完全按照其优先级权值来进行调度,谁的权值大,谁优先。

      而负载均衡中的WRR更多的是在空间上考虑公平性,在空间维度,打散结果是最好的方案。

      其实,我们也可以按照队列调度的思想来重新实现负载均衡的WRR算法,以下是一个简单的代码,参照Linux CFS调度器的原理:

    #include <stdio.h>
    #include <stdlib.h>
    
    struct entry {
            int weight;
            int curr_cfs;
    };
    
    struct entry *curr_entry = NULL;
    struct entry *g_entry = NULL;
    
    
    struct entry *next_cfs(struct entry *entrys, int size)
    {
            struct entry *ent;
            int i = 0, total = 0;
            for (i = 0; i < size; i++) {
                    ent = &entrys[i];
                    // 选择最小的curr_cfs
                    if (curr_entry == NULL || ent->curr_cfs < curr_entry->curr_cfs) {
                            curr_entry = ent;
                    }
            }
        // 满足“单位1”中有weight个元素,算法的结果才是正确的
            curr_entry->curr_cfs += 100000000/(curr_entry->weight);
            return curr_entry;
    }
    
    
    int main(int argc, char **argv)
    {
            int size = atoi(argv[1]);
            int i = 0;
            int total = 0;
    
            g_entry = (struct entry *)calloc(size, sizeof(struct entry));
            for (i = 0; i < size; i++) {
                    struct entry *ent = &g_entry[i];
                    ent->weight = atoi(argv[i+2]);
                    ent->curr_cfs = 100000000/ent->weight;
                    total += ent->weight;
            }
    
    
            for (i = 0; i < total; i++) {
                    struct entry *ent = next_cfs(g_entry, size);
                    printf("[LAST_CFS]: %d\n", ent->weight);
            }
    
    }

    你可以试一下结果。你会发现,所有权值一样的元素完全挤在一起了,这非常符合在时间序列上的公平性表现(大体上,进程调度和数据包调度都是如此表现),但是在空间维度上却非常差劲。

    后记

    生日过后,待续!

    展开全文
  • 主宰操作系统的经典算法

    万次阅读 多人点赞 2020-07-24 15:22:50
    此篇文章带你梳理一下操作系统中都出现过哪些算法 进程和线程管理中的算法 进程和线程在调度时候出现过...操作系统中有一个叫做 调度程序(scheduler) 的角色存在,它就是做这件事儿的,调度程序使用算法叫做 调度算

    此篇文章带你梳理一下操作系统中都出现过哪些算法

    进程和线程管理中的算法

    进程和线程在调度时候出现过很多算法,这些算法的设计背景是当一个计算机是多道程序设计系统时,会频繁的有很多进程或者线程来同时竞争 CPU 时间片。 那么如何选择合适的进程/线程运行是一项艺术。当两个或两个以上的进程/线程处于就绪状态时,就会发生这种情况。如果只有一个 CPU 可用,那么必须选择接下来哪个进程/线程可以运行。操作系统中有一个叫做 调度程序(scheduler) 的角色存在,它就是做这件事儿的,调度程序使用的算法叫做 调度算法(scheduling algorithm)

    调度算法分类

    针对不同的操作系统环境,也有不同的算法分类,操作系统主要分为下面这几种

    • 批处理操作系统
    • 交互式操作系统
    • 实时操作系统

    下面我们分别来看一下这些操作系统中的算法。

    批处理操作系统中的算法

    设计目标

    批处理系统广泛应用于商业领域,比如用来处理工资单、存货清单、账目收入、账目支出、利息计算、索赔处理和其他周期性作业。在批处理系统中,一般会选择使用非抢占式算法或者周期性比较长抢占式算法。这种方法可以减少线程切换因此能够提升性能。

    交互式用户环境中,因为为了用户体验,所以会避免长时间占用进程,所以需要抢占式算法。由于某个进程出现错误也有可能无限期的排斥其他所有进程。为了避免这种情况,抢占式也是必须的。

    实时系统中,抢占式不是必须的,因为进程知道自己可能运行不了很长时间,通常很快的做完自己的工作并挂起。

    关键指标

    通常有三个指标来衡量系统工作状态:吞吐量、周转时间和 CPU 利用率

    • 吞吐量(throughout) 是系统每小时完成的作业数量。综合考虑,每小时完成 50 个工作要比每小时完成 40 个工作好。
    • 周转时间(Turnaround time) 是一种平均时间,它指的是从一个批处理提交开始直到作业完成时刻为止的平均时间。该数据度量了用户要得到输出所需的平均等待时间。周转时间越小越好。
    • CPU 利用率(CPU utilization) 通常作为批处理系统上的指标。即使如此,CPU 利用率也不是一个好的度量指标,真正有价值的衡量指标是系统每小时可以完成多少作业(吞吐量),以及完成作业需要多长时间(周转时间)。

    下面我们就来认识一下批处理中的算法。

    先来先服务

    很像是先到先得。。。它是一种非抢占式的算法。此算法将按照请求顺序为进程分配 CPU。最基本的,会有一个就绪进程的等待队列。当第一个任务从外部进入系统时,将会立即启动并允许运行任意长的时间。它不会因为运行时间太长而中断。当其他作业进入时,它们排到就绪队列尾部。当正在运行的进程阻塞,处于等待队列的第一个进程就开始运行。当一个阻塞的进程重新处于就绪态时,它会像一个新到达的任务,会排在队列的末尾,即排在所有进程最后。

    这个算法的强大之处在于易于理解编程,在这个算法中,一个单链表记录了所有就绪进程。要选取一个进程运行,只要从该队列的头部移走一个进程即可;要添加一个新的作业或者阻塞一个进程,只要把这个作业或进程附加在队列的末尾即可。这是很简单的一种实现。

    不过,先来先服务也是有缺点的,那就是没有优先级的关系,试想一下,如果有 100 个 I/O 进程正在排队,第 101 个是一个 CPU 密集型进程,那岂不是需要等 100 个 I/O 进程运行完毕才会等到一个 CPU 密集型进程运行,这在实际情况下根本不可能,所以需要优先级或者抢占式进程的出现来优先选择重要的进程运行。

    最短作业优先

    批处理中的第二种调度算法是 最短作业优先(Shortest Job First),我们假设运行时间已知。例如,一家保险公司,因为每天要做类似的工作,所以人们可以相当精确地预测处理 1000 个索赔的一批作业需要多长时间。当输入队列中有若干个同等重要的作业被启动时,调度程序应使用最短优先作业算法

    如上图 a 所示,这里有 4 个作业 A、B、C、D ,运行时间分别为 8、4、4、4 分钟。若按图中的次序运行,则 A 的周转时间为 8 分钟,B 为 12 分钟,C 为 16 分钟,D 为 20 分钟,平均时间内为 14 分钟。

    现在考虑使用最短作业优先算法运行 4 个作业,如上图 b 所示,目前的周转时间分别为 4、8、12、20,平均为 11 分钟,可以证明最短作业优先是最优的。考虑有 4 个作业的情况,其运行时间分别为 a、b、c、d。第一个作业在时间 a 结束,第二个在时间 a + b 结束,以此类推。平均周转时间为 (4a + 3b + 2c + d) / 4 。显然 a 对平均值的影响最大,所以 a 应该是最短优先作业,其次是 b,然后是 c ,最后是 d 它就只能影响自己的周转时间了。

    需要注意的是,在所有的进程都可以运行的情况下,最短作业优先的算法才是最优的。

    最短剩余时间优先

    最短作业优先的抢占式版本被称作为 最短剩余时间优先(Shortest Remaining Time Next) 算法。使用这个算法,调度程序总是选择剩余运行时间最短的那个进程运行。当一个新作业到达时,其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间,当前进程就被挂起,而运行新的进程。这种方式能够使短期作业获得良好的服务。

    交互式系统中的调度

    交互式系统中在个人计算机、服务器和其他系统中都是很常用的,所以有必要来探讨一下交互式调度

    轮询调度

    一种最古老、最简单、最公平并且最广泛使用的算法就是 轮询算法(round-robin)。每个进程都会被分配一个时间段,称为时间片(quantum),在这个时间片内允许进程运行。如果进程在时间片结束前阻塞或结束,则 CPU 立即进行切换。轮询算法比较容易实现。调度程序所做的就是维护一个可运行进程的列表,就像下图中的 a,当一个进程用完时间片后就被移到队列的末尾,就像下图的 b。

    时间片轮询调度中唯一有意思的一点就是时间片的长度。从一个进程切换到另一个进程需要一定的时间进行管理处理,包括保存寄存器的值和内存映射、更新不同的表格和列表、清除和重新调入内存高速缓存等。这种切换称作 进程间切换(process switch)上下文切换(context switch)

    优先级调度

    轮询调度假设了所有的进程是同等重要的。但事实情况可能不是这样。例如,在一所大学中的等级制度,首先是院长,然后是教授、秘书、后勤人员,最后是学生。这种将外部情况考虑在内就实现了优先级调度(priority scheduling)

    它的基本思想很明确,每个进程都被赋予一个优先级,优先级高的进程优先运行。

    但是也不意味着高优先级的进程能够永远一直运行下去,调度程序会在每个时钟中断期间降低当前运行进程的优先级。如果此操作导致其优先级降低到下一个最高进程的优先级以下,则会发生进程切换。或者,可以为每个进程分配允许运行的最大时间间隔。当时间间隔用完后,下一个高优先级的进程会得到运行的机会。

    可以很方便的将一组进程按优先级分成若干类,并且在各个类之间采用优先级调度,而在各类进程的内部采用轮转调度。下面展示了一个四个优先级类的系统

    它的调度算法主要描述如下:上面存在优先级为 4 类的可运行进程,首先会按照轮转法为每个进程运行一个时间片,此时不理会较低优先级的进程。若第 4 类进程为空,则按照轮询的方式运行第三类进程。若第 4 类和第 3 类进程都为空,则按照轮转法运行第 2 类进程。如果不对优先级进行调整,则低优先级的进程很容易产生饥饿现象。

    最短进程优先

    对于批处理系统而言,由于最短作业优先常常伴随着最短响应时间,所以如果能够把它用于交互式进程,那将是非常好的。交互式进程通常遵循下列模式:等待命令、执行命令、等待命令、执行命令。。。如果我们把每个命令的执行都看作一个分离的作业,那么我们可以通过首先运行最短的作业来使响应时间最短。这里唯一的问题是如何从当前可运行进程中找出最短的那一个进程。

    一种方式是根据进程过去的行为进行推测,并执行估计运行时间最短的那一个。假设每个终端上每条命令的预估运行时间为 T0,现在假设测量到其下一次运行时间为 T1,可以用两个值的加权来改进估计时间,即aT0+ (1- 1)T1。通过选择 a 的值,可以决定是尽快忘掉老的运行时间,还是在一段长时间内始终记住它们。当 a = 1/2 时,可以得到下面这个序列

    可以看到,在三轮过后,T0 在新的估计值中所占比重下降至 1/8。

    有时把这种通过当前测量值和先前估计值进行加权平均从而得到下一个估计值的技术称作 老化(aging)。这种方法会使用很多预测值基于当前值的情况。

    保证调度

    一种完全不同的调度方法是对用户做出明确的性能保证。一种实际而且容易实现的保证是:若用户工作时有 n 个用户登录,则每个用户将获得 CPU 处理能力的 1/n。类似地,在一个有 n 个进程运行的单用户系统中,若所有的进程都等价,则每个进程将获得 1/n 的 CPU 时间。

    彩票调度

    对用户进行承诺并在随后兑现承诺是一件好事,不过很难实现。但是有一种既可以给出预测结果而又有一种比较简单的实现方式的算法,就是 彩票调度(lottery scheduling)算法。

    其基本思想是为进程提供各种系统资源(例如 CPU 时间)的彩票。当做出一个调度决策的时候,就随机抽出一张彩票,拥有彩票的进程将获得该资源。在应用到 CPU 调度时,系统可以每秒持有 50 次抽奖,每个中奖者将获得比如 20 毫秒的 CPU 时间作为奖励。

    如果希望进程之间协作的话可以交换它们之间的票据。例如,客户端进程给服务器进程发送了一条消息后阻塞,客户端进程可能会把自己所有的票据都交给服务器,来增加下一次服务器运行的机会。当服务完成后,它会把彩票还给客户端让其有机会再次运行。事实上,如果没有客户机,服务器也根本不需要彩票。

    可以把彩票理解为 buff,这个 buff 有 15% 的几率能让你产生 速度之靴 的效果。

    公平分享调度

    到目前为止,我们假设被调度的都是各个进程自身,而不用考虑该进程的拥有者是谁。结果是,如果用户 1 启动了 9 个进程,而用户 2 启动了一个进程,使用轮转或相同优先级调度算法,那么用户 1 将得到 90 % 的 CPU 时间,而用户 2 将之得到 10 % 的 CPU 时间。

    为了阻止这种情况的出现,一些系统在调度前会把进程的拥有者考虑在内。在这种模型下,每个用户都会分配一些CPU 时间,而调度程序会选择进程并强制执行。因此如果两个用户每个都会有 50% 的 CPU 时间片保证,那么无论一个用户有多少个进程,都将获得相同的 CPU 份额。

    实时系统中的调度

    实时系统(real-time) 对于时间有要求的系统。实时系统可以分为两类,硬实时(hard real time)软实时(soft real time) 系统,前者意味着必须要满足绝对的截止时间;后者的含义是虽然不希望偶尔错失截止时间,但是可以容忍。在这两种情形中,实时都是通过把程序划分为一组进程而实现的,其中每个进程的行为是可预测和提前可知的。这些进程一般寿命较短,并且极快的运行完成。在检测到一个外部信号时,调度程序的任务就是按照满足所有截止时间的要求调度进程。

    实时系统中的事件可以按照响应方式进一步分类为周期性(以规则的时间间隔发生)事件或 非周期性(发生时间不可预知)事件。一个系统可能要响应多个周期性事件流,根据每个事件处理所需的时间,可能甚至无法处理所有事件。例如,如果有 m 个周期事件,事件 i 以周期 Pi 发生,并需要 Ci 秒 CPU 时间处理一个事件,那么可以处理负载的条件是

    只有满足这个条件的实时系统称为可调度的,这意味着它实际上能够被实现。一个不满足此检验标准的进程不能被调度,因为这些进程共同需要的 CPU 时间总和大于 CPU 能提供的时间。

    实时系统的调度算法可以是静态的或动态的。前者在系统开始运行之前做出调度决策;后者在运行过程中进行调度决策。只有在可以提前掌握所完成的工作以及必须满足的截止时间等信息时,静态调度才能工作,而动态调度不需要这些限制。

    调度策略和机制

    到目前为止,我们隐含的假设系统中所有进程属于不同的分组用户并且进程间存在相互竞争 CPU 的情况。通常情况下确实如此,但有时也会发生一个进程会有很多子进程并在其控制下运行的情况。例如,一个数据库管理系统进程会有很多子进程。每一个子进程可能处理不同的请求,或者每个子进程实现不同的功能(如请求分析、磁盘访问等)。主进程完全可能掌握哪一个子进程最重要(或最紧迫),而哪一个最不重要。但是,以上讨论的调度算法中没有一个算法从用户进程接收有关的调度决策信息,这就导致了调度程序很少能够做出最优的选择。

    解决问题的办法是将 调度机制(scheduling mechanism)调度策略(scheduling policy) 分开,这是长期一贯的原则。这也就意味着调度算法在某种方式下被参数化了,但是参数可以被用户进程填写。让我们首先考虑数据库的例子。假设内核使用优先级调度算法,并提供了一条可供进程设置优先级的系统调用。这样,尽管父进程本身并不参与调度,但它可以控制如何调度子进程的细节。调度机制位于内核,而调度策略由用户进程决定,调度策略和机制分离是一种关键性思路。

    内存管理中的算法

    操作系统在内存管理上也出现过许多算法,这些算法的目标的最终目的都是为了合理分配内存。

    操作系统有两种内存管理方式,一种是位图,一种是 链表

    在使用链表管理内存时,有几种方法的变体

    当按照地址顺序在链表中存放进程和空闲区时,有几种算法可以为创建的进程(或者从磁盘中换入的进程)分配内存。我们先假设内存管理器知道应该分配多少内存,最简单的算法是使用 首次适配(first fit)。内存管理器会沿着段列表进行扫描,直到找个一个足够大的空闲区为止。除非空闲区大小和要分配的空间大小一样,否则将空闲区分为两部分,一部分供进程使用;一部分生成新的空闲区。首次适配算法是一种速度很快的算法,因为它会尽可能的搜索链表。

    首次适配的一个小的变体是 下次适配(next fit)。它和首次匹配的工作方式相同,只有一个不同之处那就是下次适配在每次找到合适的空闲区时就会记录当时的位置,以便下次寻找空闲区时从上次结束的地方开始搜索,而不是像首次匹配算法那样每次都会从头开始搜索。Bays(1997) 证明了下次适配算法的性能略低于首次匹配算法

    另外一个著名的并且广泛使用的算法是 最佳适配(best fit)。最佳适配会从头到尾寻找整个链表,找出能够容纳进程的最小空闲区。最佳适配算法会试图找出最接近实际需要的空闲区,以最好的匹配请求和可用空闲区,而不是先一次拆分一个以后可能会用到的大的空闲区。比如现在我们需要一个大小为 2 的块,那么首次匹配算法会把这个块分配在位置 5 的空闲区,而最佳适配算法会把该块分配在位置为 18 的空闲区,如下

    那么最佳适配算法的性能如何呢?最佳适配会遍历整个链表,所以最佳适配算法的性能要比首次匹配算法差。但是令人想不到的是,最佳适配算法要比首次匹配和下次匹配算法浪费更多的内存,因为它会产生大量无用的小缓冲区,首次匹配算法生成的空闲区会更大一些。

    最佳适配的空闲区会分裂出很多非常小的缓冲区,为了避免这一问题,可以考虑使用 最差适配(worst fit) 算法。即总是分配最大的内存区域(所以你现在明白为什么最佳适配算法会分裂出很多小缓冲区了吧),使新分配的空闲区比较大从而可以继续使用。仿真程序表明最差适配算法也不是一个好主意。

    如果为进程和空闲区维护各自独立的链表,那么这四个算法的速度都能得到提高。这样,这四种算法的目标都是为了检查空闲区而不是进程。但这种分配速度的提高的一个不可避免的代价是增加复杂度和减慢内存释放速度,因为必须将一个回收的段从进程链表中删除并插入空闲链表区。

    如果进程和空闲区使用不同的链表,那么可以按照大小对空闲区链表排序,以便提高最佳适配算法的速度。在使用最佳适配算法搜索由小到大排列的空闲区链表时,只要找到一个合适的空闲区,则这个空闲区就是能容纳这个作业的最小空闲区,因此是最佳匹配。因为空闲区链表以单链表形式组织,所以不需要进一步搜索。空闲区链表按大小排序时,首次适配算法与最佳适配算法一样快,而下次适配算法在这里毫无意义。

    另一种分配算法是 快速适配(quick fit) 算法,它为那些常用大小的空闲区维护单独的链表。例如,有一个 n 项的表,该表的第一项是指向大小为 4 KB 的空闲区链表表头指针,第二项是指向大小为 8 KB 的空闲区链表表头指针,第三项是指向大小为 12 KB 的空闲区链表表头指针,以此类推。比如 21 KB 这样的空闲区既可以放在 20 KB 的链表中,也可以放在一个专门存放大小比较特别的空闲区链表中。

    快速匹配算法寻找一个指定代销的空闲区也是十分快速的,但它和所有将空闲区按大小排序的方案一样,都有一个共同的缺点,即在一个进程终止或被换出时,寻找它的相邻块并查看是否可以合并的过程都是非常耗时的。如果不进行合并,内存将会很快分裂出大量进程无法利用的小空闲区。

    页面置换算法

    页面置换有非常多的算法,下面一起来认识一下

    当发生缺页异常时,操作系统会选择一个页面进行换出从而为新进来的页面腾出空间。如果要换出的页面在内存中已经被修改,那么必须将其写到磁盘中以使磁盘副本保持最新状态。如果页面没有被修改过,并且磁盘中的副本也已经是最新的,那么就不需要进行重写。那么就直接使用调入的页面覆盖需要移除的页面就可以了。

    当发生缺页中断时,虽然可以随机的选择一个页面进行置换,但是如果每次都选择一个不常用的页面会提升系统的性能。如果一个经常使用的页面被换出,那么这个页面在短时间内又可能被重复使用,那么就可能会造成额外的性能开销。在关于页面的主题上有很多页面置换算法(page replacement algorithms),这些已经从理论上和实践上得到了证明。

    下面我们就来探讨一下有哪些页面置换算法。

    最优页面置换算法

    最优的页面置换算法很容易描述,但在实际情况下很难实现。它的工作流程如下:在缺页中断发生时,这些页面之一将在下一条指令(包含该指令的页面)上被引用。其他页面则可能要到 10、100 或者 1000 条指令后才会被访问。每个页面都可以用在该页首次被访问前所要执行的指令数作为标记。

    最优化的页面算法表明应该标记最大的页面。如果一个页面在 800 万条指令内不会被使用,另外一个页面在 600 万条指令内不会被使用,则置换前一个页面,从而把需要调入这个页面而发生的缺页中断推迟。计算机也像人类一样,会把不愿意做的事情尽可能的往后拖。

    这个算法最大的问题时无法实现。当缺页中断发生时,操作系统无法知道各个页面的下一次将在什么时候被访问。这种算法在实际过程中根本不会使用。

    最近未使用页面置换算法

    为了能够让操作系统收集页面使用信息,大部分使用虚拟地址的计算机都有两个状态位,R 和 M,来和每个页面进行关联。每当引用页面(读入或写入)时都设置 R,写入(即修改)页面时设置 M,这些位包含在每个页表项中,就像下面所示

    因为每次访问时都会更新这些位,因此由硬件来设置它们非常重要。一旦某个位被设置为 1,就会一直保持 1 直到操作系统下次来修改此位。

    如果硬件没有这些位,那么可以使用操作系统的缺页中断时钟中断机制来进行模拟。当启动一个进程时,将其所有的页面都标记为不在内存;一旦访问任何一个页面就会引发一次缺页中断,此时操作系统就可以设置 R 位(在它的内部表中),修改页表项使其指向正确的页面,并设置为 READ ONLY 模式,然后重新启动引起缺页中断的指令。如果页面随后被修改,就会发生另一个缺页异常。从而允许操作系统设置 M 位并把页面的模式设置为 READ/WRITE

    可以用 R 位和 M 位来构造一个简单的页面置换算法:当启动一个进程时,操作系统将其所有页面的两个位都设置为 0。R 位定期的被清零(在每个时钟中断)。用来将最近未引用的页面和已引用的页面分开。

    当出现缺页中断后,操作系统会检查所有的页面,并根据它们的 R 位和 M 位将当前值分为四类:

    • 第 0 类:没有引用 R,没有修改 M
    • 第 1 类:没有引用 R,已修改 M
    • 第 2 类:引用 R ,没有修改 M
    • 第 3 类:已被访问 R,已被修改 M

    尽管看起来好像无法实现第一类页面,但是当第三类页面的 R 位被时钟中断清除时,它们就会发生。时钟中断不会清除 M 位,因为需要这个信息才能知道是否写回磁盘中。清除 R 但不清除 M 会导致出现一类页面。

    NRU(Not Recently Used) 算法从编号最小的非空类中随机删除一个页面。此算法隐含的思想是,在一个时钟内(约 20 ms)淘汰一个已修改但是没有被访问的页面要比一个大量引用的未修改页面好,NRU 的主要优点是易于理解并且能够有效的实现

    先进先出页面置换算法

    另一种开销较小的方式是使用 FIFO(First-In,First-Out) 算法,这种类型的数据结构也适用在页面置换算法中。由操作系统维护一个所有在当前内存中的页面的链表,最早进入的放在表头,最新进入的页面放在表尾。在发生缺页异常时,会把头部的页移除并且把新的页添加到表尾。

    先进先出页面可能是最简单的页面替换算法了。在这种算法中,操作系统会跟踪链表中内存中的所有页。下面我们举个例子看一下(这个算法我刚开始看的时候有点懵逼,后来才看懂,我还是很菜)

    • 初始化的时候,没有任何页面,所以第一次的时候会检查页面 1 是否位于链表中,没有在链表中,那么就是 MISS,页面1 进入链表,链表的先进先出的方向如图所示。
    • 类似的,第二次会先检查页面 2 是否位于链表中,没有在链表中,那么页面 2 进入链表,状态为 MISS,依次类推。
    • 我们来看第四次,此时的链表为 1 2 3,第四次会检查页面 2 是否位于链表中,经过检索后,发现 2 在链表中,那么状态就是 HIT,并不会再进行入队和出队操作,第五次也是一样的。
    • 下面来看第六次,此时的链表还是 1 2 3,因为之前没有执行进入链表操作,页面 5 会首先进行检查,发现链表中没有页面 5 ,则执行页面 5 的进入链表操作,页面 2 执行出链表的操作,执行完成后的链表顺序为 2 3 5

    第二次机会页面置换算法

    我们上面学到的 FIFO 链表页面有个缺陷,那就是出链和入链并不会进行 check 检查,这样就会容易把经常使用的页面置换出去,为了避免这一问题,我们对该算法做一个简单的修改:我们检查最老页面的 R 位,如果是 0 ,那么这个页面就是最老的而且没有被使用,那么这个页面就会被立刻换出。如果 R 位是 1,那么就清除此位,此页面会被放在链表的尾部,修改它的装入时间就像刚放进来的一样。然后继续搜索。

    这种算法叫做 第二次机会(second chance)算法,就像下面这样,我们看到页面 A 到 H 保留在链表中,并按到达内存的时间排序。

    a)按照先进先出的方法排列的页面;b)在时刻 20 处发生缺页异常中断并且 A 的 R 位已经设置时的页面链表。

    假设缺页异常发生在时刻 20 处,这时最老的页面是 A ,它是在 0 时刻到达的。如果 A 的 R 位是 0,那么它将被淘汰出内存,或者把它写回磁盘(如果它已经被修改过),或者只是简单的放弃(如果它是未被修改过)。另一方面,如果它的 R 位已经设置了,则将 A 放到链表的尾部并且重新设置装入时间为当前时刻(20 处),然后清除 R 位。然后从 B 页面开始继续搜索合适的页面。

    寻找第二次机会的是在最近的时钟间隔中未被访问过的页面。如果所有的页面都被访问过,该算法就会被简化为单纯的 FIFO 算法。具体来说,假设图 a 中所有页面都设置了 R 位。操作系统将页面依次移到链表末尾,每次都在添加到末尾时清除 R 位。最后,算法又会回到页面 A,此时的 R 位已经被清除,那么页面 A 就会被执行出链处理,因此算法能够正常结束。

    时钟页面置换算法

    即使上面提到的第二次页面置换算法也是一种比较合理的算法,但它经常要在链表中移动页面,既降低了效率,而且这种算法也不是必须的。一种比较好的方式是把所有的页面都保存在一个类似钟面的环形链表中,一个表针指向最老的页面。如下图所示

    当缺页错误出现时,算法首先检查表针指向的页面,如果它的 R 位是 0 就淘汰该页面,并把新的页面插入到这个位置,然后把表针向前移动一位;如果 R 位是 1 就清除 R 位并把表针前移一个位置。重复这个过程直到找到了一个 R 位为 0 的页面位置。了解这个算法的工作方式,就明白为什么它被称为 时钟(clokc)算法了。

    最近最少使用页面置换算法

    最近最少使用页面置换算法的一个解释会是下面这样:在前面几条指令中频繁使用的页面和可能在后面的几条指令中被使用。反过来说,已经很久没有使用的页面有可能在未来一段时间内仍不会被使用。这个思想揭示了一个可以实现的算法:在缺页中断时,置换未使用时间最长的页面。这个策略称为 LRU(Least Recently Used) ,最近最少使用页面置换算法。

    虽然 LRU 在理论上是可以实现的,但是从长远看来代价比较高。为了完全实现 LRU,会在内存中维护一个所有页面的链表,最频繁使用的页位于表头,最近最少使用的页位于表尾。困难的是在每次内存引用时更新整个链表。在链表中找到一个页面,删除它,然后把它移动到表头是一个非常耗时的操作,即使使用硬件来实现也是一样的费时。

    然而,还有其他方法可以通过硬件实现 LRU。让我们首先考虑最简单的方式。这个方法要求硬件有一个 64 位的计数器,它在每条指令执行完成后自动加 1,每个页表必须有一个足够容纳这个计数器值的域。在每次访问内存后,将当前的值保存到被访问页面的页表项中。一旦发生缺页异常,操作系统就检查所有页表项中计数器的值,找到值最小的一个页面,这个页面就是最少使用的页面。

    用软件模拟 LRU

    尽管上面的 LRU 算法在原则上是可以实现的,但是很少有机器能够拥有那些特殊的硬件。上面是硬件的实现方式,那么现在考虑要用软件来实现 LRU 。一种可以实现的方案是 NFU(Not Frequently Used,最不常用)算法。它需要一个软件计数器来和每个页面关联,初始化的时候是 0 。在每个时钟中断时,操作系统会浏览内存中的所有页,会将每个页面的 R 位(0 或 1)加到它的计数器上。这个计数器大体上跟踪了各个页面访问的频繁程度。当缺页异常出现时,则置换计数器值最小的页面。

    NFU 最主要的问题是它不会忘记任何东西,想一下是不是这样?例如,在一个多次(扫描)的编译器中,在第一遍扫描中频繁使用的页面会在后续的扫描中也有较高的计数。事实上,如果第一次扫描的执行时间恰好是各次扫描中最长的,那么后续遍历的页面的统计次数总会比第一次页面的统计次数。结果是操作系统将置换有用的页面而不是不再使用的页面。

    幸运的是只需要对 NFU 做一个简单的修改就可以让它模拟 LRU,这个修改有两个步骤

    • 首先,在 R 位被添加进来之前先把计数器右移一位;
    • 第二步,R 位被添加到最左边的位而不是最右边的位。

    修改以后的算法称为 老化(aging) 算法,下图解释了老化算法是如何工作的。

    我们假设在第一个时钟周期内页面 0 - 5 的 R 位依次是 1,0,1,0,1,1,(也就是页面 0 是 1,页面 1 是 0,页面 2 是 1 这样类推)。也就是说,在 0 个时钟周期到 1 个时钟周期之间,0,2,4,5 都被引用了,从而把它们的 R 位设置为 1,剩下的设置为 0 。在相关的六个计数器被右移之后 R 位被添加到 左侧 ,就像上图中的 a。剩下的四列显示了接下来的四个时钟周期内的六个计数器变化。

    当缺页异常出现时,将置换(就是移除)计数器值最小的页面。如果一个页面在前面 4 个时钟周期内都没有被访问过,那么它的计数器应该会有四个连续的 0 ,因此它的值肯定要比前面 3 个时钟周期内都没有被访问过的页面的计数器小。

    这个算法与 LRU 算法有两个重要的区别:看一下上图中的 e,第三列和第五列

    它们在两个时钟周期内都没有被访问过,在此之前的时钟周期内都引用了两个页面。根据 LRU 算法,如果需要置换的话,那么应该在这两个页面中选择一个。那么问题来了,我萌应该选择哪个?现在的问题是我们不知道时钟周期 1 到时钟周期 2 内它们中哪个页面是后被访问到的。因为在每个时钟周期内只记录了一位,所以无法区分在一个时钟周期内哪个页面最早被引用,哪个页面是最后被引用的。因此,我们能做的就是置换页面3因为页面 3 在周期 0 - 1 内都没有被访问过,而页面 5 却被引用过

    LRU 与老化之前的第 2 个区别是,在老化期间,计数器具有有限数量的位(这个例子中是 8 位),这就限制了以往的访问记录。如果两个页面的计数器都是 0 ,那么我们可以随便选择一个进行置换。实际上,有可能其中一个页面的访问次数实在 9 个时钟周期以前,而另外一个页面是在 1000 个时钟周期之前,但是我们却无法看到这些。在实际过程中,如果时钟周期是 20 ms,8 位一般是够用的。所以我们经常拿 20 ms 来举例。

    工作集页面置换算法

    在最单纯的分页系统中,刚启动进程时,在内存中并没有页面。此时如果 CPU 尝试匹配第一条指令,就会得到一个缺页异常,使操作系统装入含有第一条指令的页面。其他的错误比如 全局变量堆栈 引起的缺页异常通常会紧接着发生。一段时间以后,进程需要的大部分页面都在内存中了,此时进程开始在较少的缺页异常环境中运行。这个策略称为 请求调页(demand paging),因为页面是根据需要被调入的,而不是预先调入的。

    在一个大的地址空间中系统的读所有的页面,将会造成很多缺页异常,因此会导致没有足够的内存来容纳这些页面。不过幸运的是,大部分进程不是这样工作的,它们都会以局部性方式(locality of reference) 来访问,这意味着在执行的任何阶段,程序只引用其中的一小部分。

    一个进程当前正在使用的页面的集合称为它的 工作集(working set),如果整个工作集都在内存中,那么进程在运行到下一运行阶段(例如,编译器的下一遍扫面)之前,不会产生很多缺页中断。如果内存太小从而无法容纳整个工作集,那么进程的运行过程中会产生大量的缺页中断,会导致运行速度也会变得缓慢。因为通常只需要几纳秒就能执行一条指令,而通常需要十毫秒才能从磁盘上读入一个页面。如果一个程序每 10 ms 只能执行一到两条指令,那么它将需要很长时间才能运行完。如果只是执行几条指令就会产生中断,那么就称作这个程序产生了 颠簸(thrashing)

    在多道程序的系统中,通常会把进程移到磁盘上(即从内存中移走所有的页面),这样可以让其他进程有机会占用 CPU 。有一个问题是,当进程想要再次把之前调回磁盘的页面调回内存怎么办?从技术的角度上来讲,并不需要做什么,此进程会一直产生缺页中断直到它的工作集 被调回内存。然后,每次装入一个进程需要 20、100 甚至 1000 次缺页中断,速度显然太慢了,并且由于 CPU 需要几毫秒时间处理一个缺页中断,因此由相当多的 CPU 时间也被浪费了。

    因此,不少分页系统中都会设法跟踪进程的工作集,确保这些工作集在进程运行时被调入内存。这个方法叫做 工作集模式(working set model)。它被设计用来减少缺页中断的次数的。在进程运行前首先装入工作集页面的这一个过程被称为 预先调页(prepaging),工作集是随着时间来变化的。

    根据研究表明,大多数程序并不是均匀的访问地址空间的,而访问往往是集中于一小部分页面。一次内存访问可能会取出一条指令,也可能会取出数据,或者是存储数据。在任一时刻 t,都存在一个集合,它包含所哟欧最近 k 次内存访问所访问过的页面。这个集合 w(k,t) 就是工作集。因为最近 k = 1次访问肯定会访问最近 k > 1 次访问所访问过的页面,所以 w(k,t) 是 k 的单调递减函数。随着 k 的增大,w(k,t) 是不会无限变大的,因为程序不可能访问比所能容纳页面数量上限还多的页面。

    事实上大多数应用程序只会任意访问一小部分页面集合,但是这个集合会随着时间而缓慢变化,所以为什么一开始曲线会快速上升而 k 较大时上升缓慢。为了实现工作集模型,操作系统必须跟踪哪些页面在工作集中。一个进程从它开始执行到当前所实际使用的 CPU 时间总数通常称作 当前实际运行时间。进程的工作集可以被称为在过去的 t 秒实际运行时间中它所访问过的页面集合。

    下面来简单描述一下工作集的页面置换算法,基本思路就是找出一个不在工作集中的页面并淘汰它。下面是一部分机器页表

    因为只有那些在内存中的页面才可以作为候选者被淘汰,所以该算法忽略了那些不在内存中的页面。每个表项至少包含两条信息:上次使用该页面的近似时间和 R(访问)位。空白的矩形表示该算法不需要其他字段,例如页框数量、保护位、修改位。

    算法的工作流程如下,假设硬件要设置 R 和 M 位。同样的,在每个时钟周期内,一个周期性的时钟中断会使软件清除 Referenced(引用)位。在每个缺页异常,页表会被扫描以找出一个合适的页面把它置换。

    随着每个页表项的处理,都需要检查 R 位。如果 R 位是 1,那么就会将当前时间写入页表项的 上次使用时间域,表示的意思就是缺页异常发生时页面正在被使用。因为页面在当前时钟周期内被访问过,那么它应该出现在工作集中而不是被删除(假设 t 是横跨了多个时钟周期)。

    如果 R 位是 0 ,那么在当前的时钟周期内这个页面没有被访问过,应该作为被删除的对象。为了查看是否应该将其删除,会计算其使用期限(当前虚拟时间 - 上次使用时间),来用这个时间和 t 进行对比。如果使用期限大于 t,那么这个页面就不再工作集中,而使用新的页面来替换它。然后继续扫描更新剩下的表项。

    然而,如果 R 位是 0 但是使用期限小于等于 t,那么此页应该在工作集中。此时就会把页面临时保存起来,但是会记生存时间最长(即上次使用时间的最小值)的页面。如果扫描完整个页表却没有找到适合被置换的页面,也就意味着所有的页面都在工作集中。在这种情况下,如果找到了一个或者多个 R = 0 的页面,就淘汰生存时间最长的页面。最坏的情况下是,在当前时钟周期内,所有的页面都被访问过了(也就是都有 R = 1),因此就随机选择一个页面淘汰,如果有的话最好选一个未被访问的页面,也就是干净的页面。

    工作集时钟页面置换算法

    当缺页异常发生后,需要扫描整个页表才能确定被淘汰的页面,因此基本工作集算法还是比较浪费时间的。一个对基本工作集算法的提升是基于时钟算法但是却使用工作集的信息,这种算法称为WSClock(工作集时钟)。由于它的实现简单并且具有高性能,因此在实践中被广泛应用。

    与时钟算法一样,所需的数据结构是一个以页框为元素的循环列表,就像下面这样

    最初的时候,该表是空的。当装入第一个页面后,把它加载到该表中。随着更多的页面的加入,它们形成一个环形结构。每个表项包含来自基本工作集算法的上次使用时间,以及 R 位(已标明)和 M 位(未标明)。

    与时钟算法一样,在每个缺页异常时,首先检查指针指向的页面。如果 R 位被是设置为 1,该页面在当前时钟周期内就被使用过,那么该页面就不适合被淘汰。然后把该页面的 R 位置为 0,指针指向下一个页面,并重复该算法。该事件序列化后的状态参见图 b。

    现在考虑指针指向的页面 R = 0 时会发生什么,参见图 c,如果页面的使用期限大于 t 并且页面为被访问过,那么这个页面就不会在工作集中,并且在磁盘上会有一个此页面的副本。申请重新调入一个新的页面,并把新的页面放在其中,如图 d 所示。另一方面,如果页面被修改过,就不能重新申请页面,因为这个页面在磁盘上没有有效的副本。为了避免由于调度写磁盘操作引起的进程切换,指针继续向前走,算法继续对下一个页面进行操作。毕竟,有可能存在一个老的,没有被修改过的页面可以立即使用。

    原则上来说,所有的页面都有可能因为磁盘I/O 在某个时钟周期内被调度。为了降低磁盘阻塞,需要设置一个限制,即最大只允许写回 n 个页面。一旦达到该限制,就不允许调度新的写操作。

    那么就有个问题,指针会绕一圈回到原点的,如果回到原点,它的起始点会发生什么?这里有两种情况:

    • 至少调度了一次写操作
    • 没有调度过写操作

    在第一种情况中,指针仅仅是不停的移动,寻找一个未被修改过的页面。由于已经调度了一个或者多个写操作,最终会有某个写操作完成,它的页面会被标记为未修改。置换遇到的第一个未被修改过的页面,这个页面不一定是第一个被调度写操作的页面,因为硬盘驱动程序为了优化性能可能会把写操作重排序。

    对于第二种情况,所有的页面都在工作集中,否则将至少调度了一个写操作。由于缺乏额外的信息,最简单的方法就是置换一个未被修改的页面来使用,扫描中需要记录未被修改的页面的位置,如果不存在未被修改的页面,就选定当前页面并把它写回磁盘。

    页面置换算法小结

    我们到现在已经研究了各种页面置换算法,现在我们来一个简单的总结,算法的总结归纳如下

    算法注释
    最优算法不可实现,但可以用作基准
    NRU(最近未使用) 算法和 LRU 算法很相似
    FIFO(先进先出) 算法有可能会抛弃重要的页面
    第二次机会算法比 FIFO 有较大的改善
    时钟算法实际使用
    LRU(最近最少)算法比较优秀,但是很难实现
    NFU(最不经常食用)算法和 LRU 很类似
    老化算法近似 LRU 的高效算法
    工作集算法实施起来开销很大
    工作集时钟算法比较有效的算法
    • 最优算法在当前页面中置换最后要访问的页面。不幸的是,没有办法来判定哪个页面是最后一个要访问的,因此实际上该算法不能使用。然而,它可以作为衡量其他算法的标准。

    • NRU 算法根据 R 位和 M 位的状态将页面氛围四类。从编号最小的类别中随机选择一个页面。NRU 算法易于实现,但是性能不是很好。存在更好的算法。

    • FIFO 会跟踪页面加载进入内存中的顺序,并把页面放入一个链表中。有可能删除存在时间最长但是还在使用的页面,因此这个算法也不是一个很好的选择。

    • 第二次机会算法是对 FIFO 的一个修改,它会在删除页面之前检查这个页面是否仍在使用。如果页面正在使用,就会进行保留。这个改进大大提高了性能。

    • 时钟 算法是第二次机会算法的另外一种实现形式,时钟算法和第二次算法的性能差不多,但是会花费更少的时间来执行算法。

    • LRU 算法是一个非常优秀的算法,但是没有特殊的硬件(TLB)很难实现。如果没有硬件,就不能使用 LRU 算法。

    • NFU 算法是一种近似于 LRU 的算法,它的性能不是非常好。

    • 老化 算法是一种更接近 LRU 算法的实现,并且可以更好的实现,因此是一个很好的选择

    • 最后两种算法都使用了工作集算法。工作集算法提供了合理的性能开销,但是它的实现比较复杂。WSClock 是另外一种变体,它不仅能够提供良好的性能,而且可以高效地实现。

    总之,最好的算法是老化算法和WSClock算法。他们分别是基于 LRU 和工作集算法。他们都具有良好的性能并且能够被有效的实现。还存在其他一些好的算法,但实际上这两个可能是最重要的。

    文件系统中的算法

    文件系统在备份的过程中会使用到算法,文件备份分为逻辑转储和物理转储

    物理转储和逻辑转储

    物理转储的主要优点是简单、极为快速(基本上是以磁盘的速度运行),缺点是全量备份,不能跳过指定目录,也不能增量转储,也不能恢复个人文件的请求。因此句大多数情况下不会使用物理转储,而使用逻辑转储

    逻辑转储(logical dump)从一个或几个指定的目录开始,递归转储自指定日期开始后更改的文件和目录。因此,在逻辑转储中,转储磁盘上有一系列经过仔细识别的目录和文件,这使得根据请求轻松还原特定文件或目录。

    既然逻辑转储是最常用的方式,那么下面就让我们研究一下逻辑转储的通用算法。此算法在 UNIX 系统上广为使用,如下图所示

    待转储的文件系统,其中方框代表目录,圆圈代表文件。黄色的项目表是自上次转储以来修改过。每个目录和文件都被标上其 inode 号。

    此算法会转储位于修改文件或目录路径上的所有目录(也包括未修改的目录),原因有两个。第一是能够在不同电脑的文件系统中恢复转储的文件。通过这种方式,转储和重新存储的程序能够用来在两个电脑之间传输整个文件系统。第二个原因是能够对单个文件进行增量恢复

    逻辑转储算法需要维持一个 inode 为索引的位图(bitmap),每个 inode 包含了几位。随着算法的进行,位图中的这些位会被设置或清除。算法的执行分成四个阶段。第一阶段从起始目录(本例为根目录)开始检查其中所有的目录项。对每一个修改过的文件,该算法将在位图中标记其 inode。算法还会标记并递归检查每一个目录(不管是否修改过)。

    在第一阶段结束时,所有修改过的文件和全部目录都在位图中标记了,如下图所示

    理论上来说,第二阶段再次递归遍历目录树,并去掉目录树中任何不包含被修改过的文件或目录的标记。本阶段执行的结果如下

    注意,inode 编号为 10、11、14、27、29 和 30 的目录已经被去掉了标记,因为它们所包含的内容没有修改。它们也不会转储。相反,inode 编号为 5 和 6 的目录本身尽管没有被修改过也要被转储,因为在新的机器上恢复当日的修改时需要这些信息。为了提高算法效率,可以将这两阶段的目录树遍历合二为一。

    现在已经知道了哪些目录和文件必须被转储了,这就是上图 b 中标记的内容,第三阶段算法将以节点号为序,扫描这些 inode 并转储所有标记为需转储的目录,如下图所示

    为了进行恢复,每个被转储的目录都用目录的属性(所有者、时间)作为前缀。

    最后,在第四阶段,上图中被标记的文件也被转储,同样,由其文件属性作为前缀。至此,转储结束。

    从转储磁盘上还原文件系统非常简单。一开始,需要在磁盘上创建空文件系统。然后恢复最近一次的完整转储。由于磁带上最先出现目录,所以首先恢复目录,给出文件系统的框架(skeleton),然后恢复文件系统本身。在完整存储之后是第一次增量存储,然后是第二次重复这一过程,以此类推。

    尽管逻辑存储十分简单,但是也会有一些棘手的问题。首先,既然空闲块列表并不是一个文件,那么在所有被转储的文件恢复完毕之后,就需要从零开始重新构造。

    另外一个问题是关于链接。如果文件链接了两个或者多个目录,而文件只能还原一次,那么并且所有指向该文件的目录都必须还原。

    还有一个问题是,UNIX 文件实际上包含了许多 空洞(holes)。打开文件,写几个字节,然后找到文件中偏移了一定距离的地址,又写入更多的字节,这么做是合法的。但两者之间的这些块并不属于文件本身,从而也不应该在其上进行文件转储和恢复。

    最后,无论属于哪一个目录,特殊文件,命名管道以及类似的文件都不应该被转储。

    I/O 中的算法

    在 I/O 的磁盘调度中也出现过很多算法,关于寻址和磁盘臂的转动都会对算法产生影响,下面我们就来一起看下

    一般情况下,影响磁盘快读写的时间由下面几个因素决定

    • 寻道时间 - 寻道时间指的就是将磁盘臂移动到需要读取磁盘块上的时间
    • 旋转延迟 - 等待合适的扇区旋转到磁头下所需的时间
    • 实际数据的读取或者写入时间

    这三种时间参数也是磁盘寻道的过程。一般情况下,寻道时间对总时间的影响最大,所以,有效的降低寻道时间能够提高磁盘的读取速度。

    如果磁盘驱动程序每次接收一个请求并按照接收顺序完成请求,这种处理方式也就是 先来先服务(First-Come, First-served, FCFS) ,这种方式很难优化寻道时间。因为每次都会按照顺序处理,不管顺序如何,有可能这次读完后需要等待一个磁盘旋转一周才能继续读取,而其他柱面能够马上进行读取,这种情况下每次请求也会排队。

    通常情况下,磁盘在进行寻道时,其他进程会产生其他的磁盘请求。磁盘驱动程序会维护一张表,表中会记录着柱面号当作索引,每个柱面未完成的请求会形成链表,链表头存放在表的相应表项中。

    一种对先来先服务的算法改良的方案是使用 最短路径优先(SSF) 算法,下面描述了这个算法。

    假如我们在对磁道 6 号进行寻址时,同时发生了对 11 , 2 , 4, 14, 8, 15, 3 的请求,如果采用先来先服务的原则,如下图所示

    我们可以计算一下磁盘臂所跨越的磁盘数量为 5 + 9 + 2 + 10 + 6 + 7 + 12 = 51,相当于是跨越了 51 次盘面,如果使用最短路径优先,我们来计算一下跨越的盘面

    跨越的磁盘数量为 4 + 1 + 1 + 4 + 3 + 3 + 1 = 17 ,相比 51 足足省了两倍的时间。

    但是,最短路径优先的算法也不是完美无缺的,这种算法照样存在问题,那就是优先级 问题,

    这里有一个原型可以参考就是我们日常生活中的电梯,电梯使用一种电梯算法(elevator algorithm) 来进行调度,从而满足协调效率和公平性这两个相互冲突的目标。电梯一般会保持向一个方向移动,直到在那个方向上没有请求为止,然后改变方向。

    电梯算法需要维护一个二进制位,也就是当前的方向位:UP(向上)或者是 DOWN(向下)。当一个请求处理完成后,磁盘或电梯的驱动程序会检查该位,如果此位是 UP 位,磁盘臂或者电梯仓移到下一个更高跌未完成的请求。如果高位没有未完成的请求,则取相反方向。当方向位是 DOWN时,同时存在一个低位的请求,磁盘臂会转向该点。如果不存在的话,那么它只是停止并等待。

    我们举个例子来描述一下电梯算法,比如各个柱面得到服务的顺序是 4,7,10,14,9,6,3,1 ,那么它的流程图如下

    所以电梯算法需要跨越的盘面数量是 3 + 3 + 4 + 5 + 3 + 3 + 1 = 22

    电梯算法通常情况下不如 SSF 算法。

    一些磁盘控制器为软件提供了一种检查磁头下方当前扇区号的方法,使用这样的控制器,能够进行另一种优化。如果对一个相同的柱面有两个或者多个请求正等待处理,驱动程序可以发出请求读写下一次要通过磁头的扇区。

    这里需要注意一点,当一个柱面有多条磁道时,相继的请求可能针对不同的磁道,这种选择没有代价,因为选择磁头不需要移动磁盘臂也没有旋转延迟。

    对于磁盘来说,最影响性能的就是寻道时间和旋转延迟,所以一次只读取一个或两个扇区的效率是非常低的。出于这个原因,许多磁盘控制器总是读出多个扇区并进行高速缓存,即使只请求一个扇区时也是这样。一般情况下读取一个扇区的同时会读取该扇区所在的磁道或者是所有剩余的扇区被读出,读出扇区的数量取决于控制器的高速缓存中有多少可用的空间。

    磁盘控制器的高速缓存和操作系统的高速缓存有一些不同,磁盘控制器的高速缓存用于缓存没有实际被请求的块,而操作系统维护的高速缓存由显示地读出的块组成,并且操作系统会认为这些块在近期仍然会频繁使用。

    当同一个控制器上有多个驱动器时,操作系统应该为每个驱动器都单独的维护一个未完成的请求表。一旦有某个驱动器闲置时,就应该发出一个寻道请求来将磁盘臂移到下一个被请求的柱面。如果下一个寻道请求到来时恰好没有磁盘臂处于正确的位置,那么驱动程序会在刚刚完成传输的驱动器上发出一个新的寻道命令并等待,等待下一次中断到来时检查哪个驱动器处于闲置状态。

    死锁中的算法

    在死锁的处理策略中,其中一点是忽略死锁带来的影响(惊呆了),出现过一个叫做鸵鸟算法

    最简单的解决办法就是使用鸵鸟算法(ostrich algorithm),把头埋在沙子里,假装问题根本没有发生。每个人看待这个问题的反应都不同。数学家认为死锁是不可接受的,必须通过有效的策略来防止死锁的产生。工程师想要知道问题发生的频次,系统因为其他原因崩溃的次数和死锁带来的严重后果。如果死锁发生的频次很低,而经常会由于硬件故障、编译器错误等其他操作系统问题导致系统崩溃,那么大多数工程师不会修复死锁。

    在死锁的检测中出现过一些算法

    每种类型多个资源的死锁检测方式

    如果有多种相同的资源存在,就需要采用另一种方法来检测死锁。可以通过构造一个矩阵来检测从 P1 -> Pn 这 n 个进程中的死锁。

    现在我们提供一种基于矩阵的算法来检测从 P1 到 Pn 这 n 个进程中的死锁。假设资源类型为 m,E1 代表资源类型1,E2 表示资源类型 2 ,Ei 代表资源类型 i (1 <= i <= m)。E 表示的是 现有资源向量(existing resource vector),代表每种已存在的资源总数。

    现在我们就需要构造两个数组:C 表示的是当前分配矩阵(current allocation matrix) ,R 表示的是 请求矩阵(request matrix)。Ci 表示的是 Pi 持有每一种类型资源的资源数。所以,Cij 表示 Pi 持有资源 j 的数量。Rij 表示 Pi 所需要获得的资源 j 的数量

    一般来说,已分配资源 j 的数量加起来再和所有可供使用的资源数相加 = 该类资源的总数。

    死锁的检测就是基于向量的比较。每个进程起初都是没有被标记过的,算法会开始对进程做标记,进程被标记后说明进程被执行了,不会进入死锁,当算法结束时,任何没有被标记过的进程都会被判定为死锁进程。

    上面我们探讨了两种检测死锁的方式,那么现在你知道怎么检测后,你何时去做死锁检测呢?一般来说,有两个考量标准:

    • 每当有资源请求时就去检测,这种方式会占用昂贵的 CPU 时间。
    • 每隔 k 分钟检测一次,或者当 CPU 使用率降低到某个标准下去检测。考虑到 CPU 效率的原因,如果死锁进程达到一定数量,就没有多少进程可以运行,所以 CPU 会经常空闲。

    还有死锁避免的算法

    银行家算法

    银行家算法是 Dijkstra 在 1965 年提出的一种调度算法,它本身是一种死锁的调度算法。它的模型是基于一个城镇中的银行家,银行家向城镇中的客户承诺了一定数量的贷款额度。算法要做的就是判断请求是否会进入一种不安全的状态。如果是,就拒绝请求,如果请求后系统是安全的,就接受该请求。

    比如下面的例子,银行家一共为所有城镇居民提供了 15 单位个贷款额度,一个单位表示 1k 美元,如下所示

    城镇居民都喜欢做生意,所以就会涉及到贷款,每个人能贷款的最大额度不一样,在某一时刻,A/B/C/D 的贷款金额如下

    上面每个人的贷款总额加起来是 13,马上接近 15,银行家只能给 A 和 C 进行放贷,可以拖着 B 和 D、所以,可以让 A 和 C 首先完成,释放贷款额度,以此来满足其他居民的贷款。这是一种安全的状态。

    如果每个人的请求导致总额会超过甚至接近 15 ,就会处于一种不安全的状态,如下所示

    这样,每个人还能贷款至少 2 个单位的额度,如果其中有一个人发起最大额度的贷款请求,就会使系统处于一种死锁状态。

    这里注意一点:不安全状态并不一定引起死锁,由于客户不一定需要其最大的贷款额度,但是银行家不敢抱着这种侥幸心理。

    银行家算法就是对每个请求进行检查,检查是否请求会引起不安全状态,如果不会引起,那么就接受该请求;如果会引起,那么就推迟该请求。

    类似的,还有多个资源的银行家算法,读者可以自行了解。

    展开全文
  • Java使用遗传算法实现智能组卷

    千次阅读 多人点赞 2021-02-26 17:56:20
    用户选择年级(非必传)、科目(非必传)、题目分类(知识点初版没有)、每个题型对应的题型数、难度系数,一键智能生成试卷,如下图,需要使用到遗传算法来实现出题规则 1.遗传算法: 1.0 参考博文: 理论概念详解:...
  • 使用森林优化算法的特征选择

    千次阅读 2017-10-16 16:01:08
    转自:...摘要:特征选择作为组合优化问题是数据挖掘中的重要预处理步骤,借助于去除不相关冗余特征,可以提高学习算法的性能。由于进化算法被报告适用于优化任务,所以森林优化算法(FOA) - 最初
  • 网上有很多博客讲解遗传算法,但是大都只是“点到即止”,虽然给了一些代码实现,但也是“浅尝辄止”,没能很好地帮助大家进行扩展应用,抑或是进行深入的研究。 这是我的开篇之作~之前没有写博客的习惯,一般是将...
  • 使用遗传算法解决图着色问题

    万次阅读 2021-01-04 11:05:09
    在图论中,图是对象的结构集合,用于表示...图着色任务可以简单概括为:为图中的每个节点分配颜色,并保证相连接的节点对不会使用相同的颜色,同时,我们希望使用尽可能少的颜色。使用遗传算法解决图着色问题。
  • 十大排序算法

    万次阅读 多人点赞 2021-08-20 13:37:46
    如果第一个比第二个大(小),就交换它们个 对每一对相邻元素作同样的工作,从开始第一对到尾部的最后一对,这样在最后的元素应该会是最大(小)的数 重复步骤1~2,重复次数等于数组的长度,直到排序完成 代码实现 ...
  • 页面置换算法(FIFO&LRU)

    万次阅读 多人点赞 2020-12-27 11:23:43
    页面置换算法 实验目的 1.通过模拟实现几种基本页面置换的算法,了解虚拟存储技术的特点。 2.通过置换算法的模拟和比较,进一步了解它们的优...(3)计算并输出以上两种算法分配不同内存物理块数时(讨论内存物理 块
  • 个性推荐算法总结

    万次阅读 多人点赞 2019-04-11 23:24:58
    读书笔记 |《推荐系统实践》- 个性推荐系统总结 对于推荐系统,本文总结内容,如下图所示: 一、什么是推荐系统 1. 为什么需要推荐系统 为了解决互联网时代下的信息超载问题。 2. 搜索引擎与推荐系统 ...
  • C++ STL标准库:std::vector 使用详解

    万次阅读 多人点赞 2020-12-15 22:02:12
    使用示例3. 构造、析构、赋值3.1 std::vector::vector 构造函数3.2 std::vector::~vector 析构函数3.3 std::vector::operator= “=”符号4. Iterators 迭代器4.1 std::vector::begin4.2 std::vector::end4.3 std::...
  • 分配功能要求至少使用两种算法用户可以选择使用。 回收功能: 空闲块的合并:即紧凑功能,用以消除碎片。当做碎片整理时,需要跟踪分配的空间,修改其引用以保证引用的正确性。...
  • 深入理解Java虚拟机-垃圾回收器与内存分配策略

    万次阅读 多人点赞 2020-01-04 13:08:32
    文章目录概述对象已死吗引用计数法可达性分析算法再谈引用生存还是死亡回收方法区垃圾收集算法标记-清除算法复制算法标记-整理算法分代收集算法新生代(Young generation)老年代(Old generation)永久代...
  • 算法和数据结构》算法零基础五十题讲解

    万次阅读 多人点赞 2021-10-02 10:52:03
    「 让天下没有难学的算法
  • 超硬核!操作系统学霸笔记,考试复习面试全靠它

    万次阅读 多人点赞 2021-03-22 18:43:49
    之后会发布基于基础知识的大部分算法的模拟代码合集,敬请关注。
  • 本文代码实现基本按照《数据结构》课本目录顺序,外加大量的复杂算法实现,一篇文章足够。能换你一个收藏了吧?
  • 使用机器学习和数据挖掘算法进行数据处理

    万次阅读 多人点赞 2017-12-12 21:08:54
    数据挖掘和机器学习是进行数据处理的非常有用的工具,当代的好多数据都使用两种方法。但是这两种方法却包含很多模型和方法,对于初学者来说,面对这些模型总是无从下手。因此,后面的论述主要以处理数据的流程入手...
  • 实验六:《操作系统》之进程调度算法的模拟实现

    千次阅读 多人点赞 2020-06-28 15:23:13
    Part6. 进程调度算法的模拟实现 往期回顾: Part0. 实验环境 Part1-1....Part1-2....Part2....Part3....Part4....编程模拟实现传统的进程调度算法:FCFS调度算法、SPF调度算法、RR调度算法、优先级调度等算法。
  • C语言每日一练 —— 第21天:算法的应用

    万次阅读 多人点赞 2022-01-25 04:59:06
    算法的应用有哪些?为什么大厂注重算法能力?如何学好算法
  • 超硬核!数据结构学霸笔记,考试面试吹牛就靠它

    万次阅读 多人点赞 2021-03-26 11:11:21
    实现统一功能两种算法:时间O(2^N),O(N^10),假设计算机可以运行10^7秒,每秒可执行基本操作10^5次,问可解问题规模各为多少?选哪个更为合适? 计算机一共可执行10^7*10^5=10^12次 第一种:n=log2,(10^12)=12log(2...
  • 聚类算法综述(一)

    万次阅读 2018-12-09 09:55:49
    此外,一些聚类技术使用簇原型(即代表簇中其他对象的数据对象)来刻画簇的特征。聚类分析是研究发现最具有代表性的簇原型的技术。注意:簇的定义是不精确的,而最好的定义依赖于数据的特征和期望的结果。聚类分析与...
  • 算法和数据结构》题海战术篇

    万次阅读 多人点赞 2021-07-15 06:13:43
    刷了 3333 题 算法题 后的一点点经验总结 —— 题不是这么刷的!
  • 最近年,外卖的市场规模持续以超常速度发展。近期美团外卖订单量峰值达到 1600 万,是全球规模最大的外卖平台。目前各外卖平台正在优质供给、配送体验、软件体验等各维度展开全方位的竞争,其中,配送时效、准时率...
  • ArrayList初始化长度

    万次阅读 2018-07-24 11:10:19
    每个ArrayList实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的...在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的...
  • 一般分配模型 ...注意,这个规划问题是整数线性规划(ILP)问题,也就是说,个约束方程,保证每个任务被分配一次。决策变量仅允许取离散值0/1  二、实例分析---穷举法 在讲将匈牙利算法解决任务...
  • 操作系统实验二 银行家算法

    千次阅读 2020-06-05 16:11:43
    3、理解银行家算法是一最有代表性的避免死锁的算法,掌握其实现原理及实现过程。 二、实验环境 虚拟机的Ubuntu 64位系统 三、实验内容 根据银行家算法的基本思想,编写和调试一个实现动态资源分配的模拟程序,并...
  • 牛逼!Java 从入门到精通,超全汇总版

    万次阅读 多人点赞 2021-05-06 19:40:33
    Linux 进行开发的,所以我们这里不探讨 Linux 的方式 Mac 上的相关配置可以看这篇 Windows 上的相关配置可以看这篇 编写入门 Java 程序 这里你需要使用集成开发工具,一是 Eclipse 、一是 IDE,初学者建议使用 ...
  • 图解机器学习 | 聚类算法详解

    千次阅读 2022-03-10 18:42:33
    聚类是最常见的无监督学习算法。本文讲解聚类问题常见算法及用途,包括划分聚类的K-Means算法、K-Medoids算法,层次聚类的Single-Linkage 算法、Complete-Linkage算法,和DB-SCAN算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,963
精华内容 28,385
关键字:

初始化功能,分配功能:要求至少使用两种算法,用户可以选择使用。