状态机/迭代器/LINQ/协程-白红宇

状态机/迭代器/LINQ/协程

阅读量：6421 次

发布时间：2019-06-23

本文共 19298 字，大约阅读时间需要 64 分钟。

状态机

有限状态机（Finite State Machine 或 Finite State Automata)是软件领域中一种重要的工具。

状态机允许一个对象在其内部状态改变时改变它的行为。对象内部状态决定行为方式，对象状态改变行为方式改变,这里强调内部状态。

Command 模式是将命令请求封装成一个为对象，将不同的请求对象参数化以达到同样的调用执行不同的命令；

State 模式是将对象的状态封装成一个对象，是在不同的状态下同样的调用执行不同的操作。

迭代器是一个典型的状态机例子，后续会讲解。

状态机的几种实现方式

switch

class Object StateMachine{    int state;        void work(data){        switch(state){            case 0：                do state 0;// may change state or not                break;            case 1:                do state 1；// may change state or not                break；            default;                throw;        }    }}

优点：简单直观,比较常用

缺点：如果状态较多难以维护

通过容器

class Object StateMachine{    int state;    static readonly method[] methods={StateMachine:workOnState0,workOnState1};//下标代表状态，值代表处理函数        workOnState0(data){        //do    }        workOnState1(date){        //do    }            void work(data){        //check state        method = methods[state];        method.call(data);    }}

优点：代码简单了些，只需要维护状态容器和处理函数

缺点：需要容器，占用内存，状态必须为整型。

还有其他实现方式,最常用的应该是 swich 方式了。

状态机应用：迭代器

现在多数开发语言都支持迭代器。

可以直接用 foreach 遍历的对象都是可迭代对象 Iterable，迭代开始时会自动生成迭代器 Iterator。

在 java 中迭代器有 reset() 接口，但大部分都不支持此接口，通用起见，以下讨论都假设迭代器不支持此接口。

Java

for(Item item:Iterable){    //do something}

在编译时编辑器自动转换为以下代码。

Iterator iter = Iterable.Iterator();while(iter.hasNext()){    Item item=iter.next();    //do something.}

在 C# 中可迭代对象为 IEnumerable 迭代器为 IEnumerator(比 Java 多实现了 IDisposable 等同于 Java 的 Closeable 或 AutoCloseable)

foreach(Item item in IEnumerator){    //do something}

在编译时编辑器自动转换为以下代码。

using(IEnumerator enumerator = IEnumerable.GetEnumerator()){    while(enumerator.MoveNext()){        Item item=iter.Current；        //do something.    }}//释放资源 using 等同于 java 的 try use resource。

python

python 的迭代器实现方式比较特别。只有一个 next() 没有判断是否结束的函数。当结束时抛出 StopIteration 异常。

for i in iterable:     //do something.

等同于

iterator = iter(iterable)try:    item = next(iterator)    # do something.except StopIteration:    pass

通过以上几个迭代器的例子我们可以推断出：

可迭代对象之所以能被 foreach 遍历，都是迭代器的功劳。 foreach 迭代一个元素就是状态机往前步进一次，如此循环，直到符合停止条件。

可迭代对象可以获取迭代器，每次遍历需要 new 一个迭代器。

迭代器可以执行迭代，每个实例只能被单向遍历一遍，不能重复使用。

Java 和 .net 的迭代器在实现方式上有所不同。

Java 的迭代移动在 next() 函数中，.net 的在 MoveNext() 中。比较两种方式，Java 的需要在 hasNext() 和 next() 分别处理逻辑。而 .net 的只要在 MoveNext() 处理两种逻辑，而 Current 属性只是返回已经取到的元素。对于迭代操作而言这种在一个函数中取出元素又返回是否存在的方法能减少很多代码量。对于实现 linq 而言 hasNext() next() 的方式就回略显复杂。

两种方式能够互相转换

hastNext() next() 转为 moveNext() current() close()

// 迭代器class IEnumerator {    int state;    Object current;    Iterator iterator;        boolean moveNext() {        switch (this.state) {            case 0:                if (this.iterator.hasNext()) {                    this.current = this.iterator.next();                    return true;                }                this.close();                return false;            default:                return false;        }    }        Object current(){        return this.current;    }        void close(){        this.current = null;        this.state = -1;    }}

moveNext() current() 转为 hastNext() next()

// 迭代器class Iterator {    boolean checkedNext;    boolean hasNext;    IEnumerator enumerator;        public boolean hasNext() {        if (!this.checkedNext) {            this.hasNext = this.enumerator.moveNext();            this.checkedNext = true;        }        return this.hasNext;    }    public TSource next() {        if (this.hasNext()) {            this.checkedNext = false;            return this.enumerator.current();        }        throw Errors.noSuchElement();    }}

通过代码可以看出，.net 的迭代器是个标准的状态机，而 java 的应该算不上是状态机了。但这点并不影响我们对迭代器的使用。

为何要用迭代器，迭代器有什么好处

懒加载例如给定一些文件名，需要将这些文件批量上传到服务器，要求上传过程中能报告进度，并封装成一个方法。

普通方式

public static int batchUpload(String[] fileNames){    for(String fileName : fileNames){        upload(fileName);    }    return fileNames.length;}//调用void main(){    String[] fileNames = {"a.txt","b.txt"};    int count = batchUpload(fileNames);    System.out.println("uploaded "+ count + "files.");}-- outuploaded 2 files.

迭代器

public class Uploader implements IEnumerator
    
      {    private String[] fileNames;    private int index;        public Uploader(String[] fileNames){        this.fileNames = fileNames;    }        @Override    public boolean moveNext(){        switch (this.state){            case 0:                this.index = -1;                this.state = 1;            case 1:                 this.index++;                 if(this.index >= this.fileNames.length){                     this.close();                     return false;                 }                 upload(this.fileNames[this.index]);                 this.current = this.index + 1;                 return true;            default:                return false;        }    }}//调用void main(){    String[] fileNames = {"a.txt","b.txt"};    Uploader uploader = new Uploader(fileNames);    for(int i : uploader){        System.out.println("uploaded "+ count + "files.");    }}-- outuploaded 1 files.uploaded 2 files.

结论：对比发现，普通的方式只有全部执行后才返回。而迭代器，每迭代一次就返回一个元素，这种特性叫延迟执行（只有在遍历的时候才执行）。以后的所有扩展将充分根据此特性展开。

迭代器应用：linq

项目地址：

简介

LINQ，语言集成查询（Language Integrated Query）最早由微软提出并在 .net 平台实现。

它允许编写程序代码以查询数据库相同的方式操作内存数据。

操作内存数据的只能算是 Linq to Objects。同时微软提出了 Linq to Anything 的概念。只要编写响应的驱动可以用 Linq 查询任何类型的数据。例如：Linq to Xml 可以用 Linq 查询 Xml 文档。Linq to Sql 可以查询 SqlServer 数据库。开源库中也有人开发了响应的其他数据库的驱动。以及现在的 EntityFramework 都是 Linq to Anything 的实现。

此处我们只讨论简单的 Linq to Objects 中的同步实现，这已经足够大大提高我们操作集合的效率。

另外完整的 Linq 应包含更多的内容。比如：

表达式树（数据库查询就是应用的表达式树将 linq 翻译为 sql）。

并行 Linq。

匿名类型。

等等

时代在发展科技在进步，于是 Oracle 终于在 Java8 中引入了 Lambda 和 stream api。

其实 stream api 就是 linq，其实现了同步和并行 linq。

虽然 stream 很优秀，但还是有一些不足。

stream api 没有基于 iterable 实现，而是另起炉灶基于 Stream 接口。

最大的缺陷就是不能 foreach 遍历，而通过forEach 函数又不能随时终止遍历。而先转换为 List 再 foreach 仍然需要遍历一遍才能转换为 List。

并且有些 api 并没有实现，例如 join，union，intersect等。

而有的又设计的比较难用，例如排序不提供默认比较器,toList 需要传入 Collector 等。

发现了痛点就要去解决。

我们的目标

由于无法修改 iterable 源代码，并且有些常规的序列（数组，集合，列表，可迭代对象我们统称为序列）并且有些序列也没有实现 iterable。所以我们需要一类函数，将序列转换为拥有 linq api 的迭代对象（IEnumerable）。

对 IEnumerable 扩展实现 linq api。

实现方法

扩展迭代器

public interface IEnumerator
    
      extends Iterator
     
      , AutoCloseable {    boolean moveNext();//更容易一次处理是否有下一个和获取下一个元素的逻辑    T current();//从字段取下一个元素,可重复调用    boolean hasNext();    T next();    void reset();//不支持该方法    void close();//释放资源方法}

扩展可迭代对象

public interface IEnumerable
    
      extends Iterable
     
       {    IEnumerator
      
        enumerator();    default Iterator
       
         iterator() {        return this.enumerator();    }}

实现 IEnumerable 接口

//可迭代对象public final class IterableEnumerable
    
      implements IEnumerable
     
       {    private final Iterable
      
        source;    public IterableEnumerable(Iterable
       
         source) {        this.source = source;    }    @Override    public IEnumerator
        
          enumerator() {        return new IterableEnumerator<>(this.source);    }}//配套的迭代器public abstract class IterableEnumerator
         
           implements IEnumerator
          
            { protected int state; protected TSource current; private boolean checkedNext; private boolean hasNext; // private final Iterable
           
             source; private Iterator
            
              iterator; public IterableEnumerator(Iterable
             
               source) { this.source = source; } @Override public boolean moveNext() { switch (this.state) { case 0: this.iterator = this.source.iterator(); this.state = 1; case 1: if (this.iterator.hasNext()) { this.current = this.iterator.next(); return true; } this.close(); return false; default: return false; } } @Override public void close() { this.iterator = null; super.close(); } @Override public boolean hasNext() { return this.iterator.hasNext(); } @Override public TSource next() { return this.iterator.next(); } 
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               @Override public void reset() { throw Errors.notSupported(); } @Override public void close() { this.current = null; this.state = -1; }}

实现序列转 IEnumerable 方法

public interface IEnumerable
    
      extends Iterable
     
       {    IEnumerator
      
        enumerator();    default Iterator
       
         iterator() {        return this.enumerator();    }        public static 
        
          IEnumerable
         
           asEnumerable(Iterable
          
            source) { if (source == null) throw Errors.argumentNull("source"); return new IterableEnumerable<>(source); }}

扩展 IEnumerable 添加一个默认方法

default IEnumerable
    
      where(Func1
     
       predicate) {    if (source == null) throw Errors.argumentNull("source");    if (predicate == null) throw Errors.argumentNull("predicate");    return new WhereEnumerable<>(source, predicate);}    //Func 1 是一个 函数式接口@FunctionalInterfacepublic interface Func1
      
        {    TResult apply(T arg);}

实现 WhereEnumerable

class WhereEnumerable
    
      implements IEnumerable
     
       {    private final IEnumerable
      
        source;    private final Func1
       
         predicate;    private IEnumerator
        
          enumerator;    public WhereEnumerableIterator(IEnumerable
         
           source, Func1
          
            predicate) { this.source = source; this.predicate = predicate; } public IEnumerator
           
             enumerator(){ return new WhereEnumerator(this.source, this.predicate); } ...}

实现 WhereEnumerator

class WhereEnumerator
    
      implements IEnumerator
     
       {    private final IEnumerable
      
        source;    private final Func1
       
         predicate;    private IEnumerator
        
          enumerator;    private int state;    private TSource current;    public WhereEnumerator(IEnumerable
         
           source, Func1
          
            predicate) { this.source = source; this.predicate = predicate; } @Override public boolean moveNext() { switch (this.state) { case 0: this.enumerator = this.source.enumerator(); this.state = 1; case 1: while (this.enumerator.moveNext()) { TSource item = this.enumerator.current(); if (this.predicate.apply(item)) { this.current = item; return true; } } this.close(); return false; default: return false; } } @Override public void close() { this.state=-1; this.current=null; if(this.enumerator!=null){ this.enumerator.close(); this.enumerator=null; } } ...}

调用

@Testvoid call(){    List
    
      stringList = Arrays.asList("a", "bc", "def");    IEnumerable
     
       enumerable = IEnumerable.asEnumerable(stringList).where(str->str.length() > 1);    enumerable.forEach(System.out::println);}----bcdef

懒加载，延迟加载或叫延迟执行特性，得益于状态机

注意上述例子中

IEnumerable
    
      enumerable = IEnumerable.asEnumerable(stringList).where(str->str.length() > 1);

asEnumerable() 方法返回了一个 new IterableEnumerable(), where() 方法返回了一个 new WhereEnumerable(); 其中并没有执行循环.此时仍然可以对 enumerable 进行其他操作,仍然不会执行循环(有些特殊命令除外);

当执行 foreach 循环或执行 forEach() 方法时，Iterable 会创建 Iterator 导致 WhereEnumerable 创建 WhereEnumerator。迭代第一个元素时会导致 IterableEnumerable 创建 IterableEnumerator，每迭代一个元素，会引起迭代器链式反应，执行迭代，此时才是真正的执行。

优点（为什么使用懒加载）：

执行串行 api 时，无需每调用一次 api 执行一遍循环，可以大大提高性能。

foreach 时，可在一定的条件下终止循环。如果不使用延迟执行，则会浪费很多 cpu 时间。而该特性是 stream api 不具有的。

缺点（可以避免）

如果要对筛选结果进行多次随机访问或遍历多次等操作，注意是多次，不要直接在 IEnumerable 上重复执行。因为懒加载特性，每次执行都会导致所有的筛选操作重新执行一遍。

解决方式就是将 IEnumerable 强制执行。调用 toArray(),或 toList() 回立即执行迭代将结果存储在容器中。然后再对容器进行随机访问。

与原始代码比较性能会略有损失，但对比提升开发效率和降低编码错误率而言，优点大于缺点。

编译器代码 yield。

部分语言支持 yield X 语法糖，可简化 IEnumerable 创建，注意是语法糖，编译时最终将会被编译为状态机。例如

static 
    
      IEnumerable
     
       where(IEnumerable
      
        source, Func1
       
         predicate){    if (source == null) throw Errors.argumentNull("source");    if (predicate == null) throw Errors.argumentNull("predicate");    for(TSource item : source){        if(predicate.apply(item))            yield return item;    }}

上述方法编译后，生成的代码就跟 WhereEnumerable 的逻辑完全一样。当然，现阶段 java 还不支持 yield 关键字。如果 JCP 委员会不再固执己见的话将来可能会支持，否则将会遥遥无期。不过 github 上有个 lombok-pg 实现了这个语法糖，但是需要插件与 IDE 结合，效果并不好，而且生成的代码正确性得不到保证。

好在，我们用最原始的方法实现了 LINQ to Objects 库，包含了多数常用的集合操作。

地址：

Linq 应用举例

操作符分类见 Linq to Objects.png

部门

public final class Department {    public final String name;    public final Integer deptno;    public final List
    
      employees;    public Department(String name, Integer deptno, List
     
       employees) {        this.name = name;        this.deptno = deptno;        this.employees = employees;    }    public String toString() {        return String.format("Department(name: %s, deptno:%d, employees: %s)", this.name, this.deptno, this.employees);    }}

人员

public final class Employee {    public final int empno;    public final String name;    public final Integer deptno;    public Employee(int empno, String name, Integer deptno) {        this.empno = empno;        this.name = name;        this.deptno = deptno;    }    public String toString() {        return String.format("Employee(name: %s, deptno:%d)", this.name, this.deptno);    }    @Override    public int hashCode() {        final int prime = 31;        int result = 1;        result = prime * result + (this.deptno == null ? 0 : this.deptno.hashCode());        result = prime * result + this.empno;        result = prime * result + ((this.name == null) ? 0 : this.name.hashCode());        return result;    }    @Override    public boolean equals(Object obj) {        if (this == obj) {            return true;        }        if (obj == null) {            return false;        }        if (this.getClass() != obj.getClass()) {            return false;        }        Employee other = (Employee) obj;        if (!Objects.equals(this.deptno, other.deptno)) {            return false;        }        if (this.empno != other.empno) {            return false;        }        if (this.name == null) {            if (other.name != null) {                return false;            }        } else if (!this.name.equals(other.name)) {            return false;        }        return true;    }}

数据

private static final Employee[] badEmps = {            new Employee(140, "Cedric", 40),            new Employee(150, "Gates", null)};    private static final Department[] badDepts = {            new Department("Manager", null, Collections.emptyList())};    private static final Employee[] emps = {            new Employee(100, "Fred", 10),            new Employee(110, "Bill", 30),            new Employee(120, "Eric", 10),            new Employee(130, "Janet", 10)};    private static final Department[] depts = {            new Department("Sales", 10, Arrays.asList(emps[0], emps[2], emps[3])),            new Department("HR", 20, Collections.emptyList()),            new Department("Marketing", 30, Collections.singletonList(emps[1]))};

过滤操作符

Linq.asEnumerable(emps).where(employee -> employee.deptno < 15);//等同于 stream api 的 filter

投影操作符

Linq.asEnumerable(emps).select(emp -> emp.name);//等同于 stream api 的 map

排序操作符

Linq.asEnumerable(emps)        .orderBy(emp -> emp.deptno)        .thenBy(emp -> emp.name);//先按部门号,再按姓名排序

连接操作符

Linq.asEnumerable(emps)                .join(Linq.asEnumerable(depts),                        emp -> emp.deptno,                        dept -> dept.deptno,                        (emp, dept) -> String.format("%s works in %s", emp.name, dept.name))

分组操作符

Linq.asEnumerable(emps).groupBy(emp -> emp.deptno);//按指定键分组

量词操作符

Linq.asEnumerable(emps).contains(emps[0]);//序列是否包含指定元素

分区操作符

Linq.asEnumerable(emps).skip(1).take(2);//跳过1个,取两个元素.可用于分页

生成操作符

Linq.range(0, 100);//生成 [0, 99] 共100个数,延迟执行Linq.repeat(0,100);//生成 100 个 0 的序列,延迟执行Linq.empty();//生成有 0 个元素的序列,延迟执行

转换操作符

Linq.range(0, 100).toList();//立即执行

合计操作符

Linq.range(0, 100).sum();//求和

元素操作符

Linq.range(0,100).last();//最后一个

集合操作符

Linq.asEnumerable(emps).concat(Linq.asEnumerable(badEmps));

组合应用示例

//条件:给定员工和部门,员工和部门通过部门编号关联.//要求:按部门分组,组按部门编号排序,组内员工按姓名排序.按顺序打印部门编号、名称和员工编号、姓名IEnumerable
    
      allEmps = Linq.asEnumerable(emps).concat(Linq.asEnumerable(badEmps));IEnumerable
     
       allDepts = Linq.asEnumerable(depts).concat(Linq.asEnumerable(badDepts));allEmps.join(allDepts, emp -> emp.deptno, dept -> dept.deptno, (emp, dept) -> Tuple.create(emp, dept))//Tuple::create        .groupBy(tup -> tup.getItem2())//按部门分组 Tuple2::getItem2        .orderBy(g -> g.getKey().deptno)//组 按部门编号排序        .forEach(g -> {            System.out.println(String.format("========deptno:%s  deptname:%s========", g.getKey().deptno, g.getKey().name));            g.orderBy(tup -> tup.getItem1().name)                    .forEach(tup -> System.out.println(String.format("empno:%s empname:%s", tup.getItem1().empno, tup.getItem1().name)));        });//不打印,生成 List
      
       
        
         >>List lst = allEmps.join(allDepts, emp -> emp.deptno, dept -> dept.deptno, (emp, dept) -> Tuple.create(emp, dept))//Tuple::create        .groupBy(tup -> tup.getItem2())//按部门分组 Tuple2::getItem2        .orderBy(g -> g.getKey().deptno)//组 按部门编号排序        .select(g -> {            Map
         
          > map = new HashMap<>(); map.put(g.getKey(), g.select(tup -> tup.getItem1()).orderBy(emp -> emp.name).toList()); return map; }) .toList();

迭代器应用：协程

进程和线程的定义：

一、进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的一个独立单位。

二、线程是进程的一个实体，是CPU调度和分派的基本单位，他是比进程更小的能独立运行的基本单位，线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器，一组寄存器和栈），一个线程可以创建和撤销另一个线程；

进程和线程的关系：

（1）一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。

（2）资源分配给进程，同一进程的所有线程共享该进程的所有资源。

（3）线程在执行过程中，需要协作同步。不同进程的线程间要利用消息通信的办法实现同步。

（4）处理机分给线程，即真正在处理机上运行的是线程。

（5）线程是指进程内的一个执行单元，也是进程内的可调度实体。

线程与进程的区别：

（1）调度：线程作为调度和分配的基本单位，进程作为拥有资源的基本单位。

（2）并发性：不仅进程之间可以并发执行，同一个进程的多个线程之间也可以并发执行。

（3）拥有资源：进程是拥有资源的一个独立单位，线程不拥有系统资源，但可以访问隶属于进程的资源。

（4）系统开销：在创建或撤销进程的时候，由于系统都要为之分配和回收资源，导致系统的明显大于创建或撤销线程时的开销。但进程有独立的地址空间，进程崩溃后，在保护模式下不会对其他的进程产生影响，而线程只是一个进程中的不同的执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但是在进程切换时，耗费的资源较大，效率要差些。线程的划分尺度小于进程，使得多线程程序的并发性高。

另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大的提高了程序运行效率。线程在执行过程中，每个独立的线程有一个程序运行的入口，顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，有应用程序提供多个线程执行控制。从逻辑角度看，多线程的意义子啊与一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。

协程

定义

coroutine 协程全称被称作协同式多线程（collaborative multithreading）。每个coroutine有一个独立的运行线路。然而和多线程不同的地方就是，coroutine只有在显式调用yield函数后才被挂起，同一时间内只有一个协程正在运行。

演进

一开始大家想要同一时间执行那么三五个程序，大家能一块跑一跑。特别是UI什么的，别一上计算量比较大的玩意就跟死机一样。于是就有了并发，从程序员的角度可以看成是多个独立的逻辑流。内部可以是多cpu并行，也可以是单cpu时间分片，能快速的切换逻辑流，看起来像是大家一块跑的就行。

但是一块跑就有问题了。我计算到一半，刚把多次方程解到最后一步，你突然插进来，我的中间状态咋办，我用来储存的内存被你覆盖了咋办？所以跑在一个cpu里面的并发都需要处理上下文切换的问题。进程就是这样抽象出来个一个概念，搭配虚拟内存、进程表之类的东西，用来管理独立的程序运行、切换。

后来一电脑上有了好几个cpu，好咧，大家都别闲着，一人跑一进程。就是所谓的并行。

因为程序的使用涉及大量的计算机资源配置，把这活随意的交给用户程序，非常容易让整个系统分分钟被搞跪，资源分配也很难做到相对的公平。所以核心的操作需要陷入内核(kernel)，切换到操作系统，让老大帮你来做。

有的时候碰着I/O访问，阻塞了后面所有的计算。空着也是空着，老大就直接把CPU切换到其他进程，让人家先用着。当然除了I\O阻塞，还有时钟阻塞等等。一开始大家都这样弄，后来发现不成，太慢了。为啥呀，一切换进程得反复进入内核，置换掉一大堆状态。进程数一高，大部分系统资源就被进程切换给吃掉了。后来搞出线程的概念，大致意思就是，这个地方阻塞了，但我还有其他地方的逻辑流可以计算，这些逻辑流是共享一个地址空间的，不用特别麻烦的切换页表、刷新TLB，只要把寄存器刷新一遍就行，能比切换进程开销少点。