Tiezhu Blog

闲来无事，想做个小项目玩玩，也可以趁此机会亲身体验开发的每一个环节。第一步就是搭建环境：一个应用服务器，用于部署后台代码。

环境概览

• 云服务：阿里云ECS，1核/2G/40G/1Mbps带宽
• 操作系统：CentOS7.8 64位
• MySQL 5.6
• Nginx 1.18
• Tomcat 8.5

问题类型

       在LeetCode上目前共有200道左右的动态规划相关的题，根据现有题目可以总结出一些题型，熟悉题型以及相关的描述能够帮助我们更准确地判断动态规划使用的场景。

• 通向目标点的最小（最大）路径
• 不同方法数
• 区间合并
• 字符串上的动态规划
• 决策类

何时能够使用动态规划

       动态规划（Dynamic Programming, DP）与其说是一种算法，更准确地说是一种解决问题的思维方式，因为其并没有对所有相关问题抽象出一种通用的算法程序，而是要在解题时根据具体的问题运用动态规划的思想进行问题的建模并编码求解。因此在理解动态规划解题之前，首先要了解什么样的问题能够用动态规划的思想解决。

        本质上来说，动态规划是一种更高效的递归算法的实现，所以在学习动态规划之前要对递归算法有比较深刻的理解。

在用朴素递归解决问题时，首先将目标问题分解成多个子问题，而在解决这些子问题时又被分解成更小的子问题……如此重复，直到分解到递归的边界为止。在分解过程中，同一个子问题可能会被多次重复解决。

        动态规划的思想就是，每解决一个子问题，都将该子问题的结果保存起来，则每个子问题只需要被解决一次。那么，哪些递归算法可以用动态规划的思想去实现呢？最简单的方法就是看朴素递归的算法有没有将同一个子问题一次次重复计算（可以画一个简单的递归树，能够很直观地发现，如果同一个子问题在树中不断出现，并且不止一次地出现在非叶节点上，那么就可以判断该子问题被重复计算了）。

问题建模

动态连通性问题

       对于一类问题，问题的输入是一些对象两两之间的“相连关系”，并且这种“相连关系”是一种等价关系，即它具有以下性质：

• 自反性：任何对象和其自身都是相连的；
• 对称性：如果p和q是相连的，那么q和p也是相连的；
• 传递性：如果p和q是相连的，q和r是相连的，那么p和r也是相连的。

       那么我们可以把相连的对象划分为一个等价类。问题的目标是根据输入的所有相连关系，将对象空间划分为多个等价类，并能够判断任意两个对象是否属于同一个等价类。这个问题称为动态连通性问题，动态连通性问题有以下现实场景的应用：

• 网络：输入的对象表示一个大型计算机网络中的计算机，相连关系表示计算机之间的连接，那么只有属于同一个等价类的两台计算机才能相互通信；或者也可以是社交网络，即对象是人，相连关系表示人之间的朋友关系，那么可以将人划分为“朋友圈”(即等价类)。
• 数学集合：抽象地说，可以将相连关系看作“属于同一个集合”。

什么是Bean的生命周期

       用最简单的说法，Bean的生命周期就是一个Bean实例从产生到灭亡所经历的阶段，包括每个阶段的状态和阶段之间转移的时机。本文主要讨论Spring框架中最常见的单例Bean的生命周期。

    在前一篇文章Spring探秘2：ApplicationContext启动流程中提到了Spring容器启动的最后一步是refresh，即配置的刷新，这是容器启动过程中一个核心的步骤，实现了启动容器的主要的功能。本文会简单介绍一下AbstractApplicationContext#refresh()方法的流程，其中涉及到的比较复杂的过程还需要另外详细分析。首先其源码如下：

     ApplicationContext是Spring框架中最基础的接口之一，可以认为其实现类就是一个Spring的环境（容器），而一个简单的Spring应用的启动过程就是一个ApplicationContext的实现类的实例化过程，是研究Spring源码的很好的切入点。这里研究的实现类是AnnotationConfigApplicationContext，运行的代码为前文Spring探秘0：源码构建中的测试代码，启动类的代码如下：

1
2
3
4
5
6
7
8
9
10

public class DemoApp {
  public static void main(String[] args) {
        ApplicationContext context =
                new AnnotationConfigApplicationContext(AppConfig.class);

        DemoComponent component = context.getBean(DemoComponent.class);
        component.foo();

    }
}

        BeanFactory和FactoryBean都是Spring框架中重要的接口，名字很像，但是功能上是有很大的不同的。

先上结论

相同点

• 都是接口
• 都没有父接口，是Spring框架中比较基础的接口

不同点

• BeanFactory正如其接口名的暗示，是一个工厂类，用于管理（生成）Bean。也可以认为其实现类就是一个IOC容器。
• FactoryBean是一个Bean, 而该Bean的功能是控制其他Bean实例化的逻辑。
• 因此，FactoryBean类型的对象也是由BeanFactory管理的

       从源码构建出Spring框架运行，方便探索Spring源码。

构建环境

• OS: MacOS 10.15.2
• JDK 1.8
• Spring 源码版本：5.1.x
• Gradle: 项目源码自带的Gardle Wrapper（gradlew）
• IntelliJ IDEA Ultimate 2019.3.3

  斯坦福深度自然语言处理课程CS224N Lecture 6课程笔记，Language Models and Recurrent Neural Networks.

语言模型，Language Model

  语言模型是用来预测“下一个词”的模型。即给模型输入一个词语序列，输出应该是下一个词（的概率分布）。对这个问题进行形式化的描述如下：

给定一个词语序列$x^{(1)}, x^{(2)},...,x^{(t)}$，计算下一个词$x^{(t+1)}$的概率分布：

$$P(x^{(t+1)}|x^{(t)},...,x^{(1)}) \tag{1}$$

其中$x^{(t+1)}$可以是词汇表 $V$ 中的任意一个词。

  也可以从另一个角度看待语言模型，将其看作是计算“一条文本”出现的概率。（一条文本指的就是一串词语）。即对于一条文本：$x^{(1)},...,x^{(T)}$，其出现的概率是：

(3)中的概率就是由语言模型给出的。