精华内容
下载资源
问答
  • 动态代理及JDK动态代理源码分析

    千次阅读 2014-04-14 23:16:41
    JAVA的动态代理机制可以动态的创建代理并动态的处理代理方法调用,只要简单指定一组接口及为拖累对象,就能动态的获取代理类
    1.为什么要动态代理
    
    现在有这样一个需求:在聊天系统中,把每一个所说的话记录到日志文件里面,初学者可能是这样来设计


    在speak方法中调用log方法,记录到数据库。这样设计有明显的不足:1、log方法不应该属于Person类中 2、如果改类库已经编译,我们就不能修改原有代码,在其方法内部增加代码。此时,有经验的开发者可能会想到代理模式。我们修改一下类图


    我们将讲话给抽象出来,客户端使用接口声明,LogProxy与Person依赖,共同实现Speak接口,然后在LogPersonProxy中实现记录日志,这样就可以解决之前的问题。但是新问题又来了:我们必须为为委托类维护一个代理,不易管理而且增加了代码量。


    2.JDK中的动态代理
    JAVA的动态代理机制可以动态的创建代理并动态的处理代理方法调用,只要简单指定一组接口及为拖累对象,就能动态的获取代理类,JAVA已经给我们提供了强大的支持,其具体实现可以参照马士兵的动态代理视频。核心类是Proxy,负责创建所有代理类,并且创建的代理类都是其子类,而且这些子类继承所代理的一组接口,因此它就可以安全的转换成需要的类型,进行方法调用。InvocationHandler是调用处理器的接口,它自定义了一个invoke方法,用于机制处理在动态代理类上的方法调用,通常在该方法中实现对委托类的代理访问。相关类图如下



    具体代理要实现InvocationHandler接口详细代码如下

    public class LogProxy implements InvocationHandler {
     
     private Object object;
     public LogProxy(Object object) {
      super();
      this.object = object;
     }
     @Override
     public Object invoke(Object proxy, Method method, Object[] args)
       throws Throwable {
      method.invoke(this.object, args);
      System.out.println("记录到数据库..");
      return null;
     }
     public void setObject(Object object) {
      this.object = object;
     }
     public Object getObject() {
      return object;
     }
    }
    public class PowerProxy implements InvocationHandler {
     private Object object;
     public PowerProxy(Object object) {
      super();
      this.object = object;
     }
     
     @Override
     public Object invoke(Object proxy, Method method, Object[] args)
       throws Throwable {
      System.out.println("进行权限验证..是否是黑名单..");
      method.invoke(this.object, args);
      return null;
     }
     public void setObject(Object object) {
      this.object = object;
     }
     public Object getObject() {
      return object;
     }
    }




    我们可以在invoke方法中接到一下参数:Object proxy, Method method, Object[] args


    其中,proxy是被代理的类,第二个参数表示被执行的委托方法,第三个参数表被执行的委托方法,我们在客户端测试一下,代码如下
    public class Client {
     /**
      * @Title: main
      * @Description: TODO(这里用一句话描述这个方法的作用)
      * @param args 描述
      * @return void 返回类型
      * @throws
      */
     public static void main(String[] args) {
      Person zhangsan = new Person("张三");
      Zegapain jiqiren = new Zegapain("编号89757");
      Speakable zhangsanProxy = (Speakable) Proxy.newProxyInstance(Speakable.class.getClassLoader(), new Class[]{Speakable.class}, new LogProxy(zhangsan));
      Speakable jiqirenProxy = (Speakable) Proxy.newProxyInstance(Speakable.class.getClassLoader(), new Class[]{Speakable.class}, new LogProxy(jiqiren));
      zhangsanProxy.speak("呵呵");
      jiqirenProxy.speak("您好,我是机器人");
      System.out.println("----------------------------");
      Speakable zhangsanPowerProxy = (Speakable) Proxy.newProxyInstance(Speakable.class.getClassLoader(), new Class[]{Speakable.class}, new PowerProxy(zhangsan));
      zhangsanPowerProxy.speak("我不是坏人");
      System.out.println("----------------------------");
        Speakable jiqirenPowerProxy = (Speakable) Proxy.newProxyInstance(Speakable.class.getClassLoader(), new Class[]{Speakable.class}, new PowerProxy(jiqirenProxy));
        jiqirenPowerProxy.speak("我是您的机器人");
     }
    }




    3.JDK动态代理必须要接口的原因


    在aspectj和cglib里面,被代理的对象要实现一个接口如上面的测试代码:

     Speakable zhangsanPowerProxy = (Speakable) Proxy.newProxyInstance(Speakable.class.getClassLoader(), new Class[]{Speakable.class}, new PowerProxy(zhangsan)); 


     
    在cglib下是这样的:

    TestProxy tp = new TestProxy();
    zhangsan= (Person ) tp.getProxy(Person.class);



    JDK动态代理为什么必须使用接口?这个问题很有意思。
    我们查看Proxy的源码


    Class cl = getProxyClass(loader, interfaces);


    上面代码是创建一个代理类,我们看看getProxyClass的源码

     if (interfaces.length > 65535) {
         throw new IllegalArgumentException("interface limit exceeded");
     }


    接口类数组的长度小于65535,65535是计算机16位二进制最大数,如果大于就会内存溢出,继续往下。
    Class proxyClass = null;
     /* collect interface names to use as key for proxy class cache */
     String[] interfaceNames = new String[interfaces.length];
     Set interfaceSet = new HashSet();	// for detecting duplicates
     for (int i = 0; i < interfaces.length; i++) {
         /*
          * Verify that the class loader resolves the name of this
          * interface to the same Class object.
          */
         String interfaceName = interfaces[i].getName();
         Class interfaceClass = null;
         try {
      interfaceClass = Class.forName(interfaceName, false, loader);
         } catch (ClassNotFoundException e) {
         }
         if (interfaceClass != interfaces[i]) {
      throw new IllegalArgumentException(
          interfaces[i] + " is not visible from class loader");
         }
         /*
          * Verify that the Class object actually represents an
          * interface.
          */
         if (!interfaceClass.isInterface()) {
      throw new IllegalArgumentException(
          interfaceClass.getName() + " is not an interface");
         }
         /*
          * Verify that this interface is not a duplicate.
          */
         if (interfaceSet.contains(interfaceClass)) {
      throw new IllegalArgumentException(
          "repeated interface: " + interfaceClass.getName());
         }
         interfaceSet.add(interfaceClass);
         interfaceNames[i] = interfaceName;
     }
    



    从上面代码可以看出,接口名放在了一个数组里,接口类的Class的数组缓存在了了HashSet里面,之所以用Set是为了排除重复


    Map cache;
     synchronized (loaderToCache) {
         cache = (Map) loaderToCache.get(loader);
         if (cache == null) {
      cache = new HashMap();
      loaderToCache.put(loader, cache);
         }
         /*
          * This mapping will remain valid for the duration of this
          * method, without further synchronization, because the mapping
          * will only be removed if the class loader becomes unreachable.
          */
     }
     /*
      * Look up the list of interfaces in the proxy class cache using
      * the key. This lookup will result in one of three possible
      * kinds of values:
      * null, if there is currently no proxy class for the list of
      * interfaces in the class loader,
      * the pendingGenerationMarker object, if a proxy class for the
      * list of interfaces is currently being generated,
      * or a weak reference to a Class object, if a proxy class for
      * the list of interfaces has already been generated.
      */
     synchronized (cache) {
         /*
          * Note that we need not worry about reaping the cache for
          * entries with cleared weak references because if a proxy class
          * has been garbage collected, its class loader will have been
          * garbage collected as well, so the entire cache will be reaped
          * from the loaderToCache map.
          */
         do {
      Object value = cache.get(key);
      if (value instanceof Reference) {
          proxyClass = (Class) ((Reference) value).get();
      }
      if (proxyClass != null) {
          // proxy class already generated: return it
          return proxyClass;
      } else if (value == pendingGenerationMarker) {
          // proxy class being generated: wait for it
          try {
       cache.wait();
          } catch (InterruptedException e) {
       /*
        * The class generation that we are waiting for should
        * take a small, bounded time, so we can safely ignore
        * thread interrupts here.
        */
          }
          continue;
      } else {
          /*
           * No proxy class for this list of interfaces has been
           * generated or is being generated, so we will go and
           * generate it now. Mark it as pending generation.
           */
          cache.put(key, pendingGenerationMarker);
          break;
      }
         } while (true);
     }



    找到或创建的类加载器代理类缓存

    String proxyPkg = null;
    String proxyPkg = null;	// package to define proxy class in
         /*
          * Record the package of a non-public proxy interface so that the
          * proxy class will be defined in the same package. Verify that
          * all non-public proxy interfaces are in the same package.
          */
         for (int i = 0; i < interfaces.length; i++) {
      int flags = interfaces[i].getModifiers();
      if (!Modifier.isPublic(flags)) {
          String name = interfaces[i].getName();
          int n = name.lastIndexOf('.');
          String pkg = ((n == -1) ? "" : name.substring(0, n + 1));
          if (proxyPkg == null) {
       proxyPkg = pkg;
          } else if (!pkg.equals(proxyPkg)) {
       throw new IllegalArgumentException(
           "non-public interfaces from different packages");
          }
      }
         }
      if (proxyPkg == null) {	// if no non-public proxy interfaces,
      proxyPkg = "";	 // use the unnamed package
         }
    
    	// package to define proxy class in
         /*
          * Record the package of a non-public proxy interface so that the
          * proxy class will be defined in the same package. Verify that
          * all non-public proxy interfaces are in the same package.
          */
         for (int i = 0; i < interfaces.length; i++) {
      int flags = interfaces[i].getModifiers();
      if (!Modifier.isPublic(flags)) {
          String name = interfaces[i].getName();
          int n = name.lastIndexOf('.');
          String pkg = ((n == -1) ? "" : name.substring(0, n + 1));
          if (proxyPkg == null) {
       proxyPkg = pkg;
          } else if (!pkg.equals(proxyPkg)) {
       throw new IllegalArgumentException(
           "non-public interfaces from different packages");
          }
      }
         }
      if (proxyPkg == null) {	// if no non-public proxy interfaces,
      proxyPkg = "";	 // use the unnamed package
         }



    这句代码是给新生成的代理类截取接口,JDK是这样设计的:如果接口为public,则生成到顶包底下,如果为默认修饰符,也就是修饰符为空,则会生成到接口所定义的包下,继续往下


    long num;
      synchronized (nextUniqueNumberLock) {
          num = nextUniqueNumber++;
      }
      String proxyName = proxyPkg + proxyClassNamePrefix + num;




    这里是设计动态代理类的类名,JDK的设计师为"$ProxyN",其中N为从0递增的一个阿拉伯数字,加了synchronized 关键字,不会重复


    byte[] proxyClassFile =	ProxyGenerator.generateProxyClass(
          proxyName, interfaces);
      try {
          proxyClass = defineClass0(loader, proxyName,
       proxyClassFile, 0, proxyClassFile.length);
      } catch (ClassFormatError e) {
          /*
           * A ClassFormatError here means that (barring bugs in the
           * proxy class generation code) there was some other
           * invalid aspect of the arguments supplied to the proxy
           * class creation (such as virtual machine limitations
           * exceeded).
           */
          throw new IllegalArgumentException(e.toString());
      }
         }
         // add to set of all generated proxy classes, for isProxyClass
         proxyClasses.put(proxyClass, null);
     } finally {
         /*
          * We must clean up the "pending generation" state of the proxy
          * class cache entry somehow. If a proxy class was successfully
          * generated, store it in the cache (with a weak reference);
          * otherwise, remove the reserved entry. In all cases, notify
          * all waiters on reserved entries in this cache.
          */
         synchronized (cache) {
      if (proxyClass != null) {
          cache.put(key, new WeakReference(proxyClass));
      } else {
          cache.remove(key);
      }
      cache.notifyAll();
         }
     }
     return proxyClass;
        }




    上面代码是说调用class处理文件生成类的字节码,根据接口列表创建一个新类,这个类为代理类,通过JNI接口,将Class字节码文件定义一个新类,下面是newProxyInstance后面的代码


    Constructor cons = cl.getConstructor(constructorParams);
    return (Object) cons.newInstance(new Object[] { h });


    根据前面的代码Constructor cons = cl.getConstructor(constructorParams);


    可以猜测到接口创建的新类proxyClassFile 不管采用什么接口,都是以下结构


    public class $Proxy1 extends Proxy implements 传入的接口{


        


    }
    生成新类的看不到源代码,不过猜测它的执行原理很有可能是如果类是Proxy的子类,则调用InvocationHandler进行方法的Invoke
    到现在大家都应该明白了吧,JDK动态代理的原理是根据定义好的规则,用传入的接口创建一个新类,JDK的动态代理只能代理接口中的方法,是针对接口生成代理类。  
    这就是为什么采用动态代理时为什么只能用接口引用指向代理,而不能用传入的类引用执行动态类。




    附:Spring中的动态代理
    关于Spring中的动态代理我之前写过一篇博文《对Spring.Net的AOP一些思考及应用》,里面写的比较的深在里面举得例子有点复杂,大家在第一次看的时候可以看看一个博友的《Spring.Net 面向切面AOP》


    参考:

    《spring 3.x 企业级应用程序开发实战》

    http://www.cnblogs.com/frankliiu-java/articles/1896443.html




    展开全文
  • 病毒分析教程第二话--动态行为分析

    千次阅读 2018-07-07 16:12:26
    静态特征分析可以说是分析一个病毒的前奏,属于比较简单的分析分析环节包括:VT检测、编译时间、加壳信息、导入函数、可疑字符串,等等。 Lab 1-1 本节实验使用到两个样本Lab01-01.dll和Lab01-01....

    动态行为分析


    教程参考自《恶意代码分析实战》
    程序来自:http://www.nostarch.com/malware.htm


    若样本经过了高级加密,使用静态特征分析将得不到太多有价值的信息,这时候就需要我们使用动态行为分析技术了,这种技术也叫行为监控。


    Lab 3-1

    本节实验使用样本Lab03-01.exe。
    Lab03-01.exe

    导入函数和字符串

    查看导入表,只有一个ExitProcess,该样本应该是被加密过,通过导入表得不到什么信息。
    Imports

    样本被加密过的,但在字符串表中我们却发现了很多可视化的字符串,接下来我们就使用动态行为分析技术来看看这些字符串背后的恶意行为。
    Strings

    Process Explorer

    运行样本后,使用ProcExp查看进程信息,点击View->Lower Pane View->Handles,可以在下方的窗口中发现该进程创建了一个名为WinVMX32的互斥量。
    Mutant

    点击View->Lower Pane View->DLLs,可以查看该进程导入了哪些DLL,如下图中的红色框,我们发现了该进程导入了几个与socket有关的DLL,那么就可以猜测该进程发起了网络连接。
    Dll

    Process Monitor

    运行程序前先配置ProcMon的规则,我配置了以下3个过滤规则(用于筛选出我们关心的恶意行为):

    1. 进程名为Lab03-01.exe
    2. 写注册表的操作
    3. 创建文件的操作
      Rules
      配置完过滤规则后,ProcMon就可以开始监控了,然后运行Lab03-01.exe。

    ProcMon成功监控到了Lab03-01.exe的可疑行为,但其中非红框中的行为是合法的,因为每一个程序启动时都会帮随机数发生器更新种子。
    Reg&File
    红框中有两个可疑行为:

    1. 创建文件vmx32to64.exe,大小为7168字节,细心的同学可能会发现大小跟Lab03-01.exe大小一样,应该是样本自复制到了系统目录。
    2. 在注册表自启动项\Run\VideoDriver中写入了一个新的注册表键值,双击可以发现其写入的值是:
      C:\Windows\system32\vmx32to64.exe,这样就实现了每次开机自启动vmx32to64.exe。
      Run

    网络数据包

    通过Wireshark抓包可以发现进程发起了DNS请求,域名为www.practicalmalwareanalysis.com。然后一直发送HTTPS的数据包,由于数据包经过加密,所以无法获取其内容。
    Packets


    Lab 3-2

    本节实验使用样本Lab03-02.dll。

    导入导出函数

    由于该样本是个DLL,我们可以从它的导出函数中找到很多有价值的信息。如下图,我门一下就可以发现了两个与服务有关的函数,看来这个样本会将自己安装成一个服务,安装函数就是intallA。
    Exports

    再看导入函数,果然也有许多与服务相关的函数。其中还有一些操作注册表的函数(这是当然的,注册服务必然要再注册表中配置)。
    Imports

    也存在许多网络连接的函数。
    Imports

    字符串

    字符串中中显示了许多与要创建的服务相关的信息。
    Strings

    Process Monitor

    打开ProcMon按Lab03-1的过滤规则进行配置,开始监控rundll32.exe。然后在命令行中输入rundll32.exe Lab03-02.dll,installA运行样本。ProcMon立马监控到了修改注册表的行为,样本首先在服务项下创建了IPRIP健,然后为这个键添加了很多相应的键值,这是典型的创建服务的操作。
    ProcMon

    每个键值都描述了IPRIP服务的信息。这样,一个恶意的服务就创建完成了。
    ProcMon

    Process Explorer

    创建完IPRIP服务后,我们使用命令net start IPRIP来启动该服务,启动后,可以发现该服务出现在了一个svchost进程中。
    ProcExp

    网络数据包

    过了一会儿,我们通过Wireshark发现了该样本的恶意行为,首先它发起了对域名practicalmalwareanalysis.com的DNS请求,然后访问了这个网站的serve.html。点开细看后,我们发现了端倪,User-Agent处的值居然夹藏着我的主机信息,样本将我的主机信息传输到了黑客服务器。
    Packets


    Lab 3-3

    本节实验使用样本Lab03-03.exe。

    导入函数和字符串

    先看字符串,得到的信息不多,但我们看到红框中的字符串,更像是终端中显示的调试信息,所以我们可以选择在终端中运行该程序,以获得更多提示信息。
    Strings

    导入函数中可以得到的信息就多了,第一个红框中的函数暗示了该样本有进程注入的行为(先调用SetThreadContext修改傀儡进程的EIP,指向恶意代码,然后调用ResumeThread恢复傀儡进程的运行),第二个红框暗示了样本会从自己的资源节中读取数据,所以我们可以猜测样本资源节中存放的就是一段恶意代码,样本运行后将其注入到傀儡进程中。
    Imports

    Process Monitor

    打开ProcMon监控Lab03-03.exe的运行,没有发现篡改注册表,建立网络连接等操作,但却发现有许多对svchost.exe的文件操作,结合上面的进程注入行为,可以猜测样本是运行了svchost进程然后对其进行注入。
    ProcMon

    Process Explorer

    使用ProcExp监控也印证了上面的观点,Lab03-03.exe运行后启动了进程svchost,将恶意代码注入到svchost进程之后退出。
    ProcExp

    Procexp还有个强大的功能,右键svchost.exe->Properties->Strings,选择下方的Memory选项,即可查看该进程在内存中的所有字符串。然后看到红框部分,这些字符串显得非常可疑,praticalmalwareanalysis.log说明进程可能会创建这个文件,下面的都是一些跟键盘按键相关的特征,有理由猜测进程在进行键盘记录的恶意行为。
    ProcExp

    最后我在样本目录下找到了practicalmalwareanaysis.log文件,原来它就是用来记录按键的文件。它记录了用户在哪个窗口下敲下了哪些按键。
    File


    Lab 3-4

    本节实验使用样本Lab03-04.exe。

    导入函数和字符串

    导入函数跟上一节的实验的样本相似,也是啥可疑函数都有,如:服务函数、注册表操作函数、网络连接函数。
    Imports

    Imports

    可疑的字符串比较多,我们先来看第一个红框,都是日期,这个暂时不能猜测其目的。。。接着看第二个红框,有一些HTTP的操作,GET、DOWNLOAD、UPLOAD,看来该样本会跟黑客服务器进行通信。最后的一个红框,有cmd.exe,应该是会调用cmd.exe干什么。
    Strings

    Process Monitor

    使用ProcMon进行监控,没有可疑的注册表操作和文件操作,只有一个创建进程的操作比较可疑。同时,Lab03-04.exe运行后消失了!
    ProcMon

    点开这个创建进程的行为,真相大白,原来是该样本调用cmd.exe运行命令把自己给删除了,这是个典型的自删除手法。
    ProcMon

    其余的也没发现什么可疑的网络连接,看来需要后续的逆向技术才能分析出该样本的具体行为了。


    总结

    1. 使用Process Monitor犹如沙箱一样可以监控样本的一举一动,但是设置过滤规则是一门艺术,确保监控到所有可疑行为的同时又要减少噪声,还有就是,排除噪声也需要平时经验的积累,如上面实验中的注册表项\RNG\Seed。

    2. 使用Process Explorer可以查看每个进程的详细信息,其中查看进程的内存字符串是用的最多的方法,因为一个样本再怎么加密,加载到内存中后都是以明文的方式显示,这时候再检测该内存中的可疑字符串,就可以判断该进程是否合法。

    3. 网络数据包抓包也是很关键的一步,现在主流的恶意软件如挖矿、蠕虫、木马都需要跟C&C服务器保持连接,这时监控终端的网络连接就显得很重要,但棘手的是,网络数据包可以经过复杂加密,所以有时得到加密的网络连接是很难判断行为的合法性的。

    4. 本节介绍的动态行为分析技术其实就是沙箱的雏形,想必大家也看到了沙箱的弊端,一是监控过程中噪声很多,很难把控,二是像最后一个例子Lab03-04.exe运行后没有明显的可疑行为,这可能是我们运行样本时传入的参数不对,或是该样本运行可能要在特定的时间点等等,要深究这些样本的底层原理就必须使用逆向技术对它们进行分析。

    展开全文
  • 理解动态规划 动态规划中递推式的求解方法不是动态规划的本质。 我曾经作为省队成员参加过NOI,保送之后也给学校参加NOIP的同学多次讲过动态规划,我试着讲一下我理解的动态规划,争取深入浅出。希望你看了我的答案...

    理解动态规划


    动态规划中递推式的求解方法不是动态规划的本质。


    我曾经给学校参加NOIP的同学多次讲过动态规划,我试着讲一下我理解的动态规划,争取深入浅出。希望你看了我的答案,能够喜欢上动态规划。

    0. 动态规划的本质,是对问题状态的定义 状态转移方程 的定义
    引自维基百科
    dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.
    动态规划是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。
    本题下的其他答案,大多都是在说递推的求解方法,但如何拆分问题,才是动态规划的核心。
    拆分问题,靠的就是状态的定义状态转移方程的定义

    1. 什么是状态的定义?

    首先想说大家千万不要被下面的数学式吓到,这里只涉及到了函数相关的知识。
    我们先来看一个动态规划的教学必备题:
    给定一个数列,长度为N,
    求这个数列的最长上升(递增)子数列(LIS)的长度.
    以 1 7 2 8 3 4 为例。
    这个数列的最长递增子数列是 1 2 3 4,长度为4;
    次长的长度为3, 包括 1 7 8; 1 2 3 等.
    要解决这个问题,我们首先要定义这个问题和这个问题的子问题。
    有人可能会问了,题目都已经在这了,我们还需定义这个问题吗?需要,原因就是这个问题在字面上看,找不出子问题,而没有子问题,这个题目就没办法解决。

    所以我们来重新定义这个问题:
    给定一个数列,长度为N,
    F_{k}为:以数列中第k项结尾的最长递增子序列的长度.
    F_{1}..F_{N} 中的最大值.
    显然,这个新问题与原问题等价。
    而对于F_{k}来讲,F_{1} .. F_{k-1}都是F_{k}的子问题:因为以第k项结尾的最长递增子序列(下称LIS),包含着以第1..k-1中某项结尾的LIS。

    上述的新问题F_{k}也可以叫做状态,定义中的“F_{k}为数列中第k项结尾的LIS的长度”,就叫做对状态的定义。
    之所以把F_{k}做“状态”而不是“问题” ,一是因为避免跟原问题中“问题”混淆,二是因为这个新问题是数学化定义的。

    对状态的定义只有一种吗?当然不是
    我们甚至可以二维的,以完全不同的视角定义这个问题:
    给定一个数列,长度为N,
    F_{i, k}为:
    在前i项中的,长度为k的最长递增子序列中,最后一位的最小值. 1\leq k\leq N.
    若在前i项中,不存在长度为k的最长递增子序列,则F_{i, k}为正无穷.
    求最大的x,使得F_{N,x}不为正无穷。
    这个新定义与原问题的等价性也不难证明,请读者体会一下。
    上述的F_{i, k}就是状态,定义中的“F_{i, k}为:在前i项中,长度为k的最长递增子序列中,最后一位的最小值”就是对状态的定义。

    2. 什么是状态转移方程

    上述状态定义好之后,状态和状态之间的关系式,就叫做状态转移方程

    比如,对于LIS问题,我们的第一种定义:
    F_{k}为:以数列中第k项结尾的最长递增子序列的长度.
    设A为题中数列,状态转移方程为:
    F_{1} = 1 (根据状态定义导出边界情况)
    F_{k}=max(F_{i}+1 | A_{k}>A_{i}, i\in (1..k-1)) (k>1)
    用文字解释一下是:
    以第k项结尾的LIS的长度是:保证第i项比第k项小的情况下,以第i项结尾的LIS长度加一的最大值,取遍i的所有值(i小于k)。

    第二种定义:
    F_{i, k}为:在数列前i项中,长度为k的递增子序列中,最后一位的最小值
    设A为题中数列,状态转移方程为:
    A_{i}>F_{i-1,k-1}F_{i,k}=min(A_{i},F_{i-1,k})
    否则:F_{i,k}=F_{i-1,k}
    (边界情况需要分类讨论较多,在此不列出,需要根据状态定义导出边界情况。)
    大家套着定义读一下公式就可以了,应该不难理解,就是有点绕。

    这里可以看出,这里的状态转移方程,就是定义了问题和子问题之间的关系。
    可以看出,状态转移方程就是带有条件的递推式。

    3. 动态规划迷思

    本题下其他用户的回答跟动态规划都有或多或少的联系,我也讲一下与本答案的联系。

    a. “缓存”,“重叠子问题”,“记忆化”:
    这三个名词,都是在阐述递推式求解的技巧。以Fibonacci数列为例,计算第100项的时候,需要计算第99项和98项;在计算第101项的时候,需要第100项和第99项,这时候你还需要重新计算第99项吗?不需要,你只需要在第一次计算的时候把它记下来就可以了。
    上述的需要再次计算的“第99项”,就叫“重叠子问题”。如果没有计算过,就按照递推式计算,如果计算过,直接使用,就像“缓存”一样,这种方法,叫做“记忆化”,这是递推式求解的技巧。这种技巧,通俗的说叫“花费空间来节省时间”。都不是动态规划的本质,不是动态规划的核心。

    b. “递归”:
    递归是递推式求解的方法,连技巧都算不上。

    c. "无后效性",“最优子结构”:
    上述的状态转移方程中,等式右边不会用到下标大于左边i或者k的值,这是"无后效性"的通俗上的数学定义,符合这种定义的状态定义,我们可以说它具有“最优子结构”的性质,在动态规划中我们要做的,就是找到这种“最优子结构”。
    在对状态和状态转移方程的定义过程中,满足“最优子结构”是一个隐含的条件(否则根本定义不出来)。对状态和“最优子结构”的关系的进一步解释,什么是动态规划?动态规划的意义是什么? - 王勐的回答 写的很好,大家可以去读一下。

    需要注意的是,一个问题可能有多种不同的状态定义和状态转移方程定义,存在一个有后效性的定义,不代表该问题不适用动态规划这也是其他几个答案中出现的逻辑误区:
    动态规划方法要寻找符合“最优子结构“的状态和状态转移方程的定义在找到之后,这个问题就可以以“记忆化地求解递推式”的方法来解决。而寻找到的定义,才是动态规划的本质。

    有位答主说:
    分治在求解每个子问题的时候,都要进行一遍计算
    动态规划则存储了子问题的结果,查表时间为常数
    这就像说多加辣椒的菜就叫川菜,多加酱油的菜就叫鲁菜一样,是存在误解的。

    文艺的说,动态规划是寻找一种对问题的观察角度,让问题能够以递推(或者说分治)的方式去解决。寻找看问题的角度,才是动态规划中最耀眼的宝石!(大雾)


    王勐动态规划的本质


          动态规划的本质不在于是递推或是递归,也不需要纠结是不是内存换时间

          理解动态规划并不需要数学公式介入,只是完全解释清楚需要点篇幅…首先需要明白哪些问题不是动态规划可以解决的,才能明白为神马需要动态规划。不过好处时顺便也就搞明白了递推贪心搜索和动规之间有什么关系,以及帮助那些总是把动规当成搜索解的同学建立动规的思路。当然熟悉了之后可以直接根据问题的描述得到思路,如果有需要的话再补充吧。
          动态规划是对于 某一类问题 的解决方法!!重点在于如何鉴定“某一类问题”是动态规划可解的而不是纠结解决方法是递归还是递推!
    怎么鉴定dp可解的一类问题需要从计算机是怎么工作的说起…计算机的本质是一个状态机,内存里存储的所有数据构成了当前的状态,CPU只能利用当前的状态计算出下一个状态(不要纠结硬盘之类的外部存储,就算考虑他们也只是扩大了状态的存储容量而已,并不能改变下一个状态只能从当前状态计算出来这一条铁律)

          当你企图使用计算机解决一个问题是,其实就是在思考如何将这个问题表达成状态(用哪些变量存储哪些数据)以及如何在状态中转移(怎样根据一些变量计算出另一些变量)。所以所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少,所谓时间复杂度就是从初始状态到达最终状态中间需要多少步!
          太抽象了还是举个例子吧:
          比如说我想计算第100个非波那契数,每一个非波那契数就是这个问题的一个状态,每求一个新数字只需要之前的两个状态。所以同一个时刻,最多只需要保存两个状态,空间复杂度就是常数;每计算一个新状态所需要的时间也是常数且状态是线性递增的,所以时间复杂度也是线性的。
          上面这种状态计算很直接,只需要依照固定的模式从旧状态计算出新状态就行(a[i]=a[i-1]+a[i-2]),不需要考虑是不是需要更多的状态,也不需要选择哪些旧状态来计算新状态。对于这样的解法,我们叫递推
          非波那契那个例子过于简单,以至于让人忽视了阶段的概念,所谓阶段是指随着问题的解决,在同一个时刻可能会得到的不同状态的集合。非波那契数列中,每一步会计算得到一个新数字,所以每个阶段只有一个状态。想象另外一个问题情景,假如把你放在一个围棋棋盘上的某一点,你每一步只能走一格,因为你可以东南西北随便走,所以你当你同样走四步可能会处于很多个不同的位置。从头开始走了几步就是第几个阶段,走了n步可能处于的位置称为一个状态,走了这n步所有可能到达的位置的集合就是这个阶段下所有可能的状态。
    现在问题来了,有了阶段之后,计算新状态可能会遇到各种奇葩的情况,针对不同的情况,就需要不同的算法,下面就分情况来说明一下:
          假如问题有n个阶段,每个阶段都有多个状态,不同阶段的状态数不必相同,一个阶段的一个状态可以得到下个阶段的所有状态中的几个。那我们要计算出最终阶段的状态数自然要经历之前每个阶段的某些状态。
          好消息是,有时候我们并不需要真的计算所有状态,比如这样一个弱智的棋盘问题:从棋盘的左上角到达右下角最短需要几步。答案很显然,用这样一个弱智的问题是为了帮助我们理解阶段和状态。某个阶段确实可以有多个状态,正如这个问题中走n步可以走到很多位置一样。但是同样n步中,有哪些位置可以让我们在第n+1步中走的最远呢?没错,正是第n步中走的最远的位置。换成一句熟悉话叫做“下一步最优是从当前最优得到的”。所以为了计算最终的最优值,只需要存储每一步的最优值即可,解决符合这种性质的问题的算法就叫贪心。如果只看最优状态之间的计算过程是不是和非波那契数列的计算很像?所以计算的方法是递推。

          既然问题都是可以划分成阶段和状态。这样一来我们一下子解决了一大类问题:一个阶段的最优可以由前一个阶段的最优得到。
          如果一个阶段的最优无法用前一个阶段的最优得到呢?
          什么你说只需要之前两个阶段就可以得到当前最优?那跟只用之前一个阶段并没有本质区别。最麻烦的情况在于你需要之前所有的情况才行。

          再来一个迷宫的例子。在计算从起点到终点的最短路线时,你不能只保存当前阶段的状态,因为题目要求你最短,所以你必须知道之前走过的所有位置。因为即便你当前再的位置不变,之前的路线不同会影响你的之后走的路线。这时你需要保存的是之前每个阶段所经历的那个状态,根据这些信息才能计算出下一个状态!

          每个阶段的状态或许不多,但是每个状态都可以转移到下一阶段的多个状态,所以解的复杂度就是指数的,因此时间复杂度也是指数的。哦哦,刚刚提到的之前的路线会影响到下一步的选择,这个令人不开心的情况就叫做有后效性
          刚刚的情况实在太普遍,解决方法实在太暴力(爆搜),有没有哪些情况可以避免如此的暴力呢?
          契机就在于后效性
          有一类问题,看似需要之前所有的状态,其实不用。不妨也是拿最长上升子序列的例子来说明为什么他不必需要暴力搜索,进而引出动态规划的思路。

          假装我们年幼无知想用搜索去寻找最长上升子序列。怎么搜索呢?需要从头到尾依次枚举是否选择当前的数字,每选定一个数字就要去看看是不是满足“上升”的性质,这里第i个阶段就是去思考是否要选择第i个数,第i个阶段有两个状态,分别是选和不选。哈哈,依稀出现了刚刚迷宫找路的影子!咦慢着,每次当我决定要选择当前数字的时候,只需要和之前选定的一个数字比较就行了!这是和之前迷宫问题的本质不同!这就可以纵容我们不需要记录之前所有的状态啊!既然我们的选择已经不受之前状态的组合的影响了,那时间复杂度自然也不是指数的了啊!虽然我们不在乎某序列之前都是什么元素,但我们还是需要这个序列的长度的。所以只需要记录以某个元素结尾的LIS长度就好!因此第i个阶段的最优解只是由前i-1个阶段的最优解得到的,然后就得到了DP方程(感谢@韩曦 指正)
    LIS(i)=max\{LIS(j)+1\} \ \ \ \ j<i \ and\ a[j] < a[i]
    <span style="font-size:18px;">#include <iostream>
    using namespace std;
    
    int lis(int A[], int n)
    {
        int *d = new int[n];
        int len = 1;
        for(int i=0; i<n; ++i)
       {
            d[i] = 1;
            for(int j=0; j<i; ++j)
                if(A[j]<=A[i] && d[j]+1>d[i])
                    d[i] = d[j] + 1;
            if(d[i]>len) len = d[i];
        }
        delete[] d;
        return len;
    }
    int main(){
        int A[] = {5, 3, 4, 8, 6, 7};
        cout<<lis(A, 6)<<endl;
        return 0;
    }</span>
    该算法的时间复杂度是O(n^2 ),并不是最优的解法。还有一种很巧妙的算法可以将时间复杂度降到O(nlogn),网上已经有各种文章介绍它,主要是维护一个上升序列表,然后对每一个新加入的数字尝试去二分插入。
    传送门:LIS的O(nlogn)解法。此题还可以用“排序+LCS”来解,感兴趣的话可自行Google。

    所以一个问题是该用递推、贪心、搜索还是动态规划,完全是由这个问题本身阶段间状态的转移方式决定的!

    每个阶段只有一个状态->递推;
    每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心;
    每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索;
    每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到这个性质叫做最优子结构
    不管之前这个状态是如何得到的,这个性质叫做无后效性

    另:其实动态规划中的最优状态的说法容易产生误导,以为只需要计算最优状态就好,LIS问题确实如此,转移时只用到了每个阶段“选”的状态。但实际上有的问题往往需要对每个阶段的所有状态都算出一个最优值,然后根据这些最优值再来找最优状态。比如背包问题就需要对前i个包(阶段)容量为j时(状态)计算出最大价值。然后在最后一个阶段中的所有状态种找到最优值。

    常见的动态规划问题分析与求解

    五岳——算法设计手册常用算法归类

    动态规划(Dynamic Programming,简称DP),虽然抽象后进行求解的思路并不复杂,但具体的形式千差万别,找出问题的子结构以及通过子结构重新构造最优解的过程很难统一,并不像回溯法具有解决绝大多数问题的银弹(全面解析回溯法:算法框架与问题求解)。为了解决动态规划问题,只能靠多练习、多思考了。本文主要是对一些常见的动态规划题目的收集,希望能有所帮助。难度评级受个人主观影响较大,仅供参考。

    目录(点击跳转)

    动态规划求解的一般思路

    备忘录法

    1.硬币找零

      扩展1:单路取苹果

      扩展2:装配线调度

    2.字符串相似度/编辑距离(edit distance)

      应用1:子串匹配

      应用2:最长公共子序列

    3.最长公共子序列(Longest Common Subsequence,lcs)

      扩展1:输出所有lcs

      扩展2:通过LCS获得最长递增自子序列

    4.最长递增子序列(Longest Increasing Subsequence,lis)

      扩展:求解lis的加速

    5.最大连续子序列和/积

      扩展1:正浮点数数组求最大连续子序列积

      扩展2:任意浮点数数组求最大连续子序列积

    6.矩阵链乘法

      扩展:矩阵链乘法的备忘录解法(伪码)

    7.0-1背包问题

    8.有代价的最短路径

    9.瓷砖覆盖(状态压缩DP)

    10.工作量划分

    11.三路取苹果

    参考资料

    附录1:其他的一些动态规划问题与解答(链接)

    附录2:《算法设计手册》第八章 动态规划 面试题解答

    动态规划求解的一般思路: 

      判断问题的子结构(也可看作状态),当具有最优子结构时,动态规划可能适用。

      求解重叠子问题。一个递归算法不断地调用同一问题,递归可以转化为查表从而利用子问题的解。分治法则不同,每次递归都产生新的问题。

      重新构造一个最优解。

    备忘录法:

      动态规划的一种变形,使用自顶向下的策略,更像递归算法。

      初始化时表中填入一个特殊值表示待填入,当递归算法第一次遇到一个子问题时,计算并填表;以后每次遇到时只需返回以前填入的值。

      实例可以参照矩阵链乘法部分。 

    1.硬币找零

    难度评级:★

      假设有几种硬币,如1、3、5,并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。 

    解法:

      用待找零的数值k描述子结构/状态,记作sum[k],其值为所需的最小硬币数。对于不同的硬币面值coin[0...n],有sum[k] = min(sum[k-coin[0]] , sum[k-coin[1]], ...)+1。对应于给定数目的找零total,需要求解sum[total]的值。

    typedef struct {
        int nCoin; //使用硬币数量
        //以下两个成员是为了便于构造出求解过程的展示
        int lastSum;//上一个状态
        int addCoin;//从上一个状态达到当前状态所用的硬币种类
    } state;
    state *sum = malloc(sizeof(state)*(total+1));
    
    //init
    for(i=0;i<=total;i++) 
        sum[i].nCoin = INF;
    sum[0].nCoin = 0;
    sum[0].lastSum = 0;
    
    for(i=1;i<=total;i++)
        for(j=0;j<n;j++)
            if(i-coin[j]>=0 && sum[i-coin[j]].nCoin+1<sum[i].nCoin)
            {
                sum[i].nCoin = sum[i-coin[j]].nCoin+1;
                sum[i].lastSum = j;
                sum[i].addCoin = coin[j];
            }
    
        if(sum[total].nCoin == INF) 
        {
            printf("can't make change.\n");
            return 0;
        }
        else
            //output
        ;

      通过sum[total].lastSum和sum[total].addCoin,很容易通过循环逆序地或者编写递归调用的函数正序地输出从结束状态到开始状态使用的硬币种类。以下各题输出状态转换的方法同样,不再赘述。下面为了方便起见,有的题没有在构造子结构的解时记录状态转换,如果需要请类似地完成。

    扩展:

    (1)一个矩形区域被划分为N*M个小矩形格子,在格子(i,j)中有A[i][j]个苹果。现在从左上角的格子(1,1)出发,要求每次只能向右走一步或向下走一步,最后到达(N,M),每经过一个格子就把其中的苹果全部拿走。请找出能拿到最多苹果数的路线。

    难度评级:★

    分析:

      这道题中,当前位置(i,j)是状态,用M[i][j]来表示到达状态(i,j)所能得到的最多苹果数,那么M[i][j] = max(M[i-1][j],M[i][j-1]) + A[i][j] 。特殊情况是M[1][1]=A[1][1],当i=1且j!=1时,M[i][j] = M[i][j-1] + A[i][j];当i!=1且j=1时M[i][j] = M[i-1][j] + A[i][j]。

      求解程序略。

    (2)装配线调度(《算法导论》15.1)

    难度评级:★

      


    2.字符串相似度/编辑距离(edit distance)

    难度评级:★

      对于序列S和T,它们之间距离定义为:对二者其一进行几次以下的操作(1)删去一个字符;(2)插入一个字符;(3)改变一个字符。每进行一次操作,计数增加1。将S和T变为同一个字符串的最小计数即为它们的距离。给出相应算法。

    解法:

      将S和T的长度分别记为len(S)和len(T),并把S和T的距离记为m[len(S)][len(T)],有以下几种情况:

           如果末尾字符相同,那么m[len(S)][len(T)]=m[len(S)-1][len(T)-1];

           如果末尾字符不同,有以下处理方式

           修改S或T末尾字符使其与另一个一致来完成,m[len(S)][len(T)]=m[len(S)-1][len(T)-1]+1;

           在S末尾插入T末尾的字符,比较S[1...len(S)]和S[1...len(T)-1];

           在T末尾插入S末尾的字符,比较S[1...len(S)-1]和S[1...len(T)];

            删除S末尾的字符,比较S[1...len(S)-1]和S[1...len(T)];

           删除T末尾的字符,比较S[1...len(S)]和S[1...len(T)-1];

      总结为,对于i>0,j>0的状态(i,j),m[i][j] = min( m[i-1][j-1]+(s[i]==s[j])?0:1 , m[i-1][j]+1, m[i][j-1] +1)。

      这里的重叠子结构是S[1...i],T[1...j]。

      以下是相应代码。考虑到C语言数组下标从0开始,做了一个转化将字符串后移一位。

    #include <stdio.h>
    #include <string.h>
    #define MAXLEN 20
    #define MATCH 0
    #define INSERT 1
    #define DELETE 2
    
    typedef struct {
        int cost;
        int parent;
    } cell;
    
    cell m[MAXLEN+1][MAXLEN+1];
    
    int match(char a,char b)
    {
        //cost of match
        //match:    0
        //not match:1
        return (a==b)?0:1;
    }
    
    int string_compare(char *s,char *t)
    {
        int i,j,k;
        int opt[3];
        
        //row_init(i);
        for(i=0;i<=MAXLEN;i++) {
            m[i][0].cost = i;
            if(i==0)
                m[i][0].parent = -1;
            else
                m[i][0].parent = INSERT;
        }
    
        //column_init(i);
        for(i=0;i<=MAXLEN;i++) {
            m[0][i].cost = i;
            if(i==0)
                continue;
            else
                m[0][i].parent = INSERT;
        }
        
        char m_s[MAXLEN+1] = " ",m_t[MAXLEN+1] =" ";
        strcat(m_s,s);
        strcat(m_t,t);
    
        for(i=1;i<=strlen(s);i++)
        {
            for(j=1;j<=strlen(t);j++) {
                opt[MATCH] = m[i-1][j-1].cost + match(m_s[i],m_t[j]);
                opt[INSERT] = m[i][j-1].cost + 1;
                opt[DELETE] = m[i-1][j].cost + 1;
                m[i][j].cost = opt[MATCH];
                m[i][j].parent = MATCH;
                for(k=INSERT;k<=DELETE;k++)
                    if(opt[k]<m[i][j].cost)
                    {
                        m[i][j].cost = opt[k];
                        m[i][j].parent = k;
                    }
            }
        }
        i--,j--;
        //goal_cell(s,t,&i,&j);
        return m[i][j].cost;
    }
    
    int main() {
        char t[] = "you should not";
        char p[] = "thou shalt not";
    
        int n = string_compare(t,p);
        printf("%d\n",n);
    }
    
    字符串相似度/edit distance

    应用:

      (1)子串匹配

      难度评级:★★

      修改两处即可进行子串匹配:

    row_init(int i)
    {
        m[0][i].cost = 0; /* note change */
        m[0][i].parent = -1; /* note change */
    }
    
    goal_cell(char *s, char *t, int *i, int *j)
    {
        int k; /* counter */
        *i = strlen(s) - 1;
        *j = 0;
        for (k=1; k<strlen(t); k++)
            if (m[*i][k].cost < m[*i][*j].cost) *j = k;
    }
    
    <span style="font-family:Microsoft YaHei;">修改部分</span>

    如果j= strlen(S) - strlen(T),那么说明T是S的一个子串。

      (这部分是根据《算法设计手册》8.2.4和具体实例Skiena与Skienaa、Skiena与somta的分析获得的,解释不够全面,可能有误,请注意)

      (2)最长公共子序列

      难度评级:★★

      将match时不匹配的代价转化为最大长度即可:

    int match(char c, char d)
    {
        if (c == d) return(0);
        else return(MAXLEN);
    }

      此时,最小值是两者不同部分的距离。

      (这部分同样也不好理解,对于最长公共子序列,建议直接使用下一部分中的解法)

    扩展:

      如果在编辑距离中各个操作的代价不同,如何寻找最小代价? 


    展开全文
  • VAR模型分析联合内生变量的动态关系一、实验介绍1.1 实验内容VAR模型是向量自回归模型的简称,是基于数据的统计性质建立的一种常用的计量经济模型,它把系统中每一个内生变量作为系统中所有内生变量的滞后值的函数来...

    VAR模型分析联合内生变量的动态关系

    一、实验介绍

    1.1 实验内容

    VAR模型是向量自回归模型的简称,是基于数据的统计性质建立的一种常用的计量经济模型,它把系统中每一个内生变量作为系统中所有内生变量的滞后值的函数来构造模型,从而将单变量自回归模型推广到由多元时间序列变量组成的“向量”自回归模型。本实验运用 R 语言来建立两变量的向量自回归模型,首先是检验两变量序列的平稳性,然后进行协整检验,确定待拟合模型的滞后阶数,再拟合VAR模型和做脉冲响应分析,最终对拟合的VAR模型进行分析于预测。通过本实验学会用VAR模型处理多个相关经济指标的分析与预测。

    1.2 实验知识点

    • 平稳性检验
    • 协整检验
    • 滞后阶数的确定
    • VAR 模型的拟合
    • 脉冲响应分析
    • VAR 模型的预测

    1.3 实验环境

    • R version 3.4.1
    • Xfce 终端

    1.4 适合人群

    本课程难度为较难,属于中级级别课程,适合具有 R 语言基础并且有一定经管背景的用户,熟悉 R 语言基础知识并加深巩固,学会用 R 语言建立计量经济模型分析经济数据。

    1.5 实验准备

    打开Xfce 终端,下载实验所需的数据,并启动 R :

    $ wget http://labfile.oss.aliyuncs.com/courses/910/monthdata.csv
    $ sudo R
    

    二、实验原理

    以下实验原理介绍来自 MBA 智库百科:向量自回归模型

    向量自回归模型简称VAR模型,是一种常用的计量经济模型,1980年由克里斯托弗·西姆斯(Christopher Sims)提出。VAR模型是用模型中所有当期变量对所有变量的若干滞后变量进行回归。VAR模型用来估计联合内生变量的动态关系,而不带有任何事先约束条件。它是AR模型的推广,此模型目前已得到广泛应用。

    向量自回归(VAR)是基于数据的统计性质建立模型,VAR模型把系统中每一个内生变量作为系统中所有内生变量的滞后值的函数来构造模型,从而将单变量自回归模型推广到由多元时间序列变量组成的“向量”自回归模型。VAR模型是处理多个相关经济指标的分析与预测最容易操作的模型之一,并且在一定的条件下,多元MA和ARMA模型也可转化成VAR模型,因此近年来VAR模型受到越来越多的经济工作者的重视。

    此处输入图片的描述

    三、实验步骤

    本实验利用 2005 年 8 月汇率改革后消费者价格指数(CPI)和人民币名义有效汇率(NEER)的月度数据建立两变量 VAR 模型来分析人民币汇率变动与CPI之间的动态关系。

    3.1 实验准备

    > data<-read.csv("monthdata.csv")  #读取数据
    > CPI<-data[,1]    #将 data 数据的第一列赋值给 CPI 数据框
    > NEER<-data[,2]    
    > length(CPI)  #查看 CPI 变量的数据长度
    > length(NEER)
    

    此处输入图片的描述

    可以看到数据长度为 137,即包含了 137 个月度 CPI 和 NEER 数据。

    下面我们绘制两个变量的时序图,观察消费者价格指数和名义汇率的波动情况。

    > CPI.ts<-ts(CPI,start=c(2005,8),end=c(2016,12),freq=12)   #将数据转化为时间序列
    > NEER.ts<-ts(NEER,start=c(2005,8),end=c(2016,12),freq=12)
    > par(mfrow=c(2,1))
    > plot(CPI.ts,type="l",xlab="Date", ylab="CPI")     
    > plot(NEER.ts,type="l",xlab="Date", ylab="NEER")
    

    此处输入图片的描述

    可以看到消费者价格指数(CPI)的波动幅度较大,而名义有效汇率波动较小但明显呈现一个波动上升的趋势,两个变量序列大致是不平稳的。

    3.2 平稳性检验

    在拟合 VAR 模型之前,需要对变量进行平稳性检验,如果要拟合的内生变量都是平稳的或者同阶单整的才可进行 VAR 模型的拟合。但在平稳性检验之前需要先项两变量取对数,以消除时间序列的异方差的影响。

    > lncpi<-log(CPI)     
    > lnneer<-log(NEER)
    

    进行平稳性检验本实验选择 urca 包中的 ur.df 函数进行单位根检验,若存在单位根则序列不平稳;反之,不存在单位根则序列平稳。

    > install.packages("urca")    #镜像选择 China (Lanzhou) [https]
    > library(urca)
    > urt.lncpi<-ur.df(lncpi,type='trend',selectlags='AIC')
    > urt.lnneer<-ur.df(lnneer,type='trend',selectlags='AIC')
    > summary(urt.lncpi)    
    
      ############################################### 
      # Augmented Dickey-Fuller Test Unit Root Test # 
      ############################################### 
    
      Test regression trend 
    
    
      Call:
      lm(formula = z.diff ~ z.lag.1 + 1 + tt + z.diff.lag)
    
      Residuals:
            Min        1Q    Median        3Q       Max 
      -0.028676 -0.003311  0.000381  0.003035  0.043118 
    
      Coefficients:
                    Estimate Std. Error t value Pr(>|t|)  
      (Intercept)  3.047e-01  1.477e-01   2.063   0.0411 *
      z.lag.1     -6.555e-02  3.185e-02  -2.058   0.0416 *
      tt          -1.443e-05  1.678e-05  -0.860   0.3912  
      z.diff.lag  -1.178e-01  8.627e-02  -1.365   0.1745  
      ---
      Signif. codes:  0 \u2018***\u2019 0.001 \u2018**\u2019 0.01 \u2018*\u2019 0.05 \u2018.\u2019 0.1 \u2018 \u2019 1
    
      Residual standard error: 0.007505 on 131 degrees of freedom
      Multiple R-squared:  0.05455,    Adjusted R-squared:  0.0329 
      F-statistic: 2.519 on 3 and 131 DF,  p-value: 0.06084
    
    
      Value of test-statistic is: -2.0578 1.5223 2.2719 
    
      Critical values for test statistics: 
            1pct  5pct 10pct
      tau3 -3.99 -3.43 -3.13
      phi2  6.22  4.75  4.07
      phi3  8.43  6.49  5.47
    
    > summary(urt.lnneer)   
    
      ############################################### 
      # Augmented Dickey-Fuller Test Unit Root Test # 
      ############################################### 
    
      Test regression trend 
    
    
      Call:
      lm(formula = z.diff ~ z.lag.1 + 1 + tt + z.diff.lag)
    
      Residuals:
            Min     1Q    Median        3Q       Max 
      -0.038574 -0.007164 -0.000990  0.009182  0.033482 
    
      Coefficients:
                    Estimate Std. Error t value Pr(>|t|)    
      (Intercept)  0.4429099  0.1380821   3.208  0.00168 ** 
      z.lag.1     -0.0995380  0.0312008  -3.190  0.00178 ** 
      tt           0.0003157  0.0001058   2.983  0.00341 ** 
      z.diff.lag   0.4099249  0.0810914   5.055 1.42e-06 ***
      ---
      Signif. codes:  0 \u2018***\u2019 0.001 \u2018**\u2019 0.01 \u2018*\u2019 0.05 \u2018.\u2019 0.1 \u2018 \u2019 1
    
      Residual standard error: 0.01267 on 131 degrees of freedom
      Multiple R-squared:  0.1877,    Adjusted R-squared:  0.1691 
      F-statistic: 10.09 on 3 and 131 DF,  p-value: 5.01e-06
    
    
      Value of test-statistic is: -3.1902 4.2783 5.1509 
    
      Critical values for test statistics: 
            1pct  5pct 10pct
      tau3 -3.99 -3.43 -3.13
      phi2  6.22  4.75  4.07
      phi3  8.43  6.49  5.47
    

    判断是否平稳主要看详细拟合结果的最后两个部分,即:

    • 1.Value of test-statistic is:
    • 2.Critical values for test statistics:

    1 是检验统计量的值,2 是对应的显著性水平下检验统计量的临界值。

    单位根检验的原假设是序列存在单位根。

    对于 lncpi 和 lnneer 的单位根检验结果:

    lncpilnneer
    Value of test-statistic is: -2.0578 1.5223 2.2719Value of test-statistic is: -3.1902 4.2783 5.1509
    Critical values for test statistics:Critical values for test statistics:
    1pct 5pct 10pct1pct 5pct 10pct
    tau3 -3.99 -3.43 -3.13tau3 -3.99 -3.43 -3.13
    phi2 6.22 4.75 4.07phi2 6.22 4.75 4.07
    phi3 8.43 6.49 5.47phi3 8.43 6.49 5.47
    • lncpi的检验统计量的值 -2.0578 在 1%、5%、10% 的显著性水平下都大于临界值(-3.99 -3.43 -3.13),则不能拒绝原价设而接受存在单位根的假设,说明 lncpi 序列是不平稳的。(注意,统计量的值和临界值为负,统计量的值大于临界值是接受原假设;若统计量的值和临界值为正值,统计量的值大于临界值是拒绝原假设。)
    • 同理,lnneer 的检验统计量的值 -3.1902 在 1% 、5% 的显著性水平下都大于对应的临界值(-3.99 -3.43 -3.13),不能拒绝原假设,lnneer 序列也是不平稳的,存在单位根。

    由于两个变量都存在单位根,对序列差分后检验序列的平稳性。

    > dlncpi<-diff(lncpi)   #取一阶差分
    > dlnneer<-diff(lnneer)
    > urt.dlncpi<-ur.df(dlncpi,type='trend',selectlags='AIC')
    > urt.dlnneer<-ur.df(dlnneer,type='trend',selectlags='AIC')
    > summary(urt.dlncpi)  
    > summary(urt.dlnneer)
    

    由于检验的详细结果太长,截取需要的部分一阶差分平稳性检验结果:

    • lncpi 的一阶差分平稳性检验

      此处输入图片的描述

      由于 dlncpi 的检验统计量的值为 -8.1895,在 1%、5%、10% 的显著性水平上都小于对应的临界值,因此拒绝存在单位根的原假设,即 lncpi 是一阶差分平稳的。

    • lnneer 的一阶差分平稳性检验

      此处输入图片的描述

      由于 dlnneer 的检验统计量的值为 -7.0409,在 1%、5%、10% 的显著性水平上都小于对应的临界值,因此拒绝存在单位根的原假设,即 lncpi 是一阶差分平稳的。

    我们再来看一阶差分后的时间序列图:

    > par(mfrow=c(2,1))
    > plot(dlncpi,type="l",xlab="Date", ylab="diff.CPI")     
    > plot(dlnneer,type="l",xlab="Date", ylab="diff.NEER")
    

    此处输入图片的描述

    可以看到差分后的两个变量序列没有明显的波动聚集或则上升下降的趋势,比较平稳。

    两个内生变量都是一阶差分平稳的,即都是一阶单整的,是不平稳的时间序列,不能做 Granger 因果检验,只能做协整检验。

    3.3 协整检验

    协整检验主要针对非平稳的单个序列,但它们的线性组合可能是平稳的。几个变量之间可能存在的一种长期均衡关系进行检验,表现为存在某个协整方程。

    由于所有变量都是一阶单整的,是非平稳时间序列,因此各变量之间可能存在协整关系,如果要对所选择的内生变量进行VAR模型的构建,需要进行协整检验,以判断各个变量之间是否存在长期稳定的协整关系,处理各变量之间的是否存在伪回归问题。在本实验我们运用E-G两步法协整检验,需要用到 lmtest 包中的 dwtest 函数。

    • E-G两步法:第一步:回归方程的估计
    > fit<-lm(lncpi~lnneer)  
    > summary(fit)
    

    此处输入图片的描述

    由于拟合的模型变量和截距项的 t 检验在 5% 的显著性水平上都是显著的,且模型的 F 检验在5%的显著性水平上也是显著的,因此拟合的线性模型是合理的。

    协整回归方程为:lncpi=4.80296-0.03666 lnneer+εt

    > install.packages("lmtest")
    > library(zoo)
    > library(lmtest)
    > dwtest(fit)    #检验序列的自相关性
    

    此处输入图片的描述

    此处输入图片的描述

    由于 Durbin-Watson test 检验的 p-value 的值几乎为 0,该数值小于 0.05 ,说明在 5% 的显著性水平上残差序列不独立,具有自相关性。

    • 检验残差序列的平稳性:

      > error<-residuals(fit)  #提取残差序列
      > urt.residuals<-ur.df(error,type='none',selectlags='AIC')
      > summary(urt.residuals)
      

      此处输入图片的描述

      此处输入图片的描述

      根据残差序列的平稳性检验结果,在 5% 的显著性水平上拒绝残差序列存在单位根的原假设,即残差序列是平稳的,说明 CPI 和名义有效汇率两个序列之间存在协整关系,意味着我国的消费者价格指数和名义有效汇率之间具有长期均衡关系,增长或者减少具有协同效应。

    • E-G两步法:第二步:误差修正模型的建立

    > error.lag<-error[-c(137,138)]       
    > ecm.fit<-lm(dlncpi~error.lag+dlnneer)   #拟合误差修正模型
    > summary(ecm.fit)  
    > dwtest(ecm.fit)
    

    此处输入图片的描述此处输入图片的描述

    协整回归方程:此处输入图片的描述

    误差修正项的系数为负,符合误差修正机制,反映了上一期偏离长期均衡的数量将在下一期得到反向修正,这也符合之前证明的协整关系。

    3.4 滞后阶数的确定

    在拟合 VAR 模型之前还需要确定拟合几阶 VAR 模型,也就是确定滞后阶数。确定滞后阶数需要用到 vars 包中的 VARselect 函数。

    > install.packages("vars")
    > library(MASS)
    > library(sandwich)
    > library(strucchange)
    > library(vars)
    > data.new<-data.frame(lncpi,lnneer)  #合并数据
    > VARselect(data.new,lag.max=10,type="const")  #在10以内选择最优滞后阶数
    

    此处输入图片的描述

    根据结果,不同的信息准则有不同的滞后阶数,选择 2 阶或者 4 阶都是可以的,一般来说选择在相同条件下更加简洁的模型,因此选择 2 阶滞后。

    3.5 VAR模型的拟合和预测

    3.5.1.VAR 模型的拟合

    在确定好最优滞后阶数以后我们就可以拟合模型:

    > var<-VAR(data.new,lag.max=2,ic="AIC")
    > summary(var)
    
      VAR Estimation Results:   #VAR(2) 模型拟合结果
      ========================= 
      Endogenous variables: lncpi, lnneer 
      Deterministic variables: const 
      Sample size: 135 
      Log Likelihood: 873.227 
      Roots of the characteristic polynomial:
      0.9621 0.9621 0.3829 0.1847
      Call:
      VAR(y = data.new, lag.max = 2, ic = "AIC")
    
      Estimation results for equation lncpi:     #模型估计结果一
      ====================================== 
      lncpi = lncpi.l1 + lnneer.l1 + lncpi.l2 + lnneer.l2 + const 
    
                Estimate Std. Error t value Pr(>|t|)    
      lncpi.l1   0.80917    0.08578   9.433   <2e-16 ***
      lnneer.l1 -0.09248    0.04705  -1.965   0.0515 .  
      lncpi.l2   0.12907    0.08483   1.521   0.1306    
      lnneer.l2  0.08381    0.04712   1.779   0.0777 .  
      const      0.32677    0.15855   2.061   0.0413 *  
      ---
      Signif. codes:  0 \u2018***\u2019 0.001 \u2018**\u2019 0.01 \u2018*\u2019 0.05 \u2018.\u2019 0.1 \u2018 \u2019 1
    
    
      Residual standard error: 0.007369 on 130 degrees of freedom
      Multiple R-Squared: 0.8791,    Adjusted R-squared: 0.8754 
      F-statistic: 236.3 on 4 and 130 DF,  p-value: < 2.2e-16 
    
    
      Estimation results for equation lnneer:        #模型估计结果二
      ======================================= 
      lnneer = lncpi.l1 + lnneer.l1 + lncpi.l2 + lnneer.l2 + const 
    
                Estimate Std. Error t value Pr(>|t|)    
      lncpi.l1  -0.18430    0.14954  -1.232 0.220030    
      lnneer.l1  1.31275    0.08203  16.003  < 2e-16 ***
      lncpi.l2   0.28850    0.14789   1.951 0.053238 .  
      lnneer.l2 -0.31998    0.08215  -3.895 0.000156 ***
      const     -0.44726    0.27641  -1.618 0.108065    
      ---
      Signif. codes:  0 \u2018***\u2019 0.001 \u2018**\u2019 0.01 \u2018*\u2019 0.05 \u2018.\u2019 0.1 \u2018 \u2019 1
    
    
      Residual standard error: 0.01285 on 130 degrees of freedom
      Multiple R-Squared: 0.9908,    Adjusted R-squared: 0.9905 
      F-statistic:  3504 on 4 and 130 DF,  p-value: < 2.2e-16 
    
    
      Covariance matrix of residuals:       #残差的协方差矩阵
                 lncpi    lnneer
      lncpi  5.430e-05 7.761e-06
      lnneer 7.761e-06 1.650e-04
    
      Correlation matrix of residuals:      #残差的相关阵
               lncpi  lnneer
      lncpi  1.00000 0.08198
      lnneer 0.08198 1.00000
    

    根据模型拟合结果,所得的 VAR(2) 的模型方程(保留两位小数)为:

    此处输入图片的描述

    也可以用 coef 函数来查看模型估计的简明结果。

    > coef(var)   #查看模型估计的简明结果
    

    此处输入图片的描述

    会拟合出一致的 VAR(2) 方程(系数保留两位小数)。

    > plot(var)       #画出每个变量的时序图、残差图、ACF 图、PACF 图
    按<Return>键来看下一个图      #也就是<Enter>键
    
    • 变量 lncpi 的时序图、残差图、ACF 图、PACF 图此处输入图片的描述
    • 变量 lnneer 的时序图、残差图、ACF 图、PACF 图此处输入图片的描述

    3.5.2 脉冲响应分析

    在查看完拟合结果的图形之后,我们来绘制拟合结果的脉冲响应图,需要用到 var 包中的 irf 函数。然后通过 plot 函数画出图形。

    > var.irf<-irf(var)  
    > plot(var.irf)       
    按<Return>键来看下一个图:
    

    此处输入图片的描述

    此处输入图片的描述

    根据图形 lncpi 自身以及 lnneer 的波动对 lncpi 有正向的冲击。 lncpi 对自身的影响没有滞后期,并且自身波动的影响随着时期的增加会越来越小。lnneer 波动对 lncpi 的影响在第一期以前是逐渐减少的,但在第一期减少为 0 之后随着时间的增加影响越来越大。

    lncpi 波动对 lnneer 有一个负向的冲击,并且随着时期数的增加负向的影响会越来越大。lnneer 波动对自身有一个正向的冲击,这个冲击从开始先增加,在第二期达到最大值以后又逐渐减少。

    3.5.3 VAR(2)模型的预测

    模型预测通常需要用到 predict 函数,具体用法如下:

    > var.predict<-predict(var,n.ahead=10,ci=0.95)
    > var.predict
    

    这样我们就得到了两变量(lncpi、lnneer)的 VAR(2)模型的滞后 10 期预测结果:

    此处输入图片的描述

    四、实验总结

    通过本次实验深入了解向量自回归模型,学会运用 R 语言来进行 VAR模型建模。学习如何检验一个序列的平稳性,以及如何运用协整检验来分析非平稳时间序列的关系。学会运用 var 包中的包括 VARselect() 函数、VAR() 函数、coef() 函数以及 irf() 函数各种函数来进行 VAR 模型的建模,选择最优滞后阶数,拟合 VAR 模型,对模型结果进行脉冲响应分析以及模型的预测。希望同过实验能够独立的运用 R 语言进行 VAR 模型建模于分析,巩固 R 的同时加深自己的金融知识。


    展开全文
  • 8.1 系统评价决策模型概论 8.1.1 问题的引入 8.1.2 系统评价决策模型的基本概念 8.1.3 系统评价决策模型的要素 8.1.4 系统评价决策模型的...8.2 案例分析-汽车选购 8.2.1 问题引入 8.2.2 决策矩阵的规范化 ...
  • R语言建立VAR模型分析联合内生变量的动态关系

    万次阅读 多人点赞 2017-09-05 13:40:38
    VAR模型分析联合内生变量的动态关系 一、实验介绍 1.1 实验内容 VAR模型是向量自回归模型的简称,是基于数据的统计性质建立的一种常用的计量经济模型,它把系统中每一个内生变量作为系统中所有内生变量的滞后值的...
  • 动态规划常见类型总结

    千次阅读 多人点赞 2019-03-26 23:55:28
    严格来说,递推不属于动态规划问题,因为动态规划不仅有递推过程,还要有决策(即取最优),但广义的动态规划是可以包含递推的,递推是一类简单的、特殊的动态规划,毕竟动态规划与递推密不可分。动态规划类型主要...
  • 主成分分析

    万次阅读 多人点赞 2019-03-25 09:50:04
    Principal components analysis ...   我们在作数据分析处理时,数据往往包含多个变量,而较多的变量会带来...主成分分析(Principal components analysis,以下简称PCA)是一种通过降维技术把多个变量化为少数几个主...
  • 动态规划

    千次阅读 2014-07-16 16:22:02
    终于来到了算法设计思想中最难,也最有趣的这部分,在去年的google笔试中,7道算法设计题有2道动态规划(Dynamic Programming)。 看了这么久的算法,这部分也是唯一感觉到了比较难的地方, 从这篇文章开始,将花...
  • 国内外主流静态分析类工具汇总

    万次阅读 2019-07-27 11:17:48
    笔者从事该软件安全方面工作,在工作和学习中收集了国内外比较主流的静态分析类工具,供大家参考。大多是资料来自于网络整理,如有不足或欠缺,还请在评论中指出。我进行修正。也欢迎同行多多交流。 我使用0标注...
  • 聊聊Linux动态链接中的PLT和GOT(4)—— 穿针引线

    千次阅读 多人点赞 2016-07-13 00:01:51
    通过图表方式,清晰介绍PLT/GOT表的静态结构和每个场景下的动态运行过程
  • 动态规划 最长公共子序列 过程图解

    万次阅读 多人点赞 2016-05-29 22:54:25
    难证明有以下性质:  如果am=bn,则zk=am=bn,且“z0,z1,…,z(k-1)”是“a0,a1,…,a(m-1)”和“b0,b1,…,b(n-1)”的一个最长公共子序列;  如果am!=bn,则若zk!=am,蕴涵“z0,z1,…,zk”是“a0...
  • 自制Lex-词法分析器生成器(C++)

    万次阅读 多人点赞 2016-10-31 23:03:26
    如果还知道词法分析器该怎么实现,可以去看c语言词法分析初试(C++实现)。 简介 上图是维基百科对lex的定义。 从中可以明确lex的功能:读进一个代表词法分析器规则的输入字符串流,然后输出以C语言实做的词
  • 动态规划总结

    万次阅读 2017-08-05 13:42:12
    终于来到了算法设计思想中最难,也最有趣的这部分,在去年的google笔试中,7道算法设计题有2道动态规划(Dynamic Programming)。看了这么久的算法,这部分也是唯一感觉到了比较难的地方,从这篇文章开始,将花连续...
  • 数据中台被誉为大数据的下一站,由阿里兴起,核心思想是数据共享,2015年阿里提出“大中台,小前台”的策略...普通企业该该做数据中台?数据中台的出现会给现有数据从业者们带来颠覆式的挑战吗? 数据中台不是大...
  • 运筹优化(七)--动态规划解析

    万次阅读 多人点赞 2019-01-15 20:15:30
    动态规划的思想随处可见,用同事的话说,就是一种很朴素的方法,我之所以记录这么多文字,是今天看完动态规划,突然发现,有时候,静下心,好好理解理解最最基础的理论原理,你对这个算法的体会和理解会完全一样。...
  • 动态规划算法介绍

    千次阅读 2019-02-17 19:34:49
    动态规划算法及其应用 动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。动态规划算法的思想和分治算法类似,基本思想也是将待求问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原...
  • 注:这里只是列出了我个人认为属于核心的部件,请读者不要先入为主,认为MyBatis就只有这些部件哦!每个人对MyBatis的理解不同,分析出的结果自然会有所不同,欢迎读者提出质疑和不同的意见,我们共同探讨~) ...
  • 随着人类生活全面向互联网转移,大数据时代将会可避免的到来!   作为全球互联网的前沿概念,大数据主要包括两方面特征:一方面整个社会的信息量急剧增长,另一方面个人可获取的信息也呈指数增长。从科技发展...
  • 什么是人工智能、机器学习、深度学习、数据挖掘以及数据分析?本文尝试给出自己的理解和认知。
  • 猫眼产品分析

    千次阅读 2015-12-23 15:21:42
    本文试图通过对猫眼电影的版本迭代历程分析、用户分析、功能分析、运营分析以及数据表现来回答以下几个问题: (1)猫眼电影的产品定位? (2)猫眼电影产品设计及运营中有哪些亮点和策略? (3)产品以后的迭代...
  • 最近看了一些TestNG的源代码,觉得这个测试框架的功能其实满强大的,里面的功能点很多,以后有机会慢慢分析一下它们的实现方法,今天主要介绍一下它如何实现方法之间的依赖关系。   背景知识:   想必...
  • 什么是动态语言

    千次阅读 2010-03-30 09:04:00
    除此之外如Ruby、Python等也都属于动态语言,而C、C++等语言则不属于动态语言。这里需要澄清一下。很多人以为脚本语言就是动态语言。其实两者是不一样的——虽然两者有很大的交集。比如C#在4.0之后
  • java数据结构与算法之顺序表与链表深入分析

    万次阅读 多人点赞 2016-11-05 16:24:30
    接下来将从以下几点出发分析线性表的设计与实现。 线性表抽象数据类型概述 线性表的顺序存储设计与实现顺序表 1 顺序存储结构的设计原理概要 2 顺序存储结构的实现分析 3 顺序存储结构的效率分析 线性表的链式存
  • Java技术——Java反射机制分析

    千次阅读 2016-08-14 21:28:37
    动态语言是指在程序运行时允许改变程序结构或者变量类型,从这个观点看,JAVA和C++一样,都不是动态语言。但Java它却有着一个非常突出的动态相关机制:反射。 Java反射机制是在运行状态中,对于任意一个类,都能够...
  • 静态分析方法简介

    千次阅读 2018-02-07 16:24:14
    程序分析分为动态分析和静态分析两种,其中静态分析是指实际运行程序而通过词法分析、语法分析、控制流、数据流等技术对源码进行扫描分析 本文从宏观上对静态分析技术做一个大体的介绍,并为后续文章做一个好的...
  • 当然,建议“知识体系”的这个过程并简单,一般都需要经历以下六步,这里就一一展开,想要更加深入了解可以自己去做进一步的了解。 3、将学过的东西忘记,剩下的便是教育的本质 美国教育学家斯金纳曾有过一句...
  • 它的大小并固定,可动态扩张或缩减。当进程调用 malloc 等函数分配内存时,新分配的内存就被动态加入到堆上(堆被扩张)。当利用 free 等函数释放内存时,被释放的内存从堆中被剔除(堆被缩减); 栈(stack):栈...
  • 信息系统分析与设计课程心得

    万次阅读 2017-02-28 13:41:39
    信息系统分析与设计课程心得此博客为信息系统分析与设计课程的学习心得记录。一、绪论1概念1.1信息要了解信息系统,首先要了解信息的概念。信息是我们理解世界的重要概念,我对它的定义是:信息是对客观事物及其相互...
  • 数据分析侠A的成长故事

    万次阅读 多人点赞 2016-03-09 10:46:40
    数据分析侠A的成长故事面包君 同学A:22岁,男,大四准备实习,计算机专业,迷茫期作为一个很普通的即将迈入职场的他来说,看到周边的同学都找了技术开发的岗位,顿觉自己很迷茫,因为自己不是那么喜欢钻研写代码,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 131,715
精华内容 52,686
关键字:

以下哪个不属于动态分析