杂谈-2021 Java基础 JVM JMM JMX JMX，全称Java Management Extensions，用于管理和监控java应用程序。JMX有以下用途： 监控应用程序的运行状态和相关统计信息。 修改应用程序的配置（无需重启）。 状态变化或出错时通知处理。 JMX的基础架构 这里简单介绍下这三层结构： 层次 描述 Instrumentation 主要包括了一系列的接口定义和描述如何开发MBean的规范。在JMX中MBean代表一个被管理的资源实例，通过MBean中暴露的方法和属性，外界可以获取被管理的资源的状态和操纵MBean的行为。 Agent 用来管理相应的资源，并且为远端用户提供访问的接口。该层的核心是MBeanServer,所有的MBean都要向它注册，才能被管理。注册在MBeanServer上的MBean并不直接和远程应用程序进行通信，他们通过协议适配器（Adapter）和连接器（Connector）进行通信。 Distributed 定义了一系列用来访问Agent的接口和组件，包括Adapter和Connector的描述。注意，Adapter 和Connector的区别在于：Adapter是使用某种Internet协议来与 Agent获得联系，Agent端会有一个对象 (Adapter)来处理有关协议的细节。比如SNMP Adapter和HTTP Adapter。而Connector则是使用类似RPC的方式来访问Agent，在Agent端和客户端都必须有这样一个对象来处理相应的请求与应答。比如RMI Connector。 GC CMS G1 ZGC Jar jar xvf xxx.jar 解包 jar命令格式jar {c t x u f } v m e 0 M i 文件名…{ctxu}，这四个参数必须选选其一。[v f m e 0 M […]
已知问题规模为n的前提A，求解一个未知解B。（我们用An表示“问题规模为n的已知条件”） 此时，如果把问题规模降到0，即已知A0，可以得到A0->B. 如果从A0添加一个元素，得到A1的变化过程。即A0->A1; 进而有A1->A2; A2->A3; …… ; Ai->Ai+1. 这就是严格的归纳推理，也就是我们经常使用的数学归纳法； 对于Ai+1，只需要它的上一个状态Ai即可完成整个推理过程（而不需要更前序的状态）。我们将这一模型称为马尔科夫模型。对应的推理过程叫做“贪心法”。 然而，Ai与Ai+1往往不是互为充要条件，随着i的增加，有价值的前提信息越来越少，我们无法仅仅通过上一个状态得到下一个状态，因此可以采用如下方案： {A1->A2}; {A1, A2->A3}; {A1,A2,A3->A4};……; {A1,A2,…,Ai}->Ai+1. 这种方式就是第二数学归纳法。 对于Ai+1需要前面的所有前序状态才能完成推理过程。我们将这一模型称为高阶马尔科夫模型。对应的推理过程叫做“动态规划法”。 上述两种状态转移图如下图所示： 能用动规解决的问题的特点 能采用动态规划求解的问题的一般要具有3个性质： (1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。 (2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。 （3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势） 动规解题的一般思路 动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。 初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态 图1 动态规划决策过程示意图 (1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。 (2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 (3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。 (4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。 一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。 实际应用中可以按以下几个简化的步骤进行设计： （1）分析最优解的性质，并刻画其结构特征。 （2）递归的定义最优解。 （3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值 （4）根据计算最优值时得到的信息，构造问题的最优解 算法实现的说明 动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。 使用动态规划求解问题，最重要的就是确定动态规划三要素： （1）问题的阶段 （2）每个阶段的状态 （3）从前一个阶段转化到后一个阶段之间的递推关系。 递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。 确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)} **算法实现的步骤** […]
代码：包含初始化、合并（包含按秩优化）、查询（包含路径压缩）、校验是否为同一集合
转自某论坛 （i）邻接矩阵表示法，如图： 矩阵中，行和列 与图中的节点对应 也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有 个元素中，只有 个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。 同样，对于网络中的权，也可以用类似邻接矩阵的 矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权。 （ii）关联矩阵表示法 也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为 -1；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0。对于简单图，关联矩阵每列只含有两个非零元（一个 1，一个-1）可以看出，这种表示法也非常简单、直接。但是，在关联矩阵的所有mn 个元素中，只有 2m个为非零元。如果网络比较稀疏，这种表示法也会浪费大量的存储空间。但由于关联矩阵有许多特别重要的理论性质，因此它在网络优化中是非常重要的概念。 同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如果网络中每条弧有一个权，我们可以把关联矩阵增加一行，把每一条弧所对应的权存储在增加的行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存储在增加的行中。 （iii）弧表示法 例如，例7所示的图，假设弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的权分别为8，9，6，4，0，3，6和7，则弧表表示如上： 为了便于检索，一般按照起点、终点的字典序顺序存储弧表，如上面的弧表就是按照这样的顺序存储的。 （iv）邻接表表示法 邻接表表示法将图以邻接表（adjacency lists）的形式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。例如，例7所示的图，邻接表表示为 最后的0应该表示结尾。 （v）星形表示法 星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。也就是说，在该数组中首先存放从节点1出发的所有弧，然后接着存放从节点2出发的所有孤，依此类推，最后存放从节点n 出发的所有孤。对每条弧，要依次存放其起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号，只是从同一节点出发的弧的顺序可以任意排列。此外，为了能够快速检索从每个节点出发的所有弧，我们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的编号）。在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法称为前向星形（forward star）表示法。 例如，在例7所示的图中，仍然假设弧（1,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的权分别为8，9，6，4，0，3，6和7。此时该网络图可以用前向星形表示法表示如下： 《星形表示法详解及其转化算法》 注意：上面的第一张表实际上有个错误，仔细看的童鞋应该能发现，起始地址point(i) : 1 , 3 , 4 , 5 , 7 , 9 ,那个6应该是5（这里待核实） 通常情况下会设置一个st[i] 数组，和STL类似， [st[i],st[i+1]) 恰好为以结点i开头的边下标。对应于上个例子的第一张表，则该数组为： st[6]={1,3,4,5,7,9}; 还会有一个数组对应于第二张表，主要使用第三行数据， v[8]={2,3,4,2,3,5,3,4}; 下面的程序把树的前向星表示转化成左儿子-右兄弟表示，以方便后续算法实现。 图最常用的表示法是邻接矩阵和邻接表。对于静态图（建图完毕后不再修改图的结构）往往用前向星来代替邻接表，节省空间和时间。 邻接矩阵不管输入格式如何，总是很容易得到邻接矩阵，只需要注意平行边的情况。前向星邻接矩阵本身就包含了顶点序，因此很容易转化为前向星： 把邻接矩阵转换为前向星表示法： 把边列表转化成前向星的方法类似，只需要把第一顶点相同的结点串成链表，用计数器法进行结点编号分配，和前向星转化成左儿子-右兄弟一样每次插入到链表首部，在O(m)时间内可以建立前向星表示。当然，也可以按第一顶点为关键字直接进行快速排序，不过速度稍微慢一些
转自某故事会。 最近在看数据结构中图的相关知识，之前看的很混乱，现在总算是理清了，在此记录一下。 目录： 图的基本知识 广度优先搜索（BFS） 深度优先搜索（DFS） 总结 代码实现 一、图的基本知识 日常有很多地方都用到了图，比如地铁线路图，计算机网络连线图等。 图就就是下面这种由节点和连接每对节点的边所构成的图形。 这是最简单的图，我们可以根据图的一些特性将其进行分类： 1、如果给边加上一个值表示权重，这种图就是加权图，没有权重的图就是非加权图，没有权重的边只能表示两个节点的连接状态，而有权重的边就可以表示节点之间的“连接程度”。 2、如果给边加上表示方向的箭头，即表示节点之间的传递方向，这种图就是有向图，而边上没有箭头的图就是无向图。 3、如果图中任意两个节点都能找到路径可以将它们进行连接，则称该图为连通图，上面这个图就是连通图，反之则为非连通图。 下面两个图分别为加权图和有向图： 非连通图如下所示： 知道了什么是图，和图相关的算法主要有两类： 图的搜索算法：图的搜索指的就是从图的某一节点开始，通过边到达不同的节点，最终找到目标节点的过程。根据搜索的顺序不同，图的搜索算法可分为“广度优先搜索”和“深度优先搜索”两种。 图的最短路径问题：最短路径问题就是要在两个节点的所有路径中，找到一条所经过的边的权重总和最小的路径。相关算法有“贝尔曼-福特算法”，“狄克斯特拉算法”和“A* 算法”三种。 二、广度优先搜索 广度优先搜索和深度优先搜索一样，都是对图进行搜索的算法，都是从起点开始顺着边搜索，此时并不知道图的整体结构，直到找到指定节点(即终点)。在此过程中每走到一个节点，就会判断一次它是否为终点。 广度优先搜索会根据离起点的距离，按照从近到远的顺序对各节点进行搜索。而深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条路径。 在广度优先搜索中，有一个保存候补节点的队列，队列的性质就是先进先出，即先进入该队列的候补节点就先进行搜索。 下图中红色表示当前所在的节点（节点A），终点设为节点G，将与节点A直连的三个节点B, C, D放入存放候补节点的队列中（与节点A直连的三个节点放入时可以没有顺序，这里的放入顺序为B, C, D），用绿色表示。 此时队列中有B, C, D三个节点，我们来看看广度优先搜索是如何对各节点进行搜索的。 1、上面左图：此时从队列中选出一个节点，优先选择最早放入队列的那个节点，这里选择最左边的节点B。将已经搜索过的节点变为橙色（节点A），搜索到节点B时，将与节点B直连的两个节点E和F放入队列中，此时队列为 [C, D, E, F]。 2、上面中图：对节点B搜索完毕，节点B不是要找的终点，再搜索节点C，将与节点C直连的节点H放入队列中，此时队列为 [D, E, F, H]。 3、然后对节点D进行同样的操作，此时队列为 [E, F, H, I, J]。 4、上面右图：对与节点A直连的节点搜索完毕，再对与节点B直连的节点进行搜索（因为剩下的点中它们最先放入队列），这里选择节点E，将与节点E直连的节点K放入队列中，此时队列为 [F, H, I, J, K]。 […]
当消费侧出现异常时，若未进行处理，可能会导致消息再次被消费，然后再次出现异常，进入循环 官方文档：https://www.rabbitmq.com/confirms.html 前言 思考：因为在开发项目时，RabbitMQ的消费端出现了异常（工具类操作文件时，未找到文件路径）。由于在此之前并未对该异常进行预判，导致异常出现后，消费端仍然对MQ的消息进行消费，但是出现异常后无法对MQ进行回复，所以造成后果消费端一直消费该条信息，进入死循环！ 另需注意：若在消费者上加了声明式事物，基于事务的传播行为，默认为加入当前事务，这样以来，如果内部报错，即便在外层加了try-catch，事务也会进行回滚，因为默认是在最后进行ack的，消息就不会被ack，从而再次被消费。 从而引发了自己的思考：1. 开发时难免会出现异常，这种异常如果事先未预判，那么在程序运行中，消费端该怎么避免以上出现的死循环；2. 如果事先预判到异常，对其进行了抛出或捕获，消费端又该如何表现？ 异常 第一种方法，可以对可能发生异常的部分try、catch；只要事先将问题catch住，就证明消费端已经将该问题消费掉，然后该消息就不存在于队列中，不会造成无限报错的情况。这里，你可以在catch中写一些业务，把这个出现异常的“消息”记录到数据库或者怎么怎么处理，反正是相当于被消费掉了。 第二种方法，因为RabbitMQ 默认的异常策略是不断重试，除非抛出了fatal（致命）类型的异常，这种异常类型如下 异常类 MessageConversionException MessageConversionException MethodArgumentNotValidException MethodArgumentTypeMismatchException NoSuchMethodException ClassCastException 所以可以在catch语句块中抛出fatal 类型的异常（虽然不推荐，但也是种方式） 第三种方法，”消费者重试“模式。基本配置同一，只是在catch中显式的抛异常。这样其实就和没有catch差不多，就相当于未知状况下出现了异常。catch是为了解决业务问题，在这里处理自己需要的业务。catch中的throw有什么用呢？ throw配合着application.yml中的“开启消费者重试”模式：若异常发生，重试n次（n为yml中的 max-attempts），之后消息就自动进入死信队列（或者如果没配置死信队列，消息被扔掉）。 具体如下，消费者的mq配置类中设置了死信队列（参数只有死信交换机和路由，没有TTL）。 消费者端不做任何异常处理，模拟开发时并不知道会出现异常的情况。（注释掉的，catch里的throw和这个是一样的效果） 但是配置文件中开启“消费者尝试”，并配置最大尝试数。 这样，消费端发现了异常，尝试了规定次数后，这条“问题消息”就会被解决（如果设置了死信队列，就被送到了死信队列；否则直接扔掉）。是开启了“消费者重试尝试”的功劳。如果不开启该模式，那么会无限的循环下去。和 “default-requeue-rejected: true”参数没有任何关系，“消费者重试”模式会覆盖掉default-requeue-rejected(默认为true)。所以，只要是开了该模式，异常就可以被解决。如果只设置 default-requeue-rejected: true（消费者重试未开启，应答方式为默认），那么会无限报错！ 第四种，只设置 default-requeue-rejected: false（消费者重试未开启，应答方式为默认），异常只出现一次，然后该“问题消息”被解决（如果设置了死信队列，就被送到了死信队列；否则直接扔掉）。 第五种，在队列中设置了TTL参数！！！那么异常会无脑的跑一会，当消息到了一定时间就会过期，自动进入死信队列。这是TTL的功劳。 目前为止，都是自动（acknowledge-mode默认auto）应答mq，不需要手动应答。 第六种，yml配置文件手动应答,见最后一行的配置。 这时，消费端的监听需要如下这样，参照死信队列的概念，channel.basicReject的requeue参数必须设为false。 如果把requeue的值设为true，那就白玩了，“问题消息”又被你放到了当前队列，下一次消费方又执行这条“问题消息”。可以看出，第六种方案的推行并不依赖于“消费端重试”和TTL，仅仅依照死信队列的定义：利用basicReject拒绝，并把requeue设置为false. 注意：如果是，不管是否设置“消费者重试”模式，配置了default-requeue-rejected: false，且手动应答，异常只会出现一次，但是不会进入死信队列。消息以unack形式存在队列中。 综上所述，我们可以发现消费端异常的几种方案的特点： TTL可以设置消息的过期时间，不管你是不是无脑抛异常，只要过期，就进入死信队列； “消费者重试”模式，只要你抛异常抛到了我的底线（次数达标），那我就把你送走，可能是直接扔了，也可能是扔到死信队列； try、catch，只要你能提前预判，捕获到相应异常，那就平平安安，没有一点波澜； 手动回应，需要提前知道哪里会出错，就在哪里拒绝，而且requeue设成false；还要在哪里不拒绝（普通的消息回应），对mq做出相应正确的反馈 其实从这些特点可以看出，死信的定义就是最好的答案。 死信的产生： 消息被拒绝(basic.reject / basic.nack)，并且requeue = false 消息TTL过期 […]
以下文章来源于CS指南 ，作者大白 这篇文章我会首先结合我们日常的软件系统开发介绍 「“为什么网络要分层”？」 ，随后我会介绍 「“OSI 7 层模型”」 以及 「“ TCP/IP 4层模型 ”」。我会详细介绍目前广泛使用的 「“ TCP/IP 4层模型 ”」 包括每一层做的事情以及相关的协议介绍。 01 为什么网络要分层？ 说到分层，我们先从我们平时使用框架开发一个后台程序来说，我们往往会按照每一层做不同的事情的原则将系统分为 三层（复杂的系统分层可能会更多）: Repository（数据库操作） Service（业务操作） Controller（前后端数据交互） 「复杂的系统需要分层，因为每一层都需要专注于一类事情。我们的网络分层的原因也是一样，每一层只专注于做一类事情。」 「为什么计算机网络要分层呢？」 ,我们再来较为系统的说一说： 「各层之间相互独立」：各层之间相互独立，各层之间不需要关心其他层是如何实现的，只需要知道自己如何调用下层提供好的功能就可以了（可以简单理解为接口调用）「。这个和我们对开发时系统进行分层是一个道理。」 「提高了整体灵活性」 ：每一层都可以使用最适合的技术来实现，你只需要保证你提供的功能以及暴露的接口的规则没有改变就行了。「这个和我们平时开发系统的时候要求的高内聚、低耦合的原则也是可以对应上的。」 「大问题化小」 ：分层可以将复杂的网络间题分解为许多比较小的、界线比较清晰简单的小问题来处理和解决。这样使得复杂的计算机网络系统变得易于设计，实现和标准化。 「这个和我们平时开发的时候，一般会将系统功能分解，然后将复杂的问题分解为容易理解的更小的问题是相对应的，这些较小的问题具有更好的边界（目标和接口）定义。」 说到计算机网络分层，我想到了计算机世界非常非常有名的一句话，这里分享一下： 「计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决，计算机整个体系从上到下都是按照严格的层次结构设计的。」 即：如果一层不够那就加两层吧！ 「为了更好地去了解网络分层，我们先来看一个虽然失败，但是却提供了很多不错的理论基础的OSI七层模型。」 02 OSI七层模型 OSI七层模型的大体结构以及每一层提供的功能如下。「每一层都专注做一件事情，并且每一层都需要使用下一层提供的功能比如传输层需要使用网络层提供的路有和寻址功能，这样传输层才知道把数据传输到哪里去。」 OSI七层模型 「OSI的七层体系结构概念清楚，理论也很完整，但是它比较复杂而且不实用，而且有些功能在多个层中重复出现。」 上面这种图可能比较抽象，再来一个比较生动的图片。下面这个图片是我在国外的一个网站上看到的，非常赞！ 在这里顺带提一下：「为什么最开始的时候一直被一些大公司甚至一些国家政府支持的OSI七层模型会失败呢？」 OSI的专家缺乏实际经验，他们在完成OSI标准时缺乏商业驱动力 OSI的协议实现起来过分复杂，而且运行效率很低 OSI制定标准的周期太长，因而使得按OSI标准生产的设备无法及时进入市场（20世纪90年代初期，虽然整套的OSI国际标准都已经制定出来，但基于TCP/IP的互联网已经抢先在全球相当大的范围成功运行了） OSI的层次划分不太合理，有些功能在多个层次中重复出现。 03 TCP/IP 4层模型 这是目前被广泛采用的一种模型,我们可以将 TCP / […]